April 28, 2012

Recent Advances Towards a Truly Darwinian Neurodynamics

In this post, I will be highlighting a new paper by Fernando, Szathmary, and Husbands [1] called "Selectionist and evolutionary approaches to brain function: a critical apprasial" [2]. The paper was published in the most recent edition of Frontiers in Computational Neuroscience, an open-source journal. This post is a mix of reviewing the featured paper, a more general discussion on neuroevolutionary modeling, and my own thoughts/insights.

This paper reviews so-called Darwinian models of brain dynamics and function (as part of a field referred to as Darwinian Neurodynamics), and then proposes a new method for building an evolvable, artificial brain. This can be used as an analogical model for studying brain evolution, or as a template for simulating brain evolution or building intelligent machines. While all of the models presented are selectionist (e.g. utilizing a natural selective mechanism), many of them do not propose an explicit mechanism for heredity nor envision neurons as replicator vehicles. Thus, they are quasi-evolutionary without being explicitly Darwinian.

The authors also show that all models included for the review (there are six major Darwinian theories out there) can be restated using the Price equation. While the Price equation [3] allows for natural selection to be understood in terms of additive covariance, it does not have an explicitly algorithmic basis. This means that tools such as fitness landscapes cannot be extended to such theories. Fortunately, the authors consider how existing Darwinian theories might be extended to algorithmic search, which will become manifest in a model system that can be used to test specific hypotheses.

The authors contrast their model with Gerald Edelman's Neuronal Group Selection (NGS) model [4]. The idea behind NGS is simple: the evolution of intelligent behavior is shaped by the selection of some neuronal groups (e.g. neurons, brain regions) over others. While this is loosely inspired by group selection theories in evolutionary biology, it is in many ways more akin to Hebbian [5] principles (e.g. cells that wire together also fire together). In NGS, it is the initial connectivity and number of cells that determine the success of this brain architecture with respect to a given set of stimuli. This only serves as a loose analogy to natural selection, which can be defined as differential reproduction with respect to changes in allele frequencies. In the paper, the authors spend a significant amount of time criticizing NGS on these grounds, which leads to a discussion of the Price equation.

Figure 1. A model of the Price equation extended to neuronal groups using several different scenarios. COURTESY: Figure 1 in [2].

The Price equation, a generalized model for quantifying natural selection, can be extended to neuronal groups as shown in Figure 1. In fact, the Price equation is well suited to modeling selection in neural systems, because it mathematically formalizes how selective pressures "weight" things over multiple units of time. In Figure 1, we can see how weakening and strengthening of some trait in a population (illustrated on the left) can affect connectivity of a neuronal network (illustrated on the right) in a Hebbian manner. The network utilizes statistical information to become active and learn, but does not engage in formalized statistical learning. The Price equation is also robust to the addition of many potential sources of selection, which is semi-compatible with the integrative capacity of neuronal networks (e.g. any given synaptic connection is the product of many sources of downstream activation).

The theory of synaptic selection (TSS) [6], the Darwinian synapse model [7], and the neuronal replicator hypothesis [8] are all important take-off points for what the authors of [2] consider to be algorithmically-robust Darwinian neurodynamics. With his Darwinian synapse model, Sebastian Seung [7] suggests that the stochasticity inherent in neural activity is directly analogous to the random components of genetic mutation and recombination. Meanwhile, the Dehaene and Changeaux's TSS theory [6] suggests that objects are first encoded in redundent fashion by the stochastic activity of a large number of neurons, then later stabilized by learning, which is a form of selection. This is known as selection by amplification [9], which refers to the consequences of this process on a neuronal network topology (see Figure 2 for a general example). Despite some accounting of the stochastic nature of both population dynamics and brain activity, evolutionary neutrality is not accounted for in these models (e.g. they are strictly selectionist).

Figure 2. An example of how selection can amplify activity in a (simulated) neuronal network. COURTESY: Figure A2 in [2].

What does it mean to be "algorithmically robust"? In this case, the implication is that since no heritable genotypes exist, the individuals that constitute a population (neurons and/or synaptic connections) can not explore all possible genotypic and/or phenotypic states. In the language of physics, none of these models assume ergodicity as the initial condition.

According to Fernando, Szathmary, and Husbands, one way to make the Price equation-based models algorithmic is to add units of evolution to their structure. This involves applying the Maynard-Smith model of evolutionary units to a neuronal context, which requires modeled neuronal units to exhibit autocatalytic growth, inheritance, and variability [10]. This is not incompatible with a Hebbian view of the brain, however, and gives a candidate model of neural dynamics a set of "lifelike" attributes. This approach can be further validated using mathematical logic: a modified Hebb rule is compatible with the well-known Quasispecies (Eigen) equation [11], which like the biological brain incorporates all three elements of the Maynard-Smith's model.

The authors of [2] then propose that an evolutionary algorithm could be used to bridge the gap between existing neuronal theories and the gradient descent (or continuous exploratory) behavior more indiciative of fitness landscapes. While this is not a novel idea, assumptions regarding the encoding scheme [12] used by the authors is rooted in previous, non-Darwinian approaches. This is what makes for a unique approach. It is fitting then that the rest of the paper moves in this direction. One way to bridge the gap between brain function and Darwinian dynamics is to use a Bayesian model to approximate how a population learns from information and moves towards an adaptive state. The second is to view evolution by natural selection as a optimum-seeking process in which the global optimum is not always guaranteed. Third, population structure needs to be incorporated into a model of neural evolution so as to account for explicitly dynamic phenomena [13].

