COMPLEXITY OF PROTEIN-FOLDING

被引：51

作者：

FRAENKEL, AS ^{[1
]}

机构：

[1] WEIZMANN INST SCI,DEPT APPL MATH & COMP SCI,IL-76100 REHOVOT,ISRAEL

来源：

BULLETIN OF MATHEMATICAL BIOLOGY | 1993年 / 55卷 / 06期

关键词：

D O I：

10.1007/BF02460704

中图分类号：

Q [生物科学];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

It is believed that the native folded three-dimensional conformation of a protein is its lowest free energy state, or one of its lowest. It is shown here that both a two- and three-dimensional mathematical model describing the folding process as a free energy minimization problem is NP-hard. This means that the problem belongs to a large set of computational problems, assumed to be very hard (''conditionally intractable''). Some of the possible ramifications of this result are speculated upon.

引用

页码：1199 / 1210

页数：12

共 26 条

[1] PRINCIPLES THAT GOVERN FOLDING OF PROTEIN CHAINS [J].

ANFINSEN, CB .

SCIENCE, 1973, 181 (4096) :223-230

[2] ON THE COMPUTATIONAL-COMPLEXITY OF ISING SPIN-GLASS MODELS [J].

BARAHONA, F .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1982, 15 (10) :3241-3253

[3] MORPHOLOGY OF GROUND-STATES OF TWO-DIMENSIONAL FRUSTRATION MODEL [J].

BARAHONA, F ;

MAYNARD, R ;

RAMMAL, R ;

UHRY, JP .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1982, 15 (02) :673-699

[4]

Baxter R. J., 2007, EXACTLY SOLVED MODEL

[5]

Bennett C. H., 1989, SIGACT News, V20, P78, DOI 10.1145/74074.74087

[6]

Bennett C. H., 1992, Journal of Cryptology, V5, P3, DOI 10.1007/BF00191318

[7] QUANTUM CRYPTOGRAPHY WITHOUT BELL THEOREM [J].

BENNETT, CH ;

BRASSARD, G ;

MERMIN, ND .

PHYSICAL REVIEW LETTERS, 1992, 68 (05) :557-559

[8]

BENNETT CH, 1992, P CRYPT, V91, P351

[9] ON THE GROUND-STATES OF THE FRUSTRATION MODEL OF A SPIN-GLASS BY A MATCHING METHOD OF GRAPH-THEORY [J].

BIECHE, I ;

MAYNARD, R ;

RAMMAL, R ;

UHRY, JP .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1980, 13 (08) :2553-2576

[10]

BRASSARD G, 1990, P CRYPT, V90, P49

← 1 2 3 →