Published October 2002
| Published
Journal Article
Open
Protein Design is NP-hard
- Creators
-
Pierce, Niles A.
-
Winfree, Erik
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
Files
(115.2 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:090223df8fb25eed4f6da97802206fb5
|
115.2 kB | Preview Download |
Additional details
- Eprint ID
- 3650
- Resolver ID
- CaltechAUTHORS:PIEpeds02.939
- Burroughs-Wellcome Foundation
- Defense Advanced Research Projects Agency (DARPA)
- F30602-010200561
- Air Force Research Laboratory
- Caltech Initiative in Computational Molecular Biology
- Created
-
2006-06-22Created from EPrint's datestamp field
- Updated
-
2022-10-05Created from EPrint's last_modified field