Document Open Access Logo

Embedding Phylogenetic Trees in Networks of Low Treewidth

Authors Leo van Iersel, Mark Jones , Mathias Weller

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.69.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

Leo van Iersel
  • Delft Institute of Applied Mathematics, Delft University of Technology, The Netherlands
Mark Jones
  • Delft Institute of Applied Mathematics, Delft University of Technology, The Netherlands
Mathias Weller
  • CNRS, LIGM (UMR 8049), Champs-s/-Marne, France

Funding

  • van Iersel, Leo: Partially funded by Netherlands Organization for Scientific Research (NWO) Vidi grant 639.072.602 and KLEIN grant OCENW.KLEIN.125.
  • Jones, Mark: Partially funded by Netherlands Organization for Scientific Research (NWO) KLEIN grant OCENW.KLEIN.125.

Acknowledgements

We are extremely grateful to the anonymous reviewers for their many insightful and helpful comments.

Cite AsGet BibTex

Leo van Iersel, Mark Jones, and Mathias Weller. Embedding Phylogenetic Trees in Networks of Low Treewidth. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.69

Abstract

Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called Tree Containment, arises when validating networks constructed by phylogenetic inference methods. We present the first algorithm for (rooted) Tree Containment using the treewidth t of the input network N as parameter, showing that the problem can be solved in 2^O(t²)⋅|N| time and space.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • fixed-parameter tractability
  • treewidth
  • phylogenetic tree
  • phylogenetic network
  • display graph
  • tree containment
  • embedding

Metrics

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

Related Versions

