title: Robust proofs of NP-hardness for protein folding: general lattices and energy potentials.
abstract: This paper addresses the robustness of intractability arguments for simplified models of protein folding that use lattices to discretize the space of conformations that a protein can assume. We present two generalized NP-hardness results. The first concerns the intractability of protein folding independent of the lattice used to define the discrete protein-folding model. We consider a previously studied model and prove that for any reasonable lattice the protein-structure prediction problem is NP-hard. The second hardness result concerns the intractability of protein folding for a class of energy formulas that contains a broad range of mean force potentials whose form is similar to commonly used pair potentials (e.g., the Lennard-Jones potential). We prove that protein-structure prediction is NP-hard for any energy formula in this class. These are the first robust intractability results that identify sources of computational complexity of protein-structure prediction that transcend particular problem formulations.
authors.affiliation: Sandia National Laboratories, Algorithms and Discrete Mathematics Department, Albuquerque, New Mexico 87185-1110, USA. wehart@cs.sandia.gov
authors.forename: W E
authors.initials: WE
authors.lastname: Hart
authors.forename: S
authors.initials: S
authors.lastname: Istrail
mesh_terms: D008956:Models, Chemical; D011487:Protein Conformation; D017510:Protein Folding