@inproceedings{Backofen:CP98,
author = {Backofen, Rolf},
title = {Constraint Techniques for Solving the Protein
         Structure Prediction Problem},
booktitle = {Proceedings of 4th International Conference on
             Principle and Practice of Constraint Programming
             (CP'98)},
year = {1998},
doi = {https://link.springer.com/chapter/10.1007/3-540-49481-2_7},
volume = {1520},
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag},
pages = {72-86},
editor = {Michael Maher and Jean-Francois Puget},
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.
            }
}