A GENERAL-METHOD FOR FAST MULTIPLE SEQUENCE ALIGNMENT

We have developed a fast heuristic algorithm for multiple sequence ali gnment which provides near-to-optimal results for sufficiently homolog ous sequences. The algorithm makes use of the standard dynamic program ming procedure by applying it to all pairs of sequences. The resulting score matrices for pair-wise alignment give rise to secondary matrice s containing the additional charges imposed by forcing the alignment p ath to run through a particular vertex Such a constraint corresponds t o slicing the sequences at the positions defining that vertex, and ali gning the remaining pairs of prefix and suffix sequences separately. F rom these secondary matrices, one can compute - for any given family o f sequences - suitable positions for cutting all of these sequences si multaneously, thus reducing the problem of aligning a family of n sequ ences of average length I 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, a nd we demonstrate its potential and its limits by discussing its behav iour for several test families. A generalization for aligning more tha n 3 sequences is lined out, and some actual alignments constructed by our algorithm for various user-defined parameters are presented.