Landscape analysis for protein-folding simulation in the H-P model

K Steinhofel, A Skaliotis, A A Albrecht, P Bucher (Editor), B M E Moret (Editor)

Research output: Chapter in Book/Report/Conference proceedingConference paper

4 Citations (Scopus)


The hydrophobic-hydrophilic (H-P) model for protein folding was introduced by Dill et al. [7]. A problem instance consists of a sequence of amino acids, each labeled as either hydrophobic (H) or hydrophilic (P). The sequence must be placed on a 2D or 3D grid without overlapping, so that adjacent amino acids in the sequence remain adjacent in the grid. The goal is to minimize the energy, which in the simplest variation corresponds to maximizing the number of adjacent hydrophobic pairs. The protein folding problem in the H-P model is NP-hard in both 2D and 3D. Recently, Fu and Wang [10] proved an exp(O(n(1-1/d)) (.) lnn) algorithm for d-dimensional protein folding simulation in the HP-model. Our preliminary results on stochastic search applied to protein folding utilize complete move sets proposed by Lesh et al. [15] and Blazewicz et al. [4]. We obtain that after (m/delta)(O(Gamma)) Markov chain transitions, the probability to be in a minimum energy conformation is at least 1 - delta, where m is the maximum neighbourhood size and Gamma is the maximum value of the minimum escape height from local minima of the underlying energy landscape. We note that the time bound depends on the specific Id instance. Based on [10] we conjecture Gamma
Original languageEnglish
Title of host publicationAlgorithms in Bioinformatics, Proceedings
Place of PublicationBERLIN
Pages252 - 261
Number of pages10
Volume4175 LNBI
ISBN (Print)0302-9743
Publication statusPublished - 2006
Event6th International Workshop on Algorithms in Bioinformatics (WABI 2006) - Zurich, Switzerland
Duration: 11 Sept 000613 Sept 0006

Publication series



Conference6th International Workshop on Algorithms in Bioinformatics (WABI 2006)


Dive into the research topics of 'Landscape analysis for protein-folding simulation in the H-P model'. Together they form a unique fingerprint.

Cite this