The Balanced Minimum Evolution Problem
(2011) INFORMS Journal on Computing — Vol. 24, n° 2, p. 187-341 (2011)
Files
7e3db8c825c6480341e2a9ef7dd508cdbbc2.pdf
Open Access - Adobe PDF
- 513.86 KB
Details
- Authors
- Abstract
- 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 Balanced Minimum Evolution Problem (BMEP). We present a mixed integer linear programming model 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.
- Affiliations
ULB Computer Science Department
Citations
Catanzaro, D., Labbé, M., Pesenti, R., & Salazar-González, J.-J. (2011). The Balanced Minimum Evolution Problem. INFORMS Journal on Computing, 24(2), 187-341. https://doi.org/10.1287/ijoc.1110.0455 (Original work published 2011)