Tree contractions and evolutionary trees

Ming Yang Kao*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

An evolutionary tree is a rooted tree where each internal vertex has at least two children and where the leaves are labeled with distinct symbols representing species. Evolutionary trees are useful for modeling the evolutionary history of species. An agreement subtree of two evolutionary trees is an evolutionary tree which is also a topological subtree of the two given trees. We give an algorithm to determine the largest possible number of leaves in any agreement subtree of two trees T1 and T2 with n leaves each. If the maximum degree d of these trees is bounded by a constant, the time complexity is O(n log2 n) and is within a log n factor of optimal. For general d, this algorithm runs in O(nd2 log d log2 n) time or alternatively in O(nd√d log3 n) time.

Original languageEnglish (US)
Pages (from-to)1592-1616
Number of pages25
JournalSIAM Journal on Computing
Volume27
Issue number6
DOIs
StatePublished - Dec 1998

Keywords

  • Computational biology
  • Evolutionary trees
  • Minimal condensed forms
  • Tree contractions

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'Tree contractions and evolutionary trees'. Together they form a unique fingerprint.

Cite this