A Memetic Algorithm for Phylogenetic Reconstruction with Maximum Parsimony

TitreA Memetic Algorithm for Phylogenetic Reconstruction with Maximum Parsimony
Type de publicationCommunication
TypeCommunication avec actes dans un congrès
Date du colloque2009
Titre du colloque7th European Conference, EvoBIO 2009
Titre des actes ou de la revueEvolutionary Computation, Machine Learning and Data Mining in Bioinformatics
Pagination164 - 175
AuteurRicher, Jean-Michel, Goëffon, Adrien , Hao, Jin-Kao
ISBN978-3-642-01183-2 / 978-3-642-01184-9
Mots-clésalgorithm analysis and problem complexity, Artificial Intelligence (incl. Robotics), Computation by Abstract Devices, Computational Biology/Bioinformatics, maximum parsimony, memetic algorithm, pattern recognition, Phylogeny, Programming Techniques, progressive descent, tree crossover
Résumé en anglais

The Maximum Parsimony problem aims at reconstructing a phylogenetic tree from DNA, RNA or protein sequences while minimizing the number of evolutionary changes. Much work has been devoted by the research community to solve this NP-complete problem and many algorithms and techniques have been devised in order to find high quality solutions with reasonable computational resources. In this paper we present a memetic algorithm (implemented in the software Hydra) which is based on an integration of an effective local search operator with a specific topological tree crossover operator. We report computational results of Hydra on a set of 12 benchmark instances from the literature and demonstrate its effectiveness with respect to one of the most powerful software (TNT). We also study the behavior of the algorithm with respect to some fundamental ingredients.


Date du colloque : 04/2009

URL de la noticehttp://okina.univ-angers.fr/publications/ua4503
Lien vers le document en ligne