<p>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 <em>e.g.</em> <a href="http://www.ped.fas.harvard.edu/people/faculty/" rel="nofollow">Martin Nowak's group</a>, such as the '05 paper <a href="http://www.ped.fas.harvard.edu/people/faculty/publications_nowak/nature05.pdf" rel="nofollow">"Evolutionary Dynamics on Graphs"</a>).</p>

<p>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).</p>

<p>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!)</p>

<p>I do think that evolutionary game theory or evolutionary dynamics <em>could</em> 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 <em>e.g.</em> 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.</p>

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

<p>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.</p>

<p>(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.</p>

CC BY-SA 3.0
2012-10-27T18:57:22.340Z
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
CC BY-SA 3.0
2012-10-27T19:01:30.230Z
Right, well, I was trying to answer in the negative (as far as evolutionary dynamics goes) as helpfully as possible.
usul
CC BY-SA 3.0
2012-10-27T19:04:03.707Z
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
CC BY-SA 3.0
2012-10-27T19:16:34.027Z
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
CC BY-SA 3.0
2012-10-27T19:36:00.357Z
Ah, OK, so part of my response is to indicate that I'm not sure if I'd consider LPDF08 part of TCS, so I don't necessarily see it as fitting into the goal you're describing; or else conversely, if that paper fits, I would say a large amount of Evolutionary Dynamics research also should fit.
usul
CC BY-SA 3.0
2012-10-27T20:47:25.843Z
I would agree that LPDF08 is right on the border, since a lot of the analysis is physics-y. Valiant is definitely a better example of TCS proper. I would also agree that Nowak's work is also almost touching that border, but it still reads mostly physics-y to me, but that could be a bias I bring to my readings from knowing the educational background of Nowak and Papadimitriou. However, I do feel that LPDF08 tries to make more of a connection to cstheory than the work from PED.
Artem Kaznatcheev
CC BY-SA 3.0
2012-10-28T23:18:51.427Z
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
CC BY-SA 3.0
2012-10-29T22:52:56.297Z
Thanks, updated! Agreed, it seems hard to pin down (but maybe interesting to think about!) what, if anything, correlated equilibria might signify in evolutionary game theory.
usul
CC BY-SA 3.0
2012-10-27T18:21:49.140Z
2012-10-29T22:47:19.017Z
2012-10-29T22:47:19.017Z
usul
<p>One (recent) line of work related to asexual evolution with applications to drug design and uses interesting Markov chain techniques: <a href="http://research.microsoft.com/en-us/um/people/nvishno/Site/Publications_files/evolution-without-sex.pdf" rel="nofollow">Evolution Without Sex</a></p>

CC BY-SA 3.0
2012-11-29T10:19:23.927Z
2013-03-14T23:28:25.660Z
2013-03-14T23:28:25.660Z
anonymous
<p>heres a new notable paper linking evolution/genetics to the Multiplicative Weight Update algorithm, also just profiled by the <a href="http://www.simonsfoundation.org/quanta/20140618-the-game-theory-of-life/" rel="nofollow noreferrer">Simons foundation</a> &amp; includes a coauthor cited in the question (Papadimitriou):</p>
<ul>
<li><p><a href="http://www.pnas.org/content/early/2014/06/11/1406556111.abstract" rel="nofollow noreferrer">Algorithms, games, and evolution</a> Erick Chastain,  Adi Livnat, Christos Papadimitriou, and Umesh Vazirani</p>
<blockquote>
<p>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.</p>
</blockquote>
</li>
</ul>

CC BY-SA 3.0
2014-06-25T02:40:31.447Z
2014-06-25T02:40:31.447Z
2020-06-17T09:38:08.363Z
vzn
<p>Misha Gromov's recent broad-ranging survey <a href="http://www.ams.org/journals/bull/2011-48-02/S0273-0979-2010-01319-7/" rel="nofollow" title="Crystals"><em>Crystals, proteins, stability and isoperimetry</em></a> (Bull.&nbsp;Amer. Math.&nbsp;Soc. 48 (2011), 229-257) is a rich vein of biology-related mathematical topics (including many topics that connect to TCS methods).</p>

<p>The question asked for a listing of</p>

<blockquote>
  <p><strong>Results</strong> that use modern-ish and non-trivial aspects of computer science [&hellip;] of a very discrete nature [&hellip;] through an algorithmic lens</p>
</blockquote>

<p>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</p>

<blockquote>
  <p><strong><i>Questions</i></strong> that (potentially) use modern-ish and non-trivial aspects of computer science [&hellip;]  (many of which) are a very discrete nature [&hellip;] through (what is often) an algorithmic lens.</p>
</blockquote>

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

<p>Perhaps the article's main virtue is that the author is&nbsp;&hellip; <a href="http://en.wikipedia.org/wiki/Mikhail_Gromov_%28mathematician%29#Prizes_and_honors" rel="nofollow" title="Prizes">Misha Gromov</a>!</p>

CC BY-SA 3.0
2013-03-15T02:29:31.477Z
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
CC BY-SA 3.0
2013-03-15T14:39:36.443Z
@Artem, the answer has been expanded as requested.  Thank you Artem.
John Sidles
CC BY-SA 3.0
2013-03-15T01:11:49.160Z
2013-03-15T14:38:41.703Z
2013-03-15T14:38:41.703Z
John Sidles
<p>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 (&amp; 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 <a href="http://en.wikipedia.org/wiki/Falsifiability" rel="nofollow noreferrer">falsifiability</a> 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). </p>

<p>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 <em>proposing</em> such a research program.</p>

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

<ul>
<li><p>in the field of <a href="http://en.wikipedia.org/wiki/Artificial_life" rel="nofollow noreferrer">"artificial life"</a> 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: <a href="http://www.damer.com/writings/doctoral/Damer-Bruce-Phd-thesis-COMPRESSED-FINAL.pdf" rel="nofollow noreferrer">THE EVOGRID:
An Approach to Computational Origins of Life Endeavours</a> Damer</p>

<blockquote>
  <p>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.</p>
</blockquote></li>
<li><p><a href="http://www.agner.org/evolution/group_selection.pdf" rel="nofollow noreferrer">A GROUP SELECTION MODEL OF TERRITORIAL WAR, XENOPHOBIA AND ALTRUISM IN HUMANS
AND OTHER PRIMATES</a> Agner Fog</p>

<blockquote>
  <p>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.</p>
</blockquote></li>
<li><p>remarkably the question appears to be very similar to: <a href="https://stackoverflow.com/questions/396938/computer-simulation-of-the-evolution-process">computer simulation of the evolution process on earth</a> dating to 2008 on stack overflow with some misc refs.</p></li>
</ul>

CC BY-SA 3.0
2014-03-18T02:16:01.133Z
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
CC BY-SA 3.0
2014-03-18T02:08:56.837Z
2014-03-18T02:08:56.837Z
2017-05-23T12:40:09.333Z
vzn
<p>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 <a href="http://www.ncbi.nlm.nih.gov/pubmed/10962027" rel="noreferrer">SLBS00</a>) and could <a href="http://egtheory.wordpress.com/2012/06/23/turing-biolog/" rel="noreferrer">benefit from a computer science perspective</a>. 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:</p>
<ol>
<li><p>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. [<a href="http://www.cs.berkeley.edu/%7Echristos/papers/MixabilityTheory-1.pdf" rel="noreferrer">pdf</a>]</p>
</li>
<li><p>Valiant, L.G. [2009] &quot;Evolvability&quot; Journal of the ACM 56(1): 3.</p>
</li>
</ol>
<p>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 <a href="http://www.pnas.org/content/107/4/1452.short" rel="noreferrer">follow ups</a> 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.</p>
<p>Are there more results in these veins? <strong>Are their other deep/non-trivial applications of theoretical computer science to understanding ecology and evolution as it is studied by biologists?</strong></p>
<hr />
<h2>Notes</h2>
<ul>
<li><p>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.</p>
</li>
<li><p>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.</p>
</li>
<li><p>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 <a href="http://egtheory.wordpress.com/2012/06/29/proving-darwin/" rel="noreferrer">Chaitin's metabiology</a>.</p>
</li>
</ul>
<h2>Related questions</h2>
<ul>
<li><p><a href="https://cstheory.stackexchange.com/q/844/1037">Provable statements about genetic algorithms</a></p>
</li>
<li><p><a href="https://cstheory.stackexchange.com/q/6387/1037">Algorithmic lens in the social sciences</a></p>
</li>
<li><p><a href="https://cstheory.stackexchange.com/q/7286/1037">Sources for Algorithmic Evolutionary Game Theory</a></p>
</li>
<li><p><a href="https://cstheory.stackexchange.com/q/7951/1037">Computational complexity in quantitative finance</a></p>
</li>
</ul>

