Local search for the maximum parsimony problem

被引：0

作者：

Goëffon, A ^{[1
]}

Richer, JM ^{[1
]}

Hao, JK ^{[1
]}

机构：

[1] Univ Angers, LERIA, F-49045 Angers, France

来源：

ADVANCES IN NATURAL COMPUTATION, PT 3, PROCEEDINGS | 2005年 / 3612卷

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Four local search algorithms are investigated for the phylogenetic tree reconstruction problem under the Maximum Parsimony criterion. A new subtree swapping neighborhood is introduced and studied in combination with an effective array-based tree representation. Computational results are shown on a set of randomly generated benchmark instances as well as on 8 real problems (sequences of phytopathogen gamma-proteobacteria) and compared with two references from the literature.

引用

页码：678 / 683

页数：6

共 14 条

[1] Heuristics for the phylogeny problem
Andreatta, AA
Ribeiro, CC
[J]. JOURNAL OF HEURISTICS, 2002, 8 (04) : 429 - 447
[2] LVB: parsimony and simulated annealing in the search for phylogenetic trees
Barker, D
[J]. BIOINFORMATICS, 2004, 20 (02) : 274 - 275
[3] A METHOD FOR DEDUCING BRANCHING SEQUENCES IN PHYLOGENY
CAMIN, JH
SOKAL, RR
[J]. EVOLUTION, 1965, 19 (03) : 311 - 326
[4] FELSENSTEIN J, 1993, PHYLOGENETIC INFEREN
[5] Felsenstein J., 2003, INFERRING PHYLOGENIE
[6] TOWARD DEFINING COURSE OF EVOLUTION - MINIMUM CHANGE FOR A SPECIFIC TREE TOPOLOGY
FITCH, WM
[J]. SYSTEMATIC ZOOLOGY, 1971, 20 (04): : 406 - &
[7] Foulds L.R., 1982, ADV APPL MATH, V3, P43, DOI DOI 10.1016/S0196-8858(82)80004-3
[8] BIONJ: An improved version of the NJ algorithm based on a simple model of sequence data
Gascuel, O
[J]. MOLECULAR BIOLOGY AND EVOLUTION, 1997, 14 (07) : 685 - 695
[9] A SIMPLE METHOD FOR ESTIMATING EVOLUTIONARY RATES OF BASE SUBSTITUTIONS THROUGH COMPARATIVE STUDIES OF NUCLEOTIDE-SEQUENCES
KIMURA, M
[J]. JOURNAL OF MOLECULAR EVOLUTION, 1980, 16 (02) : 111 - 120
[10] KUHNER MK, 1994, MOL BIOL EVOL, V11, P459

← 1 2 →