Figure 3. The Darwin series of brain-based devices. FROM LEFT: Darwin VII (models the somatosensory loop in mammals), Darwin VIII (models re-entrant connections within the visual pathways of mammals), Darwin IX (texture discrimination using artificial whiskers).COURTESY: Neurosciences Institute website. 

 Figure 4: Images of the gantry robot (left), which uses the GasNet evolutionary encoding (right). COURTESY: Figures 6 and A1, [2].

Like Edelman before them (see Figure 3), the authors test this model in a robot. Edelman is famous for his Darwin series of robots built specifically to test NGS. In [2], a gantry robot is used to test the GasNet encoding of a neuronal network. Neural "gas" networks (e.g. GasNet) are built around nodes (neurons) and arcs (synapses), but also utilize a gas (series of concentric circles -- see Figure 4) emitted from each neuron to simulate the release of neurotransmitter. In this way, neurons can be indirectly affected by local activity, and by extension use the "gas" as a signal for selection. These features enable the evolution and selection of certain pathways in the model that enable many of the adaptive features (e.g. evolvability, robustness) that are common features in formal evolutionary systems such as complex genotypes and phenotypes.

There are many other innovations featured in this model that I will let the reader explore on their own. There have been a number of other papers published involving one or more of the authors on this paper which elaborate on particular details of the evolutionary computation and modeling. Overall, this paper is a comprehensive foray into the world of brain evolution, modeling, and evolutionary computation that synthesizes a lot of previous work on evolution and brain function. By preparing this post, I learned a lot about both contemporary thinking in this area and what the future directions might be for applying these models to designing artificial systems and understanding in vivo systems alike.

[1] This is an interesting collaboration. Eors Szathmary is an evolutionary geneticist, and Phil Husbands is an artificial life/evolutionary robotics researcher. Did they team up through interactions with the first author?

[2] Fernando, C., Szathmary, E., and Husbands, P. (2012). Selectionist and evolutionary approaches to brain function: a critical apprasial. Frontiers in Computational Neuroscience, 8(24), 1-28.

[3] Price, G.R. (1995). The nature of selection. Journal of Theoretical Biology, 175, 389-396. Home of the Price equation.

[4] Edelman, G. (1987). Neural Darwinism. The Theory of Neuronal Group Selection. Basic Books, New york.

[5] Hebb, D.O. (1949). The Organization of Behavior. John Wiley and Sons, New York.

[6] Changeux, J.P. and Dehaene, S. (1989). Neuronal models of cognitive function. Cognition, 33, 63-109.

[7] Seung, S.H. (2003). Learning in spiking neural networks by reinforcement of stochastic synaptic transmission. Neuron, 40, 1063-1973. Sebastian Seung just released a new book for a popular audience called "Connectome" that focuses on the implications of his work on connectomics (or the things that characterize and determine the interconnectivity of neuronal cells in the brain).

[8] Fernando, C., Karishma, K.K., and Szathmary, E. (2008). Copying and evolution of neuronal topology. PLoS One, 3, e3775.

[9] Lieberman, E., Hauert, C., and Nowak, M. (2005). Evolutionary dynamics on graphs. Nature, 433, 312-316. This is a really interesting (but purely theoretical) paper. Highly recommended.

[10] Maynard-Smith, J. (1998). Evolutionary Genetics. Oxford University Press, Oxford, UK.

[11] Fernando, C., Vasas, V., Szathmary, E., and Husbands, P. (2011). Evolvable paths: a novel basis for information and search in the brain. PLoS One, 6, e23534. This is another interesting paper, and serves as a precursor to the current work.

[12] an evolutionary encoding, for those not familiar, is the basic structure and set of assumptions that go into representing evolution as a simulation. For example, how does one represent a simple phenotype (usually a simple geometry) as a genotype (a string of binary digits)? There are many possible ways in which to do this, which is why encoding schemes are often the most critical measure for the success or failure of a particular evolutionary model.

[13] Izhikevich, E.M. (2007). Solving the distal reward problem through linkage of STDP and dopamine signaling. Cerebral Cortex, 17, 2443-2452 AND Izhikevich, E.M. (2006). Polysynchronization: computation with spikes. Neural Computation, 18, 245-282.

In this model, population heterogeneities (so-called polysynchronous groups) are reinforced by artificial dopaminergic signals incorporated into the neuronal model.

INTERESTING FACT: Izhikevich is the founder of Scholarpedia, which is a peer-reviewed version of Wikipedia.

April 26, 2012

I'm on Tumblr.....with "Tumbld Thoughts"

I opened an account on Tumblr last week (the microblogging platform), and have been experimenting with it for about a week and a half. I'm not sure how it will fit into my new media "empire". One thing is for sure -- it will be a lot more abbreviated and stream-of-consciousness than Synthetic Daisies has become. Check out "Tumbld Thoughts" for short bursts of mental function. They even have a feature where you can ask the blogger a question, so submit your question today. It might evolve into something greater, but for now it is just a place to put the things I think about during the course of a day.

April 25, 2012

Thingiverse, a treasure trove

In previous Synthetic Daisies posts, I have discussed the Maker movement and how you can engage in some pretty high-end technological innovation without too much overhead (see "Frontiers of Rapid Prototyping" and "Open Source Hardware" for more information). In the spirit of this theme, I am featuring a profile of Thingiverse, which is a repository of blueprints for objects and tools you can fabricate using a rapid prototyping machine.

