Published October 2002
| Version Published
Journal Article
Open
Protein Design is NP-hard
Abstract
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
PIEpeds02.pdf
Additional details
Identifiers
- Eprint ID
- 3650
- Resolver ID
- CaltechAUTHORS:PIEpeds02.939
Related works
- Describes
- http://peds.oxfordjournals.org/cgi/content/abstract/15/10/779 (URL)
Funding
- Burroughs-Wellcome Foundation
- Defense Advanced Research Projects Agency (DARPA)
- Air Force Research Laboratory
- F30602-010200561
- Caltech Initiative in Computational Molecular Biology
Dates
- Created
-
2006-06-22Created from EPrint's datestamp field
- Updated
-
2022-10-05Created from EPrint's last_modified field