Abstract
The previously fastest algorithms for computing the R* consensus tree of two given (rooted) phylogenetic trees T 1 and T 2 with a leaf label set of cardinality n run in Θ(n 3) time [3,8]. In this manuscript, we describe a new O(n 2 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 \(\mathcal{R}_{maj}\) which may contain Ω(n 3) elements, so any direct approach which explicitly constructs \(\mathcal{R}_{maj}\) requires Ω(n 3) time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000)
Bryant, D.: A classification of consensus methods for phylogenetics. In: Janowitz, M.F., Lapointe, F.-J., McMorris, F.R., Mirkin, B., Roberts, F.S. (eds.) Bioconsensus. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 61, pp. 163–184. American Mathematical Society, Providence (2003)
Bryant, D., Berry, V.: A structured family of clustering and tree construction methods. Advances in Applied Mathematics 27(4), 705–732 (2001)
Degnan, J.H., DeGiorgio, M., Bryant, D., Rosenberg, N.A.: Properties of consensus methods for inferring species trees from gene trees. Systematic Biology 58(1), 35–54 (2009)
Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Inc., Sunderland (2004)
Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Cambridge University Press, New York (1997)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing 13(2), 338–355 (1984)
Kannan, S., Warnow, T., Yooseph, S.: Computing the local consensus of trees. SIAM Journal on Computing 27(6), 1695–1724 (1998)
Lee, C.-M., Hung, L.-J., Chang, M.-S., Shen, C.-B., Tang, C.-Y.: An improved algorithm for the maximum agreement subtree problem. Information Processing Letters 94(5), 211–216 (2005)
Nakhleh, L., Warnow, T., Ringe, D., Evans, S.N.: A comparison of phylogenetic reconstruction methods on an Indo-European dataset. Transactions of the Philological Society 103(2), 171–192 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jansson, J., Sung, WK. (2010). Constructing the R* Consensus Tree of Two Trees in Subcubic Time. In: de Berg, M., Meyer, U. (eds) Algorithms – ESA 2010. ESA 2010. Lecture Notes in Computer Science, vol 6346. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15775-2_49
Download citation
DOI: https://doi.org/10.1007/978-3-642-15775-2_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15774-5
Online ISBN: 978-3-642-15775-2
eBook Packages: Computer ScienceComputer Science (R0)