@InProceedings{Backofen:CP98,
  author = 	 {Rolf Backofen},
  title = 	 {Constraint Techniques for Solving the Protein
                  Structure Prediction Problem},
  booktitle = 	 {Proceedings of $4^{\it th}$ International Conference on
                  Principle and Practice of Constraint Programming
                  (CP'98)},
  year =	 1998,
  pages =        {72-86},
  editor =       {Michael Maher and Jean-Francois Puget},
  volume =       1520,
  series =       {Lecture Notes in Computer Science},
  publisher =    {Springer Verlag}
, abstract = {The protein structure prediction problem is one of the most (if not
{\em the most}) important problem in computational biology. This
problem consists of finding the conformation of a protein (i.e., a
sequence of amino-acids) with minimal energy. Because of the
complexity of this problem, simplified models like Dill's HP-lattice
model 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.

We describe a constraint formulation of the HP-model structure
prediction problem, present the basic constraints and search
strategy. We then introduce a novel, general technique for excluding
geometrical symmetries in constraint programming. To our knowledge,
this is the first general and declarative technique for excluding
symmetries in constraint programming that can be added to an existing
implementation. Finally, we describe a new lower bound on the energy
of an HP-protein. Both techniques yield an efficient pruning of the
search tree.

   }
}