@inproceedings{babf7c5bdad7443ebb9f902394bf218d,
title = "Improved phylogeny comparisons: Non-shared edges, nearest neighbor interchanges, and subtree transfers",
abstract = "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(n2) 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.",
author = "Hon, {Wing Kai} and Kao, {Ming Yang} and Lam, {Tak Wah}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 ; Conference date: 18-12-2000 Through 20-12-2000",
year = "2000",
doi = "10.1007/3-540-40996-3_45",
language = "English (US)",
isbn = "3540412557",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "527--538",
editor = "D.T. Lee and Shang-Hua Teng and Shang-Hua Teng",
booktitle = "Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings",
}