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

Finkelstein and Badretdinov [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(λ⋅n2/3±χ⋅n1/2/2)ns, where λ and χ are constants close to unity. Recently, Fu and Wang [B. Fu, W. Wang, A 2O(n1−1/d⋅logn) time algorithm for d-dimensional protein folding in the HP-model, in: J. Daz, J. Karhumäki, A. Lepistö, D. Sannella (Eds.), Proceedings of the 31st International Colloquium on Automata, Languages and Programming, in: Lecture Notes in Comput. Sci., vol. 3142, Springer-Verlag, Heidelberg, 2004, pp. 630–644] published an exp(O(n1−1/d)⋅lnn) 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/δ)a⋅D Markov chain transitions the probability to be in a minimum energy conformation is at least 1−δ, where m⩽b(d)⋅n is the maximum neighbourhood size (b(d) small integer), a is a small constant, and D is the maximum value of the minimum escape height from local minima of the underlying energy landscape. We note that the time bound is instance-specific, and we conjecture D<n1−1/d as a worst case upper bound. We analyse View the MathML source experimentally on selected benchmark problems for the d=2 case.