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 (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
[
12] 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 [
3,
5].
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.