Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices

TitleApproximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices
Publication TypeTechnical Report
Year of Publication1998
AuthorsHeun, V.
Other Numbers1147
KeywordsApproximation Algorithm, Extended Cubic Lattice, HP Model, HP Side Chain Model, Polymer Structure Prediction, Protein Folding
Abstract

One of the most important open problems in computational molecular biology is the prediction of the conformation of a protein based on its amino acid sequence. In this paper, we design approximation algorithms for structure prediction in the so-called HP side chain model. The major drawback of the standard HP side chain model is the bipartiteness of the cubic lattice. To eliminate this drawback, we introduce the extended cubic lattice which extends the cubic lattice by diagonals in the plane. For this lattice, we present two linear algorithms with approximation ratios of 59/70 and 37/42, respectively. The second algorithm is designed for a 'natural' subclass of proteins, which covers more than 99.5% of all sequenced proteins. This is the first time that a protein structure prediction algorithm is designed for a 'natural' subclass of all combinatoric possible sequences.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1998/tr-98-029.pdf
Bibliographic Notes

ICSI Technical Report TR-98-029

Abbreviated Authors

V. Heun

ICSI Research Group

Algorithms

ICSI Publication Type

Technical Report