On the complexity of protein folding

被引：211

作者：

Crescenzi, P

Goldman, D

Papadimitriou, C

Piccolboni, A

Yannakakis, M

机构：

[1] Univ Florence, Dipartimento Sistemi & Informat, I-50134 Florence, Italy

[2] Univ Calif Berkeley, Dept Math, Berkeley, CA 94720 USA

[3] Univ Calif Berkeley, Div Comp Sci, Berkeley, CA 94720 USA

[4] Univ Milan, Dipartimento Sci Informaz, I-20135 Milan, Italy

[5] AT&T Bell Labs, Murray Hill, NJ 07974 USA

来源：

JOURNAL OF COMPUTATIONAL BIOLOGY | 1998年 / 5卷 / 03期

关键词：

protein folding; computational complexity;

D O I：

10.1089/cmb.1998.5.423

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

We show that the protein folding problem in the two-dimensional H-P model is NP-complete.

引用

页码：423 / 465

页数：43

共 13 条

[1]

BERGER B, 1997, J COMP0UTATIONAL JUL

[2] THE PROTEIN FOLDING PROBLEM [J].

CHAN, HS ;

DILL, KA .

PHYSICS TODAY, 1993, 46 (02) :24-32

[3] DOMINANT FORCES IN PROTEIN FOLDING [J].

DILL, KA .

BIOCHEMISTRY, 1990, 29 (31) :7133-7155

[4]

DILL KA, 1995, PROTEIN SCI, V4, P561

[5]

FRAENKEL AS, 1993, B MATH BIOL, V55, P1199, DOI 10.1016/S0092-8240(05)80170-3

[6]

Hart W. E., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P157, DOI 10.1145/225058.225106

[7]

Johnson D.S., 1985, TRAVELING SALESMAN P, P145

[8] COMPUTER-GRAPHICS AND CONNECTED TOPOLOGIES ON FINITE ORDERED SETS [J].

KHALIMSKY, E ;

KOPPERMAN, R ;

MEYER, PR .

TOPOLOGY AND ITS APPLICATIONS, 1990, 36 (01) :1-17

[9] DECIPHERING THE RULES OF PROTEIN FOLDING [J].

KING, J .

CHEMICAL & ENGINEERING NEWS, 1989, 67 (15) :32-&

[10]

NAYAK A, 1998, IN PRESS P ACMS S DI

← 1 2 →