rose.blog

The protein folding problem is this: given the primary structure of a protein (its linear sequence of amino acids), compute its three dimensional shape. Here is a good introduction.

One approximation that is often made to simplify the problem is to restrict the aminos to a lattice. A further restriction is to label all aminos as either H (hydrophobic) or P (hydrophilic).

Restricting to a lattice and H & P aminos gives the HP model, invented by Ken Dill. Finding the global energy minimum of this model of protein folding is NP-hard.

Here is a paper showing how to map the HP model of protein folding to quadratic unconstrained binary optimization. The published version is Physical Review A 78, 012320 (2008).

The techniques shown here can be extended to other more sophisticated lattice protein folding models. Once the folding instance has been reduced to a QUBO, it can be solved using Orion web services’ QUBO solver.