Some of these objects are trivial, and others are quasi-useful. I will give a quick tour of different schematics available to download from Thingiverse, and then discuss how they can be used by the budding Maker.

Do you like your cookies the same size and shape every time? Do you also like to serve them in a recursive manner? This cookie press might help on both counts. 

Thing #2: Che3po Chess

Ah, this is more my speed. Chess with liberal references to a post-rise-of-Skynet world and leetspeak

If you indeed are interested in recreating a post-rise-of-Skynet world, here is a replica of a T800 terminator head (what lies beneath the skin, of course).

Thing #4: Hand robot InMoov

If you need to give a robot (or cyborg) a hand, here's your chance.

Ah, yes, another robot. This one is a whole-body model, and in fact is the most famous Bending unit from Futurama. 

You might be asking at this point: can we make anything else besides robot parts and cookie cutters? In fact, there are thousands of designs available for download (although there is a heavy skew towards mechanical structures and simple tools). 

Of course, all of the above designs were "printed" using a rapid prototyper and a variety of raw materials. But suppose you do not have access to a rapid prototyper. Is Thingiverse still useful? Yes, it can be. All of the models are actually exchanged between users as a series of objects written in .STL (standard tesselation language) format. An example from "Che3po Chess" is shown in the image below:

The .STL format is not only accessible by software drivers for rapid prototyping machines. The models are build in an open-source program called MeshLab, which is good for mesh editing. Below is an example of the crown bishop from the "Che3po Chess" project opened in MeshLab.

Thingiverse could become quite useful in the design of virtual worlds, especially in mixed reality environments where physical objects and virtual objects co-exist in the same context. I am of course editorializing here, but by all means you should check out and experiment with Thingiverse.

April 18, 2012

The Neuromechanics and Evolution of Very Slow Movements

In January 2012, I wrote a blog post on very fast movements that focused on examples from insects. Now I would like to focus on very slow movements. The phylogenetic constraints and conditions for very slow movements are much the same as for fast movements. In this blog post, I will briefly touch on specific examples, although the types and scope of adaptation could be extended to examples from your favorite animal clade.

The Slow Loris (Genus: Nycticebus) is a strepsirrine Primate species that has lost the ability to jump from tree to tree. In response, slow lorises have evolved a very slow movement repetoire [1, 2]. These very slow movements (at least relative to other Primates) are typified by very deliberate, hand-over-hand locomotion that guides the feet forward. This type of evolutionary specialization requires coordinated changes in movement biomechanics, muscle phenotypes, and neural control. Within the clade Primates, there exists a diversity of specialized movement modalities. From this diversity, Primates are able to execute movements as wide-ranging as fast ballistic movements and slower, complex movements that enable brachiation and dancing. The very slow locomotion of the slow loris fits into this scheme (see Figure 1).

Figure 1. Examples of locomotion with regard to locomotor control and neuromechanical function from across Primate phylogeny. FROM LEFT: Slow loris locomotion, gibbon brachiation, chimpanzee rock throwing, human ballroom dancing.

In my previous post on very fast movements, I discussed a model of characterizing human upper-limb movements called the speed-accuracy tradeoff. This is not traditionally considered as an evolutionary tradeoff, but rather as a functional trade-off. If a movement is executed with great speed, the accuracy of that movement with regard to a target location is reduced. To increase accuracy, the movement must be slowed down. Part of this is due to limb biomechanics and neural control: limbs with limited degrees of freedom are particularly constrained by an ability to quickly plan movements. But the capacity to create and control intentional movements is enabled by muscle fiber composition. While fast-twitch muscle fibers allow for quick bursts of movement, slow-twitch (and associated slow tonic) fibers allow for slower, sustained movements. 

Likewise, there is a tradeoff between the ability to create "fast" movements and the quick onset of muscle fatigue. Muscles composed mainly of these fibers will produce large forces, but fatigue quickly. In the slow loris, the loss of leaping and the subsequent evolution of “slow” movements can be seen in the muscle fiber composition of both upper and lower limbs. Specifically, these composition of these muscles is dominated by slow twitch fibers and completely lack fast twitch glycotic fibers in the hindlimbs [3]. These fiber types are shown in context in Figure 2.

Figure 2. Histology of muscle fibers. SO = slow twitch oxidative fiber,FG = fast-twitch glycotic fiber. COURTESY: [4].

In the case of very slow movements, a slow down-accuracy tradeoff may exist that is inversely related to the speed-accuracy tradeoff and more directly related to an evolutionary tradeoff. In the case of very slow intentional movements in an organism that usually generated much faster movements, the severely slowed-down movements will exhibit a lot of motor noise related to the overproduction of force relative to what is required to maintain a very low speed. This suggests that barring major innovations in limb morphology, changes in muscle fiber composition would be required to enable movements that are slowed down many orders-of-magnitude. Even with these adaptations, there still exists a tradeoff between accuracy and speed.

In other vertebrate clades, work has been done on characterizing muscle fiber contributions to the slowed-down movements (see Figure 3) of the turtle species Trachemys scripta elegans (red-eared slider). In [5], several neck muscles were pre-selected for study based on their oxidative capacity. In these muscles, slow tonic (SO) fibers predominate, and are widespread in most turtle muscles [6]. As it turns out, the predominance of SO fiber type is due to their special functional role. In addition, the contribution of SO fibers to force generation is only significant in highly oxidative muscles. As in the case of the slow loris, this suggests that SO fibers become predominant in a set of muscles to dampen force and power output, thus slowing down movement.

