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 language | English (US) |
---|---|
Pages (from-to) | 1592-1616 |
Number of pages | 25 |
Journal | SIAM Journal on Computing |
Volume | 27 |
Issue number | 6 |
DOIs | |
State | Published - Dec 1998 |
Keywords
- Computational biology
- Evolutionary trees
- Minimal condensed forms
- Tree contractions
ASJC Scopus subject areas
- General Computer Science
- General Mathematics