On the subnet prune and regraft distance

zbMATH Open1411.05249arXiv1805.07839MaRDI QIDQ1740360FDOQ1740360

Authors: Jonathan Klawitter, Simone Linz 

Publication date: 30 April 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 $T$ and a phylogenetic network $N$, we show how this distance can be computed by considering the set of trees that are embedded in $N$ and then use this result to characterise the SNPR-distance between $T$ and $N$ in terms of agreement forests. Furthermore, we analyse properties of shortest SNPR-sequences between two phylogenetic networks $N$ and $N^{\prime }$, 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.

Full work available at URL: https://arxiv.org/abs/1805.07839

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

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

zbMATH Keywords

phylogenetic networkreticulationfixed-parameter tractable problemsearch operationSNPR-distance

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Efficiently inferring pairwise subtree prune-and-regraft adjacencies between phylogenetic trees
• On the computational complexity of the rooted subtree prune and regraft distance
• Subtree transfer operations and their induced metrics on evolutionary trees
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations
• Transforming phylogenetic networks: moving beyond tree space
• 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
• Bounds for phylogenetic network space metrics
• Exploring the tiers of rooted phylogenetic network space using tail moves
• Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks
• The SNPR neighbourhood of tree-child networks

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)