Ecology and evolution through the algorithmic lens 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:

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

Valiant, L.G. [2009] &quot;Evolvability&quot; 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
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.