A general method for fast multiple sequence alignment
Tönges, Udo
Perrey, Sören W.
Stoye, Jens
Dress, Andreas
Secondary matrix
Pair-wise sequence alignment
Divide and conquer
Multiple sequence alignment
Dynamic programming
ddc:004
We have developed a fast heuristic algorithm for multiple sequence alignment which provides near-to-optimal results for sufficiently homologous sequences. The algorithm makes use of the standard dynamic programming procedure by applying it to all pairs of sequences. The resulting score matrices for pair-wise alignment give rise to secondary matrices containing the additional charges imposed by forcing the alignment path to run through a particular vertex. Such a constraint corresponds to slicing the sequences at the positions defining that vertex, and aligning the remaining pairs of prefix and suffix sequences separately. From these secondary matrices, one can compute - for any given family of sequences - suitable positions for cutting all of these sequences simultaneously, thus reducing the problem of aligning a family of n sequences of average length l in a Divide and Conquer fashion to aligning two families of n sequences of approximately half that length. In this paper, we explain the method for the case of 3 sequences in detail, and we demonstrate its potential and its limits by discussing its behaviour for several test families. A generalization for aligning more than 3 sequences is lined out, and some actual alignments constructed by our algorithm for various user-defined parameters are presented.
1996
info:eu-repo/semantics/article
doc-type:article
text
https://pub.uni-bielefeld.de/record/1773351
Tönges U, Perrey SW, Stoye J, Dress A. A general method for fast multiple sequence alignment. <em>Gene</em>. 1996;172(1):GC33-GC41.
eng
info:eu-repo/semantics/altIdentifier/doi/10.1016/0378-1119(96)00123-0
info:eu-repo/semantics/altIdentifier/issn/0378-1119
info:eu-repo/semantics/altIdentifier/wos/A1996UE55600001
info:eu-repo/semantics/altIdentifier/pmid/8654965
info:eu-repo/semantics/closedAccess