An evolution strategy approach for the balanced minimum evolution problem

Abstract

Motivation: The Balanced Minimum Evolution (BME) is a powerful distance based phylogenetic estimation model introduced by Desper and Gascuel and nowadays implemented in popular tools for phylogenetic analyses. It was proven to be computationally less demanding than more sophisticated estimation methods, e.g. maximum likelihood or Bayesian inference while preserving the statistical consistency and the ability to run with almost any kind of data for which a dissimilarity measure is available. BME can be stated in terms of a nonlinear non-convex combinatorial optimization problem, usually referred to as the Balanced Minimum Evolution Problem (BMEP). Currently, the state-of-the-art among approximate methods for the BMEP is represented by FastME (version 2.0), a software which implements several deterministic phylogenetic construction heuristics combined with a local search on specific neighbourhoods derived by classical topological tree rearrangements. These combinations, however, may not guarantee convergence to close-to-optimal solutions to the problem due to the lack of solution space exploration, a phenomenon which is exacerbated when tackling molecular datasets characterized by a large number of taxa.

Results: To overcome such convergence issues, in this article, we propose a novel metaheuristic, named PhyloES, which exploits the combination of an exploration phase based on Evolution Strategies, a special type of evolutionary algorithm, with a refinement phase based on two local search algorithms. Extensive computational experiments show that PhyloES consistently outperforms FastME, especially when tackling larger datasets, providing solutions characterized by a shorter tree length but also significantly different from the topological perspective.

Availability and implementation: The software and the data are available at https://github.com/andygaspar/PHYLOES.

Figure 1.

(Left) Representation of an NNI move. When edge e is selected, two new trees are created by swapping subtrees A–D and A–C, respectively. (Right) Representation of an SPR move. When edge e is selected, the corresponding subtree is pruned from the initial phylogeny and then regrafted onto edge $e^{\prime }$.

Figure 2.

Two examples of tree encoding. (Top) The ordered edge list at the initial step is $E=\{(t_1,i_6),(t_2,i_6),(t_3,i_6)\}$. The edge selected for the insertion of $t_4$ is $(t_3,i_6)$, which is the 3-rd in the list. At the next step E becomes $\{(t_1,i_6),(t_2,i_6),(t_3,i_7),(t_4,i_7),(i_6,i_7)\}$; $t_5$ is then inserted in the edge $t_5$ is $(i_6,i_7)$, 5-th in the list, so the resulting code is $T_1=(3,5)$. (Bottom) The initial edge list is $E=\{(t_1,i_6),(t_2,i_6),(t_3,i_6)\}$. $t_4$ is inserted in $(t_1,i_6)$, 1-st in the list. At the next step E becomes $\{(t_1,i_7),(t_2,i_6),(t_3,i_6),(t_4,i_7),(i_6,i_7)\}$; the edge selected is $(t_3,i_6)$, 3-rd in the list, providing the resulting code is $T_2=(1,3)$

Figure 3.

Number of BNNI (red line) and BSPR (blue line) iterations per generation in PhyloES.