The Swing Game: a real life model for the Evolution of Cooperation

I am currently attending the very enjoyable Modelling Biological Evolution 2015 at the University of Leicester, where I have, of course, enjoyed catching up with old friends, meeting some great new people, and hearing some inspirational talks. This has led me to revisit an idea for a model for evolution of cooperation that I came up with last year. If I am being honest, I am unlikely to have the time to analyze these ideas. So I am putting them in this blog post in the hope that someone somewhere might be interested in doing the maths/simulations. If you are interested, please be in touch! It starts with a true story from.

Last year I was in a park with my two young children (aged 3 and 1) and some friends of the 3-year-old. Our 3-year-old and another child (also 3) started to argue about who was going to push the baby swing containing the 1-year-old. I discussed the situation with the children and the other child came up with the following solution: one child pushes the swing; the child who is not pushing the swing can at any point say “swap” and then they swap; repeat until they’ve had enough or we leave the park. At first I was dubious about what whether this would work – but what happened blew me away! The other child had the first time. My daughter swiftly said “swap” so she stared her turn only shortly after the other child called “swap” again. I said to my daugher: “maybe if you let X have a long turn, he might then give you a long turn too” and this is exactly what happened.

As we left the park I realized that this might be a very interesting game theory model! It has the possibility for cooperation, defection, reward, punishment, and then I realized a lot more (as I will explain below). It is also interesting for operation in continuous time rather than discrete episodes. I am not aware of other continuous time models although I would expect that they must exist. So here is my thinking:

1. The game is played for some time T (more on that later). The children take turns to push the swing and have a pay-off that is some function of the time spent pushing the swing (again, more below). The bystander can call swap – so the “stategy” lies with the bystander that will be some function to determine when they call “swap”.

2. It is immediately apparent that a linear pay-off for swing push time t won’t work (each child sums the time spent pushing the swing) as this could lead to a strategy of calling “swap” after an infinitessimaly small time interval. This might be fixed in one of a number of ways  – two spring to mind: (i) Having a penalty associated with a “swap” since there is time lost to the game (so total possible pay-off to both players is reduced) (ii) Having a non-linear pay-off for swing time t, for example a sigmoid function (t^2/(1+t^2)) or such-like. This is probably more interesting. The key question is what constraints on pay-offs are needed so as to obtain interesting playing strategies.

3. The game could be constructed with either deterministic or stochastic strategies. Stochastic strategy is probably going to be more interesting.

4. What I would find particularly interesting is to model how the children’s knowledge of T affects the extent to which they cooperate. For example, the children might know T with absolute certainty, or T might be stochastic, with children knowing some partial information about T. Suppose, for example, T has some distribution with a certain mean and variance, and the children have this information. To what extent does knowledge of the variance impact on cooperation? This is interesting because it relates to reliability of parental information. Imagine a parent who says “you have 10 minutes left” and the child knows that this means 10 with variance 1, as opposed to a parent who says “you have 10 minutes left” and the child knows that the variance is very high (say 5): does this impact on cooperation? Similarly skew of distribution (right-skewed – so 10 minutes means at least 10 minutes vs symmetrical – so 10 minutes could mean shorter).

5. There is also the question of asymmetrical knowledge of T. This could be, for example, two children who have better or less capacity to estimate T (for example an older child playing with a younger child). Would asymmetrical knowledge lead to “cheating” strategies being admitted? Anyway, these are just some of my ideas. Over to you!

Advertisements

Evolution of Novelty and Diversity: an open research idea

Spurred by the conference I have been attending (see previous post), and specifically work on evolution of diversity and complexity, I have decided to post one of my unsuccessful research grant applications as an open research idea. This is an application to the Leverhulme Trust that did not get past the first stage a couple of years ago. I really like this idea, but will never have the time to do it by myself, nor am I likely to find a suitable funder. So I am putting the idea into the public domain: after all, it serves no good to anyone sitting on my hard disk.. If you or someone you know would like to pick up on the idea, collaborate with me, maybe even come to work with me (perhaps through a Marie Curie application?) or even work completely independently of me, here it is.

Evolution of unbounded novelty and diversity using computer models of metabolism

Evolution has led to a continuous emergence of novel species, resulting in the diversity and complexity of life that we observe today. It is commonly presumed that the conditions set out by Darwin, of diversity, heredity and selection, are sufficient to explain this emergence. However, this cannot be tested in laboratory timescales, and computer simulations of evolution have been unsuccessful in producing an unending progression of novel, diverse and increasingly complex species, referred to as open-ended evolution (1). The formulation and validation of necessary and sufficient conditions for open-ended evolution is one of the biggest unsolved problems in biology (2).

