February 27, 2012

Turing Centenary Year features

In this post, I will be discussing some recent features in the popular press highlighting the life and work of Alan Turing. This year is Turing's posthumous 100th birthday. Turing contributed a lot to modern computing science, with many people calling him the "father" of computer science. Alan Turing is known for two major results (both developed in the 1930s): 

1) discoverer of the Turing machine, which is the basis of both the Church-Turing thesis and modern algorithm design.

Example of a Turing Machine (COURTESY: Wikipedia).

2) characterized Turing (chemical) morphogenesis, which is a leading model for explaining pattern formation in animal development and "spontaneous" pattern generation.

Example of Turing Morphogenesis (LEFT: striping patterns on fish, COURTESY: Wired Science, RIGHT: equations that govern pattern formation, COURTESY: Johannes Wilbert Blog).

This week's issue of Nature (Volume 482, Issue 7386) features a special section on Turing's legacy (see below). There are several interesting articles in this issue contemplating how Turing's work is also relevant to a number of scientific fields. In one article, Sydney Brenner draws parallels between biological cells and Turing machines. In another set of essays, four scientists (including Rodney Brooks) re-assess the brain as a model for machine intelligence. Check it out if you can.


The latest issue of Communications of the ACM also features Turing on the cover (see below), and contains an interesting article by Moshe Vardi on the current state of algorithm design. The major issue highlighted in this article involves the legacy of the Turing machine. While contemporary algorithms are used for diverse purposes, the following question is still outstanding: are algorithms most effective as state machines, or are they recursion engines? While I will not attempt, to answer that question in this post, it is a question worth pondering.

February 25, 2012

Fictitious life-history.........

This is fun. I found this online somewhere.... For those who are unaware, Decapodia are a faux-extraterrestrial taxon from the TV show "Futurama" loosely based on the marine invertebrates of Earth. The life-history of Dr. Zoidberg, one of the main characters on the show, is illustrated (approximated?) from polyp to adult in the chart above. The "data" are taken from the episode "Teenage Mutant Leela's Hurdles" in which the entire cast quickly ages in reverse, causing them to re-live their life-history in reverse. While we might assume that Decapodian phylogeny capitulates ontogeny, those data are not shown.

February 23, 2012

Evolution for free? Self-organization as driver of natural selection

One of the central components of current evolutionary theory, particularly the modern evolutionary synthesis, is population thinking [1]. Of the oft-cited four forces of evolution (drift, selection, recombination, and mutation), two of these are explicitly linked to populations. And the most commonly used species concepts (reproductive isolation) is also dependent on population-level phenomena. Population thinking has not only provided sufficient explanations for understanding the distribution of natural variation, but has also provided us with advanced computing tools such as genetic algorithms.

Yet any individual organism in a population can exhibit traits that are deviate from the population norm. For example, mutation and recombination occur within individuals, and genetic drift (or neutrality) can often involve very small subpopulations. While the modern synthesis does a very good job of describing phenomena that define a species or variation across phylogeny, I propose that a model that unifies aberrant, individualistic behaviors with more normative and aggregate population-level phenomena is needed.

What is the missing piece then? A natural fit to this is emergence theory, which comes in a number of varieties [2]. One of the main predictions of emergence theory is self-organization, or the notion of order from chaos. Self- organization should be expected in natural populations because individuals act both in competition and collectively to produce unsupervised patterns at the population level. These are the very same patterns that we identify when we say that a population has undergone selection or some other form of differential reproduction.

In his book "The Origins of Order", Stuart Kauffman [3] uses the term "order for free". Order for free refers to the seeming lack of thermodynamic cost to the spontaneous generation of order observed in self-organizing systems. Of course, self-organizing processes must conform to thermodynamic constraints, but nevertheless result in highly ordered patterns. Two common examples of self- organization in biology are morphogenesis (a developmental process - [4]) and insect nest building (a behavioral process - [5]). In the former example, highly-parallel gene expression and intercellular signaling result in a highly patterned and repeatable cellular architecture across organisms. In the latter example, highly-parallel interactions between organisms produces a highly patterned but variable nest architecture across subpopulations in the same species.

Figure 1. Examples of self-organization that involve animal populations. UPPER LEFT: examples of a honeybee hive and a wasp's nest, UPPER RIGHT: example of epidermal morphogenesis in worm (Courtesy, wormbook.org - Chapter on Epidermal Morphogenesis), LOWER LEFT: example of emergent states of activation in the human brain (Courtesy, Figure 2, Chialvo, Nature Physics, 6, 744–750 -- 2010), LOWER RIGHT: example of fish shoaling (Courtesy, Wikipedia).

