PMID- 18245882
OWN - NLM
STAT- MEDLINE
DCOM- 20080505
LR  - 20161020
IS  - 1545-5963 (Print)
IS  - 1545-5963 (Linking)
VI  - 5
IP  - 1
DP  - 2008 Jan-Mar
TI  - Progressive tree neighborhood applied to the maximum parsimony problem.
PG  - 136-45
LID - 10.1109/TCBB.2007.1065 [doi]
AB  - The Maximum Parsimony (MP) 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 Nearest Neighbor Interchange (NNI), Subtree Pruning Regrafting (SPR) 
      and Tree-Bisection-Reconnection (TBR) neighborhoods, we introduce the concept of 
      Progressive Neighborhood (PN) 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.
FAU - Goeffon, Adrien
AU  - Goeffon A
AD  - University of Angers, Lavoisier, France. adrien.goeffon@univ-angers.fr
FAU - Richer, Jean-Michel
AU  - Richer JM
FAU - Hao, Jin-Kao
AU  - Hao JK
LA  - eng
PT  - Journal Article
PT  - Research Support, Non-U.S. Gov't
PL  - United States
TA  - IEEE/ACM Trans Comput Biol Bioinform
JT  - IEEE/ACM transactions on computational biology and bioinformatics
JID - 101196755
SB  - IM
MH  - Algorithms
MH  - Base Sequence
MH  - Evolution, Molecular
MH  - *Models, Genetic
MH  - Models, Statistical
MH  - *Phylogeny
MH  - Probability
EDAT- 2008/02/05 09:00
MHDA- 2008/05/06 09:00
CRDT- 2008/02/05 09:00
PHST- 2008/02/05 09:00 [pubmed]
PHST- 2008/05/06 09:00 [medline]
PHST- 2008/02/05 09:00 [entrez]
AID - 10.1109/TCBB.2007.1065 [doi]
PST - ppublish
SO  - IEEE/ACM Trans Comput Biol Bioinform. 2008 Jan-Mar;5(1):136-45. doi: 
      10.1109/TCBB.2007.1065.