Tree rearrangement graphs admit paths of decreasing Robinson-Foulds distance

2025/12/24 by Lena Collienne, Collienne, Lena, Frederick A Matsen IV +1
Biochemistry, Genetics and Molecular Biology · #Bioinformatics and Genomic Networks #FOS: Biological sciences #Genome Rearrangement Algorithms #Genomics and Phylogenetic Studies #Populations and Evolution (q-bio.PE)

paper · doi:10.48550/arxiv.2512.21397

openalex publication_date 2025/12/24 · openalex created_date 2025/12/30 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• On the importance of assessing topological convergence in Bayesian phylogenetic inference
• Calculating the Unrooted Subtree Prune-and-Regraft Distance
• The generalized Robinson-Foulds metric
• Comparison of phylogenetic trees

Related

• Computing nearest neighbour interchange distances between ranked phylogenetic trees
• Chain Reduction Preserves the Unrooted Subtree Prune-and-Regraft Distance
• A rearrangement distance for fully-labelled trees
• On the neighbourhoods of trees
• On Two Measures of Distance between Fully-Labelled Trees