The question that naturally arises from this is how evolution by natural selection over multiple generations is related to these examples, since development and behavior both shape and constrain evolution. And while the answer is not straighforward, we can learn much from the structure of these examples. The first lesson is that while evolution is a population-dependent process, it is also dependent upon highly-parallel interactions between individuals. We can see this in many of the competitive and cooperative processes that define mating and social interaction. While this may seem to require no paradigm shift, the role of these processes in regulating the aggregate properties of the population is not a consideration of modern theory.

What are the regulatory processes that influence the evolution of a population? To do this, we will take a complex adaptive systems approach [6] to emergence. This implies that there are top-down, bottom- up, and hierarchical components of evolution in addition to the four factors proposed by current theory. An example of a top-down force in evolution is constraint by historical contingency. Historical contingency acts upon all members of a population more or less uniformly, and provides a organizational scheme to developmental and physiological processes such as gene expression. By contrast, a bottom-up force of evolution is embodied in the randomness produced by mutation and recombination. This is brought to the population by individual organisms. This randomness is not totally independent across individuals, but does provide a mechanism for individuality.

Neither top-down nor bottom-up mechanisms are particularly different from what is accounted for in current perspectives on evolution. Yet there is a third component (hierarchy) that unifies top-down and bottom-up components into the context of a complex system. The hierarchical component of evolution by natural selection is related to hierarchical structure of a population. By this I not only mean relationships between individuals in a population, but also the trophic levels of organismal organization (e.g. cells, tissues, organs - [7]). Hierarchical organization, particularly the multiscale nature (e.g. relationship between scales of organization) of evolving populations, is key to driving self- organization in individual animal body [8], and may provide a means to understand variability across instances of emergence in long-term evolution.

In considering the difference between developmental emergence (in which deviations are often deleterious) and social insect emergence (where deviations across nest and hive designs are often observed), evolution is much more like the latter than the former. This may be due to robustness mechanisms specific to biological evolution (e.g. modularity and evolvability) which are somewhat beyond the scope of the current essay, but have interesting implications on the emergence of evolutionary systems.

Besides acting to regulate the current population, these alternate components of evolution also operate on multiple generations of individuals. However, to observe the emergence of features in long-term processes such as evolution, we must consider a time scale between that of a single reproducing organism and the traditional signatures of evolution by natural selection. Think of emergent natural selection as a series regulatory processes as acting upon a small number of generations. This allows us to see the origins of long-term evolutionary changes.

Understanding the links between ultimate outcomes and proximal events in this way allows us to talk about "evolution for free", a play on the coinage "order for free" and a phrase I have encountered informally amongst colleagues. Specifically, an emergent view allows us to place evolution for free in a less evanescent context. In addition, placing evolution in this emergent context allows us to build sets of models that more explicitly link complex behaviors, brain function, and developmental processes to evolutionary outcomes.

Examples from the Nervous System:
One example of how this might be useful is in what is typically referred to as exaptation. Evolution for free might explain the evolution of color vision in primates on top of an existing circuit [9, 10]. This may also be true in cases where the primate color vision system utilizes existing cortical areas for purposes of processing. In terms of a fitness landscape, this could lead to a fitness amplifier, or perhaps an evolutionary “ratchet” that moves a population towards fitness peaks more quickly. Another example may involve the evolution of ocular dominance columns, which self-organize in development but are also similar across phylogenetically-distant taxa.

