Ecology and evolution through the algorithmic lens

Question

The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very discrete nature (see for example SLBS00) and could benefit from a computer science perspective. Yet, I am aware of only a few serious results from TCS that try to touch on specific questions in ecology and evolution. The two directions that spring to mind are:

1. Livnat, A., Papadimitriou, C., Dusho, J., & Feldman, M.W. [2008] "A mixability theory for the role of sex in evolution" PNAS 105(50): 19803-19808. [pdf]

2. Valiant, L.G. [2009] "Evolvability" Journal of the ACM 56(1): 3.

The former applies idea from analysis of genetic algorithms to show a qualitative difference between the way sexual and asexual organisms behave in fitness landscapes, and has lead to follow ups that help justify observed modularity. The latter connects evolution and computational learning theory, to try to prove evolvability and impositibility results. It has influenced a small collection of papers, but mostly by other computer scientists.

Are there more results in these veins? Are their other deep/non-trivial applications of theoretical computer science to understanding ecology and evolution as it is studied by biologists?

---

Notes

• I am not interested in general engineering related genetic or evolutionary algorithms results. Although this is a very interesting and exciting part of computer science, its connection to evolution as studied by biologists is often superficial. Sometimes (as in LPDF08) concrete connections are made, but most standard results are not of biological interest, and hence I am not interested in them in this post.

• Bioinformatics is a nearby field, but it is also not what I am looking for. Although it can be used to reconstruct things like phylogenetic trees and thus help evolution/ecology, the theoretical CS aspects do not take centre stage. Here, the CS results seem to be mostly to perfect a tool that can be used largely as a black-box from within existing well established theories, and not to build or extend new biological theories.

• I prefer results that use modern-ish and non-trivial aspects of computer science to influence biology at a theoretic (but still relevant to biologists) level. As such, I am not that interested in things like Chaitin's metabiology.

Related questions

• Provable statements about genetic algorithms

• Algorithmic lens in the social sciences

• Sources for Algorithmic Evolutionary Game Theory

• Computational complexity in quantitative finance

Answer 1

Hmmm. As far as evolutionary dynamics/game theory goes, my personal opinion is that the Livnat et al paper you mentioned, while very nice work, doesn't seem to fall "outside" the standard mathematical approach to evolutionary game theory (see work by e.g. Martin Nowak's group, such as the '05 paper "Evolutionary Dynamics on Graphs").

So the two claims I would make are: First, while this is some great work in Evolutionary Dynamics that happens to be done by computer scientists, I would not personally place it inside Theoretical Computer Science or as being all that closely related to TCS, except for the preexisting relationship between evolutionary and algorithmic game theory. Second, if you're inclined to disagree, then you may be surprised how much the field of Evolutionary Dynamics already shares/shared with TCS philosophically (but I'm still not sure the techniques are that similar).

In general, I would be inclined to say that there is not any work along these lines, including the reference you mentioned, that fit what you seem to be looking for, which I think is a deep connection between some core concept/technique in TCS and the study of evolution. (Of course, if anyone has a differing opinion, please say so!)

I do think that evolutionary game theory or evolutionary dynamics could benefit from more algorithic approaches, (such as Livnat et al). For a particular example, I see possible nice extensions for considering evolvable agents with (limited) computional abilities, as modeled by e.g. finite state machines. This would allow us to study the evolution of discrete agents with more complex conditional strategies such as tit-for-tat. I've looked into this a bit and heard of some preliminary work along these lines but don't have any references to cite.

But even this example is a rather straightforward application, so results of this sort probably still wouldn't answer your question.

I have much higher hopes on the other hand for learning theory, which could someday make nice connections to evolutionary dynamics as well. But, I'm not very familiar with those results so I will leave that for others to comment on.

