The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees T1and T2with a leaf label set of cardinality n run in Θ(n3) time [3,8]. In this manuscript, we describe a new O(n2log n)-time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set ℛmajwhich may contain Ω(n3) elements, so any direct approach which explicitly constructs ℛmajrequires Ω(n3) time.
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||18th Annual European Symposium on Algorithms, ESA 2010|
|Period||6/09/10 → 8/09/10|
- Computer Science(all)
- Theoretical Computer Science