Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-16T05:23:49.307Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Hitting Time for a Simple Evolutionary Model of Protein Folding

Part of: Markov processes Physiological, cellular and medical topics Limit theorems

Published online by Cambridge University Press:  14 July 2016

Véronique Ladret
Véronique Ladret*
Affiliation:
Université Claude Bernard Lyon 1
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider two versions of a simple evolutionary algorithm (EA) model for protein folding at zero temperature, namely the (1 + 1)-EA on the LeadingOnes problem. In this schematic model, the structure of the protein, which is encoded as a bit-string of length n, is evolved to its native conformation through a stochastic pathway of sequential contact bindings. We study the asymptotic behavior of the hitting time, in the mean case scenario, under two different mutations: the one-flip, which flips a unique bit chosen uniformly at random in the bit-string, and the Bernoulli-flip, which flips each bit in the bit-string independently with probability c/n, for some c ∈ ℝ+ (0 ≤ c ≤ n). For each algorithm, we prove a law of large numbers, a central limit theorem, and compare the performance of the two models.

Keywords

Evolutionary algorithmMarkov chainprotein folding

MSC classification

Secondary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 60F05: Central limit and other weak theorems 92D20: Protein sequences, DNA sequences 92C05: Biophysics
Type
Research Papers
Information
Journal of Applied Probability , Volume 42 , Issue 1 , March 2005 , pp. 39 - 51
Copyright
© Applied Probability Trust 2005 

References

Anfinsen, C. B. (1973). Principles that govern the folding of a protein chain (Nobel lecture). Science 191, 223–230.Google Scholar
Bäck, T. (1993). Optimal mutation rates in genetic search. In Proc. 5th Internat. Conf. Genet. Algorithms, ed. Forrest, S., Morgan Kaufmann, San Fransisco, pp. 2–8.Google Scholar
Bakk, A. et al. (2000). Pathways in two-state protein folding. Biophys. J. 79, 2722–2727.Google Scholar
Bérard, J. and Bienvenüe, A. (2000). Convergence of a genetic algorithm with finite population. In Mathematics and Computer Science (Versailles, 2000), Birkhäuser, Basel, pp. 155–163.Google Scholar
Bérard, J. and Bienvenüe, A. (2003). Sharp asymptotic results for simplified mutation-selection algorithms. Ann. Appl. Prob. 13, 1534–1568.Google Scholar
Binder, K. (1987). Applications of the Monte Carlo Method in Statistical Physics. Springer, Berlin.CrossRefGoogle Scholar
Cerf, R. (1996). The dynamics of mutation-selection algorithms with large population sizes. Ann. Inst. H. Poincaré Prob. Statist. 32, 455–508.Google Scholar
Cerf, R. (1998). Asymptotic convergence of genetic algorithms. Adv. Appl. Prob. 30, 521–550.Google Scholar
Del Moral, P. and Guionnet, A. (2001). On the stability of interacting processes with applications to filtering and genetic algorithms. Ann. Inst. H. Poincaré Prob. Statist. 37, 155–194.CrossRefGoogle Scholar
Dill, K. A., Feibig, K. M. and Chan, H. S. (1993). Cooperativity in protein folding kinetics. Proc. Nat. Acad. Sci. USA 90, 1942–1942.Google Scholar
Droste, S., Jansen, T. and Wegener, I. (1998). A rigorous complexity analysis of the (1+1) evolutionary algorithm for linear functions with boolean inputs. In Proc. IEEE Internat. Conf. Evolutionary Comput. (ICEC'98). IEEE Press, Piscataway, NJ, pp. 499–504.Google Scholar
Droste, S., Jansen, T. and Wegener, I. (2002). On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci. 276, 51–81.CrossRefGoogle Scholar
Garnier, J., Kallel, L. and Schoenauer, M. (1999). Rigorous hitting times for binary mutations. Evolutionary Comput. 7, 173–203.CrossRefGoogle Scholar
Jansen, T. and Wegener, I. (2001). How to cope wih plateaus of constant fitness and when to reject strings of the same fitness. IEEE Trans. Evolutionary Comput. 5, 589–599.Google Scholar
Levinthal, C. (1968). Are there pathways for protein folding? J. Chim. Phys. Phys.-Chim. Biol. 65, 44–45.CrossRefGoogle Scholar
Mazza, C. and Piau, D. (2001). On the effect of selection in genetic algorithms. Random Structures Algorithms 18, 185–200.Google Scholar
Mühlenbein, H. (1992). How genetic algorithms really work: I. Mutation and hill-climbing. In Parallel Problem Solving from Nature PPSN II, eds Männer, R. and Manderick, R., North-Holland, Amsterdam, pp. 15–25.Google Scholar
Rabinovich, Y. and Wigderson, A. (1999). Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms 14, 111–138.3.0.CO;2-6>CrossRefGoogle Scholar
Rudolph, G. (1997). Convergence Properties of Evolutionary Algorithms. Kovac, Hamburg.Google Scholar
Schellman, J. A. (1958). The factors affecting the stability of hydrogen-bounded polypeptide structures in solution. J. Phys. Chem. 62, 1485–1494.CrossRefGoogle Scholar