Figure 3. Video of a treadmill-based experiment documenting turtle locomotion. COURTESY: YouTube.

Since a new adaptation acts to scale down accuracy relative to force production, a movement which would be highly accurate in the context of the sister taxon would be an uncontrollable movement in the context of the slow movement adapted species. This is isometrically-scaled [7] across movement speed regimes (see Figure 4). Scaling is a common theme in muscle evolution [8, 9], and is related to the co-evolution of muscle cross-sectional size and limb length [10]. One could also imagine that organisms requiring very fast movements could adapt both very fast AND controlled movements given the proper morphology.

Figure 4. A schematic that demonstrates the concept of isometric scaling. In this case, the relationship between peak muscle force production (power) and muscle limb length are predicted to scale to distinct regimes specific to individual species. As the force production requirements of the upper limbs change across phylogeny, so does the evolution of neuromuscular control.

Adaptations in neuromechanical control can also be understood in terms of an evolutionary constraint. We can demonstrate this by using a gedanken experiment involving high-degrees of morphological specialization related to movement speed (see Figure 5). In woodpeckers (Family: Picidae), the neck and beak are specialized for drilling holes into tree trunks. This requires several specializations in the neck joint and upper-body muscles that enable repetitive, precision movements that generate large forces [11, 12].

Figure 5. An abstraction of woodpecker beak drilling behavior-related morphology to the structure of a simple machine. 

In Figure 5, we can see that a number of evolutionary specializations in the upper body and head are required to enable beak drilling behavior. This behavior requires the neck to pivot like a fulcrum, which allows forces generated in the neck muscles to be transferred to the beak tip. There are also associated adaptations related to protecting the brain from inertial feedback which are necessary from a functional perspective. All of this is dependent on changes in muscle fiber composition and recruitment, and rhythmic movement behavior that maximizes force production relative to energetic requirements in many different contexts [13].

How does this model inform our understanding of very slow movements? By helping us understand that specialized neuromechanical phenomena such as the slowing down of movement behavior and control in one taxon relative to other species in its clade requires a complex set of co-evolutionary responses. This creates unique conditions and involves tradeoffs that are not usually considered in studying the origins of adaptive movements.

[1] Sellers, W.I. (1996). A biomechanical investigation into the absence of leaping in the locomotor repertoire of the slender loris (Loris tardigradus). Folis Primatologica, 67, 1-14.

[2] Schmitt, D. and Lemelin, P. (2004). Locomotor mechanics of the slender loris (Loris tardigradus). Journal of Human Evolution, 47, 85-94.

[3] Kimura, T., Kumakura, H., and Inokuchi, S. (1987). Composition of muscle fibers in the slow loris, using the m. biceps brachii as an example. Primates, 28(4), 525-532. 

[4] Goldspink, G. (2011). Alterations in Myofibril Size and Structure During Growth, Exercise, and Changes in Environmental Temperature. Comprehensive Physiology, DOI: 10.1002/cphy.cp100118.

[5] Callister, R.J., Pierce, P.A., McDonagh, J.C., and Stuart, D.G. (2005). Slow-tonic muscle fibers and their potential innervation in the turtle, Pseudemys (Trachemys) scripta elegans. Journal of Morphology, 264(1), 62-74.

[6] Laidlaw, D.H., Callister, R.J., and Stuart, D.G. (1995). Fiber-type composition of hindlimb muscles in the turtle, Pseudemys (Trachemys) scripta elegans. Journal of Morphology, 225(2), 193-211.

[7] Isometric scaling is characterized by a series of parallel functions. Isometry is often the alternative hypothesis to allometric scaling, or predicted proportional growth relationships, among different species.

[8] Tobalske, B.W. (1996). Scaling of Muscle Composition, wing morphology, and intermittent flight behavior in woodpeckers. The Auk, 113(1), 151-177.

[9] Biewener, A.A. (2005). Biomechanical consequences of scaling. Journal of Experimental Biology, 208, 1665-1676.

[10] Fitts, R.H., McDonald, K.S., and Schluter, J.M. (1991). The determinants of skeletal muscle force and power: their adaptability with changes in activity pattern. Journal of Biomechanics, 24(1), 111-122.

[11] Kirby, V. (1980). An adaptive modification in the ribs of woodpeckers and piculets (Picidae). The Auk, 97, 521-532.

[12] Maier, A. (1992). The avian muscle spindle. Anatomy and Embryology, 186, 1-25.

[13] Tobalske, B.W. (2001). Morphology, velocity, and intermittent flight in birds. American Zoology, 41, 177-187.

April 9, 2012

Leaderless control: understanding "unguided" order

What does it mean to be leaderless? To some, being without a leader is tantamount to chaos. To others, leaderlessness is the only acceptable route to fairness. But in both cases, it is assumed that leadership is a fundamental outcome of complexity, for better or for worse. Yet do we even need a leader to have control over a system? Leaderlessness is fundamentally distinct than the bottom-up, emergent organization enabled by distributed (or decentralized) autonomous systems. But is some degree of leadership or supervision neccessary for order and complexity to evolve and be maintained? The short answer is: no, but only in certain contexts and under specific conditions (see Figure 1 for a range of superficial examples).

When a leader assumes and maintains control, in many cases the leader must effectively coordinate the non-uniform distribution of energetic resources, distributed information, or both. Another attribute of leadership is the unidirectional nature of relationships between the leader and other components of the system. From a statistical learning perspective, we can say that true leaderlessness is a blind process in which "follow the leader" tactics cannot be used. That is, a leaderless system is expected to explore multiple options without significant bias towards one option or another. But do these assumptions map to what we see among complex systems in the real world?

