Molecular phylogenetics provides several criteria to select a phylogeny among plausible alternative ones. Usually, such criteria can be expressed in terms of objective functions, and the phylogenies optimizing them are referred as optimal. One of the most important criteria is Minimum Evolution (ME) which states that the optimal phylogeny for a given set of organisms is the one whose sum of the edge weights is minimal. Finding the phylogeny satisfying the minimum evolution criterion involves the solution of an optimization problem, called Minimum Evolution Problem (MEP), notoriously NP-Hard. Herewith, we introduce a number of mixed integer programming models and provide possible cuts and lower bounds for the optimal value.
view more