Memetic Algorithms, Convergence and Pre-existing Fitness Landscapes

[Techne]

Memetic Algorithms (MAs) (good paper) are search techniques used to solve problems by mimicking molecular processes of evolution including selection, recombination, mutation and inheritance.

A few important aspects of MAs (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 (Figure 2).
• A fitness function determines the relationship between the fitness of the genotype (or phenotype) and the fitness landscape.
• Selection is based on fitness.

Image
Figure 1: 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.

Figure 2: 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.​

Various molecular docking programs employ genetic algorithms in order to try and predict the orientation of a ligand within a protein receptor. Autodock employs a MA for this purpose. A good docking program is one that can reproduce an existing crystallographic pose with reasonable success. The Root Means Squared Deviation (RMSD) of a docked ligand compared the to the crystallographic pose is generally used as a good indicator. A RMSD value less than 2 is considered a success. In the case of the Autodock software, the global optima is supposed to correlate with the crystallographic pose (RMSD <2)

As an example to illustrate, Colchicine binds to tubulin and interferes with tubulin dynamics by inhibiting tubulin polymerization. Colchicine binds at a position between the alpha and beta tubulin dimer (Figures 3 and 4).

Image
Figure 3: Colchicine binding site.

[URL="http://www.scienceforums.net/forum/picture.php?albumid=50&pictureid=371"]Image[/URL]
Figure 4: Colchicine binding cavity.[/CENTER]

A docking run with Autodock can be characterized by the following:
[LIST]
[*][B]Finite fitness landscape:[/B] The physical properties of the protein receptor (E.g. electrostatic properties, Van der Waals interactions and desolvation energies). Pre-existing fitness landscape.
[*][B]Search space:[/B] Confined to the protein receptor.
[*][B]At least one solution:[/B] Crystallographic pose.
[*][B]Fitness function:[/B] 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.
[*][B]Selection (guiding function):[/B] Selection is based on fitness
[/LIST]

Using Autodock, Colchicine was "docked" 4 times into the tubulin receptor. Each time the ligand is docked, 30 populations with 250 individuals (ligands) are randomly placed within the receptor. The local optima of each population is determined (blue bar graph). The results revealed the following (Figures 5a-d).

[CENTER][URL="http://www.scienceforums.net/forum/picture.php?albumid=50&pictureid=375"]Image[/URL]
Figure 5a: Run 1

[URL="http://www.scienceforums.net/forum/picture.php?albumid=50&pictureid=376"]Image[/URL]
Figure 5b: Run 2

[URL="http://www.scienceforums.net/forum/picture.php?albumid=50&pictureid=377"]Image[/URL]
Figure 5c: Run 3
[URL="http://www.scienceforums.net/forum/picture.php?albumid=50&pictureid=378"]
Image[/URL]
Figure 5d: Run 4[/CENTER]

All four runs converged on a the same global optima which also corresponded reasonably well to the crystallographic pose (RMSD<1.8). Various local optima were also repeatedly reached. Can this process of evolution be viewed to be analogous to the evolution of life?

A few observations:
[B][U]A) The Memetic Algorithms of life.[/U][/B]
[B]a)[/B] A genetic code that is optimized for random searches.
[B]b)[/B] Quality control systems (DNA repair, protein quality, programmed cell death, cell cycle control).
[B]c)[/B] Variation inducers (Cytosine deaminases, Low vs High fidelity polymerase induction, gene conversion, homologous recombination).

[B][U]B) Examples of convergence in the evolution of life.[/U][/B]
Running MAs in pre-existing fitness landscapes result in the convergence of various local optima, with the global optima being the best of the local optima.

Evolutionary history is filled with examples of convergence (local optima). These include the following:
[B]a)[/B] The spectacular convergence of abiogenesis into a universal optimized genetic code and life's memetic algorithms.
[B]b)[/B] Structural convergence:
[LIST]
[*][URL="http://www.thegreatstory.org/convergence.pdf"]Nice article[/URL] showing a sundry of examples of convergent evolution.
[/LIST]

c) Molecular convergence
[LIST]
[*][URL="http://www.ebi.ac.uk/interpro/potm/2004_1/Page2.htm"]Carbonic anhydrases[/URL]
[*][URL="http://www.pnas.org/content/105/37%20/13959.full.pdf+html"]Prestin[/URL]
[*][URL="http://en.wikipedia.org/wiki/Convergent_evolution"]More examples[/URL]
[/LIST]

C) Pre-existing fitness landscapes and the evolution of life.
The fitness of the docking pose of the ligand in the above example is dependent on the pre-existing properties of the receptor protein. These properties include:
[LIST]
[*]Van der Waals energy
[*]Electrostatic energy
[*]Desolvation energy
[*]Hydrogen bond energy
[*]Torsional free energy
[/LIST]

These are all combined to determine the fitness (binding energy) of the ligand (Figure 6).

[CENTER][IMG]http://www.scienceforums.net/forum/picture.php?albumid=50&pictureid=372
Figure 6: Convergence of local optima of Colchicine in the pre-existing fitness landscape of the tubulin protein receptor Fitness (binding energy) is measured by Van der Waals-, Electrostatic-, Desolvation-, Hydrogen bond - and Torsional free energy. Replaying the docking run yields similar results every time.​

