×

Reconstructing tree-child networks from reticulate-edge-deleted subnetworks. (English) Zbl 1428.92080

This article shows that tree-child networks of level \(k\), where \(k \geq 2\), are determined by their MLLS. A polynomial time algorithm for recovering such a network from their MLLS is derived. In this case, one of the properties of daughter trees was used – the lowest node of the tree is in a cherry or net cherry. The obvious obstacle to this method is that there are no guarantees or reasons for obtaining a set of all MLLS of the source network. Converting sequence data to MLLS can be quite complex, especially for a higher level. To make the results practical, one can use similar approaches, for example, these are methods that work with subnets of only three leaves. However, it is not necessary to know all the MLLS to restore the original network: only three are needed. A possible application of this approach may be as follows. Assume that in different studies they created networks with some patterns. However, in each of these networks some actual mesh events were skipped, possibly due to computational limitations or lack of data. A method based on the theoretical results of this work can be used to reconstruct the entire network from networks with missing events. There is also the prospect of expanding MLLS reconstruction results for a more general class of networks. Since the authors’ ultimate goal was to determine the reconstruction of networks from their MLLS, this can be done by analysis of a similar pair of leaves, but the authors obtained results for a large number of cases, with level 2 networks containing 15 possible forms. Accounting for level \(k\) generators can provide an interesting approach to this problem.

MSC:

92D15 Problems related to evolution
05C90 Applications of graph theory

Software:

TriLoNet

References:

[1] Bordewich M, Semple C (2016) Determining phylogenetic networks from inter-taxa distances. J Math Biol 73(2):283-303 · Zbl 1343.05147 · doi:10.1007/s00285-015-0950-8
[2] Bordewich M, Semple C, Tokac N (2018a) Constructing tree-child networks from distance matrices. Algorithmica 80(8):2240-2259. https://doi.org/10.1007/s00453-017-0320-6 · Zbl 1391.92028 · doi:10.1007/s00453-017-0320-6
[3] Bordewich M, Huber KT, Moulton V, Semple C (2018b) Recovering normal networks from shortest inter-taxa distance information. J Math Biol 77:1-24 · Zbl 1406.05098 · doi:10.1007/s00285-018-1218-x
[4] Cardona G, Rossello F, Valiente G (2009) Comparison of tree-child phylogenetic networks. IEEE/ACM Trans Comput Biol Bioinform 6(4):552-569 · doi:10.1109/TCBB.2007.70270
[5] Gambette P, Huber KT, Kelk S (2017) On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters. J Math Biol 74(7):1729-1751 · Zbl 1366.92087 · doi:10.1007/s00285-016-1068-3
[6] Gusfield D, Bansal V (2005) A fundamental decomposition theory for phylogenetic networks and incompatible characters. In: Annual international conference on research in computational molecular biology. Springer, pp 217-232 · Zbl 1119.92352
[7] Hein J (1990) Reconstructing evolution of sequences subject to recombination using parsimony. Math Biosci 98(2):185-200 · Zbl 0692.92014 · doi:10.1016/0025-5564(90)90123-G
[8] Huber KT, Moulton V (2013) Encoding and constructing 1-nested phylogenetic networks with trinets. Algorithmica 66(3):714-738 · Zbl 1267.05240 · doi:10.1007/s00453-012-9659-x
[9] Huber KT, van Iersel L, Moulton V, Wu T (2014) How much information is needed to infer reticulate evolutionary histories? Syst Biol 64(1):102-111 · doi:10.1093/sysbio/syu076
[10] Huson DH, Rupp R, Scornavacca C (2010) Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press, Cambridge · doi:10.1017/CBO9780511974076
[11] Huynh TN, Jansson J, Nguyen NB, Sung WK (2005) Constructing a smallest refining galled phylogenetic network. In: Annual international conference on research in computational molecular biology. Springer, pp 265-280 · Zbl 1119.92354
[12] Jansson J, Sung WK (2006) Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Theor Comput Sci 363(1):60-68 · Zbl 1110.68032 · doi:10.1016/j.tcs.2006.06.022
[13] Jin G, Nakhleh L, Snir S, Tuller T (2006) Maximum likelihood of phylogenetic networks. Bioinformatics 22(21):2604-2611 · doi:10.1093/bioinformatics/btl452
[14] Morrison DA (2005) Networks in phylogenetic analysis: new tools for population biology. Int J Parasitol 35(5):567-582 · doi:10.1016/j.ijpara.2005.02.007
[15] Nakhleh L, Warnow T, Linder CR, John KS (2005) Reconstructing reticulate evolution in species—theory and practice. J Comput Biol 12(6):796-811 · doi:10.1089/cmb.2005.12.796
[16] Oldman J, Wu T, van Iersel L, Moulton V (2016) Trilonet: piecing together small networks to reconstruct reticulate evolutionary histories. Mol Biol Evol 33(8):2151-2162 · doi:10.1093/molbev/msw068
[17] Pardi F, Scornavacca C (2015) Reconstructible phylogenetic networks: do not distinguish the indistinguishable. PLoS Comput Biol 11(4):e1004135 · doi:10.1371/journal.pcbi.1004135
[18] Sneath PH (1975) Cladistic representation of reticulate evolution. Syst Zool 24(3):360-368 · doi:10.2307/2412721
[19] Strimmer K, Moulton V (2000) Likelihood analysis of phylogenetic networks using directed graphical models. Mol Biol Evol 17(6):875-881 · doi:10.1093/oxfordjournals.molbev.a026367
[20] van Iersel L, Moulton V (2014) Trinets encode tree-child and level-2 phylogenetic networks. J Math Biol 68(7):1707-1729 · Zbl 1339.92008
[21] van Iersel L, Keijsper J, Kelk S, Stougie L, Hagen F, Boekhout T (2009) Constructing level-2 phylogenetic networks from triplets. IEEE/ACM Trans Comput Biol Bioinform 6(4):667-681 · doi:10.1109/TCBB.2009.22
[22] van Iersel L, Moulton V, de Swart E, Wu T (2017) Binets: fundamental building blocks for phylogenetic networks. Bull Math Biol 79(5):1135-1154 · Zbl 1368.92127 · doi:10.1007/s11538-017-0275-4
[23] von Haeseler A, Churchill GA (1993) Network models for sequence evolution. J Mol Evol 37(1):77-85 · doi:10.1007/BF00170465
[24] Willson SJ (2010) Properties of normal phylogenetic networks. Bull Math Biol 72(2):340-358 · Zbl 1185.92085 · doi:10.1007/s11538-009-9449-z
[25] Willson SJ (2011) Regular networks can be uniquely constructed from their trees. IEEE/ACM Trans Comput Biol Bioinform 8(3):785-796 · doi:10.1109/TCBB.2010.69
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.