Abstract
The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees with a leaf label set of cardinality n run in Θ(n3) time (Bryant and Berry in Adv. Appl. Math. 27(4):705-732, 2001; Kannan et al. in SIAM J. Comput. 27(6):1695-1724, 1998). In this manuscript, we describe a new O(n2√log n-time algorithm to solve the problem. This is a significant improvement because the R*consensus tree is defined in terms of a set Rmajwhich may contain Ω(n3) elements, so any direct approach that explicitly constructs Rmajrequires Ω(n3) time.
Original language | English |
---|---|
Pages (from-to) | 329-345 |
Number of pages | 17 |
Journal | Algorithmica |
Volume | 66 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Jun 2013 |
Externally published | Yes |
Keywords
- Apresjan cluster
- consensus tree
- Lowest common ancestor
- Offline orthogonal range counting
- Phylogenetic tree
- R
- Strong cluster
- Triplet
ASJC Scopus subject areas
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics