Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2002 | Published
Journal Article Open

Protein Design is NP-hard


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.

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).

Attached Files

Published - PIEpeds02.pdf


Files (115.2 kB)
Name Size Download all
115.2 kB Preview Download

Additional details

August 21, 2023
October 23, 2023