Standard evolutionary theory describes fitness as the capability of an individual of a certain genotype to reproduce. What are the properties of the pre-existing fitness landscape of life that determines the fitness of life forms?

Should these properties include the following?

• Self-replication
• Intelligence (Ability to process information - genetics, proteomics, metabolomics)
• Agency (Ability to manipulate information)
• Complexity (Emergence of complexity seems to be the first rule of evolution)

What are these properties composed of?
Perhaps elemental proto-experiences (PEs) as phenomenal aspects that are properties of elementary particle (superimposed) described in this paper? Can it connect quantum physics, consciousness (article) and evolution?

A "docking" (replaying the tape of life) run with such a simulation can be characterized by the following :
Finite fitness landscape: The physical properties of the universe (Mass, spin, charge and proto-experiences superimposed as elementary particles. The pre-existing fitness landscape.
Search space: Confined to the universe.
At least one solution: Self-replication.
Fitness function: Reproduction success. This is determined through a combination of various interactions including self-replication, intelligence, agency and emergence of complexity.
Selection (guiding function): Selection is based on fitness.


What would a "docking" run of life look like if we run it over and over with a pre-existing fitness landscape and universal memetic genetic algorithms (Figure 7)?

Figure 7: Convergence of local optima in a fitness landscape whereby fitness is measured by reproduction, intelligence, agency and complexity. If life's memetic algorithms are comparable to a "docking" run, it should yield similar local optima in pre-existing fitness landscapes every time the simulation is run.​

Any thoughts?​

All images in one thread​

 

[Techne]

We observe many preadaptations for multicellularity in primitive unicellular organisms. Also several toolkits (also preadaptations) for the development of body plans (Hox genes) and sensory organs in animals at the base of the metazoan tree.
Also, spectacular examples of convergence are observed in nature.

Take this into consideration and take a look at how stem cells become specialized.
Many Paths, Few Destinations: How Stem Cells Decide What They'll Become.

When exposed to a growth factor, a blood stem cell, represented by a blue marble, falls into a new "attractor state," depicted as a valley in a landscape, to become a red blood cell. Different influences, such as differentiation factors, can lead stem cells to the same attractor state, but each cell can take very different paths though the landscape to get there (just as a marble might take a different path each time it rolls down a hill). (Credit: Children's Hospital Boston)​

How does a stem cell decide what specialized identity to adopt -- or simply to remain a stem cell? A new study suggests that the conventional view, which assumes that cells are "instructed" to progress along prescribed signaling pathways, is too simplistic. Instead, it supports the idea that cells differentiate through the collective behavior of multiple genes in a network that ultimately leads to just a few endpoints -- just as a marble on a hilltop can travel a nearly infinite number of downward paths, only to arrive in the same valley.

The findings, published in the May 22 issue of Nature, give a glimpse into how that collective behavior works, and show that cell populations maintain a built-in variability that nature can harness for change under the right conditions. The findings also help explain why the process of differentiating stem cells into specific lineages in the laboratory has been highly inefficient.

"Nature has created an incredibly elegant and simple way of creating variability, and maintaining it at a steady level, enabling cells to respond to changes in their environment in a systematic, controlled way," adds Chang, first author on the paper.

The landscape analogy and collective "decision-making" are concepts unfamiliar to biologists, who have tended to focus on single genes acting in linear pathways. This made the work initially difficult to publish, notes Huang. "It's hard for biologists to move from thinking about single pathways to thinking about a landscape, which is the mathematical manifestation of the entirety of all the possible pathways," he says. "A single pathway is not a good way to understand a whole process. Our goal has been to understand the driving force behind it."

Stem cells have a built-in toolkit that responds to random changes, enabling them to respond to changes in their environment in a systematic and controlled way, ultimately leading to just a few endpoints (local optima). The toolkit harnesses random variation and selection to reach the same destination in a pre-existing fitness landscape (memetic algorithm). During development, preadaptations in primordial germ cells as a result of the developmental program (imprinting, X-inactivation and reactivation and several DNA (de)methylation and histone (de)acetylation steps) results in the formation of totipotential cells, allowing them to enter the somatic differentiating program.




Also interesting is the Predictive Behavior Within Microbial Genetic Networks

We question whether homeostasis alone adequately explains microbial responses to environmental stimuli, and explore the capacity of intra-cellular networks for predictive behavior in a fashion similar to metazoan nervous systems. We show that in silico biochemical networks, evolving randomly under precisely defined complex habitats, capture the dynamical, multidimensional structure of diverse environments by forming internal models that allow prediction of environmental change. We provide evidence for such anticipatory behavior by revealing striking correlations of Escherichia coli transcriptional responses to temperature and oxygen perturbations—precisely mirroring the co-variation of these parameters upon transitions between the outside world and the mammalian gastrointestinal-tract. We further show that these internal correlations reflect a true associative learning paradigm, since they show rapid decoupling upon exposure to novel environments.

Microarray transcriptional profiling was employed to determine whether gene expression correlates with the observed global cellular state and physiological responses. And indeed it does.
From the study it was determined that anticipatory transcriptional reprogramming occurs in response to aerobic and anaerobic environmental changes and these anticipatory transcriptional reprogramming events are as a result an “associative learning” paradigm.

Another toolkit giving the "illusion" of foresight by harnessing random variation and selection.