A Compact Weight-Space Integer Programming Formulation for Balanced Minimum Evolution

Abstract

Balanced Minimum Evolution (BME) reconstructs an unrooted binary phylogenetic tree from a distance matrix $D$ by minimizing the length ${\sum }_{i<j}{D}_{ij}{w}_{ij}$, which is linear in the weights $w_{ij}=2^{-d_{T}ij}$. We study the formulation of BME in these $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ weight variables. Theoretical results. (i) For a fixed topology $T$, the Kraft equalities, the cut equalities $\{W[S]=\frac{1}{2}\}$ of $T$, and the single convex constraint $\sum w_{ij}{\log }_2{w}_{ij}\le \frac{3}{2}-n$ admit exactly one point, the tree's weight vector. (ii) For every tree and every bipartition, the cut value $W_T[S]$ lies in $\{\frac{1}{2}\}\cup \{\frac{3}{4}\}\cup [\frac{7}{8},\infty )$; the value $\frac{3}{4}$ is attained exactly by the $2(n-3)$ bipartitions created by one nearest-neighbour interchange; and the number of bipartitions with $W_T[S]\le 1$ is $2n^2-10n+15$ for every binary topology. (iii) The crossing graph of nontrivial bipartitions has an edge clique cover with $O(n^4)$ cliques, and every edge clique cover needs $\Omega (n^2)$. (iv) The necessary conditions of Catanzaro et al. for a path-length matrix, without the four-point condition, are sufficient for $n\le 11$ and first fail at $n=12$. Computational results. A compact branch-and-bound solver built on these results, which commits and forbids splits and imposes the convex constraint exactly, certifies optimality on benchmark instances with up to $n=20$ taxa within an hour. It is faster than the distance-indexed model of Catanzaro et al. on two of these instances and slower on the others; that model, whose root bound is tighter, certifies 13 of 14 benchmark instances with $n\le 30$ within an hour in every seed. Although the compact solver does not improve on the computational state of the art overall, we explain why, and we discuss the open problems that our results raise.

arXiv comment44 pages, 1 figure