Sunday, January 09, 2005

Literature: Molecular recognition in a lattice model: An enumeration study

Molecular recognition in a lattice model: An enumeration study

We investigate the mechanisms underlying selective molecular recognition of single heteropolymers at chemically structured planar surfaces. To this end, we study systems with two-letter (HP) lattice heteropolymers by exact enumeration techniques. Selectivity for a particular surface is defined by an adsorption energy criterium. We analyze the distributions of selective sequences and the role of mutations. A particularly important factor for molecular recognition is the small-scale structure on the polymers.




Read more!

Saturday, January 08, 2005

Evolvability: The evolution of evolution

This article will explore the concept of evolvability and whether or not this concept can be explained in terms of Darwinian evolution.


Evolvability has been variously defined as the "genome's ability to produce adaptive variants when acted on by the genetic system" (Wagner & Altenberg, 1996), as the "capacity to generate heritable phenotypic variation" (Kirschner & Gerhart, 1998); and as characterized by `evolutionary watersheds' opening the "floodgates to future evolution", such as segmentation and body plans (Dawkins, 1987).
Evolvability and Sensor Evolution Symposium Call for Papers


I will show how neutrality is an essential requirement for evolvability and how evolvability is a selectable trait. The latter finding may appear to be self contradictory due to the causality principle.


Causality would suggest not due to the apparently anticipatory nature of evolvability.
Evolvability is a selectable trait David Earl, Michael Deem


The findings show that selection for evolvability can help explain many experimental results (transpositional events, evolution of drug resistance, somatic hyper-mutations) and the persistence of junk DNA.

Neutrality can help understand both phenotypic stasis followed by abrupt changes (punctuated equilibria) as well as robustness.

Modularity, scale free, multicellularity

A major tenet of the modern synthesis is that mutations are not directed by the needs of the organism or in other words, mutations are random with respect to their environment. And yet research indicates that evolution may evolve a 'strategy' which improves its ability to evolve.

Evolvability also helps explain why evolutionary operators (point mutations, recombination, etc) are so successful, when application of genetic algorithms in general requires fine tuning to the problem.

Dembski has been struggling with the problem of evolutionary algorithms for quite a while and his 'solutions' either involve appeal to a strawman evolutionary algorithm (such as Dawkin's WEASEL) or appeal to the No Free Lunch (NFL) theorems. Wesley Elsberry has a very good website in which he explores some of Dembski's arguments. Elsberry's algorithm room challenge has so far remained unanswered by ID proponents.

Others have already shown why Dembski's appeal to the NFL theorems is misplaced. Evolvability helps explain however how evolution can adapt its fitness landscape by 1) varying the set of mutators, 2) changing the phenotype-genotype mapping or by 3) neutral variations in genotype space.

In other words adaptability of exploration strategies does not necessarily require a change in the genotype-phenotype mapping!!!


For evolutionary biology the representation problem has important implications: how is it that extant species acquired a genotype-phenotype map which allows improvement by mutation and selection? Is the genotype-phenotype map able to change in evolution? What are the selective forces, if any, that shape the genotype-phenotype map? We propose that the genotype-phenotype map can evolve by two main routes: epistatic mutations, or the creation of new genes
Complex Adaptations and the Evolution of Evolvability Wagner and Altenberg


Thus Dembski's arguments why evolutionary algorithms smuggle in complex specified information are misguided.


My argument in NFL is that if that probability is reasonably high (as it should be for a useful GA), then the search on the original phase space was transferred to the space of fitness functions. There's no magic to evolutionary computation. This is being admitted even by fans of evolutionary computation like Geoffrey Miller:

"Genetic algorithms are rather robust search methods for [simple problems] and small design spaces. But for hard problems and very large design spaces, designing a good genetic algorithm is very, very difficult. All the expertise that human engineers would use in confronting a design problem -- their knowledge base, engineering principles, analysis tools, invention heuristics and common sense -- must be built into the genetic algorithm. Just as there is no general-purpose engineer, there as no general-purpose genetic algorithm.
Dembski on ISCID


Dembski is right, knowledge about the problem is what is required to improve the likelihood of finding a solution. So the question becomes: "How can evolution learn about the problem structure and exploit it? And the answer is simple: It seems that evolution is its own 'designer'. Or as Toussaint puts it in his thesis:


How in principle can evolution realize this? The answer we will give is that the implicit process of the evolution of genetic representations allows for the self-adaptation of the “search strategy” (i.e., the phenotypic variability induced by mutation and recombination).



In other words, the genome 'learns' to adapt its fitness landscape to improve its potential to successfully deal with improving fitness. But what is the meaning of evolution 'learning about the problem structure'? As Toussaint shows, this learning takes place by incorporating information given by the evaluations (correlations) in future searches. Toussaint shows that neutrality in the genotype-phenotype representation is essential for the evolution of phenotype variability.

In order to appreciate the subtleties of the argument lets walk through the argument step by step.

Variation is induced by mutation and recombination of the genetic representation of a particular phenotype. Since the same phenotype may have different genotypes, the set of phenotypic neighbors (the set of possible offsprings) even for the same phenotype may be different. The neighborhood of the phenotype depends on its genotype.

Toussaint:


How might evolution exploit this fact? Suppose evolution found an organism which is functionally quite well adapted but suffers from a lack of innovatability, i.e., all its children are no better than the parent. Now, evolution can change the genetic representation of this organism without changing its functional phenotype. This change of genetic representation, called neutral mutation, also changes the organism’s offspring neighborhood and in occasion will lead to more innovatability.


Now we are getting to a crucial insight namely that the genetic representation itself should be the outcome of a selection process


Since the choice of the genetic representation of a phenotype decisively determines the possibilities of phenotypic mutations and innovations, it has been argued that the genetic representations in todays natural organisms are not a mere incident. Instead, they should be the outcome of an adaptive process that optimized these representations with respect to the phenotypic variability
and “innovatability” they induce (Wagner & Altenberg 1996).



But this argument, while convincing, needs to be carefully formalized and Toussaint does exactly this in his thesis.

The cornerstone of Toussaint's theory are that


  1. Neutrality forms the basis of the evolution of gene interactions because it allows that phenotypic variability (formalized by the distribution of phenotypic mutants, the phenotypic exploration distribution) is itself variable and adaptable (Riedl 1977; Kimura 1986; Wagner 1996; Rice 1998). Gene interactions are the origin of structure in phenotypic variability, where structure means correlations or mutual information between different phenotypic traits within this distribution.
  2. The evolution of the genetic representations does not imply an evolution of the genotype-phenotype mapping itself. With fixed genotype-phenotype mapping, phenotypically neutral variations may rearrange the genetic system so severely that different gene interactions occur, a different phenotypic variability is induced, and one might even speak of a different genetic encoding. The phenotype is unaffected, but the phenotypic exploration distribution changes.
  3. The driving force for such rearrangements of the genetic system is the indirect effect of selection on the evolution of exploration distributions. We develop a theoretical model that formulates an evolution equation for exploration distributions and allows to identify the effective fitness of exploration distributions guiding their evolution: Exploration distributions are selected with higher probability the better they match the fitness distribution over phenotype space; in particular they are selected more likely if they exhibit a correlational structure
    similar to the correlations between phenotypic traits in selection. Hence, exploration distributions evolve such that dependencies and correlations between phenotypic traits in selection are naturally adopted by the way evolution explores phenotype space.
  4. Eventually, this allows an information theoretic interpretation of evolutionary dynamics: The information that is given by the selection or non-selection of solutions is implicitly accumulated by evolutionary dynamics and exploited for further search. This information is stored in the way phenotypes are represented. In that way evolution implicitly learns about the problem by adapting its genetic representations accordingly.






  1. Evolvability is a selectable trait David Earl, Michael Deem, PNAS, August 10, 2004, vol. 101, no. 32, 11531-11536


    Concomitant with the evolution of biological diversity must have been the evolution of mechanisms that facilitate evolution, due to the essentially infinite complexity of protein sequence space. We describe how evolvability can be an object of Darwinian selection, emphasizing the collective nature of the process. We quantify our theory with computer simulations of protein evolution. These simulations demonstrate that rapid or dramatic environmental change leads to selection for greater evolvability. The selective pressure for large scale genetic moves, such as DNA exchange, becomes increasingly strong as the environmental conditions become more uncertain. Our results demonstrate that evolvability is a selectable trait and allow for the explanation of a large body of experimental results.

  2. Complex Adaptations and the Evolution of Evolvability by Gunter P. Wagner and Lee Altenberg
  3. Neutrality and the Evolvability of Boolean Function Landscape Tina Yu and Julian Miller

    This work is a study of neutrality in the context of Evolutionary Computation systems. In particular, we introduce the use of explicit neutrality with an integer string coding scheme to allow neutrality to be measured during evolution. We tested this method on a Boolean benchmark problem. The experimental results indicate that there is a positive relationship between neutrality and evolvability: neutrality improves evolvability. We also identify four characteristics of adaptive/neutral mutations that are associated with high evolvability. They may be the ingredients in designing effective Evolutionary Computation systems for the Boolean class problem.


  4. Mark Toussaint publications on neutrality and evolvability
  5. Natural Selection: Evolving evolvability LINDA PARTRIDGE AND NICHOLAS H. BARTON Nature 407, 457 - 458 (2000)

    It is likely that specific gene sequences have evolved to generate specific kinds of variation (for example, in the vertebrate immune system). Moreover, the genetic recombination that occurs during sexual reproduction is likely to have evolved as an adaptation to generate variability. Yet it is sobering that, despite several decades of intense research, we still have little direct evidence that genetic systems have in fact evolved to facilitate evolution.
  6. Transposons and genome evolution in plants Nina Federoff, PNAS, June 20, 2000, vol. 97, no. 13, 7002-7007
  7. Prokaryote and eukaryote evolvability. Poole AM, Phillips MJ, Penny D. Biosystems. 2003 May;69(2-3):163-85
  8. Evolutionary Algorithms smuggle in design



Read more!