We aim to address this research gap. Our hypothesis is that to obtain open-ended evolution, there must be positive feedback from the development of novelty in one species leading to the construction of new niches for other species to exploit. We propose that this positive feedback is a missing component from the current formulation of the theory of evolution. We will test this hypothesis using a computer evolution approach, by building a simulation of evolvable artificial single-cell organisms.

The novelty of our proposed approach is the use of real biochemistry to provide a rich and varied context for evolution. In the simulations, different ‘species’ of ‘organism’ will be distinguished because they possess different sets of enzymes. To survive and reproduce, organisms will be required to produce certain quantities and proportions of key chemicals: fatty acids, amino acids, nucleic acids and carbohydrates. Organisms will live in spatial patches, grow on available nutrients, and die to release chemicals that can be reused by other organisms. Fitness in the simulations will be identical to fitness in real biology: species that are better able to survive and reproduce are fitter than those that are not. Diversity will be driven by the gain or loss of enzymes, enabling organisms to use different resources and/or manufacture different biochemicals.

Our approach is radically different from previous attempts to evolve open-ended novelty. Laboratory approaches, commonly using the bacterium Escherichia coli, have been successful in evolving novel carbon source utilization (3) and diversification into two sub-types (4, 5). These results are exciting. However, experimental approaches are fundamentally limited because it is impossible to study millions of years of evolution in a laboratory setting. We cannot make broader generalizations from these results.

Computer simulations allow study of evolution on longer timescales and more focussed conditions than possible in the laboratory. The most celebrated examples are Tierra (6) and Avida (7). However, these do not exhibit open-ended evolution, but convergence to a small number of species (8). Other approaches evolve models that already contain complex building blocks, such as neural controllers or locomotive mechanisms (9, 10). Even though these approaches have evolved novelty, they start with considerable granularity and complexity. It is not clear to what extent these systems allow for unbounded novelty beyond the complexity inherent in the components. Moreover, all of these approaches lack the reusability of compounds and functional plasticity of enzymes present in real chemistry, which underpins biological evolution.

Although it is tempting to perceive the diversity of life in terms of the range of plants and animals familiar to us, single-cell organisms (bacteria and archaea) account for over 95% of genetic diversity (11). Even the bacterial species E. coli contains more genetic diversity than that which distinguishes humans from social amoebae (12). Single-cell organisms differ not by their developmental complexity (limbs, organs etc.), but their metabolic complexity: their capacity to use different biochemical sources to provide energy and reproduce. Thus we propose that it is sufficient to consider the richness of the biochemical world of single-cell creatures to obtain open-ended evolution. The positive feedback required by our hypothesis arises because the emergence of a new metabolic pathway in one species, leading to biosynthesis of novel compounds, provides opportunities for other species to evolve to exploit those compounds.

The use of an appropriately rich model chemistry is central for a successful simulation environment. A common approach is to use an artificial chemistry, such as string chemistries (13), or rich chemistries using molecular graphs (14, 15). A novelty of our approach is the use of real biochemistry. This bridges the gap between previous unrealistic computational approaches (6,7), and real-life evolution (3-5). There are three advantages of moving closer to the biology. First, we know that biology has the open-ended evolution property that we seek to reproduce. Second, there are now considerable data available that we can utilize. And third, the results obtained will be more applicable to the biological world.

Preliminary research from DJS’s group on modelling evolution has focussed on the evolution of transcription regulation. We have found that networks evolve repressor functions and hierarchical regulation to control energy usage (16-19) and that basal expression is necessary to obtain realistic network evolution (17). These results will inform the architecture of the transcription regulatory elements in the proposed simulations.

Technical Programme of Work

  1. Compilation of biochemical compound and enzyme reaction database, to include all known biochemicals and reactions, using relevant sources including KEGG (20) and MetaCyc (21).
  2. Compilation of data of free energies of formation for each biochemical compound. Measured free energies are available in databases including BRENDA (22), XPDB (23). Where measurements are unavailable, the group contribution method will be used to make suitable estimates (24, 25).
  3. Development of evolvable system for simulation of a lineage of organisms with a given set of enzymes, and given any input (local concentrations of biochemicals). Ordinary differential equations will be used to model both the metabolic reactions, and the transcription control mechanisms associated with expression of relevant enzymes.
  4. Development of spatial array that includes organisms and biochemical concentrations in each compartment, and appropriate levels of mixing between neighbouring spatial compartments.
  5. Development of evolutionary timescale simulation, to include mutations in enzyme sets and regulatory control, competition for resources, growth and death, and thus selection of most successful strains.
  6. Analysis for diversity and novelty in simulation results, using evolutionary activity statistics (8).

References

1. Bedau, M.A. 2008. In S. Bullock et al. (eds.) Artificial Life XI: Proceedings of the Eleventh International Conference on the Simulation and Synthesis of Living Systems, p. 750. MIT Press, Cambridge, MA.

2. Bedau, M.A. et al. 2000. Artificial Life 6: 363–376.

3. Blount, Z.D. et al. 2008. Proc Natl Acad Sci USA 105:7899-7906.

4. Rozen, D.E. and Lenski, R.E. 2000. Am Nat. 155: 24-35.

5. Rozen, D.E. et al. 2009. Ecol Lett. 12:34-44.

6. Ray, T.S. 1992. In Langton, C. G. et al. (Eds.) (1992). Artificial life II. Redwood City, CA: Addison-Wesley. Pp 371–408.

7. Ofria, C. and Wilke, C.O. 2004. Artificial Life 10:191-229.

8. Bullock, S. and Bedau, M.A. 2006. Artificial Life 12: 1–5.

9. Channon, A. 2001. In J. Kelemen & P. Sosik (Eds.). Advances in Artificial Life 2159 pp. 417-426. Springer-Verlag.

10. Turk, G. 2010. In Hellerman, H. et al. (eds). Proceedings of the Twelfth International Conference on the Synthesis and Simulation of Living Systems. Pp496 – 503. MIT Press.

11. Ciccarelli F.D. et al. 2006. Science 311:1283-1287.

12. Lukjacenko, O. et al. 2010. Microb Ecol. 60: 708-20.

13. Hickinbotham, S. et al. 2010. In Hellerman, H. et al. (eds). Proceedings of the Twelfth International Conference on the Synthesis and Simulation of Living Systems. pp24-31. MIT Press.

14. Benko, G, et al. 2003. J Chem Inf Comput Sci, 43:1085–93.

15. Ullrich, A. et al. 2011. Artificial Life 17: 87-108.

16. Jenkins, D.J. and Stekel, D.J. 2010. Journal of Molecular Evolution 71: 128-40.

17. Jenkins, D.J. and Stekel, D.J. 2010. Journal of Molecular Evolution 70: 215-231.

18. Jenkins, D.J. and Stekel, D.J. 2009. Artificial Life 15: 259-91.

19. Stekel, D.J. and Jenkins, D.J. 2008. BMC systems biology, 2:6.

20. Kanehisa, M. et al. 2008. Nucleic Acids Res. 36, D480-484.

21. Caspi, R. et al. 2008. Nucleic Acids Res. 36: D623–631.

22. Scheer, M. et al. 2011. Nucleic Acids Res. 39: D670-676.

23. Goldberg, R.N. et al. 2004. Bioinformatics 20: 2874-2877.

24. Jankowski, M.D. et al. 2008. Biophys. J. 95: 1487-99.

25. http://milolab.webfactional.com

Modelling Biological Evolution 2013: Conference Highlights

Over the last couple of days I have been attending the Modelling Biological Evolution conference at the University of Leicester organized by Andrew Morozov.

For me, the most interesting theme to have emerged is work on evolutionary branching: conditions under which polymorphisms (or even speciation) might arise. These were all talked about in the context of mathematical models (ODE-type formulations based on generalized Lotka-Volterra systems). The best talk I attended was by Andrew White (Heriot Watt University). He described various system of parasite-host co-evolution, the most interesting of which demonstrated increases in diversity: a new host could emerge that was resistant to current parasites, following which a new parasite could emerge that would infect that host. He rather nicely linked that work to experimental work from Mike Brockhurst (University of York) on phage infections of bacteria showing similar patterns. The results could of course be interpreted at a speciation level, or, probably more fairly, at the level of molecular diversification (e.g. of MHC types in an immune system). What I really appreciated about this resut is that it spoke to the idea that increased diversity can result through a positive feedback mechanism: diversification leads to new niches and thus the potential for further diversification. I have thought for some time that this is the most important mechanism that drives diversification / speciation in natural systems and it was nice to see an example of the mechanism in action.

The other talk I particularly appreciated on the subject was by Claus Rueffler (University of Vienna). He spoke about a result on complexity and diversity in Doebeli and Ispolatov 2010 that also contains this feedback idea. This paper relies on a specific model to obtain its result on conditions for evolutionary branching. Rueffler demonstrated general conditions under which branching might take place that depend only upon the properties of the Hessian matrix associated with key parameters in model space. The important point is that the analysis is model-independent: it only considers the properties of the model forms needed to obtain the result.

Similar ideas were presented by Eva Kisdi (University of Helsinki). She focussed on models that include evolutionary trade-offs (e.g. between virulence and transmissibility): her point was that instead of choosing a function and analyzing its consequences, one could consider desired properties of a model (e.g. branching or limit cycles) and then use “critical function analysis” to derive conditions for possible trade-off functions that would admit the desired behaviour. Eva made the important point that many models make ad hoc choices of functions and thus lead to ad hoc results of little predictive value.

I think Eva’s point really touched on some of the weaknesses that emerged in many of the talks that I attended: there was a great deal of theory (some of which was very good), but very little interface with real biological data. I find this somewhat surprising: modelling in ecology and evolution has been around for very much longer that modelling in say molecular biology (where I currently work), and yet seems to be less mature. I think that the field would really benefit from far greater interaction between theoretical and experimental researchers. Ideally, models should be looking to generate empirically falsifiable hypotheses.

Perhaps the most entertaining talks were given by Nadav Shnerb and David Kessler (both Bar Ilan University). Nadav’s first talk was about power-law-like distributions observed in genus/species distributions. Core to his work is Stephen Hubbell’s neutral theory of biodiversity.
Nadav showed that distributions of number of species within genera could be explained by a neutral model for radiation and the genus and species level coupled with extinction. Nadav’s most important point was that if you wish to make an argument that a certain observed trait is adaptive, then you have to rule out the null hypothesis that it could arise neutrally through mutation/drift. I hope that is something we addressed with regards global regulators in gene regulatory networks in Jenkins and Stekel 2010. David spoke about biodiversity distributions also, showing that adaptive forces could explain biodiversity data (they are generally poor at this due to competitive exclusion that occurs in many models) if the fitness trait is allowed a continuous rather than discrete distribution.

Nadav’s second talk was about first names of babies. This was very interesting – especially as I have a young family (and a daughter with a very old-fashioned name). He looked at the error distribution (easily shown to be binomial-like noise proportional to square root of mean) that is superimposed on a deterministic increase and decrease in popularity of a name over a 60 year period. His thesis was that the error distribution due to external events would be proportional to mean (not root mean), and, as only 5 names in his data set (Norwegian names in ~ 20th Century) did not fit binomial noise, he ruled out external events (e.g. celebrity) as being a major driver. The problem I have with this is that he didn’t rule out external events in the deterministic part of the data (e.g. initiating a rise in popularity of a name that then follows the deterministic feedback law he proposed).

Invitation to Contribute a Talk to Modelling Biological Evolution 2013: Recent Progress, Current Challenges and Future Directions

The International Conference Modelling Biological Evolution 2013: Recent Progress, Current Challenges and Future Directions will be held at the University of Leicester on May 1-3, 2013. The topics sound very interesting, and are:

  • Evolutionary Epidemiology of Infectious Disease
  • Models of Somatic Evolution of Cancer
  • Evolutionary Population Ecology
  • Models in Behavioural Ecology and Sociobiology
  • Solving Social Dilemmas
  • Models of Evolution of Language
  • Population and Quantitative Genetics

I have been invited to contribute a talk and will give a talk with the following title and abstract:

Title:

Adaptation for protein synthesis efficiency in natural and artificial gene regulatory networks

Authors:

Dorota Herman, Dafyd Jenkins, Chris Thomas and Dov Stekel

Abstract:

In this talk, we will summarize work on the use of mathematical and computer models to explore the evolution and adaptation of gene regulatory network architectures.

First, we will look at a natural system, the korAB operon in RK2 plasmids, which is a beautiful natural example of a negatively and cooperatively self-regulating operon. We use a biologically grounded mechanistic multi-scale stochastic model to compare four hypotheses for the action of the regulatory mechanism: increased robustness to extrinsic factors, decreased protein fluctuations, faster response-time of the operon and reduced host burden through improved efficiency of protein production. We find that the strongest impact of all elements of the regulatory architecture is on improving the efficiency of protein synthesis by reduction in the number of mRNA molecules needed to be produced, leading to a greater than ten-fold reduction in host energy required to express these plasmid proteins.

Next, we summarize results from two different artificial gene regulatory network models that are free to evolve: a fine-grained model that allows detailed molecular interactions, and a coarse-grained model that allows rapid evolution of many generations. A similar theme emerges in these models too: the control of cell energy and resources is a major driver of gene network topology and function. This is demonstrated in the fine-grained model with the emergence of biologically realistic mRNA and protein turnover rates that optimize energy usage and cell division time, and the evolution of basic repressor activities, and in the coarse-grained model by emergence of global regulators keeping all cellular systems under negative control.o

 

So far as I am aware, the conference organizers have extended their registration deadline, so places are still available for the next few days.

New Publication: Evolution of resource and energy management in biologically realistic gene regulatory network models

Today sees the publication of a new article:

Stekel, D.J. and Jenkins, D.J. 2012. Evolution of resource and energy management in biologically realistic gene regulatory network models. Advances in Experimental Medicine and Biology 751: 301-328.

This is, in fact, a chapter in the book Evolutionary Systems Biology that has been edited by Orkun Soyer and contains many interesting articles.

Our own article is a review of research work carried out mostly by Dafyd during his PhD. The abstract is:

We describe the use of computational models of evolution of artificial gene regulatory networks to understand the topologies of biological gene regulatory networks. We summarize results from three complementary approaches that explicitly represent biological processes of transcription, translation, metabolism and gene regulation: a fine-grained model that allows detailed molecular interactions, a coarse-grained model that allows rapid evolution of many generations, and a fixed-architecture model that allows for comparison of different hypotheses. In the first two cases, we are able to evolve networks towards the biological fitness objectives of survival and reproduction. A theme that emerges is that the control of cell energy and resources is a major driver of gene network topology and function. This is demonstrated in the fine-grained model with the emergence of biologically realistic mRNA and protein turnover rates that optimize energy usage and cell division time, and the evolution of basic repressor activities; in the fixed architecture model with a negative self-regulating gene evolving major efficiencies in mRNA usage; and in the coarse-grained model by the need for the inclusion of basal gene expression to obtain biologically plausible networks and the emergence of global regulators keeping all cellular systems under negative control. In summary, we demonstrate the value of biologically realistic computer evolution techniques, and the importance of energy and resource management in driving the topology and function of gene regulatory networks.

We are excited by this article as it brings together an important and emergent theme from four of our previous research articles.

e – Science Institute Theme 14 Workshop: Microbiology Modelling and Evolution

In the last three days I have been running a focussed workshop at the e-Science Institute in Edinburgh on microbiology modelling and evolution. With 16 contributors roughly equally split between experimentalists and modelers, we presented and discussed scientific work at the interface between experimental and modelling approaches to evolution in microbiology.

At the start of the meeting, I set out my personal views on the challenges and opportunities at this interface – my hope was that at the end of the meeting my views would be in need of updating ! From a biological perspective, the challenges are around emergence of antimicrobial resistance and pathogenicity; the opportunities afforded by fast and cheap genome sequencing. From a modelling perspective, the challenges are around developing suitably realistic models, of generating experimentally testable hypotheses, and of gaining recognition of evolutionary computing as a means to test hypothesis; the opportunities are afforded by the capacity for long-term evolution by high performance computation.

Every talk was interesting and of a high standard – and the discussion was lively and engaging. A few points that came up that I found especially salient were: (i) microbes are not just interesting/important in themselves, but also as models for general biological processes, especially social processes, including host-pathogen interactions, evolution of cooperativity and evolution of communication. (ii) The challenge of genomic diversity is greater than I even imagined. I’m already used to genomic diversity in E. coli strains, but it was amazing to see it across so many bacteria studied, including Pseudomonas aeruginosa from a single patient’s lung, or Rhizobium from root nodules in clover and vetch in a single tiny patch. (iii) The importance of considering horizontal gene transfer, and thus different levels of selection, in models of mircobial evolution. (iv) The criticality of spatial organization in both real and simulated evolution, and thus the opportunity to use high performance computation for simulation of spatial scales as well as time scales.

I was heartened by the genuine sense of good will to work together at this interface, and a shared view that ‘Systems Biology’ needs to move beyond modelling how systems are now, into being able to explain why systems might have evolved to be the way they are, and predict how they might evolve.

e-Science Institute Theme 14 starts today

Today saw the start of Theme 14 – Modelling and Microbiology – at the e-Science Institute in Edinburgh. The theme will run for 12 months and covers the interface between high performance computation and microbiology. We will bring together mathematicians, physicists, computer scientists and microbiologists in a series of focused workshops followed by a larger research conference next summer. The topics covered are:

  • Stochasticisty and microbial infection (this week)
  • Experiments and simulations of evolution
  • Modelling of metabolism

The next two workshops will be held in January and April and the conference at the end of June.

The theme has been funded by the e-Science Institute and is a collaboration between Rosalind Allen, Jamie Wood and myself.

The opening lecture (by Ros) will be webcast and I will post a link when it becomes available.