(Edit) One potential connection that should be mentioned is the known relationship of learning (e.g. the "expert's problem") and convergence to equilibria in repeated games. Specifically, for example (see Aaron Roth's comment for details), in a repeated game, if all players are playing no-regret strategies, then the past distribution of actions converges to a coarse correlated equilibrium of the single-round game. There may be something interesting and novel to say about this as viewed through the evolutionary game theory lens; I'm not sure.

Answer 2

One (recent) line of work related to asexual evolution with applications to drug design and uses interesting Markov chain techniques: Evolution Without Sex

Answer 3

heres a new notable paper linking evolution/genetics to the Multiplicative Weight Update algorithm, also just profiled by the Simons foundation & includes a coauthor cited in the question (Papadimitriou):

• Algorithms, games, and evolution Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani

  Even the most seasoned students of evolution, starting with Darwin himself, have occasionally expressed amazement that the mechanism of natural selection has produced the whole of Life as we see it around us. There is a computational way to articulate the same amazement: “What algorithm could possibly achieve all this in a mere three and a half billion years?” In this paper we propose an answer: We demonstrate that in the regime of weak selection, the standard equations of population genetics describing natural selection in the presence of sex become identical to those of a repeated game between genes played according to multiplicative weight updates (MWUA), an algorithm known in computer science to be surprisingly powerful and versatile. MWUA maximizes a tradeoff between cumulative performance and entropy, which suggests a new view on the maintenance of diversity in evolution.

Answer 4

Misha Gromov's recent broad-ranging survey Crystals, proteins, stability and isoperimetry (Bull. Amer. Math. Soc. 48 (2011), 229-257) is a rich vein of biology-related mathematical topics (including many topics that connect to TCS methods).

The question asked for a listing of

Results that use modern-ish and non-trivial aspects of computer science […] of a very discrete nature […] through an algorithmic lens

Gromov's survey is more oriented toward general mathematical questions than specific research programs. Thus the survey can be read as a Gromov's selection of

Questions that (potentially) use modern-ish and non-trivial aspects of computer science […] (many of which) are a very discrete nature […] through (what is often) an algorithmic lens.

As a list of unanswered questions rather than a list of known results, Gromov's article places significant creative demands upon the reader.

Perhaps the article's main virtue is that the author is … Misha Gromov!

Answer 5

alas there seems to be a massive gap here in scientific interest/significance vs actual scientific research as also evidenced in high votes on this question vs low votes on answers (& not expecting to defy that pattern here). it appears to be a very important study/research program at the heart of scientific theory in its early infancy. we now have the tools to do computational experiments that can subject evolution theory to falsifiability constraints at least in the sense that if evolutionary theory is accurate, then it should it be possible to model/simulate it at least roughly on a computer; but there seem to be very few attempting the project (which is, surely, extremely ambitious to say the least).

for example, is there some simulation that matches known evolutionary changes in the phylogenetic tree over billions of years? the challenge is interdisciplinary and crosscutting and does not seem to fit neatly/exactly into existing scientific fields/boundaries. remarkably there does not even seem to be any major scientists or biologists explicitly proposing such a research program.

here are a few other refs turned up which surely will not fit strictly into the narrow criteria outlined in the question but may be roughly close:

• in the field of "artificial life" there is some interest in attempting to simulate the conditions that led to "chemical soup" self-organizing into some kind of quasi-life forms that show basic aspects of replication etcetera. eg: THE EVOGRID: An Approach to Computational Origins of Life Endeavours Damer

  The quest to understand the mechanisms of the origin of life on Earth could be enhanced by computer simulations of plausible stages in the emergence of life from non-life at the molecular level. This class of simulation could then support testing and validation through parallel laboratory chemical experiments. This combination of a computational, or “cyber” component and a parallel effort investigation in chemical abiogenesis could be termed a cyberbiogenesis approach. The central technological challenge to cyberbiogenesis endeavours is to design computer simulation models permitting de novo emergence of prebiotic and biological virtual molecular structures and processes through multiple thresholds of complexity. This thesis takes on the challenge of designing, implementing and analyzing one such simulation model. This model can be described concisely as: distributed processing and global optimization through the method of search coupled with stochastic hill climbing supporting emergent phenomena within small volume, short time frame molecular dynamics simulations.

• A GROUP SELECTION MODEL OF TERRITORIAL WAR, XENOPHOBIA AND ALTRUISM IN HUMANS AND OTHER PRIMATES Agner Fog

  Abstract: A theoretical model of wars over group territories shows that behavioural traits like cooperative warfare, justice, altruism and outsider exclusion may have coevolved in higher primates and prehistoric man. The conditions for territorial war to be an effective mechanism of group selection are discussed. These conditions may have been present in tribal societies in prehistoric times but not in modern times. The geographic evolution of territories is illustrated with computer simulations.

• remarkably the question appears to be very similar to: computer simulation of the evolution process on earth dating to 2008 on stack overflow with some misc refs.