Figure 1. Portraits of leaderlessness, from top: shoaling fish, human advocating leaderless social institutions, human flash mobs, and leaderless mRNA molecules (COURTESY: Figure 6 from [1]). But how do they all work? Is there one common mechanism, or a series of interrelated ones?

The first example of leaderless systems I will discuss is that of leaderless molecules. In the biochemistry of cells, there are leaderless proteins and mRNA, both of which are characterized by clevage of the molecule's 3' end, which in turn modifies the site of action [1]. This enables an alternate pathway to be utilized by the cell for specialized signaling tasks. This is also true of the protein interleukin 1-beta, as its lack of the proper signal peptide enables an alternate transport pathway [2]. Upon closer examination, these signaling pathways can be characterized as parallel distributed processing networks with specialized components such as anchors, scaffolds, and adaptors that allow for context-dependent optimization [3].

One way the function of leaderless networked systems can be better understood is through the concept of heterarchy. Heterarchy was first contemplated by Walter McCullough [4], who defined it as a transitive hierarchy organized by self-referential connections (for example from nervous system, see Figure 2). A transitive hierarchy is a set of relationships in which there is no clear dominant state. For example, A is greater than B and B is greater than C, but A is NOT greater than C. This is similar to the reflex arc [4, 5], or re-entrant connections found between isocortex and other parts of the Mammalian brain.

Figure 2.  An early structural diagram of a reflex arc. COURTESY: Figure 1 in [4].

Social systems exhibit many examples of heterarchical structure. In the study of social complexity [6, 7], heterarchy is defined as a hierarchy (or perhaps more precisely, a directed network) in which the rank between levels can be ordered in many different ways. For example, Crumley [6] proposes that heterarchical societies exist in cases where hierarchical social organization is decoupled from top-down control that strict implementations of hierarchy tend to produce. Examples of highly-complex societies exist throughout world history, but it does not follow that this organization always resulted from strict top-down control by a single city or ruler. Likewise, Bondarenko [7] argues that social complexity neccessitates hierarchical organization, but not in a way that restricts control to a single, one-way set of relationships.

Heterarchical relationships also result from the evolution of biological systems [8]. Gunji, Sasai, and Wakisaka [9] define heterarchical relationships as logical inconsistencies between levels of an existing hierarchical system (again, this could be described as a directed network). In the case of an organism, changes in a gene or protein sequence can have effects on multiple levels of biological organization (e.g. morphology and behavior), even if the effects on fitness are contradictory. Heterarchical relations in the structure of an organism may also play a role in confering developmental stability and evolutionary robustness [10].

The simulation of social systems can also reveal how leaderless systems can exhibit dynamic, coherent behavior. Hartman and Benes [11] addressed this using boids (a particle simulation of collective bird behavior). In the original boids simulation [12], coherent flocking behaviors similar to what is observed among birds using just three interaction rules: centering, alignment, and seperation. All rules were followed by each boid, and conformity was assumed throughout the flock. In the case of [11], centering and seperation were achieved not by relying on conformity, but by continually reassigning leadership status to different members of the flock (see Figure 3).

Figure 3. Flocking behaviors in birds as a consequence of continual leadership change. COURTESY: Figure 4 from [11].

Overall, it is the incorporation of self-reference (e.g. feedback or recursion) into a hierarchical structure that allows for heterarchical dynamics to be observed [13]. This can be understood using formal computational models based on connected dynamical systems, but a more intuitive way is to use a thought experiment. This idea came to me while looking through a new book on leaderless political movements [14]. Imagine what a leaderless game of chess would look like. Chess is a game of strategy with many potential moves, but strategy is constrained by the rank of each piece. The rank of each piece does not change, so the overall strategy of the game is oriented by there the king is and where the king will be as the game progresses. In terms of control mechanisms for engineered systems, a leaderless system can produce either multiple stable states over time, or a set of contigency pathways that enable a robust architecture. In both cases, the effects of leaderlessness can be local (as with signaling pathways in the cell) or much more global (as in the case of leaderless chess).

What are the principles learned from this foray into leaderlessness? One is that the existance of a hierarchical structure does not neccessitate strong, centralized leadership. Hierarchical structure is a consequence of scale (order of magnitude) rather than causality (order of events). The second is that transient or composite leadership (shared among parts of the system) seems to be stable and robust, but may not extend to all cases. The third lesson is that leaderlessness has consequences for how a complex system explores its state space. Since leaderlessness is in many ways a transient phenomenon, a fixed strategy is not particularly useful. Instead, leaderlessness may play an underappreciated role in fostering innovation and creativity. There are also many unexplored consequences for our understanding of collective behavior and emergent order which are just now beginning to be understood.

[1] Vesper, O. et.al (2011). Selective Translation of Leaderless mRNAs by Specialized Ribosomes Generated by MazF in Escherichia coli. Cell, 147(1), 147-157.

[2] Andrei, C. et.al (1999). The secretory route of the leaderless protein interleukin 1β involves exocytosis of endolysosome-related vesicles. Molecular Biology of the Cell, 10(5), 1463-1475.

[3] Fisher, M.J., Paton, R.C., and Matsuno, K. (1999). Intracellular signalling proteins as ‘smart’ agents in parallel distributed processes. Biosystems, 50(3), 159–171.

[4] McCullough, W.S. (1945). A heterarchy of values determined by the topology of nervous nets. Bulletin of Mathematical Biophysics, 7, 89-93.

