Document Open Access Logo

Minimal Phylogenetic Supertrees and Local Consensus Trees

Authors Jesper Jansson, Wing-Kin Sung

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.53.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Jesper Jansson
Wing-Kin Sung

Cite AsGet BibTex

Jesper Jansson and Wing-Kin Sung. Minimal Phylogenetic Supertrees and Local Consensus Trees. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.53

Abstract

The problem of constructing a minimally resolved phylogenetic supertree (i.e., having the smallest possible number of internal nodes) that contains all of the rooted triplets from a consistent set R is known to be NP-hard. In this paper, we prove that constructing a phylogenetic tree consistent with R that contains the minimum number of additional rooted triplets is also NP-hard, and develop exact, exponential-time algorithms for both problems. The new algorithms are applied to construct two variants of the local consensus tree; for any set S of phylogenetic trees over some leaf label set L, this gives a minimal phylogenetic tree over L that contains every rooted triplet present in all trees in S, where ``minimal'' means either having the smallest possible number of internal nodes or the smallest possible number of rooted triplets. The second variant generalizes the RV-II tree, introduced by Kannan, Warnow, and Yooseph in 1998.
Keywords
  • phylogenetic tree
  • rooted triplet
  • local consensus
  • minimal supertree
  • computational complexity
  • bioinformatics

Metrics

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

References

  1. E. N. Adams III. Consensus techniques and the comparison of taxonomic trees. Systematic Zoology, 21(4):390-397, 1972. Google Scholar
  2. A. V. Aho, Y. Sagiv, T. G. Szymanski, and J. D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing, 10(3):405-421, 1981. 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. O. R. P. Bininda-Emonds. The evolution of supertrees. TRENDS in Ecology and Evolution, 19(6):315-322, 2004. Google Scholar
  5. O. R. P. Bininda-Emonds, M. Cardillo, K. E. Jones, R. D. E. MacPhee, R. M. D. Beck, R. Grenyer, S. A. Price, R. A. Vos, J. L. Gittleman, and A. Purvis. The delayed rise of present-day mammals. Nature, 446(7135):507-512, 2007. Google Scholar
  6. D. Bryant. Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis. PhD thesis, University of Canterbury, Christchurch, New Zealand, 1997. Google Scholar
  7. 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
  8. J. Byrka, S. Guillemot, and J. Jansson. New results on optimizing rooted triplets consistency. Discrete Applied Mathematics, 158(11):1136-1147, 2010. Google Scholar
  9. B. Chor, M. Hendy, and D. Penny. Analytic solutions for three taxon ML trees with variable rates across sites. Discrete Applied Mathematics, 155(6-7):750-758, 2007. Google Scholar
  10. M. Constantinescu and D. Sankoff. An efficient algorithm for supertrees. Journal of Classification, 12(1):101-112, 1995. Google Scholar
  11. J. Felsenstein. Inferring Phylogenies. Sinauer Associates, Inc., Sunderland, Massachusetts, 2004. Google Scholar
  12. M. Garey and D. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979. Google Scholar
  13. L. Ga̧sieniec, J. Jansson, A. Lingas, and A. Östlin. On the complexity of constructing evolutionary trees. Journal of Combinatorial Optimization, 3(2-3):183-197, 1999. Google Scholar
  14. Y. J. He, T. N. D. Huynh, J. Jansson, and W.-K. Sung. Inferring phylogenetic relationships avoiding forbidden rooted triplets. Journal of Bioinformatics and Computational Biology, 4(1):59-74, 2006. Google Scholar
  15. M. R. Henzinger, V. King, and T. Warnow. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica, 24(1):1-13, 1999. Google Scholar
  16. J. Jansson, R. S. Lemence, and A. Lingas. The complexity of inferring a minimally resolved phylogenetic supertree. SIAM Journal on Computing, 41(1):272-291, 2012. Google Scholar
  17. S. Kannan, T. Warnow, and S. Yooseph. Computing the local consensus of trees. SIAM Journal on Computing, 27(6):1695-1724, 1998. Google Scholar
  18. M. P. Ng and N. C. Wormald. Reconstruction of rooted trees from subtrees. Discrete Applied Mathematics, 69(1-2):19-31, 1996. Google Scholar
  19. C. Semple. Reconstructing minimal rooted trees. Discrete Applied Mathematics, 127(3):489-503, 2003. Google Scholar
  20. C. Semple, P. Daniel, W. Hordijk, R. D. M. Page, and M. Steel. Supertree algorithms for ancestral divergence dates and nested taxa. Bioinformatics, 20(15):2355-2360, 2004. Google Scholar
  21. S. Snir and S. Rao. Using Max Cut to enhance rooted trees consistency. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):323-333, 2006. Google Scholar
  22. M. Steel. The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification, 9(1):91-116, 1992. Google Scholar
  23. W.-K. Sung. Algorithms in Bioinformatics: A Practical Introduction. Chapman &Hall/CRC, Boca Raton, Florida, 2010. Google Scholar
  24. S. J. Willson. Constructing rooted supertrees using distances. Bulletin of Mathematical Biology, 66(6):1755-1783, 2004. Google Scholar
  25. C. Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In Proceedings of the 24^th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pages 1757-1769. SIAM, 2013. 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