Generation of Orchard and Tree-Child Networks
Tóm tắt
Phylogenetic networks are an extension of phylogenetic trees that allow for the representation of reticulate evolution events. One of the classes of networks that has gained the attention of the scientific community over the last years is the class of orchard networks, that generalizes tree-child networks, one of the most studied classes of networks. In this paper we focus on the combinatorial and algorithmic problem of the generation of binary orchard networks, and also of binary tree-child networks. To this end, we use that these networks are defined as those that can be recovered by reversing a certain reduction process. Then, we show how to choose a “minimum” reduction process among all that can be applied to a network, and hence we get a unique representation of the network that, in fact, can be given in terms of sequences of pairs of integers, whose length is related to the number of leaves and reticulations of the network. Therefore, the generation of networks is reduced to the generation of such sequences of pairs. Our main result is a recursive method for the efficient generation of all minimum sequences, and hence of all orchard (or tree-child) networks with a given number of leaves and reticulations. An implementation in C of the algorithms described in this paper, along with some computational experiments, can be downloaded from the public repository
https://github.com/gerardet46/OrchardGenerator
. Using this implementation, we have computed the number of binary orchard networks with at most 6 leaves and 8 reticulations.
Tài liệu tham khảo
Aldous D (1996) Probability distributions on cladograms. In: Random discrete structures. Springer, pp 1–18. https://doi.org/10.1007/978-1-4612-0719-1_1
Bordewich M, Semple C (2016) Determining phylogenetic networks from inter-taxa distances. J Math Biol 73(2):283–303. https://doi.org/10.1007/s00285-015-0950-8
Cardona G (2023) PhyloNetwork, v.2.2. https://github.com/bielcardona/PhyloNetwork
Cardona G, Zhang L (2020) Counting and enumerating tree-child networks and their subclasses. J Comput Syst Sci 114:84–104. https://doi.org/10.1016/j.jcss.2020.06.001
Cardona G, Rossello F, Valiente G (2009) Comparison of tree-child phylogenetic networks. IEEE/ACM Trans Comput Biol Bioinf 6:552–569. https://doi.org/10.1109/TCBB.2007.70270
Cardona G, Pons JC, Scornavacca C (2019) Generation of binary tree-child phylogenetic networks. PLoS Comput Biol 15(9):e1007347. https://doi.org/10.1371/journal.pcbi.1007347
Erdős PL, Semple C, Steel M (2019) A class of phylogenetic networks reconstructable from ancestral profiles. Math Biosci 313:33–40. https://doi.org/10.1016/j.mbs.2019.04.009
Fuchs M, Gittenberger B, Mansouri M (2021) Counting phylogenetic networks with few reticulation vertices: exact enumeration and corrections. Australas J Comb 81(2):257–282
Fuchs M, Yu GR, Zhang L (2021) On the asymptotic growth of the number of tree-child networks. Eur J Comb 93:103278. https://doi.org/10.1016/j.ejc.2020.103278
van Iersel L, Janssen R, Jones M et al (2022) Orchard networks are trees with additional horizontal arcs. Bull Math Biol 84(8):76. https://doi.org/10.1007/s11538-022-01037-z
Janssen R, Liu P (2021) Comparing the topology of phylogenetic network generators. J Bioinform Comput Biol 19(06):2140012. https://doi.org/10.1142/S0219720021400126
Janssen R, Murakami Y (2021) On cherry-picking and network containment. Theor Comput Sci 856:121–150. https://doi.org/10.1016/j.tcs.2020.12.031
Kong S, Pons JC, Kubatko L et al (2022) Classes of explicit phylogenetic networks and their biological and mathematical significance. J Math Biol 84(6):47. https://doi.org/10.1007/s00285-022-01746-y
Pons JC, Scornavacca C, Cardona G (2019) Generation of level-\( k \) lgt networks. IEEE/ACM Trans Comput Biol Bioinf 17(1):158–164. https://doi.org/10.1109/TCBB.2019.2895344
Pons M, Batle J (2021) Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks. Sci Rep 11(1):21875. https://doi.org/10.1038/s41598-021-01166-w
Semple C, Simpson J (2018) When is a phylogenetic network simply an amalgamation of two trees? Bull Math Biol 80(9):2338–2348. https://doi.org/10.1007/s11538-018-0463-x
Steel M (2016) Phylogeny: discrete and random processes in evolution. SIAM, New Delhi
Willson SJ (2010) Properties of normal phylogenetic networks. Bull Math Biol 72:340–358. https://doi.org/10.1007/s11538-009-9449-z