Metaheuristics for the Maximum Parsimony Problem
Karla E. Vazquez-Ortiz, Eduardo Rodríguez-Tello · Computational Intelligence and Bioinformatics / 755: Modelling, Identification, and Simulation · 2011
The Maximum Parsimony (MP) problem aims at recon-structing a phylogenetic tree from DNA sequences while minimizing the total number of genetic transformations. In this paper two different metaheuristic algorithm for finding near-optimal solutions for the MP problem are proposed: iterated local search (ILS) and simulated annealing (SA). Different possibilities for the key components of these al-gorithms were carefully analyzed in order to find the com-bination of them offering the best quality solutions to the problem at a reasonable computational effort. The perfor-mance of both metaheuristics is investigated through exten-sive experimentation over well known benchmark instances showing that our SA algorithm is able to improve some pre-vious best-known solutions.