Abstract
This paper presents two new deterministic algorithms for constructing consensus trees. Given an input of k phylogenetic trees with identical leaf label sets and n leaves each, the first algorithm constructs the majority rule (+) consensus tree in O(k n) time, which is optimal since the input size is Ω(k n), and the second one constructs the frequency difference consensus tree in min {O(k n 2), O(k n (k + log2 n))} 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
Adams III, E.N.: Consensus techniques and the comparison of taxonomic trees. Systematic Zoology 21(4), 390–397 (1972)
Amenta, N., Clarke, F., St. John, K.: A linear-time majority tree algorithm. In: Benson, G., Page, R.D.M. (eds.) WABI 2003. LNCS (LNBI), vol. 2812, pp. 216–227. Springer, Heidelberg (2003)
Barthélemy, J.-P., McMorris, F.R.: The median procedure for n-trees. Journal of Classification 3(2), 329–334 (1986)
Bremer, K.: Combinable component consensus. Cladistics 6(4), 369–372 (1990)
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 (2003)
Cole, R., Farach-Colton, M., Hariharan, R., Przytycka, T., Thorup, M.: An O(n logn) algorithm for the maximum agreement subtree problem for binary trees. SIAM Journal on Computing 30(5), 1385–1404 (2000)
Cotton, J.A., Wilkinson, M.: Majority-rule supertrees. Systematic Biology 56(3), 445–452 (2007)
Cui, Y., Jansson, J., Sung, W.-K.: Polynomial-time algorithms for building a consensus MUL-tree. Journal of Computational Biology 19(9), 1073–1088 (2012)
Day, W.H.E.: Optimal algorithms for comparing trees with labeled leaves. Journal of Classification 2(1), 7–28 (1985)
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)
Dong, J., Fernández-Baca, D., McMorris, F.R., Powers, R.C.: Majority-rule (+) consensus trees. Mathematical Biosciences 228(1), 10–15 (2010)
Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Inc., Sunderland (2004)
Felsenstein, J.: PHYLIP, version 3.6. Software package, Department of Genome Sciences. University of Washington, Seattle (2005)
Goloboff, P.A., Farris, J.S., Källersjö, M., Oxelman, B., Ramírez, M.J., Szumik, C.A.: Improvements to resampling measures of group support. Cladistics 19(4), 324–332 (2003)
Goloboff, P.A., Farris, J.S., Nixon, K.C.: TNT, a free program for phylogenetic analysis. Cladistics 24(5), 774–786 (2008)
Holder, M.T., Sukumaran, J., Lewis, P.O.: A justification for reporting the majority-rule consensus tree in Bayesian phylogenetics. Systematic Biology 57(5), 814–821 (2008)
Jansson, J., Shen, C., Sung, W.-K.: Improved algorithms for constructing consensus trees. In: Proceedings of SODA 2013, pp. 1800–1813. SIAM (2013)
Jansson, J., Shen, C., Sung, W.-K.: An optimal algorithm for building the majority rule consensus tree. In: Deng, M., Jiang, R., Sun, F., Zhang, X. (eds.) RECOMB 2013. LNCS, vol. 7821, pp. 88–99. Springer, Heidelberg (2013)
Jansson, J., Sung, W.-K.: Constructing the R* consensus tree of two trees in subcubic time. Algorithmica 66(2), 329–345 (2013)
Lott, M., Spillner, A., Huber, K.T., Petri, A., Oxelman, B., Moulton, V.: Inferring polyploid phylogenies from multiply-labeled gene trees. BMC Evolutionary Biology 9, 216 (2009)
Margush, T., McMorris, F.R.: Consensus n-Trees. Bulletin of Mathematical Biology 43(2), 239–244 (1981)
McMorris, F.R., Powers, R.C.: A characterization of majority rule for hierarchies. Journal of Classification 25(2), 153–158 (2008)
Page, R.: COMPONENT, version 2.0. Software package, University of Glasgow, U.K. (1993)
Ronquist, F., Huelsenbeck, J.P.: MrBayes 3: Bayesian phylogenetic inference under mixed models. Bioinformatics 19(12), 1572–1574 (2003)
Sokal, R.R., Rohlf, F.J.: Taxonomic congruence in the Leptopodomorpha re-examined. Systematic Zoology 30(3), 309–325 (1981)
Sukumaran, J., Holder, M.T.: DendroPy: A Python library for phylogenetic computing. Bioinformatics 26(12), 1569–1571 (2010)
Sung, W.-K.: Algorithms in Bioinformatics: A Practical Introduction. Chapman & Hall/CRC (2010)
Swofford, D.L.: PAUP*, version 4.0. Software package. Sinauer Associates, Inc., Sunderland (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jansson, J., Shen, C., Sung, WK. (2013). Algorithms for the Majority Rule (+) Consensus Tree and the Frequency Difference Consensus Tree. In: Darling, A., Stoye, J. (eds) Algorithms in Bioinformatics. WABI 2013. Lecture Notes in Computer Science(), vol 8126. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40453-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-40453-5_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40452-8
Online ISBN: 978-3-642-40453-5
eBook Packages: Computer ScienceComputer Science (R0)