References

  1. Julien Baste, Christophe Paul, Ignasi Sau, and Scornavacca Celine. Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees. Bulletin of Mathematical Biology, 79:920-938, 2017. Google Scholar
  2. Matthias Bentert, Josef Malík, and Mathias Weller. Tree containment with soft polytomies. In SWAT'18, volume 101, pages 9-1, 2018. Google Scholar
  3. Vincent Berry, Celine Scornavacca, and Mathias Weller. Scanning phylogenetic networks is NP-hard. In SOFSEM'20, pages 519-530. Springer, 2020. Google Scholar
  4. Hans L Bodlaender. Dynamic programming on graphs with bounded treewidth. In ICALP'88, pages 105-118. Springer, 1988. Google Scholar
  5. Hans L Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305-1317, 1996. Google Scholar
  6. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. Google Scholar
  7. Hans L Bodlaender, Pål Grønås Drange, Markus S Dregi, Fedor V Fomin, Daniel Lokshtanov, and Michał Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. Google Scholar
  8. Magnus Bordewich and Charles Semple. Computing the minimum number of hybridization events for a consistent evolutionary history. Discrete Applied Mathematics, 155(8):914-928, 2007. Google Scholar
  9. David Bryant and Jens Lagergren. Compatibility of unrooted phylogenetic trees is FPT. Theoretical Computer Science, 351(3):296-302, 2006. Parameterized and Exact Computation. Google Scholar
  10. Bruno Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. In Handbook Of Graph Grammars And Computing By Graph Transformation: Volume 1: Foundations, pages 313-400. World Scientific, 1997. Google Scholar
  11. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  12. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Joham MM van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS'11, pages 150-159. IEEE, 2011. Google Scholar
  13. Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon. Measuring what matters: A hybrid approach to dynamic programming with treewidth. Journal of Computer and System Sciences, 121:57-75, 2021. Google Scholar
  14. Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38(2):629-657, 2008. Google Scholar
  15. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Hitting Topological Minors is FPT, pages 1317-1326. Association for Computing Machinery, New York, NY, USA, 2020. Google Scholar
  16. Steven Fortune, John Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111-121, 1980. Google Scholar
  17. Philippe Gambette, Andreas D. M. Gunawan, Anthony Labarre, Stéphane Vialette, and Louxin Zhang. Solving the tree containment problem for genetically stable networks in quadratic time. In IWOCA'15, pages 197-208, 2015. Google Scholar
  18. Philippe Gambette, Andreas DM Gunawan, Anthony Labarre, Stéphane Vialette, and Louxin Zhang. Solving the tree containment problem in linear time for nearly stable phylogenetic networks. Discrete Applied Mathematics, 246:62-79, 2018. Google Scholar
  19. Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar. Are there any good digraph width measures? Journal of Combinatorial Theory, Series B, 116:250-286, 2016. Google Scholar
  20. A Grigoriev, S Kelk, and L Lekic. On low treewidth graphs and supertrees. Journal of Graph Algorithms and Applications, 19(1):325-343, 2015. Google Scholar
  21. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. In STOC'11, pages 479-488, 2011. Google Scholar
  22. Andreas DM Gunawan. Solving the tree containment problem for reticulation-visible networks in linear time. In AlCoB'18, pages 24-36. Springer, 2018. Google Scholar
  23. Andreas DM Gunawan, Bingxin Lu, and Louxin Zhang. A program for verification of phylogenetic network models. Bioinformatics, 32(17):i503-i510, 2016. Google Scholar
  24. Andreas DM Gunawan, Hongwei Yan, and Louxin Zhang. Compression of phylogenetic networks and algorithm for the tree containment problem. Journal of Computational Biology, 26(3):285-294, 2019. Google Scholar
  25. Katharina T Huber, Simone Linz, and Vincent Moulton. The rigid hybrid number for two phylogenetic trees. Journal of Mathematical Biology, 82(5):1-29, 2021. Google Scholar
  26. Katharina T Huber, Vincent Moulton, Mike Steel, and Taoyang Wu. Folding and unfolding phylogenetic trees and networks. Journal of Mathematical Biology, 73(6):1761-1780, 2016. Google Scholar
  27. Katharina T Huber, Leo van Iersel, Remie Janssen, Mark Jones, Vincent Moulton, Yukihiro Murakami, and Charles Semple. Rooting for phylogenetic networks. arXiv preprint, 2019. URL: http://arxiv.org/abs/1906.07430.
  28. Leo van Iersel, Steven Kelk, Georgios Stamoulis, Leen Stougie, and Olivier Boes. On unrooted and root-uncertain variants of several well-known phylogenetic network problems. Algorithmica, 80(11):2993-3022, 2018. Google Scholar
  29. 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
  30. R. Janssen, M. Jones, S. Kelk, G. Stamoulis, and T. Wu. Treewidth of display graphs: bounds, brambles and applications. Journal oof Graph Algorithms and Applications, 23:715-743, 2019. Google Scholar
  31. Remie Janssen and Yukihiro Murakami. On cherry-picking and network containment. Theoretical Computer Science, 856:121-150, 2021. Google Scholar
  32. 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
  33. Steven Kelk, Georgios Stamoulis, and Taoyang Wu. Treewidth distance on phylogenetic trees. Theoretical Computer Science, 731:99-117, 2018. Google Scholar
  34. Steven Kelk, Leo van Iersel, Celine Scornavacca, and Mathias Weller. Phylogenetic incongruence through the lens of monadic second order logic. Journal of Graph Algorithms and Applications, 20(2):189-215, 2016. Google Scholar
  35. Jonathan Klawitter and Peter Stumpf. Drawing tree-based phylogenetic networks with minimum number of crossings. arXiv preprint, 2020. URL: http://arxiv.org/abs/2008.08960.
  36. Ton Kloks. Treewidth: computations and approximations. Springer, 1994. Google Scholar
  37. Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. In FOCS'21, pages 184-192, 2021. Google Scholar
  38. Celine Scornavacca and Mathias Weller. Treewidth-based algorithms for the small parsimony problem on networks. In WABI'21, 2021. Google Scholar
  39. Leo van Iersel, Remie Janssen, Mark Jones, Yukihiro Murakami, and Norbert Zeh. Polynomial-time algorithms for phylogenetic inference problems involving duplication and reticulation. IEEE/ACM transactions on computational biology and bioinformatics, 17(1):14-26, 2019. Google Scholar
  40. Leo van Iersel, Mark Jones, and Mathias Weller. Embedding phylogenetic trees in networks of low treewidth. arXiv preprint, 2022. URL: http://arxiv.org/abs/2207.00574.
  41. Leo van Iersel, Steven Kelk, Nela Lekic, Chris Whidden, and Norbert Zeh. Hybridization number on three rooted binary trees is ept. SIAM Journal on Discrete Mathematics, 30(3):1607-1631, 2016. Google Scholar
  42. Leo van Iersel, Steven Kelk, and Celine Scornavacca. Kernelizations for the hybridization number problem on multiple nonbinary trees. Journal of Computer and System Sciences, 82(6):1075-1089, 2016. Google Scholar
  43. Leo van Iersel and Simone Linz. A quadratic kernel for computing the hybridization number of multiple trees. Information Processing Letters, 113(9):318-323, 2013. Google Scholar
  44. Mathias Weller. Linear-time tree containment in phylogenetic networks. In RECOMB CG'18, pages 309-323. Springer, 2018. 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