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

Motivation: Predicting the ground state of biopolymers is a notoriously hard problem in biocomputing, Model systems, such as lattice proteins, are simple tools and valuable to rest and improve new methods. Best known are models 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 programming techniques can be used to solve the structure prediction problem efficiently for a higher order alphabet. To our knowledge it is the first report of on exact and computationally feasible solution to model proteins of length lip to 36 and without resorting to maximally compact states, We further show that degeneracy is reduced by more than one order of magnitude and that ground state conformations are not necessarily compact. Therefore, more realistic protein simulations become feasible with our model.