The fastest known algorithms for computing the R* consensus tree of k rooted phylogenetic trees with n leaves each and identical leaf label sets run in O(n2 √ log n) time when k = 2 (ref. ) and O(kn3) time when k ≥ 3 (ref. ). This paper shows how to compute it in O(n2) time for k = 2, O(n2 log4/3n) time for k = 3, and O(n2 logk+2n) time for unbounded k.
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||25th International Symposium on Algorithms and Computation, ISAAC 2014|
|Country/Territory||Korea, Republic of|
|Period||15/12/14 → 17/12/14|
- Theoretical Computer Science
- Computer Science(all)