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.
References
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
No solutions have been posted yet.