More Web Proxy on the site http://driver.im/

research-article

Algorithms for the Majority Rule + Consensus Tree and the Frequency Difference Consensus Tree

Authors:

Jesper Jansson,

Wing-Kin SungAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 15, Issue 1

Pages 15 - 26

https://doi.org/10.1109/TCBB.2016.2609923

Published: 01 January 2018 Publication History

Abstract

This article 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 $Ok n$ time, which is optimal since the input size is $\Omega k n$, and the second one constructs the frequency difference consensus tree in $\min \lbrace Ok n^{2}, Ok n k + \log ^{2}n\rbrace$ time.

References

[1]

N. Amenta, F. Clarke, and K. S. John, "A linear-time majority tree algorithm," in Proc. 3rd Int. Workshop Algorithms Bioinf., Lecture Notes in Computer Science, vol. 2812, pp. 216-227, 2003.

[2]

J. H. Degnan, M. DeGiorgio, D. Bryant, and N. A. Rosenberg, "Properties of consensus methods for inferring species trees from gene trees," Systematic Biol., vol. 58, no. 1, pp. 35-54, 2009.

[3]

J. Felsenstein, Inferring Phylogenies. Sunderland, MA, USA: Sinauer Associates, 2004.

[4]

W.-K. Sung, Algorithms in Bioinformatics: A Practical Introduction. Boca Raton, FL, USA: Chapman & Hall/CRC, 2010.

[5]

E.N. Adams III, "Consensus techniques and the comparison of taxonomic trees," Systematic Zoology, vol. 21, no. 4, pp. 390-397, 1972.

[6]

D. Bryant, "A classification of consensus methods for phylogenetics," in Bioconsensus, M. F. Janowitz, F.-J. Lapointe, F. R. McMorris, B. Mirkin, and F. S. Roberts, Eds. Providence, RI, USA: American Mathematical Society, 2003, vol. 61, pp. 163-184.

[7]

R. R. Sokal and F. J. Rohlf, "Taxonomic congruence in the Leptopodomorpha re-examined," Systematic Zoology, vol. 30, no. 3, pp. 309-325, 1981.

[8]

W. H. E. Day, "Optimal algorithms for comparing trees with labeled leaves," J. Classification, vol. 2, no. 1, pp. 7-28, 1985.

[9]

T. Margush and F. R. McMorris, "Consensus n-Trees," Bulletin Math. Biol., vol. 43, no. 2, pp. 239-244, 1981.

[10]

M. T. Holder, J. Sukumaran, and P. O. Lewis, "A justification for reporting the majority-rule consensus tree in Bayesian phylogenetics," Systematic Biol., vol. 57, no. 5, pp. 814-821, 2008.

[11]

Y. Cui, J. Jansson, and W.-K. Sung, "Polynomial-time algorithms for building a consensus MUL-tree," J. Comput. Biol., vol. 19, no. 9, pp. 1073-1088, 2012.

[12]

J. Jansson, Z. Li, and W.-K. Sung, "On finding the Adams consensus tree," in Proc. 32nd Int. Symp. Theoretical Aspects Comput. Sci., vol. 30, pp. 487-499, 2015.

[13]

J. Jansson, C. Shen, and W.-K. Sung, "Improved algorithms for constructing consensus trees," J. ACM, vol. 63, no. 3, 2016, Art.no. 28.

[14]

J. Jansson and W.-K. Sung, "Constructing the R* consensus tree of two trees in subcubic time," Algorithmica, vol. 66, no. 2, pp. 329- 345, 2013.

[15]

J. Jansson, W.-K. Sung, H. Vu, and S.-M. Yiu, "Faster algorithms for computing the R* consensus tree," Algorithmica, accepted for publication,

[16]

K. Bremer, "Combinable component consensus," Cladistics, vol. 6, no. 4, pp. 369-372, 1990.

[17]

J. Felsenstein, "PHYLIP, version 3.6," Software package, Department of Genome Sciences, University of Washington, Seattle, USA, 2005.

[18]

M. Lott, A. Spillner, K. T. Huber, A. Petri, B. Oxelman, and V. Moulton, "Inferring polyploid phylogenies from multiply-labeled gene trees," BMC Evol. Biol., vol. 9, 2009, Art. no. 216.

[19]

J. A. Cotton and M. Wilkinson, "Majority-rule supertrees," Systematic Biol., vol. 56, no. 3, pp. 445-452, 2007.

[20]

J. Dong, D. Fern_andez-Baca, F. R. McMorris, and R. C. Powers, "Majority-rule (+) consensus trees," Math. Biosciences, vol. 228, no. 1, pp. 10-15, 2010.

