An improved algorithm for statistical alignment of sequences related by a star tree.
The insertion-deletion model developed by Thorne, Kishino and Felsenstein (1991, J. Mol. Evol., 33, 114-124; the TKF91 model) provides a statistical framework of two sequences. The statistical alignment of a set of sequences related by a star tree is a generalization of this model. The known algorithm computes the probability of a set of such sequences in O(l2k) time, where l is the geometric mean of the sequence lengths and k is the number of sequences. An improved algorithm is presented whose running time is only O(2(2k)lk).
Miklós
István
I
Department of Plant Taxonomy and Ecology, Eötvös Loránd University, Pázmány Péter Sétány l/c, H-1117 Budapest, Hungary. miklosi@ludens.elte.hu
D000465:Algorithms; D000595:Amino Acid Sequence; D001483:Base Sequence; D019143:Evolution, Molecular; D008390:Markov Chains; D008957:Models, Genetic; D016415:Sequence Alignment