TCS / Studies / T-79.4201 / Home Assignments / Thispage
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Protein Folding

Problem

The folding of proteins can be investigated with a highly simplified model where protein is represented as a string of hydrophobic(H) and polar(P) beads. The bead is folded on a grid minimizing the energy between neighboring beads by maximazing the contacts between H beads.

Your task is to find a folding (self-avoiding walk on a grid) for a 2D HP-structure with a minimum energy ie. maximum amount of h-h contacts. For example a HP-protein hhphhhph has a minimum solution with 3 contacts:



p-h
| |
h h h
| | |
h h-p
^
start

Input

A string of h and p-characters eg. "hppphhhppp"

Output

Linear program

Assignment for variables di, i = 1..n-1, where n = length of the string
di = 0, if character i+1 is above character i in the folding
di = 1, if character i+1 is below of character i
di = 2, if character i+1 is on the left of character i
di = 3, if character i+1 is on the right of character i

The above folding would be represented as:
d1=0;
d2=0;
d3=3;
d4=1;
d5=1;
d5=3;
d6=0;

SAT

Example Instances

hpphpph (2 contacts)
hphpphhphpphph (6 contacts)
hphpphhphpphphhpphph: (9 contacts)


[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 21 March 2006.