Protein design is NP-hard

被引：179

作者：

Pierce, NA ^{[1
]}

Winfree, E ^{[1
]}

机构：

[1] CALTECH, Pasadena, CA 91125 USA

来源：

PROTEIN ENGINEERING | 2002年 / 15卷 / 10期

关键词：

complexity; design; NP-complete; NP-hard; proteins;

D O I：

10.1093/protein/15.10.779

中图分类号：

Q5 [生物化学]; Q7 [分子生物学];

学科分类号：

071010 ; 081704 ;

摘要：

Biologists working in the area of computational protein design have never doubted the seriousness of the algorithmic challenges that face them in attempting in silico sequence selection. It turns out that in the language of the computer science community, this discrete optimization problem is NP-hard. The purpose of this paper is to explain the context of this observation, to provide a simple illustrative proof and to discuss the implications for future progress on algorithms for computational protein design.

引用

页码：779 / 782

页数：4

共 38 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J].