Bounding the SNPR distance between two tree-child networks using generalised agreement forests
The electronic journal of combinatorics, Tome 32 (2025) no. 3
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.
@article{10_37236_13976,
author = {Steven Kelk and Simone Linz and Charles Semple},
title = {Bounding the {SNPR} distance between two tree-child networks using generalised agreement forests},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {3},
doi = {10.37236/13976},
zbl = {8097674},
url = {http://geodesic.mathdoc.fr/articles/10.37236/13976/}
}
TY - JOUR AU - Steven Kelk AU - Simone Linz AU - Charles Semple TI - Bounding the SNPR distance between two tree-child networks using generalised agreement forests JO - The electronic journal of combinatorics PY - 2025 VL - 32 IS - 3 UR - http://geodesic.mathdoc.fr/articles/10.37236/13976/ DO - 10.37236/13976 ID - 10_37236_13976 ER -
%0 Journal Article %A Steven Kelk %A Simone Linz %A Charles Semple %T Bounding the SNPR distance between two tree-child networks using generalised agreement forests %J The electronic journal of combinatorics %D 2025 %V 32 %N 3 %U http://geodesic.mathdoc.fr/articles/10.37236/13976/ %R 10.37236/13976 %F 10_37236_13976
Steven Kelk; Simone Linz; Charles Semple. Bounding the SNPR distance between two tree-child networks using generalised agreement forests. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/13976
Cité par Sources :