@article{Backofen:Constraints2001,
  author = 	 {Rolf Backofen},
  title = 	 {The Protein Structure Prediction Problem: A
                  Constraint Optimisation Approach using a New Lower
                  Bound}, 
  journal =      {Constraints},
  volume =  6,
  pages = "223-255",
  year = 	 2001,
  user =	 {will},
  abstract = {The protein structure prediction problem is one of the most
(if not the most) important problem in computational biology. This
problem consists of finding the conformation of a protein with
minimal energy. Because of the complexity of this problem, simplified
models like Dill's HP-lattice model [15], [16] have become a major
tool for investigating general properties of protein folding. Even
for this simplified model, the structure prediction problem has been
shown to be NP-complete [5], [7]. We describe a constraint
formulation of the HP-model structure prediction problem, and present
the basic constraints and search strategy. Of course, the simple
formulation would not lead to an efficient algorithm. We therefore
describe redundant constraints to prune the search tree. Furthermore,
we need bounding function for the energy of an HP-protein. We
introduce a new lower bound based on partial knowledge about the
final conformation (namely the distribution of H-monomers to layers).

Keywords: structure prediction, protein folding, lattice models,
HP-model}
}