GOËFFON, Adrien; RICHER, Jean-Michel; HAO, Jin-Kao

doi:10.1109/TCBB.2007.1065

Métadonnées

Licence d’utilisation du document

GOËFFON, Adrien
Laboratoire d'Etudes et de Recherche en Informatique d'Angers [LERIA]
Models and Algorithms for the Genome [ MAGNOME]

RICHER, Jean-Michel
Laboratoire d'Etudes et de Recherche en Informatique d'Angers [LERIA]

HAO, Jin-Kao
Laboratoire d'Etudes et de Recherche en Informatique d'Angers [LERIA]

Langue

Article de revue

Ce document a été publié dans

IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2008, vol. 5, n° 1, p. 136--145

Institute of Electrical and Electronics Engineers

Résumé en anglais

The Maximum Parsimony problem aims at reconstructing a phylogenetic tree from DNA sequences while minimizing the number of genetic transformations. To solve this NP-complete problem, heuristic methods have been developed, often based on local search. In this article, we focus on the influence of the neighborhood relations. After analyzing the advantages and drawbacks of the well-known NNI, SPR and TBR neighborhoods, we introduce the concept of Progressive Neighborhood, which consists in constraining progressively the size of the neighborhood as the search advances. We empirically show that applied to the Maximum Parsimony problem, this progressive neighborhood turns out to be more efficient and robust than the classic neighborhoods using a descent algorithm. Indeed, it allows to find better solutions with a smaller number of iterations or trees evaluated.< Réduire

Mots clés en anglais

optimization

combinatorial algorithms

phylogeny reconstruction

maximum parsimony

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Progressive Tree Neighborhood Applied to the Maximum Parsimony Problem

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

DOI

Origine

Unités de recherche