Tree rearrangement graphs admit paths of decreasing Robinson-Foulds distance
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909975770562560 |
|---|---|
| author | Collienne, Lena Matsen IV, Frederick A |
| author_facet | Collienne, Lena Matsen IV, Frederick A |
| contents | Tree rearrangements such as Nearest Neighbor Interchange (NNI) and Subtree Prune and Regraft (SPR) are commonly used to explore phylogenetic treespace. Computing distances based on them, however, is often intractable, so the efficiently computable Robinson-Foulds (RF) distance is used in practice. We investigate how the RF distance behaves along paths in the NNI and SPR graphs, where trees are nodes, edges represent single rearrangements. We show that any two trees are connected by a path along which the RF distance to the target decreases monotonically in the NNI graph and strictly in the SPR graph; we also exhibit trees for which no strictly decreasing NNI path exists. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21397 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tree rearrangement graphs admit paths of decreasing Robinson-Foulds distance Collienne, Lena Matsen IV, Frederick A Populations and Evolution Tree rearrangements such as Nearest Neighbor Interchange (NNI) and Subtree Prune and Regraft (SPR) are commonly used to explore phylogenetic treespace. Computing distances based on them, however, is often intractable, so the efficiently computable Robinson-Foulds (RF) distance is used in practice. We investigate how the RF distance behaves along paths in the NNI and SPR graphs, where trees are nodes, edges represent single rearrangements. We show that any two trees are connected by a path along which the RF distance to the target decreases monotonically in the NNI graph and strictly in the SPR graph; we also exhibit trees for which no strictly decreasing NNI path exists. |
| title | Tree rearrangement graphs admit paths of decreasing Robinson-Foulds distance |
| topic | Populations and Evolution |
| url | https://arxiv.org/abs/2512.21397 |