EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Tree Rearrangement Graphs Admit Paths of Decreasing Robinson-Foulds Distance

Lena Collienne, Frederick A Matsen Iv

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

PhylogenyModels, GeneticMathematical ConceptsComputer SimulationComputational BiologyAlgorithms

Stichwörter der Autor:innen

PhylogeneticsTree distancesTree rearrangementsTreespace

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}
}
Kostenlos starten →