Improved phylogeny comparisons: Non-shared edges, nearest neighbor interchanges, and subtree transfers

Wing Kai Hon, Ming Yang Kao, Tak Wah Lam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings
EditorsShang-Hua Teng, D.T. Lee, Shang-Hua Teng
PublisherSpringer Verlag
Pages527-538
Number of pages12
ISBN (Print)3540412557, 9783540412557
StatePublished - Jan 1 2000
Event11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 - Taipei, Taiwan, Province of China
Duration: Dec 18 2000Dec 20 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1969
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th Annual International Symposium on Algorithms and Computation, ISAAC 2000
CountryTaiwan, Province of China
CityTaipei
Period12/18/0012/20/00

Fingerprint

Phylogeny
Interchanges
Nearest Neighbor
Approximation algorithms
Approximation Algorithms
Distance Metric
Dissimilarity
Building Blocks
Speedup
Cover
Metric
Computing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Hon, W. K., Kao, M. Y., & Lam, T. W. (2000). Improved phylogeny comparisons: Non-shared edges, nearest neighbor interchanges, and subtree transfers. In S-H. Teng, D. T. Lee, & S-H. Teng (Eds.), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings (pp. 527-538). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969). Springer Verlag.
Hon, Wing Kai ; Kao, Ming Yang ; Lam, Tak Wah. / Improved phylogeny comparisons : Non-shared edges, nearest neighbor interchanges, and subtree transfers. Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. editor / Shang-Hua Teng ; D.T. Lee ; Shang-Hua Teng. Springer Verlag, 2000. pp. 527-538 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@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}",
year = "2000",
month = "1",
day = "1",
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 = "Shang-Hua Teng and D.T. Lee and Shang-Hua Teng",
booktitle = "Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings",
address = "Germany",

}

Hon, WK, Kao, MY & Lam, TW 2000, Improved phylogeny comparisons: Non-shared edges, nearest neighbor interchanges, and subtree transfers. in S-H Teng, DT Lee & S-H Teng (eds), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1969, Springer Verlag, pp. 527-538, 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000, Taipei, Taiwan, Province of China, 12/18/00.

Improved phylogeny comparisons : Non-shared edges, nearest neighbor interchanges, and subtree transfers. / Hon, Wing Kai; Kao, Ming Yang; Lam, Tak Wah.

Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. ed. / Shang-Hua Teng; D.T. Lee; Shang-Hua Teng. Springer Verlag, 2000. p. 527-538 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Improved phylogeny comparisons

T2 - Non-shared edges, nearest neighbor interchanges, and subtree transfers

AU - Hon, Wing Kai

AU - Kao, Ming Yang

AU - Lam, Tak Wah

PY - 2000/1/1

Y1 - 2000/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84949845409&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949845409&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84949845409

SN - 3540412557

SN - 9783540412557

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 527

EP - 538

BT - Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings

A2 - Teng, Shang-Hua

A2 - Lee, D.T.

A2 - Teng, Shang-Hua

PB - Springer Verlag

ER -

Hon WK, Kao MY, Lam TW. Improved phylogeny comparisons: Non-shared edges, nearest neighbor interchanges, and subtree transfers. In Teng S-H, Lee DT, Teng S-H, editors, Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Springer Verlag. 2000. p. 527-538. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).