Exploring the tiers of rooted phylogenetic network space using tail moves
From MaRDI portal
Publication:1786929
DOI10.1007/S11538-018-0452-0zbMATH Open1398.92176arXiv1708.07656OpenAlexW2963583717WikidataQ64963408 ScholiaQ64963408MaRDI QIDQ1786929FDOQ1786929
Authors: G. Richomme 
Publication date: 25 September 2018
Published in: Bulletin of Mathematical Biology (Search for Journal in Brave)
Abstract: Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rNNI (rooted Nearest Neighbour Interchange) and rSPR (rooted Subtree Prune and Regraft). 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.
Full work available at URL: https://arxiv.org/abs/1708.07656
Recommendations
- Rooted NNI moves and distance-1 tail moves on tree-based phylogenetic networks
- Rearrangement operations on unrooted phylogenetic networks
- Heading in the right direction? Using head moves to traverse phylogenetic network space
- Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations
- Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks
Cites Work
- On the computational complexity of the rooted subtree prune and regraft distance
- On agreement forests
- Transforming phylogenetic networks: moving beyond tree space
- Title not available (Why is that?)
- On the fixed parameter tractability of agreement-based phylogenetic distances
- Extremal distances for subtree transfer operations in binary trees
- Bounds for phylogenetic network space metrics
- Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks
Cited In (13)
- Heading in the right direction? Using head moves to traverse phylogenetic network space
- Orienting undirected phylogenetic networks
- On the subnet prune and regraft distance
- Exact upper bound on the sum of squared nearest-neighbor distances between points in a rectangle
- Rearrangement operations on unrooted phylogenetic networks
- Exploring spaces of semi-directed level-1 networks
- The space of equidistant phylogenetic cactuses
- Counting phylogenetic networks of level 1 and 2
- Rooted NNI moves and distance-1 tail moves on tree-based phylogenetic networks
- Treewidth of display graphs: bounds, brambles and applications
- The SNPR neighbourhood of tree-child networks
- On the existence of funneled orientations for classes of rooted phylogenetic networks
- The agreement distance of unrooted phylogenetic networks
Uses Software
This page was built for publication: Exploring the tiers of rooted phylogenetic network space using tail moves
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786929)
