Show simple item record

hal.structure.identifierLaboratoire d'Etudes et de Recherche en Informatique d'Angers [LERIA]
hal.structure.identifierModels and Algorithms for the Genome [ MAGNOME]
dc.contributor.authorGOËFFON, Adrien
hal.structure.identifierLaboratoire d'Etudes et de Recherche en Informatique d'Angers [LERIA]
dc.contributor.authorRICHER, Jean-Michel
hal.structure.identifierLaboratoire d'Etudes et de Recherche en Informatique d'Angers [LERIA]
dc.contributor.authorHAO, Jin-Kao
dc.date.accessioned2024-04-15T09:52:51Z
dc.date.available2024-04-15T09:52:51Z
dc.date.issued2008
dc.identifier.issn1545-5963
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198557
dc.description.abstractEnThe 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.isoen
dc.publisherInstitute of Electrical and Electronics Engineers
dc.subject.enoptimization
dc.subject.encombinatorial algorithms
dc.subject.enphylogeny reconstruction
dc.subject.enmaximum parsimony
dc.title.enProgressive Tree Neighborhood Applied to the Maximum Parsimony Problem
dc.typeArticle de revue
dc.identifier.doi10.1109/TCBB.2007.1065
dc.subject.halInformatique [cs]/Bio-informatique [q-bio.QM]
dc.subject.halSciences du Vivant [q-bio]/Bio-Informatique, Biologie Systémique [q-bio.QM]
bordeaux.journalIEEE/ACM Transactions on Computational Biology and Bioinformatics
bordeaux.page136--145
bordeaux.volume5
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue1
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierinria-00350539
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00350539v1
bordeaux.COinSctx_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


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record