The authors of [11] refer to the self-organization of ocular dominance columns as canalization, a concept which has many analogies with evolutionary dynamics. Canalization [12] occurs when organisms are constrained to the same developmental pathway, and common developmental pathways are roughly equivalent to canals (hence canalization). These canals might be thought of as a series of minima with respect to energy required or changes in gene expression, or as linkages in an nk-boolean network [13]. This can be short-circuited through stresses such as heat shock, which uncover a lot of deleterious variants. Self-organization, on the other hand, is quite different. Self-organization is related to emergence, which is the production of higher-order patterns from disorderly interactions among cells or organisms (e.g. "stripes" from white noise). The way in which you might get to an emergent structure (such as a termite's nest) is not constrained in "development". Rather, there are many alternate pathways and patterns of interaction to the same structure (in this case, it is the structure which is "canalized", not the means of getting there). 

You might say that while canalized phenotypes are products of path-dependence (e.g. developmental contingency), self-organized aspects of the phenotype are path-invariant but structure-dependent. In the visual cortex, interactions between inputs might produce an interference pattern that creates spatial boundaries and, yes, maximally efficient patterns of information storage. Much like a box of Neopolitan ice cream (which has NOT undergone canalization), there is competition for space among multiple types of output. As long as those inputs are mapped to a cortical-like structure, self- organization is the predominant driving force.

 Figure 2. LEFT: Neopolitan ice cream, an intentionally striped form. MIDDLE: Striping in an ocular dominance column (courtesy of [14]), RIGHT: D-Stat mRNA expression in Drosophila (courtesy of [15]).

I have provided a very rough outline of what I believe to be a necessary component of evolutionary theory largely overlooked by contemporary theorists. It is not so much a matter of being "overlooked" as is a more explicit grounding of complexity theory in the relationship between individuals and populations. There has been much spirited discussion regarding the merits and shortcomings of group vs. individual selection, but that is not what I am proposing here. This alternative view still champions population thinking -- but is done so in a way that does not obscure the role of individualistic, non-normal events that occur in the course of natural history. Based on observations of assortative mating and differential reproduction in nature, we might ask: if a trait is rare in the population is it also rare with regard to the individual? As with most posts on this blog, this is a work in progress. Suggestions for future directions are welcome.

[1] see Sober, E. (1980). Evolution, population thinking, and essentialism. Philosophy of Science, 47(3), 350-383 for more information on population thinking.

[2] Reid, R.G.B. (2007). Biological Emergences: evolution by natural experiment. MIT Press, Cambridge, MA.

[3] Kauffman, S.A. (1993). Origins of Order: self organization and selection in evolution. Oxford University Press, Oxford, UK.

[4] Wartlick, O., Mumcu, P., Julicher, F., and Gonzalez-Gaitan, M. (2011). Understanding morphogenetic growth control: lessons from flies. Nature Reviews Molecular Cell Biology, 12, 594-604.

[5] Camazine, S., Deneubourg, J-L., Franks, N.R., Sneyd, J., Theraulaz, G., and Bonabeau, E. (1992). Self-Organization in Biological Systems.

[6] Holland, J.H. (1992). Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, MA.

[7] Alicea, B. (2008). Hierarchies of Biocomplexity: modeling life's energetic complexity. arXiv Repository, arXiv:0810.4547.

[8] Hunter, P.J. and Borg, T.K. (2003). Integration from proteins to organs: the Physiome Project. Nature Reviews Molecular and Cellular Biology, 4(3), 237-43.

[9] Surridge, A.K., Osorio, D., Mundy, N.I. (2003). Evolution and selection of trichromatic vision in primates. Trends in Ecology and Evolution, 18(4), 198-205.

[10] Barton, R.A. (2010). Evolutionary specialization in mammalian cortical structure. Journal of Evolutionary Biology, 20(4), 1504-1511.

[11] Kaschube, M., Schnabel, M., Lowel, S., Coppola, D.M., White, L.E., and Wolf, F. (2010). Universality in the Evolution of Orientation Columns in the Visual Cortex. Science, 330, 1113-1116.

[12] Waddington, C.H. (1960). Experiments on canalizing selection. Genetical Research, 1, 140-150.

[13] Bassler, K.E., Lee, C. and Lee, Y. (2004). Evolution of developmental canalization in networks of competing boolean nodes. Physical Review Letters, 93(3), 038101.

[14] Stiles, J. and Jernigan, T.L. (2010). The Basics of Brain Development. Neuropsychology Review, 20(4).

[15] Yan, R., Small, S., Desplan, C., Dearolf, C.R., Darnell, J.E. (1996). Identification of a Stat gene that functions in Drosophila development. Cell, 84(3), 421-430.

February 21, 2012

Official Host of the Carnival of Evolution #46

Hooray! Synthetic Daisies will be the official host for the Carnival of Evolution (CoE) #46. The publish date is April 1 (April Fools' Day). Carnival of Evolution features a wide range of submissions in the area of biological evolution (although cultural evolution, evolutionary psychology, biomimetics, and evolutionary computing would also be welcome). Please submit your relevant blog posts (dated March 1-March 31, 2012) here.

February 3, 2012

Hard-to-define Events (HTDE) Workshop

I just found out that the workshop I am trying to organize for Artificial Life XIII on hard-to-define phenomena was accepted by the program committee. Hard-to-define events are events in a complex system that set up major transitions or obvious features. Signatures of hard-to-define events are related to natural fluctuations, embedded patterns, and rare events of large magnitude. Unlike the underlying patterns and information revealed by machine learning techniques, hard-to-define techniques require alternative approaches not yet formalized.

It should be a good session, but I need to procure a lineup of participants. I am currently recruiting people to present their work in the context of hard-to-define events: the plan is to think about how one's research might involve hard-to-define events, and then consider how we might design analytical tools and/or measurement techniques to discover them.

I am interested in having people participate from any number of fields. Of particular interest is how this idea might apply to the biological, cognitive, and social sciences. I have launched a webpage devoted to the latest news on the session. Please check it out, and if you are interested in participating contact me for more information. If you are in the Midwest on the weekend of July 19-22, you should try to attend (see previous blog post for more information).