Protein Folding in the HP Model on Grid Lattices with Diagonals (Extended Abstract)
Hans-Joachim Böckenhauer, Dirk Bongartz · Mathematical Foundations of Computer Science · 2004
The protein folding problem, i.e., the computational predic- tion of the three-dimensional structure of a protein from its amino acid sequence, is one of the most important and challenging problems in com- putational biology. Since a complete simulation of the folding process of a protein is far too complex to handle, one tries to find an approximate solution by using a simplified, abstract model. One of the most popular models is the so-called HP model, where the hydrophobic interactions between the amino acids are considered to be the main force in the fold- ing process, and furthermore the folding space is modelled by a two- or three-dimensional grid lattice. In this paper, we will present some approximation algorithms for the pro- tein folding problem in the HP model on an extended grid lattice with plane diagonals. The choice of this kind of lattice removes one of the ma- jor drawbacks of the original HP model, namely the bipartiteness of the grid which severely restricts the set of possible foldings. Our algorithms achieve an approximation ratio of 26 ≈ 1.733 for the two-dimensional and of 8 =1 .6 for the three-dimensional lattice. This improves sig- nificantly over the best previously known approximation ratios for the protein folding problem in the HP model on any lattice.