Scientists and engineers employ various methods to design optimal structures, methods, programs, machines, molecules etc. One method that is gaining popularity is memetic algorithms.
What is it and how does it work?
Memetic Algorithms (MAs) are search techniques used to solve problems by mimicking molecular processes of evolution including selection, recombination, mutation and inheritance. In order to understand the basics, a few important aspects of MAs need to be considered (Figure 1).
The fitness landscape needs to be finite.
The search space of the MA is limited to the fitness landscape.
There is at least one solution in the fitness landscape .
A fitness function determines the relationship between the fitness of the genotype (or phenotype) and the fitness landscape.
[*]Selection is based on fitness.
Figure 1: A) Basic lay out of memetic algorithms. A population of individuals is randomly seeded with regard to fitness (initialized). The individuals are randomly mutated and their fitness is measured. Individuals with optimal fitness are further mutated until convergence of a local optima is reached. The process is carried out for the entire initialized population. The global optima is selected from the various local optima. B) Fitness landscape with local optima (A, B and D) and a global optima (C). In a memetic algorithm, the initial population of individual are randomly seeded and can be viewed as any of the arrows indicated in the figure.
Autodock (a molecular docking program) employs MAs in order to try and predict the orientation of a ligand within a protein receptor. A docking run with Autodock can be characterized by the following:
Finite fitness landscape: The physical properties of the protein receptor (E.g. electrostatic properties, Van der Waals interactions, desolvation energies etc.). This can be characterized as the pre-existing fitness landscape.
Search space: Confined to the protein receptor.
At least one solution: The original crystallographic pose.
Fitness function: Estimated Free Energy of Binding pose. This is determined through a combination of various interactions including Van der Waals-, electrostatic-, desolvation-, hydrogen bond- and torsional free energy.
[*]Selection (guiding function): Selection is based on fitness, i.e. The Estimated Free Energy of Binding pose.
Using Autodock as an example, a docking simulation of a ligand (molecule that binds to a protein) was run 4 times. Each time the ligand is docked, 30 populations with 250 individuals (ligands) are randomly placed within the receptor and the position of each ligand is randomly “mutated” after which the Estimated Free Energy of the pose is measured. The position of each ligand is “mutated” until a local optima of the Estimated Free Energy of a ligand is reached. The local optima of each of the four docking runs were measured and in all four runs, the convergence of the global optima (in each run) corresponded reasonably well to the crystallographic pose (RMSD<1.8). Two conclusions can be reached thus far:
1. The software can predict the best pose (biologically relevant) of a ligand in a protein with reasonable success.
2. Separate runs after random variation and selection converged on similar local optima even after random variation and selection processes in a pre-existing finite fitness landscape. The global optimum corresponded well with the original ligand pose.
It is also interesting that running the software on different occasions result in the convergence of similar ligand poses (optimal designs), even though random variation and selection processes were employed in the algorithm. Biased towards a few ends…
This software and MAs (mimicking evolutionary processes) can thus be used to design new molecules and predict optimal designs. Thus demonstrating evolution can be used to design optimal designs in pre-existing fitness landscapes.
Are there parallels with MAs and life and the universe? It should be an interesting scientific exercise to explore these possible parallels.