Protein design is NP-hard
Protein design is NP-hard
复制标题
DOI：
10.1093/protein/15.10.779
复制
发表时间：
2002-10-01
期刊：
影响因子：
--
通讯作者：
Winfree, E
中科院分区：
文献类型：
--
作者：
Pierce, NA;Winfree, E
在计算蛋白质设计领域工作的生物学家从未怀疑过他们在尝试计算机序列选择时所面临的算法挑战的严重性。事实证明，在计算机科学界的语言中，这个离散优化问题是NP难的。本文的目的是解释这一观察的背景下，提供一个简单的说明性证明，并讨论计算蛋白质设计算法的未来进展的影响。
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.