Bounding the SNPR Distance Between Two Tree-Child Networks Using Generalised Agreement Forests
Open Access
- 4 July 2025
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (3) , P3.46
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 33 references indexed in Scilit:
- Exploring spaces of semi-directed level-1 networksJournal of Mathematical Biology, 2023
- Classes of explicit phylogenetic networks and their biological and mathematical significanceJournal of Mathematical Biology, 2022
- 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
- New Reduction Rules for the Tree Bisection and Reconnection DistanceAnnals of Combinatorics, 2020
- Extremal Distances for Subtree Transfer Operations in Binary TreesAnnals of Combinatorics, 2018
- Bounds for phylogenetic network space metricsJournal of Mathematical Biology, 2017
- 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