Improved Phylogeny Comparisons: Non-shared Edges, Nearest Neighbor Interchanges, and Subtree Transfers

摘要

The number of the non-shared edges of two phylogenies is a basic measure of the distance (dissimilarity) between the phylogenies. The non-shared edges are also the building block for approximating a more sophisticated metric called the NNI distance. In this paper we give the first sub-quadratic time algorithm for finding the non-shared edges, which are then used to speed up the existing approximation algorithm for the NNI distance. The time is improved from O(n~2) to O(n log n). Another popular distance metric for phylogenies is the STT distance. Previous work on computing the STT distance focused on degree-3 trees only. We show that the STT distance can be applied in a broader sense, allowing us to cover degree-d trees, where d ≥ 3. In particular, we give a new approximation algorithm for the STT distance.