Relating time complexity of protein folding simulation to approximations of folding time

K Steinhofel, A Skaliotis, A A Albrecht

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


Finkelstein and Badretclinov [A.V. Finkelstein, A.Y. Badretdinov, Rate of protein folding near the point of thermodynamic equilibrium between the coil and the most stable chain fold, Fold. Des. 2 (1997) 115-121] approximated the folding time of protein sequences of length n by exp(lambda center dot n(2/3) +/- chi center dot n(1/2)/2)ns, where lambda and chi are constants close to unity. Recently, Fu and Wang [B. Fu, W. Wang, A 2(O(n-1/d center dot log n)) time algorithm for d-dimensional protein folding in the HP-model, in: J. Daz, J. Karhumaki, A. Lepisto, D. Sannella (Eds.), Proceedings of the 31st International Colloquium on Autornata, Languages and Programming, in: Lecture Notes in Comput. Sci., vol. 3142, Springer-Verlag, Heidelberg, 2004, pp. 630644] published an exp(O(n(1-1/d)) center dot In n) algorithm for d-dimensional protein folding simulation in the HP-model, which is close to the folding time approximation by Finkelstein and Badretdinov and can be seen as a Justification of the HP-model for investigating general complexity issues of protein folding. We propose a stochastic local search procedure that is based on logarithmic simulated annealing. We obtain that after (m/delta)(a center dot D) Markov chain transitions the probability to be in a minimum energy conformation is at least 1 - delta, where m
Original languageEnglish
Pages (from-to)465 - 470
Number of pages6
Issue number7
Publication statusPublished - 1 Apr 2007


Dive into the research topics of 'Relating time complexity of protein folding simulation to approximations of folding time'. Together they form a unique fingerprint.

Cite this