Improved Solutions for the Balanced Minimum Evolution Problem

The minimum evolution criterion is one of the most important criteria of molecular phylogenetic estimation. It states that the phylogeny of a given set of molecular data (taxa) is the one whose sum of edge weights is minimal. Finding the phylogeny that satisfies the minimum evolution criterion involves solving an optimization problem, called the Minimum Evolution Problem (MEP), whose versions are generally N P-Hard. The most recent version of MEP is the Balanced Minimum Evolution problem (BME), which is based on Pauplin’s edge weight estimation model [16]. In [1] we presented an algorithm for solving BME based on non-isomorphic enumeration of the phylogenies relative to a given set of taxa. The computational analysis reported in [2] shown the quality of the solution provided using a short amount of computing time. Furthermore, it highlighted that a Local Search can improve the solution quality and the need of increasing the dimension of the instance solved by a a parallel approach. The focus of this paper is therefore to report about the extension of our algorithm in order to include a Local Search method and the results obtained by a parallel version of the whole algorithm.