zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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/δ) D/γ , where m is an estimation of the average number of neighbouring conformations, γ relates to the mean of non-zero differences of the objective function for neighbouring conformations, and 1-δ is the confidence that a minimum conformation has been found. The bound complies with the results obtained for the ten benchmark problems.
MSC:
92C40Biochemistry, molecular biology
92-08Computational methods (appl. to natural sciences)
References:
[1]Aarts, E. H. L.: Local search in combinatorial optimization, (1998)
[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 · doi:10.1016/S0925-7721(02)00134-7
[3]Albrecht, A. A.: A stopping criterion for logarithmic simulated annealing, Computing 78, 55-79 (2006) · Zbl 1130.90021 · doi:10.1007/s00607-006-0167-1
[4]Albrecht, A.A., Steinhöfel, K., 2006. Run-time estimates for protein folding simulation in the H – P model. In: Online Proceedings of the 9th International Symposium on Artificial Intelligence, Mathematics, Fort Lauderdale, Florida, 2006, http://anytime.cs.umass.edu/aimath06/.
[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 · doi:10.1016/S1570-8667(03)00076-5
[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 · doi:10.1016/S0010-4655(02)00293-X
[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 · doi:10.1016/j.compbiolchem.2006.04.007
[13]Catoni, O.: Rough large deviation estimates for simulated annealing: applications to exponential schedules, Ann. prob. 20, 1109-1146 (1992) · Zbl 0755.60021 · doi:10.1214/aop/1176989682
[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 · doi:10.1007/BF00940812
[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 · doi:10.1016/j.spl.2005.07.020
[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 · doi:10.1214/aop/1176991169
[17]Clote, P.: J.wiedermannproceedings of the 26th international colloquium on automata, languages and programming, LNCS 1644, Proceedings of the 26th international colloquium on automata, languages and programming, LNCS 1644, 240-249 (1999)
[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 2O(n1--1/d·log&ApplyFunction;n) time algorithm for d-dimensional protein folding in the HP-model, Proceedings of the 31st international colloquium on automata, languages and programming, LNCS 3142, 630-644 (2004)
[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 · doi:10.1137/S0895480199355225
[26]Greenberg, H. J.; Hart, W. E.; Lancia, G.: Opportunities for combinatorial optimization in computational biology, INFORMS J. Comput. 16, 211-231 (2004)
[27]Hajek, B.: Cooling schedules for optimal annealing., Math. oper. Res. 13, 311-329 (1988) · Zbl 0652.65050 · doi:10.1287/moor.13.2.311
[28]Hales, T. C.: A proof of the Kepler conjecture, Ann. math. 162, 1065-1185 (2005) · Zbl 1096.52010 · doi:10.4007/annals.2005.162.1065
[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% of optimal, J. comput. Biol. 4, 241-260 (1997)
[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 · doi:10.1016/S0166-218X(02)00382-7
[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 · doi:10.1016/S0166-218X(01)00264-5
[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.; Jr., M. P. Vecchi: Optimization by simulated annealing, Science 220, 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[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 · doi:10.1016/S0010-4655(02)00735-X
[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, , 188-195 (2003)
[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. USA 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 · doi:10.1007/s001860100149
[43]Löwe, M.: Simulated annealing with time dependent energy function via Sobolev inequalities, Stoch. proc. Appl. 63, 221-233 (1996) · Zbl 0910.60060 · doi:10.1016/0304-4149(96)00070-1
[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)
[45]Milostan, M.; Lukasiak, P.; Dill, K. A.; Blazewicz, A.: A tabu search strategy for finding low energy structures of proteins in HP-model, , 205-206 (2003)
[46]Moore, J. W.; Pearson, R. G.: Kinetics and mechanism, (1981)
[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 · doi:10.1137/S0036144594278060 · doi:http://www.siam.org/sam-bin/dbq/toc/SIREV/39/3
[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 · doi:10.1023/A:1008228509535
[51]Paterson, M.; Przytycka, T.: On the complexity of string folding, Discrete appl. Math. 71, 217-230 (1996) · Zbl 0879.92010 · doi:10.1016/S0166-218X(96)00065-0 · doi:http://www.elsevier.com/locate/dam
[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 · doi:10.1137/S0036144501395952
[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)
[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, , 381-394 (2007)
[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)