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 Citation (Scopus)

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(n 2 ) 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(n 2 )-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

Evolutionary Tree
Asymmetry
Upper and Lower Bounds
Testing
Pairwise
Uniqueness
Query
Lower bound

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
Chen, Ting ; Kao, Ming Yang. / On the informational asymmetry between upper and lower bounds for ultrametric evolutionary trees. Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. editor / Jaroslav Nešetřil. Springer Verlag, 1999. pp. 248-256 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{2333c3f5f1b24cf58bbc07061353ec49,
title = "On the informational asymmetry between upper and lower bounds for ultrametric evolutionary trees",
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(n 2 ) 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(n 2 )-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.",
author = "Ting Chen and Kao, {Ming Yang}",
year = "1999",
month = "1",
day = "1",
doi = "10.1007/3-540-48481-7_22",
language = "English (US)",
isbn = "3540662510",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "248--256",
editor = "Jaroslav Nešetřil",
booktitle = "Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings",
address = "Germany",

}

Chen, T & Kao, MY 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1643, Springer Verlag, pp. 248-256, 7th Annual European Symposium on Algorithms, ESA 1999, Prague, Czech Republic, 7/16/99. https://doi.org/10.1007/3-540-48481-7_22

On the informational asymmetry between upper and lower bounds for ultrametric evolutionary trees. / Chen, Ting; Kao, Ming Yang.

Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. ed. / Jaroslav Nešetřil. Springer Verlag, 1999. p. 248-256 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643).

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

TY - GEN

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

AU - Chen, Ting

AU - Kao, Ming Yang

PY - 1999/1/1

Y1 - 1999/1/1

N2 - 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(n 2 ) 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(n 2 )-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.

AB - 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(n 2 ) 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(n 2 )-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.

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

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

U2 - 10.1007/3-540-48481-7_22

DO - 10.1007/3-540-48481-7_22

M3 - Conference contribution

AN - SCOPUS:84958042283

SN - 3540662510

SN - 9783540662518

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

SP - 248

EP - 256

BT - Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings

A2 - Nešetřil, Jaroslav

PB - Springer Verlag

ER -

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