TBR adjacency implies BME adjacency

About 16 years old · traced to

Let Tn\mathcal{T}_n be the space of trees on nn leaves. For T,T′∈TnT,T'\in\mathcal{T}_n, let dTBR(T,T′)d_{TBR}(T,T') denote the minimum number of tree-bisection-regrafting moves needed to transform TT to T′T'. Let dBME(T,T′)=1d_{BME}(T,T')=1 when the corresponding vertices wT\mathbf{w}^T and wT′\mathbf{w}^{T'} are joined by an edge in the balanced minimum evolution polytope Pn\mathcal{P}_n. TBR adjacency conjecture. If T,T′∈TnT,T'\in\mathcal{T}_n, then

dTBR(T,T′)=1d_{TBR}(T,T')=1

implies

dBME(T,T′)=1.d_{BME}(T,T')=1.

Nearest-neighbor interchange adjacency implies subtree-prune-regraft adjacency, and subtree-prune-regraft adjacency is known to imply BME adjacency. The paper reports no examples showing that TBR adjacency fails to imply BME adjacency, so the conjecture remains open.

References

Primary source

David C. Haws, Terrell Hodge and Ruriko Yoshida, “Optimality of the Neighbor Joining Algorithm and Faces of the Balanced Minimum Evolution Polytope”, arXiv:1004.2073 (2011).

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.