Computational theories of evolution
March 16, 2014 5 Comments
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.