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

TY - JOUR

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

AU - Steinhofel, K

AU - Skaliotis, A

AU - Albrecht, A A

PY - 2007/4/1

Y1 - 2007/4/1

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

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

U2 - 10.1016/j.cpc.2006.12.002

DO - 10.1016/j.cpc.2006.12.002

M3 - Article

VL - 176

SP - 465

EP - 470

JO - COMPUTER PHYSICS COMMUNICATIONS

JF - COMPUTER PHYSICS COMMUNICATIONS

IS - 7

ER -