×

Rooted NNI moves and distance-1 tail moves on tree-based phylogenetic networks. (English) Zbl 1460.92140

This article proves that the spaces of rooted network networks are connected with respect to the movements of the nearest neighbor (rooted nearest neighbor interchange, rNNI). This is the root analogue of the result showing the connectivity of non-root tree-like network spaces as NNI moves. The non-root result does not naturally extend to the root case, because directionality on the edges in the root case imposes significant additional restrictions on both rNNI displacements and the networks themselves. A similar result has been proven for root phylogenetic networks that allow parallel edges, but the paper shows that the spaces are connected by the introduced tail motions by a distance-1. In addition, the upper boundaries of the diameter of the space of phylogenetic networks based on trees were determined for these two displacements. Previously, similar results were obtained, but the additional limitation of staying within the level of tree networks is a key challenge of this study.

MSC:

92D15 Problems related to evolution
92C42 Systems biology, networks
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bai, A.; Erdős, P. L.; Semple, C.; Steel, M., Defining phylogenetic networks using ancestral profiles (2020), http://arxiv.org/abs/2012.00109 [math]
[2] Doolittle, W., Phylogenetic classification and the universal tree, Science, 284, 5423, 2124-2128 (1999)
[3] Erdős, P. L.; Semple, C.; Steel, M., A class of phylogenetic networks reconstructable from ancestral profiles, Math. Biosci., 313, 33-40 (2019) · Zbl 1421.05085
[4] Fischer, M.; Francis, A., How tree-based is my network? Proximity measures for unrooted phylogenetic networks, Discrete Appl. Math., 283, 98-114 (2020) · Zbl 1444.92071
[5] Fischer, M.; Francis, A., The space of tree-based phylogenetic networks, Bull. Math. Biol., vol 82, 70 (2020) · Zbl 1444.92070
[6] Francis, A.; Semple, C.; Steel, M., New characterisations of tree-based networks and proximity measures, Adv. Appl. Math., 93, 93-107 (2018) · Zbl 1372.05034
[7] Francis, A. R.; Steel, M., Which phylogenetic networks are merely trees with additional arcs?, Syst. Biol., 64, 5, 768-777 (2015)
[8] Gambette, P.; van Iersel, L.; Jones, M.; Lafond, M.; Pardi, F.; Scornavacca, C., Rearrangement moves on rooted phylogenetic networks, PLoS Comput. Biol., 13, 8, 1-21 (2017)
[9] Huber, K. T.; Moulton, V.; Wu, T., Transforming phylogenetic networks: Moving beyond tree space, J. Theoret. Biol., 404, 30-39 (2016) · Zbl 1343.92348
[10] Huson, D. H.; Rupp, R.; Scornavacca, C., Phylogenetic networks: concepts, algorithms and applications (2010), Cambridge University Press
[11] van Iersel, L.; Janssen, R.; Jones, M.; Murakami, Y.; Zeh, N., A unifying characterization of tree-based networks and orchard networks using cherry covers (2020)
[12] Janssen, R., Heading in the right direction? Using head moves to traverse phylogenetic network space (2018), http://arxiv.org/abs/1810.09795 [math, q-bio]
[13] Janssen, R.; Jones, M.; Erdős, P. L.; van Iersel, L.; Scornavacca, C., Exploring the tiers of rooted phylogenetic network space using tail moves, Bull. Math. Biol., 80, 8, 2177-2208 (2018) · Zbl 1398.92176
[14] Janssen, R.; Klawitter, J., Rearrangement operations on unrooted phylogenetic networks, Theory Appl. Graphs, 6, 2 (2019) · Zbl 1432.05101
[15] Janssen, R.; Murakami, Y., On cherry-picking and network containment (2020), http://arxiv.org/abs/1812.08065 [math] · Zbl 1478.92134
[16] Jetten, L.; van Iersel, L., Nonbinary tree-based phylogenetic networks, IEEE/ACM Trans. Comput. Biol. Bioinform. (2016)
[17] Klawitter, J., Spaces of Phylogenetic Networks (2020), University of Auckland, (PhD thesis)
[18] Koonin, E. V., The turbulent network dynamics of microbial evolution and the statistical tree of life, J. Mol. Evol., 80, 5-6, 244-250 (2015)
[19] Li, M.; Tromp, J.; Zhang, L., On the nearest neighbour interchange distance between evolutionary trees, 182, 4, 463-467 (1996)
[20] Robinson, D. F., Comparison of labeled trees with valency three, J. Combin. Theory Ser. B, 11, 2, 105-119 (1971)
[21] Semple, C., Phylogenetic networks with every embedded phylogenetic tree a base tree, Bull. Math. Biol., 78, 1, 132-137 (2016) · Zbl 1356.92067
[22] Steel, M., Phylogeny: Discrete And Random Processes in Evolution (2016), SIAM · Zbl 1361.92001
[23] Yu, Y.; Dong, J.; Liu, K. J.; Nakhleh, L., Maximum likelihood inference of reticulate evolutionary histories, Proc. Natl. Acad. Sci., 111, 46, 16448-16453 (2014)
[24] Zhang, L., On tree-based phylogenetic networks, J. Comput. Biol., 23, 7, 553-565 (2016)
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.