Protein FoldingProblemThe 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 InputA string of h and p-characters eg. "hppphhhppp" OutputLinear program
Assignment for variables di, i = 1..n-1, where n = length of the string SAT
Example Instances
hpphpph (2 contacts) [TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links] Latest update: 21 March 2006. |