A Caltech Library Service

Protein Design is NP-hard

Pierce, Niles A. and Winfree, Erik (2002) Protein Design is NP-hard. Protein Engineering, 15 (10). pp. 779-782. ISSN 0269-2139. doi:10.1093/protein/15.10.779.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle
Pierce, Niles A.0000-0003-2367-4406
Winfree, Erik0000-0002-5899-7523
Additional Information:© 2002 Oxford University Press. Reprinted with permission. Received March 13, 2002; revised May 31, 2002; accepted July 2, 2002. We thank L.J. Schulman for a critical reading of the manuscript. This research was supported by the Burroughs-Wellcome Foundation through the Caltech Initiative in Computational Molecular Biology (NAP) and by the Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory under agreement F30602-010200561 (both authors).
Funding AgencyGrant Number
Burroughs-Wellcome FoundationUNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Air Force Research LaboratoryF30602-010200561
Caltech Initiative in Computational Molecular BiologyUNSPECIFIED
Subject Keywords:complexity/design/NP-complete/NP-hard/proteins
Issue or Number:10
Record Number:CaltechAUTHORS:PIEpeds02
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3650
Deposited By: Lindsay Cleary
Deposited On:22 Jun 2006
Last Modified:08 Nov 2021 20:11

Repository Staff Only: item control page