The SPR-neighbor OLA distance bound for phylogenetic trees

About 1 year old · traced to

Let T∈RBT^nT\in\widehat{\mathcal{RBT}}_n be a fixed phylogenetic tree, and let T′T' 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 dOLA⁡d_{\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.

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

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.