Progressive Tree Neighborhood Applied to the Maximum Parsimony Problem
| hal.structure.identifier | Laboratoire d'Etudes et de Recherche en Informatique d'Angers [LERIA] | |
| hal.structure.identifier | Models and Algorithms for the Genome [ MAGNOME] | |
| dc.contributor.author | GOËFFON, Adrien | |
| hal.structure.identifier | Laboratoire d'Etudes et de Recherche en Informatique d'Angers [LERIA] | |
| dc.contributor.author | RICHER, Jean-Michel | |
| hal.structure.identifier | Laboratoire d'Etudes et de Recherche en Informatique d'Angers [LERIA] | |
| dc.contributor.author | HAO, Jin-Kao | |
| dc.date.accessioned | 2024-04-15T09:52:51Z | |
| dc.date.available | 2024-04-15T09:52:51Z | |
| dc.date.issued | 2008 | |
| dc.identifier.issn | 1545-5963 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198557 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | Institute of Electrical and Electronics Engineers | |
| dc.subject.en | optimization | |
| dc.subject.en | combinatorial algorithms | |
| dc.subject.en | phylogeny reconstruction | |
| dc.subject.en | maximum parsimony | |
| dc.title.en | Progressive Tree Neighborhood Applied to the Maximum Parsimony Problem | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1109/TCBB.2007.1065 | |
| dc.subject.hal | Informatique [cs]/Bio-informatique [q-bio.QM] | |
| dc.subject.hal | Sciences du Vivant [q-bio]/Bio-Informatique, Biologie Systémique [q-bio.QM] | |
| bordeaux.journal | IEEE/ACM Transactions on Computational Biology and Bioinformatics | |
| bordeaux.page | 136--145 | |
| bordeaux.volume | 5 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 1 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00350539 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00350539v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=IEEE/ACM%20Transactions%20on%20Computational%20Biology%20and%20Bioinformatics&rft.date=2008&rft.volume=5&rft.issue=1&rft.spage=136--145&rft.epage=136--145&rft.eissn=1545-5963&rft.issn=1545-5963&rft.au=GO%C3%8BFFON,%20Adrien&RICHER,%20Jean-Michel&HAO,%20Jin-Kao&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||