A protein is a one-dimensional string of up to several thousands of amino acids. To become biologically active it needs to fold into a three-dimensional spatial structure. It is generally believed among scientists that in principle the three-dimensional structure of a protein can be predicted from the positions of its amino acids and from knowing their pairwaise repulsion and attraction forces. A very simple and yet discrete version of the problems makes the following additional assumptions: one two types of amino acids exists, hydrophobe (H) and polar (P). Since the folding usually takes place in surrounding water, the hydrophobe amino acids try to stay away from the water and stick closely together (like oil on water), whereas the polar one are attracted by the water. Further it is assumed that only a finite number of angles between adjacent amino acids are feasible, and that the distances between adjacent amino acids are all of a unit length. Hence we can think of a regular grid in which the folded protein is embedded. Introduced by Ken A. Dill in 1985, this model is known as HP model. Despite its simplifications, it is still a difficult optimization problem.

We formulate the HP model as integer programming problem. The goal is to place the string of HP amino acids on adjacent nodes in a given regular grid, so that the number of H-H contacts (hydrophobe placed on adjacent grid positions) is maximal. This leads to a numerically difficult optimization problem. We investigate the polyhedral structure of the underlying polytope to derive further cutting planes that potentially speed up the solution process.

Partners

Agnes Dittel, TU Darmstadt,

Alexander Martin, TU Darmstadt.

Related Talks

Protein Folding and Integer Programming, Workshop on Optimization and Scientific Computing, Hirschegg, Austria, 25.8.2001.

Related Publications

1. 1.Agnes Dittel, Armin Fügenschuh, Alexander Martin, Polyhedral Aspects of Self-Avoiding Walks, ZIB Technical Report ZR-11-11, 2011.
   

2. 2.Armin Fügenschuh, Von Mikrochips, Proteinen und Schulbussen – Projektproseminare im Mathematikstudium, In: Projektveranstaltungen in Mathematik, Informatik und Ingenieurwissenschaften, Wim Görts (Eds.), UVW UniversitätsVerlagWebler, Bielefeld, pp. 21 – 43, 2003.
   

3. 3.Armin Fügenschuh, Proteinfaltung, In: Mathematische Modellierung mit Schülern - Die Modellierungswoche im Kloster Höchst, Martin Kiehl, Andreas Schich, Stefan Purpus (Eds.), Zentrum für Mathematik, Bensheim, pp. 21 – 27 and 115 – 116, 2001.