✦ LIBER ✦
An Improved Algorithm for Statistical Alignment of Sequences Related by a Star Tree
✍ Scribed by István Miklós
- Publisher
- Springer
- Year
- 2002
- Tongue
- English
- Weight
- 102 KB
- Volume
- 64
- Category
- Article
- ISSN
- 1522-9602
No coin nor oath required. For personal study only.
✦ Synopsis
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).