A combinatorial description of the closest tree algorithm for finding evolutionary trees

✍ Scribed by Michael D. Hendy

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 382 KB
• Volume: 96
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(91)90469-i

✦ Synopsis

The closest tree algorith¢a for estimating the evolutionary history of n species, from a set of homologous DNA or RNA sequences is designed to avoid the problem of inconsistency inherent in current methods. The algorithm, as previously described, required O(n~2 n) steps, making it impractical for values of n > 10. In this paper, a new description of the algorithm is given, exploiting a combinatorial inverse pair relationship. As a consequence, the algorithm can be improved in efficiency, to be O(n2") for some classes of sequences. This improvement makes the algorithm practical for problems of involving up to n = 20 species.

The undedyin 8 combinatorics of sequence component changes on trees exposes some mathematical properties of trees which may be useful for ather related problems.