CC BY-SA 3.0
2012-10-27T10:29:49.283Z
Tanya Berger-Wolf's research on [computational population biology](http://compbio.cs.uic.edu/) may be relevant here.
Jeffε
CC BY-SA 3.0
2012-10-27T20:41:27.180Z
@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
CC BY-SA 3.0
2012-11-29T22:29:02.833Z
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](http://www.lasid.ufba.br/disc2012/view/workshop_3.php).
Jukka Suomela
<reference-request><big-picture><application-of-theory><evolutionary-game-theory><algorithmic-lens>
Ecology and evolution through the algorithmic lens
Artem Kaznatcheev
# Ecology and evolution through the algorithmic lens

(Asked by: username_0 on 2012-10-27)

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](http://www.ncbi.nlm.nih.gov/pubmed/10962027)) and could [benefit from a computer science perspective](http://egtheory.wordpress.com/2012/06/23/turing-biolog/). 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](http://www.cs.berkeley.edu/%7Echristos/papers/MixabilityTheory-1.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](http://www.pnas.org/content/107/4/1452.short) 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](http://egtheory.wordpress.com/2012/06/29/proving-darwin/).

## Related questions

* [Provable statements about genetic algorithms](https://cstheory.stackexchange.com/q/844/1037)
* [Algorithmic lens in the social sciences](https://cstheory.stackexchange.com/q/6387/1037)
* [Sources for Algorithmic Evolutionary Game Theory](https://cstheory.stackexchange.com/q/7286/1037)
* [Computational complexity in quantitative finance](https://cstheory.stackexchange.com/q/7951/1037)

**Tags:** reference-request, big-picture, application-of-theory, evolutionary-game-theory, algorithmic-lens

> **Comments:**
> **username_1**: Tanya Berger-Wolf's research on [computational population biology](http://compbio.cs.uic.edu/) may be relevant here.  
> **username_0**: @username_6 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.  
> **username_2**: 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](http://www.lasid.ufba.br/disc2012/view/workshop_3.php).  

---

## 5 answers

### Answer by username_3 on 2012-10-27. Score: 4

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](http://www.ped.fas.harvard.edu/people/faculty/), such as the '05 paper ["Evolutionary Dynamics on Graphs"](http://www.ped.fas.harvard.edu/people/faculty/publications_nowak/nature05.pdf)).

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 username_4'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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: Right, well, I was trying to answer in the negative (as far as evolutionary dynamics goes) as helpfully as possible.  
> **username_3**: 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!)  
> **username_0**: 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.  
> **username_3**: Ah, OK, so part of my response is to indicate that I'm not sure if I'd consider LPDF08 part of TCS, so I don't necessarily see it as fitting into the goal you're describing; or else conversely, if that paper fits, I would say a large amount of Evolutionary Dynamics research also should fit.  
> **username_0**: I would agree that LPDF08 is right on the border, since a lot of the analysis is physics-y. Valiant is definitely a better example of TCS proper. I would also agree that Nowak's work is also almost touching that border, but it still reads mostly physics-y to me, but that could be a bias I bring to my readings from knowing the educational background of Nowak and Papadimitriou. However, I do feel that LPDF08 tries to make more of a connection to cstheory than the work from PED.  
> **username_4**: 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.  
> **username_3**: Thanks, updated! Agreed, it seems hard to pin down (but maybe interesting to think about!) what, if anything, correlated equilibria might signify in evolutionary game theory.  

---

### Answer by username_5 on 2012-11-29. Score: 3

One (recent) line of work related to asexual evolution with applications to drug design and uses interesting Markov chain techniques: [Evolution Without Sex](http://research.microsoft.com/en-us/um/people/nvishno/Site/Publications_files/evolution-without-sex.pdf)


---

### Answer by username_6 on 2014-06-25. Score: 2

heres a new notable paper linking evolution/genetics to the Multiplicative Weight Update algorithm, also just profiled by the [Simons foundation](http://www.simonsfoundation.org/quanta/20140618-the-game-theory-of-life/) & includes a coauthor cited in the question (Papadimitriou):

* [Algorithms, games, and evolution](http://www.pnas.org/content/early/2014/06/11/1406556111.abstract) 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 by username_7 on 2013-03-15. Score: 0

Misha Gromov's recent broad-ranging survey [*Crystals, proteins, stability and isoperimetry*](http://www.ams.org/journals/bull/2011-48-02/S0273-0979-2010-01319-7/ "Crystals") (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](http://en.wikipedia.org/wiki/Mikhail_Gromov_%28mathematician%29#Prizes_and_honors "Prizes")!

> **Comments:**
> **username_0**: 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.  
> **username_7**: @Artem, the answer has been expanded as requested.  Thank you Artem.  

---

### Answer by username_6 on 2014-03-18. Score: -2

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](http://en.wikipedia.org/wiki/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"](http://en.wikipedia.org/wiki/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](http://www.damer.com/writings/doctoral/Damer-Bruce-Phd-thesis-COMPRESSED-FINAL.pdf) 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](http://www.agner.org/evolution/group_selection.pdf) 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](https://stackoverflow.com/questions/396938/computer-simulation-of-the-evolution-process) dating to 2008 on stack overflow with some misc refs.

> **Comments:**
> **username_6**: 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"_...  

---

