The SPR-neighbor OLA distance bound for phylogenetic trees
The SPR-neighbor OLA distance bound for phylogenetic trees
Let be a fixed phylogenetic tree, and let be a random tree differing from by a single subtree-prune-and-regraft (SPR) move, chosen uniformly. Write for the number of edges from the root to the farthest leaf, and let denote the ordered leaf attachment (OLA) distance. SPR-neighbor OLA distance conjecture. The expectation satisfies the asymptotic upper bound
The conjecture is supported by a computational experiment sampling SPR neighbors; the paper also describes a heuristic suggesting a bound by times the tree height. The source does not state that the conjecture has been resolved.
Sources & referencesView supporting material
Primary source
Harry Richman, Cheng Zhang and Frederick A. Matsen, “Vector encoding of phylogenetic trees by ordered leaf attachment”, arXiv:2503.10169 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.