On the informational asymmetry between upper and lower bounds for ultrametric evolutionary trees

Ting Chen, Ming Yang Kao

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

1 Scopus citations

Abstract

This paper addresses the informational asymmetry for constructing an ultrametric evolutionary tree from upper and lower bounds on pairwise distances between n given species. We show that the tallest ultrametric tree exists and can be constructed in O(n2) time, while the existence of the shortest ultrametric tree depends on whether the lower bounds are ultrametric. The tallest tree construction algorithm gives a very simple solution to the construction of an ultrametric tree. We also provide an efficient O(n2)-time algorithm for checking the uniqueness of an ultrametric tree, and study a query problem for testing whether an ultrametric tree satisfies both upper and lower bounds.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 1999 - 7th Annual European Symposium, Proceedings
EditorsJaroslav Nešetřil
PublisherSpringer Verlag
Pages248-256
Number of pages9
ISBN (Print)3540662510, 9783540662518
DOIs
StatePublished - Jan 1 1999
Event7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic
Duration: Jul 16 1999Jul 18 1999

Publication series

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

Other

Other7th Annual European Symposium on Algorithms, ESA 1999
CountryCzech Republic
CityPrague
Period7/16/997/18/99

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Chen, T., & Kao, M. Y. (1999). On the informational asymmetry between upper and lower bounds for ultrametric evolutionary trees. In J. Nešetřil (Ed.), Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings (pp. 248-256). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643). Springer Verlag. https://doi.org/10.1007/3-540-48481-7_22