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

K Steinhofel; A Skaliotis; A A Albrecht; P Bucher; B M E Moret

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)

Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

4 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Algorithms in Bioinformatics, Proceedings
Place of Publication	BERLIN
Publisher	Springer
Pages	252 - 261
Number of pages	10
Volume	4175 LNBI
ISBN (Print)	0302-9743
Publication status	Published - 2006
Event	6th International Workshop on Algorithms in Bioinformatics (WABI 2006) - Zurich, Switzerland Duration: 11 Sept 0006 → 13 Sept 0006

Publication series

Name	LECTURE NOTES IN COMPUTER SCIENCE

Conference

Conference	6th International Workshop on Algorithms in Bioinformatics (WABI 2006)
Country/Territory	Switzerland
City	Zurich
Period	11/09/0006 → 13/09/0006

Cite this

@inbook{1764452a89de4d9b873cb8e79165429d,

title = "Landscape analysis for protein-folding simulation in the H-P model",

abstract = "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 ",

author = "K Steinhofel and A Skaliotis and Albrecht, {A A} and P Bucher and Moret, {B M E}",

year = "2006",

language = "English",

isbn = "0302-9743",

volume = "4175 LNBI",

series = "LECTURE NOTES IN COMPUTER SCIENCE",

publisher = "Springer",

pages = "252 -- 261",

booktitle = "Algorithms in Bioinformatics, Proceedings",

note = "6th International Workshop on Algorithms in Bioinformatics (WABI 2006) ; Conference date: 11-09-0006 Through 13-09-0006",

}

Steinhofel, K, Skaliotis, A, Albrecht, AA, Bucher, P (ed.) & Moret, BME (ed.) 2006, Landscape analysis for protein-folding simulation in the H-P model. in Algorithms in Bioinformatics, Proceedings. vol. 4175 LNBI, LECTURE NOTES IN COMPUTER SCIENCE, Springer, BERLIN, pp. 252 - 261, 6th International Workshop on Algorithms in Bioinformatics (WABI 2006), Zurich, Switzerland, 11/09/0006.

TY - CHAP

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

AU - Steinhofel, K

AU - Skaliotis, A

AU - Albrecht, A A

A2 - Bucher, P

A2 - Moret, B M E

PY - 2006

Y1 - 2006

N2 - 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

AB - 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

UR - http://www.scopus.com/inward/record.url?scp=33750257150&partnerID=8YFLogxK

M3 - Conference paper

SN - 0302-9743

VL - 4175 LNBI

T3 - LECTURE NOTES IN COMPUTER SCIENCE

SP - 252

EP - 261

BT - Algorithms in Bioinformatics, Proceedings

PB - Springer

CY - BERLIN

T2 - 6th International Workshop on Algorithms in Bioinformatics (WABI 2006)

Y2 - 11 September 0006 through 13 September 0006

ER -

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

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this