ROBUST PROOFS OF NP-HARDNESS FOR PROTEIN-FOLDING - GENERAL LATTICES AND ENERGY POTENTIALS

This paper addresses the robustness of intractability arguments for si mplified models of protein folding that use lattices to discretize the space of conformations that a protein can assume. We present two gene ralized 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 pro ve that for any reasonable lattice the protein-structure prediction pr oblem is NP-hard. The second hardness result concerns the intractabili ty of protein folding for a class of energy formulas that contains a b road range of mean force potentials whose form is similar to commonly used pair potentials (e,g,, the Lennard-Jones potential), We prove tha t protein-structure prediction is NP-hard for any energy formula in th is class. These are the first robust intractability results that ident ify sources of computational complexity of protein-structure predictio n that transcend particular problem formulations.