Bounding the SNPR distance between two tree-child networks using generalised agreement forests
Preprint
Abstract
Agreement forests continue to play a central role in the comparison of phylogenetic trees since their introduction more than 25 years ago. More specifically, they are used to characterise several distances that are based on tree rearrangement operations and related quantifiers of dissimilarity between phylogenetic trees. In addition, the concept of agreement forests continues to underlie most advancements in the development of algorithms that exactly compute the aforementioned measures. In this paper, we introduce agreement digraphs, a concept that generalises agreement forests for two phylogenetic trees to two phylogenetic networks. Analogous to the way in which agreement forests compute the subtree prune and regraft distance between two phylogenetic trees but inherently more complex, we then use agreement digraphs to bound the subnet prune and regraft distance between two tree-child networks from above and below and show that our bounds are tight.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- A duality based 2-approximation algorithm for maximum agreement forestMathematical Programming, 2022
- A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary TreesAlgorithmica, 2022
- Reflections on kernelizing and computing unrooted agreement forestsAnnals of Operations Research, 2021
- Rooted NNI moves and distance-1 tail moves on tree-based phylogenetic networksDiscrete Applied Mathematics, 2021
- Extremal Distances for Subtree Transfer Operations in Binary TreesAnnals of Combinatorics, 2018
- A parameterized algorithm for the Maximum Agreement Forest problem on multiple rooted multifurcating treesJournal of Computer and System Sciences, 2018
- Exploring the Tiers of Rooted Phylogenetic Network Space Using Tail MovesBulletin of Mathematical Biology, 2018
- Bounding the Number of Hybridisation Events for a Consistent Evolutionary HistoryJournal of Mathematical Biology, 2005
- On the Computational Complexity of the Rooted Subtree Prune and Regraft DistanceAnnals of Combinatorics, 2005
- Subtree Transfer Operations and Their Induced Metrics on Evolutionary TreesAnnals of Combinatorics, 2001