Exploring the Tiers of Rooted Phylogenetic Network Space Using Tail Moves
Open Access
- 14 June 2018
- journal article
- research article
- Published by Springer Nature in Bulletin of Mathematical Biology
- Vol. 80 (8) , 2177-2208
Abstract
Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rooted Nearest Neighbour Interchange (rNNI) and rooted Subtree Prune and Regraft (rSPR). Recently, these moves were generalized to rooted phylogenetic networks, which are a more suitable representation of reticulate evolutionary histories, and it was shown that any two rooted phylogenetic networks of the same complexity are connected by a sequence of either rSPR or rNNI moves. Here, we show that this is possible using only tail moves, which are a restricted version of rSPR moves on networks that are more closely related to rSPR moves on trees. The connectedness still holds even when we restrict to distance-1 tail moves (a localized version of tail moves). Moreover, we give bounds on the number of (distance-1) tail moves necessary to turn one network into another, which in turn yield new bounds for rSPR, rNNI and SPR (i.e. the equivalent of rSPR on unrooted networks). The upper bounds are constructive, meaning that we can actually find a sequence with at most this length for any pair of networks. Finally, we show that finding a shortest sequence of tail or rSPR moves is NP-hard.Keywords
All Related Versions
Funding Information
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (639.072.602)
- 4TU Applied Mathematics Institute
- Hungarian National Research, Development and Innovation Office (K 116769, SNN 116095)
- Agence Nationale de la Recherche Investissements d’Avenir/Bioinformatique (ANR-10-BINF-01-02)
This publication has 17 references indexed in Scilit:
- Transforming phylogenetic networks: Moving beyond tree spaceJournal of Theoretical Biology, 2016
- On the fixed parameter tractability of agreement-based phylogenetic distancesJournal of Mathematical Biology, 2016
- Contribution of recombination to the evolutionary history of HIVCurrent Opinion in HIV and AIDS, 2015
- Maximum likelihood inference of reticulate evolutionary historiesProceedings of the National Academy of Sciences, 2014
- Hybridization and speciationJournal of Evolutionary Biology, 2013
- On agreement forestsJournal of Combinatorial Theory, Series A, 2011
- Lateral gene transferCurrent Biology, 2011
- PhyloNet: a software package for analyzing and reconstructing reticulate evolutionary relationshipsBMC Bioinformatics, 2008
- On the Computational Complexity of the Rooted Subtree Prune and Regraft DistanceAnnals of Combinatorics, 2005
- On the Nearest Neighbour Interchange Distance Between Evolutionary TreesJournal of Theoretical Biology, 1996