He, Dan and Arslan, Abdullah N. and Ling, Alan C. H.: A fast algorithm for the constrained multiple sequence alignment problem. In: Acta cybernetica, (17) 4. pp. 701717. (2006)

Cikk, tanulmány, mű
DanHe_2006_ActaCybernetica.pdf Download (320kB)  Preview 
Abstract
Given n strings S1, S2, ..., Sn, and a pattern string P, the constrained multiple sequence alignment (CMSA) problem is to find an optimal multiple alignment of S1, S2, ..., Sn such that the alignment contains P, i.e. in the alignment matrix there exists a sequence of columns each entirely composed of symbol P[k] for every k, where P[k] is the kth symbol in P, 1 ≤ k ≤ P, and in the sequence, a column containing P[i] appears before the column containing P[j] for all i,j, i < j. The problem is motivated from the problem of comparing multiple sequences that share a common structure, or sequence pattern. There are O(2ns1s2...snr)time dynamic programming algorithms for the problem, where s1,s2, ...,sn and r are, respectively, the lengths of the input strings and the pattern string. Feasibility of these algorithms in practice is limited when the number of sequences is large, or the sequences are long because of the impractically long time required by these algorithms. We present a new algorithm with worstcase time complexity also O(2ns1s2...snr), but the algorithm avoids redundant computations in existing dynamic programming solutions. Experiments on both randomly generated strings and real data show that this algorithm is much faster than the existing algorithms. We present an analysis that explains the speedup obtained in our experiments by our algorithm over the naive dynamic programming algorithm for constrained multiple sequence alignment of protein sequences. The speedup is more significant when pattern is long, or n is large. For example in the case of constrained pairwise sequence alignment (the CMSA problem with n=2) when the pattern is sufficiently long for strings S1 and S2, the asymptotic time complexity is observed to be O(s1s2) instead of O(s1s2r). Main ideas in our algorithm can also be used in other constrained sequence alignment problems.
Item Type:  Article 

Journal or Publication Title:  Acta cybernetica 
Date:  2006 
Volume:  17 
Number:  4 
ISSN:  0324721X 
Page Range:  pp. 701717 
Language:  English 
Event Title:  International Conference on Automata and Formal Languages, 11., 2005, Dobogókő 
Related URLs:  http://acta.bibl.uszeged.hu/38522/ 
Uncontrolled Keywords:  Természettudomány, Informatika 
Additional Information:  Bibliogr.. p. 716717.; Abstract 
Date Deposited:  2016. Oct. 15. 12:25 
Last Modified:  2021. Mar. 24. 14:23 
URI:  http://acta.bibl.uszeged.hu/id/eprint/12792 
Actions (login required)
View Item 