Asymptotic Hitting Time for a Simple Evolutionary Model of Protein Folding

DOI10.1239/JAP/1110381369MaRDI QIDQ5312839zbMATH OpenOpenAlexFDO

Authors Véronique Ladret

Publication date 25 August 2005

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0308237

zbMATH Keywords

evolutionary algorithmMarkov chain

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Biophysics (92C05) Protein sequences, DNA sequences (92D20)

Abstract: We consider two versions of a simple evolutionary algorithm model for protein folding at temperature zero: 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 each algorithm we prove a law of large numbers, a central limit theorem and compare the performance of the two models.

Recommendations

• scientific article; zbMATH DE number 1405648
• On the analysis of the \((1+1)\) evolutionary algorithm
• Some analyses about the time complexity of evolutionary algorithms
• Some analysis about the time complexity of evolutionary algorithms
• On some theoretical properties of \((1+1)\) evolutionary algorithms

Cites work

• Asymptotic convergence of genetic algorithms
• scientific article; zbMATH DE number 1100794 (Why is no real title available?)
• scientific article; zbMATH DE number 1552333 (Why is no real title available?)
• On the analysis of the \((1+1)\) evolutionary algorithm
• On the effect of selection in genetic algorithms
• On the stability of interacting processes with applications to filtering and genetic algorithms
• Sharp asymptotic results for simplified mutation-selection algorithms
• Techniques for bounding the convergence rate of genetic algorithms
• The dynamics of mutation-selection algorithms with large population sizes

Cited in

(5)

• Runtime analysis of ant colony optimization with best-so-far reinforcement
• Solving problems with unknown solution length at almost no extra cost
• The (1+1) elitist black-box complexity of LeadingOnes
• The impact of random initialization on the runtime of randomized search heuristics
• Modeling the evolution space of breakage fusion bridge cycles with a stochastic folding process

This page was built for publication: Asymptotic Hitting Time for a Simple Evolutionary Model of Protein Folding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5312839)