A COMBINATORIAL DESCRIPTION OF THE CLOSEST TREE ALGORITHM FOR FINDING EVOLUTIONARY TREES

The closest tree algorithm 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(n)2n) 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(n2n) for some classes of sequences. This improvement makes the algorithm practical for problems of involving up to n = 20 species. The underlying combinatorics of sequence component changes on trees exposes some mathematical properties of trees which may be useful for other related problems.