In this talk, I will present an existing simple exact model, called the HP (Hydrophobic-Polar) model, for protein structure prediction. I will then describe the algorithm I have worked on, based on pruned exponential search, to solve the problem exactly in the 2D lattice.

The algorithm currently finds optimal solutions for protein sequences of around 50-60 elements