Document Open Access Logo

On Finding the Adams Consensus Tree

Authors Jesper Jansson, Zhaoxian Li, Wing-Kin Sung

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2015.487.pdf
  • Filesize: 0.65 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • phylogenetic tree
  • Adams consensus
  • centroid path
  • wavelet tree

Metrics

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

Abstract

This paper presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels, for the first time improving the time complexity of a widely used algorithm invented by Adams in 1972 [1]. Our algorithm applies
the centroid path decomposition technique [9] in a new way to traverse the input trees' centroid paths in unison, and runs in O(k n \log n) time, where k is the number of input trees and n is the size of the leaf label set. (In comparison, the old algorithm from 1972 has a worst-case running time of O(k n^2).) For the special case of k = 2, an even faster algorithm running in O(n \cdot \frac{\log n}{\log\log n}) time is provided, which relies on an extension of the wavelet tree-based technique by Bose et al. [6] for orthogonal range counting on a grid.
Our extended wavelet tree data structure also supports truncated
range maximum queries efficiently and may be of independent interest to algorithm designers.

Cite As Get BibTex

Jesper Jansson, Zhaoxian Li, and Wing-Kin Sung. On Finding the Adams Consensus Tree. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 487-499, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.487

Author Details

Jesper Jansson
Zhaoxian Li
Wing-Kin Sung

References

  1. E. N. Adams III. Consensus techniques and the comparison of taxonomic trees. Systematic Zoology, 21(4):390-397, 1972. Google Scholar
  2. E. N. Adams III. N-trees as nestings: Complexity, similarity, and consensus. Journal of Classification, 3(2):299-317, 1986. Google Scholar
  3. M. A. Bender and M. Farach-Colton. The LCA problem revisited. In Proceedings of the 4^th\!\! Latin American Symposium on Theoretical Informatics (LATIN 2000), volume 1776 of LNCS, pages 88-94. Springer-Verlag, 2000. Google Scholar
  4. M. A. Bender and M. Farach-Colton. The Level Ancestor Problem simplified. Theoretical Computer Science, 321(1):5-12, 2004. Google Scholar
  5. M. G. B. Blum, O. François, and S. Janson. The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance. The Annals of Applied Probability, 16(4):2195-2214, 2006. Google Scholar
  6. P. Bose, M. He, A. Maheshwari, and P. Morin. Succinct orthogonal range search structures on a grid with applications to text indexing. In Proceedings of the 11^\!th\! International Symposium on Algorithms and Data Structures (WADS 2009), volume 5664 of LNCS, pages 98-109. Springer-Verlag, 2009. Google Scholar
  7. K. Bremer. Combinable component consensus. Cladistics, 6(4):369-372, 1990. Google Scholar
  8. D. Bryant. A classification of consensus methods for phylogenetics. In M. F. Janowitz, F.-J. Lapointe, F. R. McMorris, B. Mirkin, and F. S. Roberts, editors, Bioconsensus, volume 61 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 163-184. American Mathematical Society, 2003. Google Scholar
  9. 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 Journal on Computing, 30(5):1385-1404, 2000. Google Scholar
  10. J. Felsenstein. Inferring Phylogenies. Sinauer Associates, Inc., Sunderland, Massachusetts, 2004. Google Scholar
  11. J. Felsenstein. PHYLIP, version 3.6. Software package, Department of Genome Sciences, University of Washington, Seattle, U.S.A., 2005. Google Scholar
  12. 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, 19(4):324-332, 2003. Google Scholar
  13. D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-355, 1984. Google Scholar
  14. E. Hernández-García, M. Tuǧrul, E. Alejandro Herrada, V. M. Eguíluz, and K. Klemm. Simple models for scaling in phylogenetic trees. International Journal of Bifurcation and Chaos, 20(3):805-811, 2010. Google Scholar
  15. Z.-X. Luo, Q. Ji, J. R. Wible, and C.-X. Yuan. An early Cretaceous tribosphenic mammal and metatherian evolution. Science, 302(5652):1934-1940, 2003. Google Scholar
  16. T. Margush and F. R. McMorris. Consensus n-Trees. Bulletin of Mathematical Biology, 43(2):239-244, 1981. Google Scholar
  17. L. Nakhleh, T. Warnow, D. Ringe, and S. N. Evans. A comparison of phylogenetic reconstruction methods on an Indo-European dataset. Transactions of the Philological Society, 103(2):171-192, 2005. Google Scholar
  18. R. Page. COMPONENT, version 2.0. Software package, University of Glasgow, U.K., 1993. Google Scholar
  19. E. R. Seiffert. Revised age estimates for the later Paleogene mammal faunas of Egypt and Oman. Proceedings of the National Academy of Sciences of the United States of America (PNAS), 103(13):5000-5005, 2006. Google Scholar
  20. C. Semple and M. Steel. Phylogenetics, volume 24 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, 2003. Google Scholar
  21. R. R. Sokal and F. J. Rohlf. Taxonomic congruence in the Leptopodomorpha re-examined. Systematic Zoology, 30(3):309-325, 1981. Google Scholar
  22. W.-K. Sung. Algorithms in Bioinformatics: A Practical Introduction. Chapman & Hall/CRC, 2010. Google Scholar
  23. D. L. Swofford. PAUP*, version 4.0. Software package, Sinauer Associates, Inc., Sunderland, Massachusetts, 2003. Google Scholar
  24. X. Xu, J. M. Clark, C. A. Forster, M. A. Norell, G. M. Erickson, D. A. Eberth, C. Jia, and Q. Zhao. A basal tyrannosauroid dinosaur from the Late Jurassic of China. Nature, 439(7077):715-718, 2006. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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