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. https://resolver.caltech.edu/CaltechAUTHORS:PIEpeds02
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 115kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:PIEpeds02
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.
| Item Type: | Article | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||||||||
| ORCID: |
| |||||||||||||||
| 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). | |||||||||||||||
| Funders: |
| |||||||||||||||
| Subject Keywords: | complexity/design/NP-complete/NP-hard/proteins | |||||||||||||||
| Issue or Number: | 10 | |||||||||||||||
| DOI: | 10.1093/protein/15.10.779 | |||||||||||||||
| Record Number: | CaltechAUTHORS:PIEpeds02 | |||||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:PIEpeds02 | |||||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||||||||
| ID Code: | 3650 | |||||||||||||||
| Collection: | CaltechAUTHORS | |||||||||||||||
| Deposited By: | Lindsay Cleary | |||||||||||||||
| Deposited On: | 22 Jun 2006 | |||||||||||||||
| Last Modified: | 08 Nov 2021 20:11 |
Repository Staff Only: item control page
