×

Display sets of normal and tree-child networks. (English) Zbl 1456.05154

Summary: Phylogenetic networks are leaf-labelled directed acyclic graphs that are used in computational biology to analyse and represent the evolutionary relationships of a set of species or viruses. In contrast to phylogenetic trees, phylogenetic networks have vertices of in-degree at least two that represent reticulation events such as hybridisation, lateral gene transfer, or reassortment. By systematically deleting various combinations of arcs in a phylogenetic network \(\mathcal{N}\), one derives a set of phylogenetic trees that are embedded in \(\mathcal{N}\). We recently showed that the problem of deciding if two binary phylogenetic networks embed the same set of phylogenetic trees is computationally hard, in particular, we showed it to be \(\Pi^P_2\)-complete. In this paper, we establish a polynomial-time algorithm for this decision problem if the initial two networks consist of a normal network and a tree-child network; two well-studied topologically restricted subclasses of phylogenetic networks, with normal networks being more structurally constrained than tree-child networks. The running time of the algorithm is quadratic in the size of the leaf sets.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
92D15 Problems related to evolution
92C42 Systems biology, networks

Software:

PhyloNetworks
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Bordewich and C. Semple. Reticulation-visible networks.Adv. Appl. Math., 76:114-141, 2016. · Zbl 1335.05170
[2] M. Bordewich and C. Semple. Determining phylogenetic networks from inter-taxa distances.J. Math. Bio., 73:283-303, 2016. · Zbl 1343.05147
[3] G. Cardona, F. Rossell´o, and G. Valiente. Comparison of tree-child phylogenetic networks.IEEE/ACM Trans. Comput. Biol. Bioinf., 6:552-569, 2009.
[4] P. Cordue, S. Linz, and C. Semple. Phylogenetic networks that display a tree twice. B. Math. Biol., 76:2664-2679, 2014. · Zbl 1330.92085
[5] J. D¨ocker, S. Linz, and C. Semple. Displaying trees across two phylogenetic networks. Theor. Comput. Sci., 796:129-146, 2019. · Zbl 1435.68231
[6] P. Gambette and K. T. Huber. On encodings of phylogenetic networks of bounded level.J. Math. Bio., 65:157-180, 2012. · Zbl 1303.92080
[7] A. D. M. Gunawan. Solving the Tree Containment problem for reticulation-visible networks in linear time. InAlgorithms for Computational Biology, pages 24-36. Springer, 2018. · Zbl 1392.92060
[8] A. D. M. Gunawan, B. DasGupta, and L. Zhang. A decomposition theorem and two algorithms for reticulation-visible networks.Inform. Comput., 252:161-175, 2017. · Zbl 1361.92053
[9] L. van Iersel and V. Moulton. Trinets encode tree-child and level-2 phylogenetic networks.J. Math. Bio., 68:1707-1729, 2014. · Zbl 1339.92008
[10] L. van Iersel, C. Semple, and M. Steel. Locating a tree in a phylogenetic network. Inform. Process. Lett., 110:1037-1043, 2010. · Zbl 1379.68184
[11] I. A. Kanj, L. Nakhleh, C. Than, and G. Xia. Seeing the trees and their branches in the network is hard.Theor. Comput. Sci., 401:153-164, 2008. · Zbl 1147.68059
[12] S. Linz, K. St John, and C. Semple. Counting trees in a phylogenetic network is #P-complete.SIAM J. Comput., 42:1768-1776, 2013. · Zbl 1276.05028
[13] C. McDiarmid, C. Semple, and D. Welsh. Counting phylogenetic networks.Ann. Comb., 19:205-224, 2015. · Zbl 1310.05120
[14] N. F. M¨uller, U. Stolz, G. Dudas, T. Stadler, and T. G. Vaughan. Bayesian inference of reassortment networks reveals fitness benefits of reassortment in human influenza viruses.P. Natl. Acad. Sci. USA, 117:17104-17111, 2020.
[15] L. Nakhleh, G. Jin, F. Zhao, and J. Mellon-Crummey. Reconstructing phylogenetic networks using maximum parsimony. InProceedings of the 2005 IEEE Computational Systems Bioinformatics Conference, pages 93-102. IEEE, 2005.
[16] C. Semple. Phylogenetic networks with every embedded phylogenetic tree a base tree. B. Math. Biol., 78:32-137, 2016. · Zbl 1356.92067
[17] C. Sol´ıs-Lemus, P. Bastide, and C. An´e. PhyloNetworks: a package for phylogenetic networks.Mol. Biol. Evol., 34:3292-3298, 2017.
[18] L. J. Stockmeyer. The polynomial-time hierarchy.Theor. Comput. Sci., 3:1-22, 1978. · Zbl 0353.02024
[19] S. J. Willson. Properties of normal phylogenetic networks.B. Math. Biol., 72:340-358, 2010. · Zbl 1185.92085
[20] S. J. Willson. Regular networks can be uniquely constructed from their trees. IEEE/ACM Trans. Comput. Biol. Bioinf., 8:785-796, 2011.
[21] S. J. Willson. Tree-average distances on certain phylogenetic networks have their weights uniquely determined.Algorithm. Mol. Biol., 7:13, 2012.
[22] J.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.