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

Albrecht, A. A.; Skaliotis, A.; Steinhöfel, K.

Comput. Biol. Chem. 32, No. 4, 248-255 (2008).

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.

MSC:

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

Keywords:

HP-model; landscape analysis; stochastic local search; simulated annealing

Software:

kepler98

References:

[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)