The Balanced Minimum Evolution Problem

A phylogeny is an unrooted binary tree that represents the evolutionary relationships of a set of $n$ species. Phylogenies find applications in several scientific areas ranging from medical research, to drug discovery, to epidemiology, to systematics, and to population dynamics. In such applications the available information is usually restricted to the leaves of a phylogeny and is represented by molecular data extracted from the analyzed species, such as DNA, RNA, amino acid or codon fragments. On the contrary, the information about the phylogeny itself is generally missing and is determined by solving an optimization problem, called the Phylogeny Estimation Problem (PEP), whose versions depend on the criterion used to select a phylogeny from among plausible alternatives. In this article we investigate a recent version of the PEP, called the \emph{Balanced Minimum Evolution Problem} (BMEP). We present a mixed integer linear programming model\footnote{See the online supplement for codes and data.} to solve exactly instances of the BMEP and develop branching rules and families of valid inequalities to further strengthen the model. Our results give perspective on the mathematics of the BMEP and suggest new directions on the development of future efficient exact approaches to solution of the problem.