[21]

P. A. Goloboff, J. S. Farris, M. Källersjö, B. Oxelman, M. J. Ramírez, and C. A. Szumik, "Improvements to resampling measures of group support," Cladistics, vol. 19, no. 4, pp. 324-332, 2003.

[22]

M. Steel and J. D. Velasco, "Axiomatic opportunities and obstacles for inferring a species tree from gene trees," Systematic Biol., vol. 63, no. 5, pp. 772-778, 2014.

[23]

J.-P. Barth_elemy and F. R. McMorris, "The median procedure for n-trees," J. Classification, vol. 3, no. 2, pp. 329-334, 1986.

[24]

F. R. McMorris and R. C. Powers, "A characterization of majority rule for hierarchies," J. Classification, vol. 25, no. 2, pp. 153-158, 2008.

[25]

P. A. Goloboff, J. S. Farris, and K. C. Nixon, "TNT, a free program for phylogenetic analysis," Cladistics, vol. 24, no. 5, pp. 774-786, 2008.

[26]

R. Page, "COMPONENT, version 2.0," Software package, University of Glasgow, U.K., 1993.

[27]

F. Ronquist and J. P. Huelsenbeck, "MrBayes 3: Bayesian phylogenetic inference under mixed models," Bioinf., vol. 19, no. 12, pp. 1572-1574, 2003.

[28]

J. Sukumaran and M. T. Holder, "DendroPy: A Python library for phylogenetic computing," Bioinf., vol. 26, no. 12, pp. 1569-1571, 2010.

[29]

D. L. Swofford, "PAUP*, version 4.0," Software package, Sinauer Associates, Inc., Sunderland, MA, USA, 2003.

[30]

R. Cole, M. Farach-Colton, R. Hariharan, T. Przytycka, and M. Thorup, "An O(n log n algorithm for the maximum agreement subtree problem for binary trees," SIAM J. Comput., vol. 30, no. 5, pp. 1385-1404, 2000.

[31]

M. Farach and M. Thorup, "Fast comparison of evolutionary trees," Inform. Comput., vol. 123, no. 1, pp. 29-37, 1995.

[32]

M. A. Bender and M. Farach-Colton, "The LCA problem revisited," in Proc. 4th Latin Amer. Symp. Theoretical Informat., Lecture Notes in Computer Science, Springer-Verlag, vol. 1776, pp. 88-94, 2000.

[33]

D. Harel and R. E. Tarjan, "Fast algorithms for finding nearest common ancestors," SIAM J. Comput., vol. 13, no. 2, pp. 338-355, 1984.

[34]

The Boost C++ Libraries. [Online]. Available: http://www.boost.org/

[35]

A. McKenzie and M. Steel, "Distributions of cherries for two models of trees," Math. Biosciences, vol. 164, no. 1, pp. 81-92, 2000.

Cited By

Dang DTruong HNguyen N(2023)Hybrid Genetic Algorithms to Determine 2-Optimality Consensus for a Collective of Ordered PartitionsComputational Collective Intelligence10.1007/978-3-031-41456-5_1(3-15)Online publication date: 27-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-41456-5_1

Algorithms for the Majority Rule + Consensus Tree and the Frequency Difference Consensus Tree
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Greedy Consensus Tree and Maximum Greedy Consensus Tree Problems
WALCOM: Algorithms and Computation
Abstract
Consensus tree is a phylogenetic tree that summarizes the branching information of a set of conflicting phylogenetic trees. Computing consensus tree is a major step in phylogenetic tree reconstruction. It also finds application in predicting a ...
Faster Algorithms for Computing the R* Consensus Tree

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(n^{2} \sqrt{\log n})$$O(n2logn) time when $$k = 2$$k=2 (Jansson and Sung in Algorithmica 66(2):...
An optimal algorithm for building the majority rule consensus tree
RECOMB'13: Proceedings of the 17th international conference on Research in Computational Molecular Biology

A deterministic algorithm for building the majority rule consensus tree of an input collection of conflicting phylogenetic trees with identical leaf labels is presented. Its worst-case running time is O(nk), where n is the size of the leaf label set and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 15, Issue 1

January 2018

352 pages

ISSN:1545-5963

Issue’s Table of Contents

Copyright © 2018.

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 January 2018

Published in TCBB Volume 15, Issue 1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
52
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dang DTruong HNguyen N(2023)Hybrid Genetic Algorithms to Determine 2-Optimality Consensus for a Collective of Ordered PartitionsComputational Collective Intelligence10.1007/978-3-031-41456-5_1(3-15)Online publication date: 27-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-41456-5_1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents