Tree Rearrangement Graphs Admit Paths of Decreasing Robinson-Foulds Distance.

Authors

Lena Collienne, Frederick A Matsen Iv

Published in

Bulletin of mathematical biology. Volume 88. Issue 11. Oct 09, 2026. Epub Oct 09, 2026.

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 and 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 show that a strictly decreasing NNI path does not always exist.

PMID:
42853487
Bibliographic data and abstract were imported from PubMed on 10 Oct 2026.

Read full publication at:
Please sign in to see all details.

Stats

1-terrible, 9-excellent. How would you rate this publication? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.