Protein Engineering, Vol. 15, No. 10, 779-782,
October 2002
© 2002 Oxford University Press
Protein Design is NP-hard
1 Applied and Computational Mathematics and 3 Computer Science and Computation and Neural Systems,California Institute of Technology, Pasadena, CA 91125, USA
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.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  I. Georgiev, D. Keedy, J. S. Richardson, D. C. Richardson, and B. R. Donald Algorithm for backrub motions in protein design Bioinformatics, July 1, 2008; 24(13): i196 - i204. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. K. Fung, C. A. Floudas, M. S. Taylor, L. Zhang, and D. Morikis Toward Full-Sequence De Novo Protein Design with Flexible Templates for Human Beta-Defensin-2 Biophys. J., January 15, 2008; 94(2): 584 - 599. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 I. W. Davis, A. Leaver-Fay, V. B. Chen, J. N. Block, G. J. Kapral, X. Wang, L. W. Murray, W. B. Arendall III, J. Snoeyink, J. S. Richardson, et al. MolProbity: all-atom contacts and structure validation for proteins and nucleic acids Nucleic Acids Res., July 13, 2007; 35(suppl_2): W375 - W383. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. Georgiev and B. R. Donald Dead-End Elimination with Backbone Flexibility Bioinformatics, July 1, 2007; 23(13): i185 - i194. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Hartmann, I. Antes, and T. Lengauer IRECS: A new algorithm for the selection of most probable ensembles of side-chain conformations in protein models Protein Sci., July 1, 2007; 16(7): 1294 - 1307. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. E. Smith, S. C. Lovell, D. F. Burke, R. W. Montalvao, and T. L. Blundell Andante: reducing side-chain rotamer search space during comparative modeling using environment-specific substitution probabilities Bioinformatics, May 1, 2007; 23(9): 1099 - 1105. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. K. Lassila, H. K. Privett, B. D. Allen, and S. L. Mayo Combinatorial methods for small-molecule placement in computational enzyme design PNAS, November 7, 2006; 103(45): 16710 - 16715. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
W. Xie and N. V. Sahinidis Residue-rotamer-reduction algorithm for the protein side-chain conformation problem Bioinformatics, January 15, 2006; 22(2): 188 - 194. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. L. Kingsford, B. Chazelle, and M. Singh Solving and analyzing side-chain positioning problems using linear and integer programming Bioinformatics, April 1, 2005; 21(7): 1028 - 1039. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. B. Endelman, J. J. Silberg, Z.-G. Wang, and F. H. Arnold Site-directed protein recombination as a shortest-path problem Protein Eng. Des. Sel., July 1, 2004; 17(7): 589 - 594. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Fox, A. Roy, S. Govindarajan, J. Minshull, C. Gustafsson, J. T. Jones, and R. Emig Optimizing the search algorithm for protein engineering by directed evolution Protein Eng. Des. Sel., August 1, 2003; 16(8): 589 - 597. [Abstract] [Full Text] [PDF]
|
|