Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
Tanya Berger-Wolf's research on computational population biology may be relevant here. –  JɛffE Oct 27 '12 at 10:29
2  
@vzn how does that have anything to do with theoretical computer science? Do any of these ideas use TCS in a non-trivial manner? I am not asking for an intro course on biology, but for the impact of cstheory thinking on ecology and evolution. –  Artem Kaznatcheev Oct 27 '12 at 20:41
1  
Possibly somewhat relevant: communication between cells in a multicellular organism from the perspective of the theory of distributed computing — see, e.g., this talk by Yuval Emek. –  Jukka Suomela Nov 29 '12 at 22:29

5 Answers 5

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.

share|improve this answer
2  
Thank you for your thoughts, but this is not an answer. I am fully aware (as I mention in my second sentence) of groups like Nowak's that rely primarily on physics inspired tools. The question is not if there could be connections (as I already know there are) or if the majority of the field pursues them (as I already know they don't) but for examples of early steps that people have taken from the TCS angle. –  Artem Kaznatcheev Oct 27 '12 at 18:57
    
Right, well, I was trying to answer in the negative (as far as evolutionary dynamics goes) as helpfully as possible. –  usul Oct 27 '12 at 19:01
    
Also I'm now a bit confused about whether you think Livnat et al is a positive answer to your own question or no? (Also, this is an awesome/interesting question and I hope you get a lot more/better answers!) –  usul Oct 27 '12 at 19:04
1  
LPDF08 and the more recent follow up work, are positive examples, as is Valiant's work and follow ups. However, I exclude these from the answers simply because I am already familiar with them. –  Artem Kaznatcheev Oct 27 '12 at 19:16
3  
Quick nit pick: under the standard notion of regret, the empirical history of no-regret play only converges to the set of "coarse" correlated equilibria in general games. The stronger notion of "internal" or "swap" regret is needed to converge to the set of correlated equilibria. Regular no-regret play does converge to Nash equilibrium in zero sum games. This may be more relevant to evolutionary notions -- correlated equilibria need a correlating device to implement, and its not clear what that would be in the context of evolution. –  Aaron Roth Oct 28 '12 at 23:18

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

share|improve this answer

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.

share|improve this answer

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!

share|improve this answer
1  
This is a cool article, but I don't see how it relates to evolution and ecology. There are a few passing references to evolution (most prominently in section 4 and 6 where it is argued that evolution should promote symmetry). There is absolutely no mention of ecology. Further, although this is a nice mathematical treatment, I don't see an algorithmic or computational focus. Can you expand your answer to explain the relevance of this paper to viewing evolution and ecology through the algorithmic lens? Otherwise this seems better suited as a comment, not an answer. –  Artem Kaznatcheev Mar 15 '13 at 2:29
    
@Artem, the answer has been expanded as requested. Thank you Artem. –  John Sidles Mar 15 '13 at 14:39

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.

share|improve this answer
    
note the "origins of life" project is actually attempting to simulate "evolution" at very primordial origins ie the pre DNA stage, so in some ways it could be argued to be actually "pre-biology"... –  vzn Mar 18 at 2:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.