[5] Marder, E. and Calabrese, R.L. (1996). Principles of rhythmic motor pattern generation. Physiological Reviews, 76, 687-717.

[6] Crumley, C.L. (1995). Heterarchy and the Analysis of Complex societies. IN Ehrenreih, R.M., Crumley, C.L., and Levy, J.E. (eds) Heterarchy and the Analysis of Complex Societies. American Anthropological Association, Washington, D.C.

[7] Bondarenko, D.M., Grinin, L.E., and Korotayev, A.V. (2002). Alternative pathways of social evolution. Social Evolution and History, 1(1), 54-79.

[8] Shapiro, J.A. (2002). A 21rst century view of evolution. Journal of Biological Physics, 28, 745-764.

[9] Gunji, Y-P., Sasai, K., and Wakisaka, S. (2008). Abstract heterarchy: time/state-scale re-entrant form. BioSystems, 91, 13-33.

[10] Jen, E. (2004). Robust Design: a repertoire of biological, ecological, and engineering case studies. Oxford University Press, New York.

[11] Hartman, C. and Benes, B. (2006). Autonomous boids. Computer Animation and Virtual Worlds, 17(3-4), 199-206.

[12] Reynolds, C. (1987). Flocks, Herds, and Schools: A Distributed Behavioral Model.
See the website http://www.red3d.com/cwr/papers/1987/boids.html for more information.

[13] Gunji, Y-P., Kamiura, M. (2004). Observational heterarchy enhancing active coupling. Physica D, 198, 74-105. AND Sasai, K. and Gunji, Y-P (2008). Heterarchy in biological systems: a logic-based dynamical model of abstract biological network derived from time-scale state. BioSystems, 92, 182-188.

[14] This thought experiment came to me while looking through a new book by Carne Ross called Leaderless Revolution. It is a thoughtful and innovative look at leaderlessness from a political perspective. See the website http://theleaderlessrevolution.com/ for more information on his work in this area. He explores strategies for using leaderless movements to affect social change, and uses the metaphor of chess to summarize the ultimate goals of social movements (although he does not contemplate "leaderless" chess).

April 1, 2012

Carnival of Evolution, Number 46 -- The Tree (structures) of Life

Welcome to Carnival of Evolution, Number 46. I am your host, Bradly Alicea. This month's theme is: the Tree (structures) of Life. Since this blog covers a mix of both biological and computational content, it is fitting that we explore this month's submissions in the context of trees (the computational kind) and biological classification (the biological kind). I will indulge in a historical and technical overview of trees used in evolutionary analysis, then present this month's posts.

What is a tree structure? In computational science, trees are a type of data structure often used to hierarchically sort information. In graph theory, this is called a directed acyclic graph (DAG). There are decision trees, factor trees, and classification trees, and even trees resulting from fractal growth  (Figure A). Factorization of the number 46 can be used to illustrate the way tree structures are built: it can be directly factored to its primes in a single bifurcation (Figure B).

Figure A. LEFT: An example of a decision tree, strict hierarchy. RIGHT: a tree that embodies fractal growth (built using a recursion process).

Figure B. A factor tree for the number "46".

In Darwin's notebooks, common descent was conceptualized as being represented by directed acyclic graph (Figure C). Indeed, one of the primary signatures of common descent (shared, derived traits) is quite well suited to analysis using directed acyclic graphs, although that relationship was not appreciated by Darwin. This connection would not become clear until the rise of phylogenetic theory many years later.

Figure C. One of the first "trees of life", from Darwin's Notebooks.

Figure D. A later version of an evolutionary tree, by Ernst Haeckel (late 19th century).

The "tree of life" is often thought of as a "branching bush" (Figure D) -- meaning that taxa (e.g. species) do not arise from one another in linear fashion. The concept of common ancestry is key. Common ancestors, or one ancestral form giving rise to many descendents, are key enablers of the proliferation of biodiversity, represented by bifurcations (binary splits) in the tree (Figure E). In a biological context then, "trees" are reconstructed from available data to infer a set of evolutionary relationships.

Figure E. Why do we use trees? To reveal a "black box" of evolutionary relatedness containing the common ancestor using a variety of character types (traits). In many cases, the more characters you have the more likely you are to find the "correct" tree, but it comes with a computational cost. Inference can be done using many different types of data.

Modern phylogenetics (or as some people prefer, cladistics) provides a specialized language and protocol for understanding evolution from common descent. Tree structures are also used to reveal clades (e.g. phylogenetic sets) and nested relationships. This is the idea behind monophyly, which postulates that given the data, all related species are directly connected to one and only one internal node (common hypothetical ancestor) in the graph (Figure E).

In general, polyphyly (e.g. parallel or convergent evolution) is considered an incorrect evolutionary hypothesis. However, in select cases, polyphyletic relationships may capture true evolutionary relationships [1]. Yet the work of Carl Woese [2] demonstrates that all three known domains of life (eukarya, bacteria, and archaea) of life can be classified as a series of monophyletic groups. 

Figure F. A modern "consensus" (based on rRNA data) phylogeny demonstrating the three domains of life. COURTESY: Wikipedia.

Some people argue that in certain cases (hybridization or horizontal gene transfer) evolution is also reticulate (or in the parlance of graph theory, cyclical). Indeed, depending on natural history, some groups of species or particular traits can exhibit a cycle [3]. Even in the case of the universal tree (Figure F), reticulations in the form of horizontal gene transfer can violate the strict hierarchy of this tree topology.

