Rearrangement operations on unrooted phylogenetic networks

DOI10.20429/TAG.2019.060206MaRDI QIDQ5213545zbMATH OpenOpenAlexFDO

Authors Remie Janssen, Jonathan Klawitter

Publication date 3 February 2020

Published in Theory and Applications of Graphs (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

phylogenetic treePR-distanceTBR-distance

Mathematics Subject Classification ID

Trees (05C05) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: Rearrangement operations transform a phylogenetic tree into another one and hence induce a metric on the space of phylogenetic trees. Popular operations for unrooted phylogenetic trees are NNI (nearest neighbour interchange), SPR (subtree prune and regraft), and TBR (tree bisection and reconnection). Recently, these operations have been extended to unrooted phylogenetic networks, which are generalisations of phylogenetic trees that can model reticulated evolutionary relationships. Here, we study global and local properties of spaces of phylogenetic networks under these three operations. In particular, we prove connectedness and asymptotic bounds on the diameters of spaces of different classes of phylogenetic networks, including tree-based and level-k networks. We also examine the behaviour of shortest TBR-sequence between two phylogenetic networks in a class, and whether the TBR-distance changes if intermediate networks from other classes are allowed: for example, the space of phylogenetic trees is an isometric subgraph of the space of phylogenetic networks under TBR. Lastly, we show that computing the TBR-distance and the PR-distance of two phylogenetic networks is NP-hard.

Recommendations

• The agreement distance of unrooted phylogenetic networks
• On the subnet prune and regraft distance
• Exploring the tiers of rooted phylogenetic network space using tail moves
• Transforming phylogenetic networks: moving beyond tree space
• Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks

Cited in

(17)

• On the subnet prune and regraft distance
• Bounds for phylogenetic network space metrics
• Exploring the tiers of rooted phylogenetic network space using tail moves
• Walks in phylogenetic treespace
• The space of tree-based phylogenetic networks
• Closure operations in phylogenetics
• Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks
• Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations
• Rooted NNI moves and distance-1 tail moves on tree-based phylogenetic networks
• Transforming phylogenetic networks: moving beyond tree space
• The agreement distance of unrooted phylogenetic networks
• The SNPR neighbourhood of tree-child networks
• Heading in the right direction? Using head moves to traverse phylogenetic network space
• Subtree transfer operations and their induced metrics on evolutionary trees
• Exploring spaces of semi-directed level-1 networks
• Bounding the SNPR distance between two tree-child networks using generalised agreement forests
• Computing nearest neighbour interchange distances between ranked phylogenetic trees

This page was built for publication: Rearrangement operations on unrooted phylogenetic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5213545)