An Improved Algorithm for Statistical Alignment of Sequences Related by a Star Tree

1 July 2002

journal article
Published by Springer Nature in Bulletin of Mathematical Biology

Vol. 64 (4) , 771-779
https://doi.org/10.1006/bulm.2002.0300

Abstract

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(l ^2k) 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 l ^k).

Keywords

STATISTICAL ALIGNMENT
SEQUENCES RELATED
MODEL
TREE
IMPROVED ALGORITHM
DELETION
MOL
EVOL
KISHINO

This publication has 0 references indexed in Scilit: