The SPR-neighbor OLA distance bound for phylogenetic trees

Let TRBT^nT\in\widehat{\mathcal{RBT}}_n be a fixed phylogenetic tree, and let TT' be a random tree differing from TT by a single subtree-prune-and-regraft (SPR) move, chosen uniformly. Write ht(T)\operatorname{ht}(T) for the number of edges from the root to the farthest leaf, and let dOLAd_{\operatorname{OLA}} denote the ordered leaf attachment (OLA) distance. SPR-neighbor OLA distance conjecture. The expectation satisfies the asymptotic upper bound

E(dOLA(T,T))=O(ht(T)).\mathbb E\bigl(d_{\operatorname{OLA}}(T,T')\bigr)=O\bigl(\operatorname{ht}(T)\bigr).

The conjecture is supported by a computational experiment sampling SPR neighbors; the paper also describes a heuristic suggesting a bound by 88 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

Never refreshed

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.