title: A general method for fast multiple sequence alignment.
abstract: 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.
authors.affiliation: Research Center for Interdisciplinary Studies on Structure Formation (RCSF), University of Bielefeld, Germany. toenges,stoye,dress@mathematik.unibielefeld.de
authors.forename: U
authors.initials: U
authors.lastname: Tönges
authors.forename: S W
authors.initials: SW
authors.lastname: Perrey
authors.forename: J
authors.initials: J
authors.lastname: Stoye
authors.forename: A W
authors.initials: AW
authors.lastname: Dress
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D008957:Models, Genetic; D008969:Molecular Sequence Data; D016415:Sequence Alignment / Q000379:methods*