PHYLOES Un approccio mediante Strategie Evolutive per l'inferenza filogenetica basata sul Balanced Minimum Evolution Criterion

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 optimisation 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 characterised by a large number of taxa. To overcome such convergence issues, in this work 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 characterised by a shorter tree length but also significantly different from the topological perspective. ​

Il Balanced Minimum Evolution (BME) è un potente modello di stima filogenetica basato sulle distanze biologiche fra i genomi, introdotto da Desper e Gascuel e attualmente implementato in efficienti software per le analisi filogenetiche. Il BME è computazionalmente meno impegnativo rispetto a metodi di stima più sofisticati, ad esempio Maximum Likelyhood o inferenza bayesiana, pur conservando la coerenza statistica e la capacità di funzionare con quasi qualsiasi tipo di dati che rappresentano una misura di dissimilarità fra genomi. Il BME può essere formulato in termini di un problema di ottimizzazione combinatoria non lineare e non convessa, denominato Balanced Minimum Evolution Problem (BMEP). Attualmente, lo stato dell’arte tra i metodi approssimati per il BMEP è rappresentato da FastME (versione 2.0), un software che implementa diverse euristiche deterministiche di costruzione filogenetica, combinate con algoritmi di ricerca locale basati sulla manipolazione di alberi filogenetici. Tuttavia, questo approccio, sebbene molto efficiente, non garantisce la convergenza a soluzioni prossime all’ottimo, a causa della mancanza di esplorazione dello spazio delle soluzioni, un fenomeno che si aggrava quando si affrontano insiemi di dati molecolari caratterizzati da un grande numero di taxa. Per ovviare a tali problemi di convergenza, in questo lavoro, proponiamo una nuova metaeuristica, denominata PhyloES, che sfrutta la combinazione di una fase esplorativa, basata su una particolare tipologia di algoritmo evolutivo, denominata Evolution Strategies, con una fase di raffinamento incentrata su due algoritmi di ricerca locale. I nostri esperimenti computazionali mostrano che PhyloES è in grado di superare le prestazioni di FastME, specialmente al crescere delle dimensioni delle istanze, fornendo soluzioni migliori nel senso della funzione obiettivo e significativamente diverse dal punto di vista topologico, fattore di particolare rilevanza dal punto di vista biologico. ​