Protein folding

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 simplyfications, 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.


  • TU Darmstadt

Related talks

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

Related publications

  • Agnes Dittel, Armin Fügenschuh, Alexander Martin, Polyhedral Aspects of Self-Avoiding Walks , ZIB Technical Report ZR-11-11, 2011.
  • Armin Fügenschuh, Von Mikrochips, Proteinen und Schulbussen – Projektproseminare im Mathematikstudium, In: Projektveranstaltungen in Mathematik, Informatik und Ingenieurwissenschaften, Wim Görts (Ed.), UVW UniversitätsVerlagWebler, Bielefeld, pp. 21 – 43, 2003.
  • 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.

This website uses cookies. There are two types of cookies: The first type supports the basic functionality of our website. The second allows us to improve our content for you by saving and analyzing pseudonymised user data. Since this second type is technically not required to run the website, you can withdraw your consent to those cookies at any time. For more information please visit our pages on data protection.


These cookies are needed for a smooth operation of our website.


For statistical reasons, we use the platform Matomo to analyse the user flow with the help of website users‘ pseudonymised data. This allows us to optimize website content.

Name Purpose Lifetime Type Provider
_pk_id Used to store a few details about the user such as the unique visitor ID. 13 months HTML Matomo
_pk_ref Used to store the attribution information, the referrer initially used to visit the website. 6 months HTML Matomo
_pk_ses Short lived cookie used to temporarily store data for the visit. 30 minutes HTML Matomo