Abstract: Phylogenetic networks are rooted directed acyclic graphs that represent evolutionary relationships between species whose past includes reticulation events such as hybridisation and horizontal gene transfer. To search the space of phylogenetic networks, the popular tree rearrangement operation rooted subtree prune and regraft (rSPR) was recently generalised to phylogenetic networks. This new operation - called subnet prune and regraft (SNPR) - induces a metric on the space of all phylogenetic networks as well as on several widely-used network classes. In this paper, we investigate several problems that arise in the context of computing the SNPR-distance. For a phylogenetic tree and a phylogenetic network , we show how this distance can be computed by considering the set of trees that are embedded in and then use this result to characterise the SNPR-distance between and in terms of agreement forests. Furthermore, we analyse properties of shortest SNPR-sequences between two phylogenetic networks and , and answer the question whether or not any of the classes of tree-child, reticulation-visible, or tree-based networks isometrically embeds into the class of all phylogenetic networks under SNPR.
Recommendations
- Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks
- The SNPR neighbourhood of tree-child networks
- The agreement distance of rooted phylogenetic networks
- Rearrangement operations on unrooted phylogenetic networks
- The agreement distance of unrooted phylogenetic networks
Cites work
- Bounds for phylogenetic network space metrics
- Efficiently inferring pairwise subtree prune-and-regraft adjacencies between phylogenetic trees
- Exploring the tiers of rooted phylogenetic network space using tail moves
- Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
- Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks
- On the computational complexity of the rooted subtree prune and regraft distance
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- ReCombinatorics. The algorithmics of ancestral recombination graphs and explicit phylogenetic networks. With contributions from Charles H. Langley, Yun S. Song and Yufeng Wu
- Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations
- Subtree transfer operations and their induced metrics on evolutionary trees
- The SNPR neighbourhood of tree-child networks
- Transforming phylogenetic networks: moving beyond tree space
Cited in
(7)- Heading in the right direction? Using head moves to traverse phylogenetic network space
- The agreement distance of rooted phylogenetic networks
- Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks
- On the combinatorics of rooted binary phylogenetic trees
- Rearrangement operations on unrooted phylogenetic networks
- The SNPR neighbourhood of tree-child networks
- The agreement distance of unrooted phylogenetic networks
This page was built for publication: On the subnet prune and regraft distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1740360)
