Document Open Access Logo

Near-Optimal Algorithm for Constructing Greedy Consensus Tree

Author Hongxun Wu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.105.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Hongxun Wu
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China

Acknowledgements

We want to thank anonymous reviewers for many helpful comments.

Cite AsGet BibTex

Hongxun Wu. Near-Optimal Algorithm for Constructing Greedy Consensus Tree. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 105:1-105:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.105

Abstract

In biology, phylogenetic trees are important tools for describing evolutionary relations, but various data sources may result in conflicting phylogenetic trees. To summarize these conflicting phylogenetic trees, consensus tree methods take k conflicting phylogenetic trees (each with n leaves) as input and output a single phylogenetic tree as consensus. Among the consensus tree methods, a widely used method is the greedy consensus tree. The previous fastest algorithms for constructing a greedy consensus tree have time complexity Õ(kn^1.5) [Gawrychowski, Landau, Sung, Weimann 2018] and Õ(k²n) [Sung 2019] respectively. In this paper, we improve the running time to Õ(kn). Since k input trees have Θ(kn) nodes in total, our algorithm is optimal up to polylogarithmic factors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • phylogenetic trees
  • greedy consensus trees
  • splay tree

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Edward N Adams III. Consensus techniques and the comparison of taxonomic trees. Systematic Biology, 21(4):390-397, 1972. Google Scholar
  2. Alfred V Aho, John E Hopcroft, and Jeffrey D Ullman. On finding lowest common ancestors in trees. SIAM Journal on computing, 5(1):115-132, 1976. Google Scholar
  3. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. Acm Transactions on Algorithms (talg), 1(2):243-264, 2005. Google Scholar
  4. Nina Amenta, Frederick Clarke, and Katherine St John. A linear-time majority tree algorithm. In International Workshop on Algorithms in Bioinformatics, pages 216-227. Springer, 2003. Google Scholar
  5. Amihood Amir and Dmitry Keselman. Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms. SIAM Journal on Computing, 26(6):1656-1669, 1997. Google Scholar
  6. Md Shamsuzzoha Bayzid, Siavash Mirarab, Bastien Boussau, and Tandy Warnow. Weighted statistical binning: enabling statistically consistent genome-scale phylogenetic analyses. PLoS One, 10(6):e0129183, 2015. Google Scholar
  7. Md Shamsuzzoha Bayzid and Tandy Warnow. Naive binning improves phylogenomic analyses. Bioinformatics, 29(18):2277-2284, 2013. Google Scholar
  8. Kåre Bremer. Combinable component consensus. Cladistics, 6(4):369-372, 1990. Google Scholar
  9. David Bryant. A classification of consensus methods for phylogenetics. DIMACS series in discrete mathematics and theoretical computer science, 61:163-184, 2003. Google Scholar
  10. William HE Day. Optimal algorithms for comparing trees with labeled leaves. Journal of classification, 2(1):7-28, 1985. Google Scholar
  11. James H Degnan, Michael DeGiorgio, David Bryant, and Noah A Rosenberg. Properties of consensus methods for inferring species trees from gene trees. Systematic Biology, 58(1):35-54, 2009. Google Scholar
  12. Martin Farach, Teresa M Przytycka, and Mikkel Thorup. Computing the agreement of trees with bounded degrees. In European Symposium on Algorithms, pages 381-393. Springer, 1995. Google Scholar
  13. Martin Farach and Mikkel Thorup. Optimal evolutionary tree comparison by sparse dynamic programming. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 770-779. IEEE, 1994. Google Scholar
  14. James S Farris. On comparing the shapes of taxonomic trees. Systematic Zoology, 22(1):50-54, 1973. Google Scholar
  15. J Felsenstein. Phylip version 3.6. Software package, Department of Genome Sciences, University of Washington, Seattle, USA, 2005. Google Scholar
  16. Pawel Gawrychowski, Gad M. Landau, Wing-Kin Sung, and Oren Weimann. A faster construction of greedy consensus trees. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 63:1-63:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.63.
  17. Jotun Hein, Tao Jiang, Lusheng Wang, and Kaizhong Zhang. On the complexity of comparing evolutionary trees. In Annual Symposium on Combinatorial Pattern Matching, pages 177-190. Springer, 1995. Google Scholar
  18. Monika Rauch Henzinger, Valerie King, and Tandy Warnow. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica, 24(1):1-13, 1999. Google Scholar
  19. Jesper Jansson, Zhaoxian Li, and Wing-Kin Sung. On finding the adams consensus tree. Information and Computation, 256:334-347, 2017. Google Scholar
  20. Jesper Jansson, Ramesh Rajaby, and Wing-Kin Sung. Minimal phylogenetic supertrees and local consensus trees. AIMS Medical Science, 5(2):181, 2018. Google Scholar
  21. Jesper Jansson, Chuanqi Shen, and Wing-Kin Sung. Algorithms for the majority rule (+) consensus tree and the frequency difference consensus tree. In International Workshop on Algorithms in Bioinformatics, pages 141-155. Springer, 2013. Google Scholar
  22. Jesper Jansson, Chuanqi Shen, and Wing-Kin Sung. Improved algorithms for constructing consensus trees. Journal of the ACM (JACM), 63(3):28, 2016. Google Scholar
  23. Jesper Jansson, Wing-Kin Sung, Hoa Vu, and Siu-Ming Yiu. Faster algorithms for computing the r* consensus tree. Algorithmica, 76(4):1224-1244, 2016. Google Scholar
  24. Erich D Jarvis, Siavash Mirarab, Andre J Aberer, Bo Li, Peter Houde, Cai Li, Simon YW Ho, Brant C Faircloth, Benoit Nabholz, Jason T Howard, et al. Whole-genome analyses resolve early branches in the tree of life of modern birds. Science, 346(6215):1320-1331, 2014. Google Scholar
  25. Sampath Kannan, Tandy Warnow, and Shibu Yooseph. Computing the local consensus of trees. SIAM Journal on Computing, 27(6):1695-1724, 1998. Google Scholar
  26. Liang Liu, Lili Yu, and Scott V Edwards. A maximum pseudo-likelihood approach for estimating species trees under the coalescent model. BMC evolutionary biology, 10(1):302, 2010. Google Scholar
  27. Liang Liu, Lili Yu, Laura Kubatko, Dennis K Pearl, and Scott V Edwards. Coalescent methods for estimating phylogenetic trees. Molecular Phylogenetics and Evolution, 53(1):320-328, 2009. Google Scholar
  28. Timothy Margush and Fred R McMorris. Consensus n-trees. Bulletin of Mathematical Biology, 43(2):239-244, 1981. Google Scholar
  29. Kurt Mehlhorn, Rajamani Sundar, and Christian Uhrig. Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica, 17(2):183-198, 1997. Google Scholar
  30. Siavash Mirarab, Md Shamsuzzoha Bayzid, and Tandy Warnow. Evaluating summary methods for multilocus species tree estimation in the presence of incomplete lineage sorting. Systematic Biology, 65(3):366-380, 2014. Google Scholar
  31. James B Pease, David C Haak, Matthew W Hahn, and Leonie C Moyle. Phylogenomics reveals three sources of adaptive variation during a rapid radiation. PLoS Biology, 14(2):e1002379, 2016. Google Scholar
  32. Fredrik Ronquist and John P Huelsenbeck. Mrbayes 3: Bayesian phylogenetic inference under mixed models. Bioinformatics, 19(12):1572-1574, 2003. Google Scholar
  33. Leonidas Salichos and Antonis Rokas. Inferring ancient divergences requires genes with strong phylogenetic signals. Nature, 497(7449):327, 2013. Google Scholar
  34. Leonidas Salichos, Alexandros Stamatakis, and Antonis Rokas. Novel information theory-based measures for quantifying incongruence among phylogenetic trees. Molecular Biology and Evolution, 31(5):1261-1271, 2014. Google Scholar
  35. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652-686, 1985. Google Scholar
  36. Jordan V Smith, Edward L Braun, and Rebecca T Kimball. Ratite nonmonophyly: independent evidence from 40 novel loci. Systematic Biology, 62(1):35-49, 2012. Google Scholar
  37. Alexandros Stamatakis. Raxml version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies. Bioinformatics, 30(9):1312-1313, 2014. Google Scholar
  38. Alexandros Stamatakis, Paul Hoover, and Jacques Rougemont. A rapid bootstrap algorithm for the raxml web servers. Systematic biology, 57(5):758-771, 2008. Google Scholar
  39. Wing-Kin Sung. Greedy consensus tree and maximum greedy consensus tree problems. In International Workshop on Algorithms and Computation, pages 305-316. Springer, 2019. Google Scholar
  40. DL Swofford. Paup*, version 4.0. software package, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact