Computational theories of evolution

If you look at your typical computer science department’s faculty list, you will notice the theorists are a minority. Sometimes they are further subdivided by being culled off into mathematics departments. As such, any institute that unites and strengthens theorists is a good development. That was my first reason for excitement two years ago when I learned that a $60 million grant would establish the Simons Institute for the Theory of Computing at UC, Berkeley. The institute’s mission is close to my heart: bringing the study of theoretical computer science to bear on the natural sciences; an institute for the algorithmic lens. My second reason for excitement was that one of the inaugural programs is evolutionary biology and the theory of computing. Throughout this term, a series workshops are being held to gather and share the relevant experience.

Right now, I have my conference straw hat on, as I wait for a flight transfer in Dallas on my way to one of the events in this program, the workshop on computational theories of evolution. For the next week I will be in Berkeley absorbing all there is to know on the topic. Given how much I enjoyed Princeton’s workshop on natural algorithms in the sciences, I can barely contain my excitement.

Although computer simulations of evolution have been around for nearly as long as computers, taking the algorithmic perspective and rigorously applying the tools of cstheory is a new and quickly growing development. The best developed theory right now, is probably Valiant’s (2009) model of evolvability, which is the single biggest presence at the workshop. For example, Leslie Valiant will introduce the model and Vitaly Feldman (2008) will show its relationship to the statistical query model. In these cases, the organisms’ genomes are relatively complex representations, which Varun Kanade considers to be unbiological (Angelino & Kanade, 2014). Angelino will delve even deeper into the gene expression levels that form the foundation of Valiant’s model and present an algebraic framework for modelling them.

But the workshop will push the connection to machine learning even further with Richard Watson drawing formal analogies between certain evolutionary processes and well studied learning algorithms. Watson et
al. (2014) showed that selective pressures on a gene regulatory network are equivalent to (supervised) associative learning (Hebbian learning). Thus, we can think of these networks as evolving a distributed
associative memory of past selective environments. This can be used to better understand how evolution overfits past environments and fails to generalize to future environments. Watson et al. (in prep) also showed that selective pressures on ecological interactions are equivalent to (unsupervised) associative learning, thus forming a generalized memory of past ecological states/environmental conditions. This unsupervised learning priming the supervised learning can allow systems that are not yet an evolutionary unit to be prepped for higher-level selection (Watson et al., 2011). These insights could help in the ongoing debate over inclusive fitness and group selection.

Of course, the connection to learning goes both ways. Chrisantha Fernando will discuss his ongoing research program on evolutionary neurodynamics, and explain how we can view language learning and other mental processes during development as evolutionary dynamics in the brain. In some ways, the workshop will reconcile evolution and learning, although it won’t go into some foundational issues like the Baldwin effect.

However, plenty of other foundational issues will be discussed. For example, Nick Barton will explore the limitations of selection, by looking at the concept of ‘load’ — similar in spirit to the price of anarchy from game theory — the difference in mean fitness between a population evolving under natural selection, relative to some ideal process. Usually such analyses have been conducted only for asexual organisms with additive inheritance, which we know is an unreasonable assumption given our knowledge of epistasis in empirical fitness landscapes. Barton will discuss how we can use cstheory tools to extend these analyses to sexual organisms in arbitrary fitness landscapes.

Nicholas Pippenger along with Adi Livnat, will call into the question the assumption — implicit in the phrase ‘rate of progress’ — that evolutionary progress is somehow proportional to time. Going even further back, Mike Steel will look at a time before progress was even possible and discuss abiogenesis. He will go further than Eric’s introduction to cooperation of enzymes in protocells, and look before membranes at the probability of formation of chemical sets that are self-sustaining, and autocatalytic.

This is only a few of the topics that will be explored, and I can guess a few more discussions based on the title and speakers. However, for this preview I wanted to confine myself to just the abstracts that
were posted ahead of time; see the whole schedule for yourself. During the week (and, given my slow posting rate recently, probably for weeks to come), I will go through the events and ideas of the workshop in computational theories of evolution here on TheEGG. For now, I just need to finish battling all these flight delays, and transit conundrums and finally reach my room in Berkeley.


Angelino, E., & Kanade, V. (2014). Attribute-efficient evolvability of linear functions. Proceedings of the 5th conference on Innovations in Theoretical Computer Science, 287-300 DOI: 10.1145/2554797.2554824

Feldman, V. (2008). Evolvability from learning algorithms. In Proceedings of the 40th annual ACM symposium on Theory of Computing (pp. 619-628). ACM.

Valiant, L.G. (2009). Evolvability. Journal of the ACM, 56(1).

Watson, R.A., Palmius, N., Mills, R., Powers, S.T., & Penn, A. (2011). Can selfish symbioses effect higher-level selection?. In Advances in Artificial Life. Darwin Meets von Neumann (pp. 27-36). Springer Berlin Heidelberg.

Watson, R.A., Wagner, G.P., Pavlicev, M., Weinreich, D.M., & Mills, R. (2014). The Evolution of Phenotypic Correlations and “Developmental Memory”. Evolution.

Watson, R.A., Power, D.A., Szathmáry, E., Mills, R., Powers, S.T., Czapp, B. (in prep) The evolution of ecological relationships and principles of distributed learning in ecosystems.

About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

5 Responses to Computational theories of evolution

  1. timgoodson0 says:

    Why do evolutionary scientist use the “geologic column”, as it is most commonly referred to, as a way of dating fossils? How can you scientifically describe the legitimacy of the dates provided, when the fossils found are dated by the layers that they are found in, while continuing to date the layers of of strata based on the fossils you find in them? I don’t know where you came from, but where I am from that’s called circular reasoning.

  2. vznvzn says:

    agreed this is a very cool area, ie merging computational/experimental/empirical approaches with evolution theory… it seems very worthwhile & shows great promise over the future. its curious that major/famous evolution proponents eg Dawkins have not latched onto this field at all. they seem to be more polemical than scientific at times.
    re “new and quickly growing development” was reminded of this old question by your blog, attempted to dig up some halfway decent addl refs & already got -2 for the trouble. thatll teach me!
    wish someone would write a nice survey of the field so far….defn a big gap right now….

  3. Pingback: Algorithmic Darwinism | Theory, Evolution, and Games Group

  4. Pingback: Cataloging a year of blogging: cancer and biology | Theory, Evolution, and Games Group

  5. Pingback: Five motivations for theoretical computer science | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.