Finally, phylogenetic relationships range from relationships that distinguish 2-3 species to complex intraspecific relationships and the three domains of life. From a computational point-of-view, this is not a trivial issue. In general, the greater the number of taxa (e.g. species) analyzed, the much greater the number of possible evolutionary hypotheses (e.g. tree structures) there are to evaluate. In equation form, this scales according to the equation in Figure G.

Figure G. Equation to find the total number of possible phylogenies (tree topologies) given a specific number of related taxa.

In Figure G, the number of possible trees (T) increases in exponential fashion with the the number of taxa (N) added to the analysis. As additional taxa are added to the analysis, finding the true tree quickly becomes an NP-hard problem (for the biologists, this means an exact solution is not likely). Fortunately, we can use search heuristics to approximate the true tree. This approximation is of course subject to the type and amount of data added to the analysis.

If you guessed from the equation that this is a combinatorics problem, you are correct, but you still have to complete the evolution crossword puzzle to claim your prize.
Now, on to the posts.........

For this version of Carnival of Evolution, I will be incorporating the submitted and other featured posts into a series of phylogenetic trees. Each tree will demonstrate a typical tree topology that one might encounter in the scientific literature. My basis for homology, character coding, etc. were conceptual more than systematic. In addition, the sampling was non-uniform over the course of March. Nevertheless, this should still be a fun (and potentially educational) experience.

Tree #1: two clades with an outgroup.

In tree #1, we have two clades (taxa that share some set of derived characteristics), as well as an outgroup (an distantly related taxon that helps to determine the polarity, or ancestral state, of traits that make up the tree. 

* the outgroup for this tree topology is a post from PZ Myers at Pharyngula, and is a link to an educational video. PZ thinks this is a good way to teach 11-year olds (or the uninitiated) about evolution. PZ's post also serves to root two clades of two posts each.
* the first clade features posts on taxonomy by Larry Moran at Sandwalk and Jerry Coyne at Why Evolution is True. Larry's post is a critique of a recent paper and press release on the taxonomic status of Pikaia (a chordate from the Burgess shale). Jerry's post is a review of a recent PNAS paper on the inactivation of the genes for taste buds (which provides human with the tastes for sweet, bitter, umami, salty, and sour) in certain carnivore species. Particularly, the inactivation of S(sweet)-genes were found to involve multiple types of changes to the genes. For a much more in-depth take on this topic (the subspecies exemplar in our clade), please see Bjorn Ostman at Pleiotropy. In a post called "Carnivores have bad taste", he will help you understand the molecular evolution behind pseudogenes that are coupled to function.

* the second clade features two posts from John Hawks at the John Hawks weblog. If you've never been to this blog, visiting for his artwork on human evolution and diversity alone is worth the time. This is the first post of of many this month on sequence data and its evolutionary implications involving the Gorilla genome [4]. In his first post, John is interested in genes that evolve with respect to hearing (particularly LOXHD1) and how those genes have diverged between Gorillas and Humans. The second post concerns the taxonomic status of humans. Commenting on a recent article about Richard Dawkins in the Washington Post, John argues that Humans should be considered Hominoids rather than apes, because Hominoidea represents a valid taxonomic (e.g. monophyletic) group.

Tree #2: the four taxon case.

In tree #2, we have a four-taxon case, which was originally used by Huelsenbeck and Hillis [5] to test search heuristics (e.g. algorithms) that allow us to determine maximum parsimony for a set of hypothesized evolutionary relationships. In this unrooted tree, we have two clades.

* the clade on the left involves two posts on the Watchmaker analogy (orginally set forth by William Paley and featured in a book by Richard Dawkins [6]). Greg Laden's Blog features a personal anecdote that leads in to the second post by Brian Lynchehaun at The Crommunist Manifesto. Brian's post argues that the Watchmaker analogy is not a valid method of reasoning for a number of reasons which are explicated in the post.

* the clade on the right involves posts on human evolution. The first post is from This Week in Evolution, and features insight on cumulative culture in primate species. The post focuses on two recent articles on solving puzzles and game playing in a cross-species context. What distinguishes humans from other primates: problem-solving ability, cumulative culture, or a bit of both? The second post, at 10,000 Birds, is a free-association-style essay on the paleoanthropology of human scavenging and its relationship to our modern energy behaviors/needs and the species around us.

Tree #3: variable branch-length tree topology

In tree #3, we have a tree with variable branch lengths. Trees of this style are often used when time-of-divergence information (e.g. mutation rate) is available. Speaking of which, there was a post by Larry Moran from Sandwalk discussing a reconsideration of how mutation rates are calculated. This is based on a recent paper that suggests there is variation in genome-wide mutation rates within and between human families.

Tree #3 (based on no particular mutation rate) features two clades: one on human taxonomy and the other on human sociocultural evolution.

* the first clade features two different takes on human taxonomy. The first post from Stephanie Zvan at Almost Diamonds is a discussion about human subspecies (always a contentious topic) and their relationship to human variation. She asks Greg Laden (a fellow blogger) about this issue, and gets a very thoughtful response. The second post is from John Wilkins at Evolving Thoughts with his thoughts and comments on John Hawks post featured in tree #1.

* the second clade features a post on a social attribute of our species and one of our cultural products, both from an evolutionary perspective. Anne Buchanan at Mermaid's Tale gives her thoughts on human altruism in the context of Hamilton's rule and what it means to be cooperative. She proposes that we must look beyond kinship to understand the true nature of altruism. The second post from This Week in Evolution involves recent finding related to diet soda and how they might be explained by a model of evolutionary tradeoffs between fertility and longetivity.

