Application of constraint programming techniques for structure prediction of lattice proteins with extended alphabets

Motivation: Predicting the ground state of biopolymers is a notoriously har d problem in biocomputing, Model systems, such as lattice proteins, are sim ple tools and valuable to rest and improve new methods. Best known are mode ls with sequences composted from a binary (hydrophobic and polar) alphabet. The major drawback is the degeneracy, i.e. the number of different ground state conformations. Results: We shaw how recently developed constraint pro gramming techniques can be used to solve the structure prediction problem e fficiently for a higher order alphabet. To our knowledge it is the first re port of on exact and computationally feasible solution to model proteins of length lip to 36 and without resorting to maximally compact states, We fur ther show that degeneracy is reduced by more than one order of magnitude an d that ground state conformations are not necessarily compact. Therefore, m ore realistic protein simulations become feasible with our model.