Tree Rearrangement Graphs Admit Paths of Decreasing Robinson-Foulds Distance
Bulletin of Mathematical Biology · 2026
DOI: 10.1007/s11538-026-01748-7 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bulletin of Mathematical Biology, 2026. Verfasst von Lena Collienne und 1 weiteren Autor:innen. Beteiligte Einrichtung: School of Computing, University of Otago, Dunedin, Otago, New Zealand. lena@lenacoll.de. Hauptthemen laut MEDLINE: Phylogeny, Models, Genetic. Die Arbeit nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NIAID NIH HHS, NIH HHS, National Science Foundation.
Abstract (Originalsprache)
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.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- School of Computing, University of Otago, Dunedin, Otago, New Zealand. lena@lenacoll.de.
- Computational Biology Program, Fred Hutchinson Cancer Research Center, Seattle, WA, USA. lena@lenacoll.de.
- Computational Biology Program, Fred Hutchinson Cancer Research Center, Seattle, WA, USA.
- Howard Hughes Medical Institute, Fred Hutchinson Cancer Research Center, Seattle, WA, USA.
- Department of Statistics, University of Washington, Seattle, WA, USA.
- Department of Genome Sciences, University of Washington, Seattle, WA, USA.
Förderung
- NIAID NIH HHS
- NIH HHS
- National Science Foundation
- National Institutes of Health
- Howard Hughes Medical Institute
Zitieren
APA
Collienne, L., & Matsen Iv, F. A. (2026). Tree Rearrangement Graphs Admit Paths of Decreasing Robinson-Foulds Distance. Bulletin of Mathematical Biology. https://doi.org/10.1007/s11538-026-01748-7
Vancouver
Collienne L, Matsen Iv FA. Tree Rearrangement Graphs Admit Paths of Decreasing Robinson-Foulds Distance. Bulletin of Mathematical Biology. 2026. doi:10.1007/s11538-026-01748-7
BibTeX
@article{Collienne2026,
author = {Collienne, Lena and Matsen Iv, Frederick A},
title = {Tree Rearrangement Graphs Admit Paths of Decreasing Robinson-Foulds Distance},
journal = {Bulletin of Mathematical Biology},
year = {2026},
doi = {10.1007/s11538-026-01748-7}
}
EUVIMED