Document Open Access Logo

Tree Containment With Soft Polytomies

Authors Matthias Bentert, Josef Malík, Mathias Weller

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.9.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Matthias Bentert
  • TU Berlin, Institut für Softwaretechnik und Theoretische Informatik, Berlin, Germany
Josef Malík
  • Czech Technical University, Prague, Czech Republic
Mathias Weller
  • CNRS, LIGM, Université Paris Est, Marne-la-Vallée, France

Cite AsGet BibTex

Matthias Bentert, Josef Malík, and Mathias Weller. Tree Containment With Soft Polytomies. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SWAT.2018.9

Abstract

The Tree Containment problem has many important applications in the study of evolutionary history. Given a phylogenetic network N and a phylogenetic tree T whose leaves are labeled by a set of taxa, it asks if N and T are consistent. While the case of binary N and T has received considerable attention, the more practically relevant variant dealing with biological uncertainty has not. Such uncertainty manifests itself as high-degree vertices ("polytomies") that are "jokers" in the sense that they are compatible with any binary resolution of their children. Contrasting the binary case, we show that this problem, called Soft Tree Containment, is NP-hard, even if N is a binary, multi-labeled tree in which each taxon occurs at most thrice. On the other hand, we reduce the case that each label occurs at most twice to solving a 2-SAT instance of size O(|T|^3). This implies NP-hardness and polynomial-time solvability on reticulation-visible networks in which the maximum in-degree is bounded by three and two, respectively.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Applied computing → Biological networks
Keywords
  • Phylogenetics
  • Reticulation-Visible Networks
  • Multifurcating Trees

Metrics

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

References

  1. Magnus Bordewich and Charles Semple. Reticulation-visible networks. Advances in Applied Mathematics, 78:114-141, 2016. Google Scholar
  2. Joseph Minhow Chan, Gunnar Carlsson, and Raul Rabadan. Topology of viral evolution. Proceedings of the National Academy of Sciences, 110(46):18566-18571, 2013. Google Scholar
  3. Richard Cole, Martin Farach-Colton, Ramesh Hariharan, Teresa Przytycka, and Mikkel 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
  4. A Dress, Katharina Huber, J Koolen, Vincent Moulton, and A Spillner. Basic Phylogenetic Combinatorics. Cambridge University Press, 2004. Google Scholar
  5. Jittat Fakcharoenphol, Tanee Kumpijit, and Attakorn Putwattana. A faster algorithm for the tree containment problem for binary nearly stable phylogenetic networks. In 12th International Joint Conference on Computer Science and Software Engineering (JCSSE'15), pages 337-342. IEEE, 2015. Google Scholar
  6. Philippe Gambette, Andreas D. M. Gunawan, Anthony Labarre, Stéphane Vialette, and Louxin Zhang. Locating a tree in a phylogenetic network in quadratic time. In Proceedings of the 19th Annual International Conference on Research in Computational Molecular Biology (RECOMB'15), volume 9029 of LNCS, pages 96-107. Springer, 2015. Google Scholar
  7. Andreas D. M. Gunawan. Solving tree containment problem for reticulation-visible networks with optimal running time. CoRR, abs/1702.04088, 2017. Google Scholar
  8. Andreas D. M. Gunawan, Bingxin Lu, and Louxin Zhang. A program for verification of phylogenetic network models. Bioinformatics, 32(17):i503-i510, 2016. Google Scholar
  9. Andreas D. M. Gunawan, Bingxin Lu, and Louxin Zhang. Fast methods for solving the cluster containment problem for phylogenetic networks. CoRR, 1801.04498, 2018. Google Scholar
  10. Andreas D.M. Gunawan, Bhaskar DasGupta, and Louxin Zhang. A decomposition theorem and two algorithms for reticulation-visible networks. Information and Computation, 252:161-175, 2017. Google Scholar
  11. Dan Gusfield. ReCombinatorics: the algorithmics of ancestral recombination graphs and explicit phylogenetic networks. MIT Press, 2014. Google Scholar
  12. John Hopcroft and Robert Tarjan. Algorithm 447: Efficient algorithms for graph manipulation. Commun. ACM, 16(6):372-378, 1973. Google Scholar
  13. Daniel H Huson, Regula Rupp, and Celine Scornavacca. Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press, 2010. Google Scholar
  14. Iyad A Kanj, Luay Nakhleh, Cuong Than, and Ge Xia. Seeing the trees and their branches in the network is hard. Theoretical Computer Science, 401(1-3):153-164, 2008. Google Scholar
  15. Todd J Treangen and Eduardo PC Rocha. Horizontal transfer, not duplication, drives the expansion of protein families in prokaryotes. PLoS Genet, 7(1):e1001284, 2011. Google Scholar
  16. René van Bevern, Matthias Mnich, Rolf Niedermeier, and Mathias Weller. Interval scheduling and colorful independent sets. J. Scheduling, 18(5):449-469, 2015. URL: http://dx.doi.org/10.1007/s10951-014-0398-5.
  17. Leo Van Iersel, Charles Semple, and Mike Steel. Locating a tree in a phylogenetic network. Information Processing Letters, 110(23):1037-1043, 2010. Google Scholar
  18. Mathias Weller. Linear-time tree containment in phylogenetic networks. CoRR, 1702.06364, 2017. 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