For a more computational view on altruism, check out Masoud Mirmomeni's work at Michigan State. He was featured in a recent Beacon Center Blog researcher profile (Mathematical Modeling of Evolution). Masoud's work focuses on understanding the Price equation (which is used here as an alternative to Hamilton's rule) using Avidians (digital organisms).

Tree #4: a reticulate tree topology (e.g. a tangled web, a tangled bank).

In tree #4, we have an example of reticulating branches (or evolutionary graph cycles, if you will). Our reticulations are due to related intellectual content or institutional affiliations rather than hybridization or horizontal gene transfer (HGT) events, but hopefully it still conveys the concept of evolution as a tangled bank [7]. Instead of calling out blog posts by clade, I will go clockwise from the upper-left portion of the graph.

* the first post is from yours truly at Synthetic Daisies (Use, reuse, and use again....), and discusses an instance of exaptation called neural recycling (which is one way the brain can acquire new functional architectures without growing accordingly). There is also discussion of homology in a neural context, and the techniques researchers use to map cross-species relationships. The second post is from the Beacon Center Blog, and features current work by Daniel Couvertier on simulating biased group selection and digital evolution. The third post is another post on the Gorilla Genome, this one from David Winter at The Atavism. In this post, the taxonomic relationship between Gorilla, Chimp, and Human is considered, as he shows why not every gene gives the same phylogenetic signal in a three-taxon relationship.

* Ken Weiss at the Mermaid's Tale posts (actually two posts) on role of "slop" in describing how life works. By "slop", he means the role of stochastic processes, non-normally distributed phenomena, and chance events. In another post from the Beacon Center Blog, Eric Bruger gives his own take on the evolution of cooperative behaviors, this time in bacteria. And in another post from Mermaid's Tale (this one by Anne Buchanan), the role of random events in ordered biological systems is pondered. The subject of the post is a recent paper on stochastic gene expression, which Anne then relates to the role populations play in averaging out and otherwise resampling random events in biological systems and evolution. The last post on this tree is from EvoAnth on reconsidering the evolution of monogamy among Primate species by using digit ratios (2D:4D) as an assay.

Tree #5: long-branch attraction.

Tree #5 demonstrates a phenomenon called long-branch attraction, which occurs when many changes accumulate along two branches that graphically-speaking appear to be in the same clade. For our long-branch attraction example, we have two blog posts. The left branch features a post from Mousetrap on Hamiltonian parasites (in this case, Hamiltonian refers to W.D. Hamilton, not the physics function). This post is an open inquiry into how parasites fit into the Red Queen hypothesis. The post on the right branch is from Safari Ecology on the toxicity of snake venom.

Alternative Evolutionary Hypotheses (evo-eco-devo posts).

Another post I could not incorporate into a tree is from Felipe Pérez Jvostov at Eco-Evolutionary Dynamics called Parasites, guppies and predation, which is on........a recent paper published by their group on parasites, guppies, and predation. Holly Dunsworth at The Mermaid's Tale wrote a comprehensive post on babyism (Forget Bipedalism, what about Babyism?) which nicely recaps some of her dissertation work on the role of early development in motherhood in evolution.

Outside of the blogosphere, there was an interesting evo-devo related talk this month in Second Life given by Marta Linde-Medina of New York Medical College. The talk was hosted by the Embryo Physics course, and was a developmental physics perspective on the origins of curved bird beaks.

Two final announcements before CoE concludes for this month:

1) this year's Artificial Life conference (Alife XIII) will be held at Michigan State University in East Lansing from July 18-22. The conference is being hosted by the BEACON center, and the theme is experimental evolution. The program will cover cutting-edge work being done in biological theory, artificial life (the simulation of evolution), and the evolution of intelligence. This will be a very interesting and intellectually stimulating conference, so be sure to attend if you can.

2) here is a bonus for those of you inclined to puzzles and games. I have created an "evolutionary" crossword puzzle for you to ponder over the next month. It is fairly light, but also requires a fair amount of knowledge about evolutionary theory and biology. If you can answer all of the clues correctly by April 20, e-mail me proof of completion and I will post your name to Synthetic Daisies saying that you are a CoE 46 puzzle solver. Good luck!


 [1] Conant, G.C. and Wagner, A. (2003). Convergent evolution of gene circuits. Nature Genetics, 34(3), 264-266. AND Eisthen, H.L. and Nishikawa, K.C. (2002). Convergence: obstacle or opportunity? Brain, Behavior, and Evolution, 59, 235-239.

[2] Woese, C.R. (2000). Interpreting the universal phylogenetic tree. PNAS, 97(15), 8392-8396.

[3] Doolittle, W.F. (1999). Phylogenetic classfication and the universal tree. Science, 284, 2124–2128.
AND  Williams D. et.al (2011). A rooted net of life. Biology Direct, 6, 45.

[4] Scally, A. et.al (2012). Insights into hominid evolution from the gorilla genome sequence. Nature, 483, 169.

 COURTESY: Figures 3 and 4, reference [3].

[5] Huelsenbeck, J.P. and Hillis, D.M. (1993). Success of Phylogenetic Methods in the Four-Taxon Case. Systematic Biology, 42(3), 247-264.

[6] Dawkins, R. The Blind Watchmaker. W.W. Norton, New York.

[7]  Zimmer, C. (2009). The Tangled Bank: an introduction to evolution. Roberts and Company, New York.