Stochastic protein folding simulation in the three-dimensional HP-model. (English) Zbl 1159.92016

Summary: We present results from three-dimensional protein folding simulations in the hydrophobic-hydrophilic (HP)-model on ten benchmark problems. The simulations are executed by a simulated annealing-based algorithm with a time-dependent cooling schedule. The neighbourhood relation is determined by the pull-move set. The results provide experimental evidence that the maximum depth \(D\) of local minima of the underlying energy landscape can be upper bounded by \(D<n^{2/3}\). The local search procedure employs the stopping criterion \((m/\delta )^{D/\gamma }\), where \(m\) is an estimation of the average number of neighbouring conformations, \(\gamma \) relates to the mean of non-zero differences of the objective function for neighbouring conformations, and \(1 - \delta \) is the confidence that a minimum conformation has been found. The bound complies with the results obtained for the ten benchmark problems.


92C40 Biochemistry, molecular biology
92-08 Computational methods for problems pertaining to biology


Full Text: DOI


[1] Aarts, E. H.L., Local Search in Combinatorial Optimization (1998), John Wiley & Sons: John Wiley & Sons New York
[2] Aichholzer, O.; Bremner, D.; Demaine, E. D.; Meijer, H.; Sacristán, V.; Soss, M., Long proteins with unique optimal foldings in the H-P model, Comp. Geom. -Theor. Appl., 25, 139-159 (2003) · Zbl 1019.92012
[3] Albrecht, A. A., A stopping criterion for logarithmic simulated annealing, Computing, 78, 55-79 (2006) · Zbl 1130.90021
[5] Anfinsen, C. B., Principles that govern the folding of protein chains, Science, 181, 223-230 (1973)
[6] Apaydin, M. S.; Brutlag, D. L.; Guestrin, C.; Hsu, D.; Latombe, J. C.; Varma, C., Stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion, J. Comp. Biol., 10, 257-281 (2003)
[7] Backofen, R., A polynomial time upper bound for the number of contacts in the HP-model on the face-centred-cubic lattice (FCC), J. Discrete Alg., 2, 161-206 (2004) · Zbl 1114.92025
[8] Bakk, A.; Dommersnes, P. G.; Hansen, A.; Høye, J. S.; Sneppen, K.; Jensen, M. H., Thermodynamics of proteins: fast folders and sharp transitions, Comput. Phys. Commun., 147, 307-312 (2002) · Zbl 0994.92020
[9] Berger, B.; Leighton, T., Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete, J. Comput. Biol., 5, 27-40 (1998)
[10] Beutler, T. C.; Dill, K. A., A fast conformational search strategy for finding low energy structures of model proteins, Protein Sci., 5, 2037-2043 (1996)
[11] Blazewicz, J.; Lukasiak, P.; Milostan, M., Application of tabu search strategy for finding low energy structure of protein, Artif. Intell. Med., 35, 135-145 (2005)
[12] Brylinski, M.; Konieczny, L.; Roterman, I., Hydrophobic collapse in (in silico) protein folding, Comput. Biol. Chem., 30, 255-267 (2006) · Zbl 1098.92024
[13] Catoni, O., Rough large deviation estimates for simulated annealing: applications to exponential schedules, Ann. Prob., 20, 1109-1146 (1992) · Zbl 0755.60021
[14] Černy, V., A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm, J. Optim. Theor. Appl., 45, 41-51 (1985) · Zbl 0534.90091
[15] Chen, N.; Liu, W.; Feng, J., Sufficient and necessary condition for the convergence of stochastic approximation algorithms, Stat. Prob. Lett., 76, 203-210 (2006) · Zbl 1093.62079
[16] Chiang, T. S.; Chow, Y. Y., A limit theorem for a class of inhomogeneous Markov processes, Ann. Prob., 17, 1483-1502 (1989) · Zbl 0687.60070
[17] Clote, P., (Wiedermann, J., Proceedings of the 26th International Colloquium on Automata, Languages and Programming, LNCS 1644 (1999), Springer-Verlag: Springer-Verlag Heidelberg), 240-249
[18] Cooper, L. R.; Corne, D. W.; Crabbe, M. J.C., Use of a novel hill-climbing genetic algorithm in protein folding simulations, Comput. Biol. Chem., 27, 575-580 (2003)
[19] Dill, K. A.; Bromberg, S.; Yue, K.; Fiebig, K. M.; Yee, D. P.; Thomas, P. D.; Chan, H. S., Principles of protein folding—a perspective from simple exact models, Protein Sci., 4, 561-602 (1995)
[20] Eastman, P.; Grønbech-Jensen, N.; Doniach, S., Simulation of protein folding by reaction path annealing, J. Chem. Phys., 114, 3823-3841 (2001)
[21] Eastwood, M. P.; Hardin, C.; Luthey-Schulten, Z.; Wolynes, P. G., Evaluating protein structure-prediction schemes using energy landscape theory, IBM J. Res. Dev., 45, 475-497 (2001)
[22] Finkelstein, A. V.; Badretdinov, A. Y., Rate of protein folding near the point of thermodynamic equilibrium between the coil and the most stable chain fold, Fold. Des., 2, 115-121 (1997)
[23] Fu, B.; Wang, W., A \(2^{O(n^{1 - - 1 / d} \cdot \log n)}\) time algorithm for \(d\)-dimensional protein folding in the HP-model, (Daz, J.; Karhumäki, J.; Lepistö, A.; Sannella, D., Proceedings of the 31st International Colloquium on Automata, Languages and Programming, LNCS 3142 (2004), Springer-Verlag: Springer-Verlag Heidelberg), 630-644 · Zbl 1099.68130
[24] Galzitskaya, O. V.; Garbuzynskiy, S. O.; Ivankov, D. N.; Finkelstein, A. V., Chain length is the main determinant of the folding rate for proteins with three-state folding kinetics, Proteins, 51, 162-166 (2003)
[25] Garnier, J.; Kallel, L., Efficiency of local search with multiple local optima, SIAM J. Discrete Math., 15, 122-141 (2002) · Zbl 0992.68039
[26] Greenberg, H. J.; Hart, W. E.; Lancia, G., Opportunities for combinatorial optimization in computational biology, INFORMS J. Comput., 16, 211-231 (2004) · Zbl 1239.90003
[27] Hajek, B., Cooling schedules for optimal annealing., Math. Oper. Res., 13, 311-329 (1988) · Zbl 0652.65050
[28] Hales, T. C., A proof of the Kepler conjecture, Ann. Math., 162, 1065-1185 (2005) · Zbl 1096.52010
[29] Hansmann, U. H.E.; Okamoto, Y., Monte Carlo simulations in generalized ensemble: multicanonical algorithm versus simulated tempering, Phys. Rev. E, 54, 5863-5865 (1996)
[30] Hart, W. E.; Istrail, S., Lattice and off-lattice side chain models of protein folding: linear time structure prediction better than 86
[31] Heun, V., Approximate protein folding in the HP side chain model on extended cubic lattices, Discrete Appl. Math., 127, 163-177 (2003) · Zbl 1014.92013
[32] Ivankov, D. N.; Garbuzynskiy, S. O.; Alm, E.; Plaxco, K. W.; Baker, D.; Finkelstein, A. V., Contact order revisited: influence of protein size on the folding rate, Protein Sci., 12, 2057-2062 (2003)
[33] Johnson, A. W.; Jacobson, S. H., On the convergence of generalized hill climbing algorithms, Discrete Appl. Math., 119, 37-57 (2002) · Zbl 0994.90115
[34] Kawai, H.; Kikuchi, T.; Okamoto, Y., A prediction of tertiary structures of peptide by the Monte Carlo simulated annealing method, Protein Eng., 3, 85-94 (1989)
[35] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[36] Klepeis, J. L.; Pieja, M. J.; Floudas, C. A., A new class of hybrid global optimization algorithms for peptide structure prediction: integrated hybrids, Comput. Phys. Commun., 151, 121-140 (2003) · Zbl 1196.90134
[37] Lee, C. L.; Stell, G.; Wang, J., First-passage time distribution and non-Markovian diffusion dynamics of protein folding, J. Chem. Phys., 118, 959-968 (2003)
[38] Leite, V. B.P.; Onuchic, J. N.; Stell, G.; Wang, J., Probing the kinetics of single molecule protein folding, Biophys. J., 87, 3633-3641 (2004)
[39] Lesh, N.; Mitzenmacher, M.; Whitesides, S., A complete and effective move set for simplified protein folding, (Proceedings of the 7th Annual International Conference on Computational Biology (2003), ACM Press: ACM Press New York), 188-195
[40] Li, M. S.; Klimov, D. K.; Thirumalai, D., Thermal denaturation and folding rates of single domain proteins: size matters, Polymer, 45, 573-579 (2004)
[41] Li, Z.; Scheraga, H. A., Monte Carlo-minimization approach to the multiple-minima problem in protein folding, Proc. Natl. Acad. Sci. U.S.A., 84, 6611-6615 (1987)
[42] Locatelli, M., Convergence and first hitting time of simulated annealing algorithms for continuous global optimization, Math. Meth. Oper. Res., 54, 171-199 (2001) · Zbl 1031.90071
[43] Löwe, M., Simulated annealing with time dependent energy function via Sobolev inequalities, Stoch. Proc. Appl., 63, 221-233 (1996) · Zbl 0910.60060
[44] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equation of state calculations by fast computing machines, J. Chem. Phys., 6, 1087-1092 (1953) · Zbl 1431.65006
[45] Milostan, M.; Lukasiak, P.; Dill, K. A.; Blazewicz, A., A tabu search strategy for finding low energy structures of proteins in HP-model, (Proceedings of the 7th Annual International Conference on Computational Biology (2003), ACM Press: ACM Press New York), 205-206
[46] Moore, J. W.; Pearson, R. G., Kinetics and Mechanism (1981), John Wiley & Sons: John Wiley & Sons New York
[47] Nayak, A.; Sinclair, A.; Zwick, U., Spatial codes and the hardness of string folding problems, J. Comput. Biol., 6, 13-36 (1999)
[48] Neumaier, A., Molecular modeling of proteins and mathematical prediction of protein structure, SIAM Rev., 39, 407-460 (1997) · Zbl 0939.92013
[49] Paine, G. H.; Scheraga, H. A., Prediction of the native conformation of a polypeptide by a statistical-mechanical procedure. I. Backbone structure of enkephalin, Biopolymers, 24, 1391-1436 (1985)
[50] Pardalos, P. M.; Liu, X.; Xue, G., Protein conformation of a lattice model using tabu search, J. Global Optim., 11, 55-68 (1997) · Zbl 0891.90169
[51] Paterson, M.; Przytycka, T., On the complexity of string folding, Discrete Appl. Math., 71, 217-230 (1996) · Zbl 0879.92010
[52] Rabow, A. A.; Scheraga, H. A., Improved genetic algorithm for the protein folding problem by use of a Cartesian combination operator, Protein Sci., 5, 1800-1815 (1996)
[53] Reidys, C. M.; Stadler, P. F., Combinatorial landscapes, SIAM Rev., 44, 3-54 (2002) · Zbl 0996.92026
[54] Sali, A.; Shakhnovich, E.; Karplus, M., How does a protein fold?, Nature, 369, 248-251 (1994)
[55] Schiemann, R.; Bachmann, M.; Janke, W., Exact sequence analysis for three-dimensional hydrophobic-polar lattice proteins, J. Chem. Phys., 122, 1-10 (2005)
[56] Shell, M. S.; Debenedetti, P. G.; Panagiotopoulos, A. Z., Computational characterization of the sequence landscape in simple protein alphabets, Proteins, 62, 232-243 (2006)
[57] Sinclair, A., Algorithms for Random Generation and Counting: A Markov Chain Approach (1993), Birkhäuser: Birkhäuser Boston · Zbl 0780.68096
[58] Steinhöfel, K.; Skaliotis, A.; Albrecht, A. A., Relating time complexity of protein folding simulation to approximations of folding time, Comput. Phys. Commun., 176, 165-170 (2007)
[59] Steinhöfel, K.; Skaliotis, A.; Albrecht, A. A., Stochastic protein folding simulation in the \(d\)-dimensional HP-model, (Proceedings of the 1st International Conference on Bioinformatics Research and Development, LNBI 4414 (2007), Springer-Verlag: Springer-Verlag Heidelberg), 381-394 · Zbl 1159.92016
[60] Unger, R.; Moult, J., Genetic algorithms for protein folding simulations, J. Mol. Biol., 231, 75-81 (1993)
[61] Voelz, V. A.; Dill, K. A., Exploring zipping and assembly as a protein folding principle, Proteins, 66, 877-888 (2007)
[62] Wang, J., The complex kinetics of protein folding in wide temperature ranges, Biophys. J., 87, 2164-2171 (2004)
[63] Wilson, S. R.; Cui, W.; Moskowitz, J. W.; Schmidt, K. E., Conformational analysis of flexible molecules: location of the global minimum energy conformation by the simulated annealing method, Tetrahedron Lett., 29, 4373-4376 (1988)
[64] Zhu, Y.; Fu, X.; Wang, T.; Tamura, A.; Takada, S.; Saven, J. G., Guiding the search for a protein’s maximum rate of folding, Chem. Phys., 307, 99-109 (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.