INFERRING EVOLUTIONARY HISTORY FROM DNA-SEQUENCES

被引：33

作者：

KANNAN, SK ^{[1
]}

WARNOW, TJ ^{[1
]}

机构：

[1] UNIV PENN,DEPT COMP & INFORMAT SCI,PHILADELPHIA,PA 19104

来源：

SIAM JOURNAL ON COMPUTING | 1994年 / 23卷 / 04期

关键词：

ALGORITHMS; GRAPHS; EVOLUTIONARY TREES; EVOLUTION;

D O I：

10.1137/S0097539791222171

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

One of the longstanding problems in computational molecular biology is the Character Compatibility Problem, which is concerned with the construction of phylogenetic trees for species sets, where the species are defined by characters. The character compatibility problem is NP-Complete in general. In this paper an O(n2k) time algorithm is described for the case where the species are described by quaternary characters. This algorithm can be used to construct phylogenetic trees from DNA sequences.

引用

页码：713 / 737

页数：25

共 29 条

[1]

AGARWALA R, 1994, IN PRESS SIAM J COMP, V23

[2]

[Anonymous], 1964, PHEN PHYLOGEN CLASSI

[3]

BODLAENDER H, IN PRESS SIMPLE LINE

[4]

Bodlaender H.L., 1992, 2 STRIKES PERFECT PH

[5]

Buneman P., 1974, Discrete Mathematics, V9, P205, DOI 10.1016/0012-365X(74)90002-8

[6] A METHOD FOR DEDUCING BRANCHING SEQUENCES IN PHYLOGENY [J].

CAMIN, JH ;

SOKAL, RR .

EVOLUTION, 1965, 19 (03) :311-326

[7] COMPUTATIONALLY DIFFICULT PARSIMONY PROBLEMS IN PHYLOGENETIC SYSTEMATICS [J].

DAY, WHE .

JOURNAL OF THEORETICAL BIOLOGY, 1983, 103 (03) :429-438

[8] THE COMPUTATIONAL-COMPLEXITY OF INFERRING ROOTED PHYLOGENIES BY PARSIMONY [J].

DAY, WHE ;

JOHNSON, DS ;

SANKOFF, D .

MATHEMATICAL BIOSCIENCES, 1986, 81 (01) :33-42

[9] COMPUTATIONAL-COMPLEXITY OF INFERRING PHYLOGENIES BY COMPATIBILITY [J].

DAY, WHE ;

SANKOFF, D .

SYSTEMATIC ZOOLOGY, 1986, 35 (02) :224-229

[10] CONVEX TREE REALIZATIONS OF PARTITIONS [J].

DRESS, A ;

STEEL, M .

APPLIED MATHEMATICS LETTERS, 1992, 5 (03) :3-6

← 1 2 3 →