Last Friday Christos Papadimitriou gave a seminar at UC Santa Barbara in the Computer Science department. The title of his talk was Computational Insights and the Theory of Evolution [announcement].
Covertly computational ideas have influenced the Theory of Evolution from the very start. This talk is about recent work on Evolution that was inspired and informed by computation. Considerations about the performance of genetic algorithms led to a novel theory of the role of sex in Evolution based on the concept of mixability, while the equations describing the evolution of a species can be reinterpreted as a repeated game between genes. The complexity of local optimality informs the mystery of variation, and a theorem on Boolean functions helps us understand better the emergence of complex adaptations.
Papadimitriou is a very accomplished computer scientist, a member of the National Academy of Sciences and has written several textbooks and has received many awards.
The work he presented at the seminar was on evolutionary theory. Of the 60 minutes he spoke, he spent the first 30 talking about the science of evolution before Darwin, about the work of Wallace and Darwin, Mendel's work, and then briefly about Fisher, Wright, and Haldane.
Following that he then spoke about Mixability. He met Adi Livnat at Berkeley in 2006, and together they ended up publishing a paper on Livnat's theory of mixability in PNAS in 2008: A mixability theory for the role of sex in evolution . In short, mixability is a theory that states that in sexually reproducing organisms, fitness alone is not what is optimized, but fitness plus population entropy is. What this means is that in addition to fitness, variation (as measured by entropy) is also optimized given the rate of recombination. Recombination introduces genetic variance by mixing the genetic material of two parents (rather than making a clone), and since genetic variance is the fuel of evolution, this is the benefit of sex, so the story goes.
Following this 2008 paper, three more papers have appeared on the same subject by the same two authors (and various others, including Marc Feldman, by the way). Now, the first PNAS paper from 2008 was edited by Dan Hartl. This means that it had a independent editor who sent the paper out for review. (As we shall hear soon, it was sent to six reviewers.) The next three papers appeared in PNAS (2010), Journal of Theoretical Biology (2011), and PNAS (2014) [2-4]. Both of these PNAS papers were contributed by Papadimitriou. Because he is a member of the NAS, he is allowed to contribute four papers per year to PNAS, which means that he acts as the editor, and is thus the person choosing which reviewers to send the paper to for review [source]:
Papers listed as “Contributed” by NAS members (at least one of the authors is an NAS member) account for only 5% of submissions and less than a quarter of published papers. NAS members are only allowed up to four Contributed papers per year. Member-contributed papers must have at least two independent reviews and are evaluated by the Editorial Board.So only two reviewers chosen by one of the authors, and the editor/author makes the final decision anyway. Hmm. Just saying*...
Anyhow, Papadimitriou's presentation ends, and I eagerly raise my hand to ask my question. Check out this recording of the exhange.
Papadimitriou: I will pray for answers, but please give me your questions.I did not stick around to talk with him afterwards. I had other obligations, plus I had basically gotten the answers that I was looking for. My conclusion is, based on this presentation and on reading the papers, that the three components at play in mixability
Me: So, you said you met Adi Livnat in 2006...
Me: In 2005 there's a paper also in PNAS by Guy Sella and Aaron Hirsch . Are you familiar with this paper?
Papadimitriou: Yes, I am familiar.
Me: They introduced the concept of free fitness analogous to the free energy.
Me: And that seems to me to be curiously identical to mixability.
Papadimitriou: Not really, no. I mean...
Me: The point is that they update both fitness and entropy at the same time, yes?
Papadimitriou: We have two conclusions that seem to... First of all they came up with [?], supposedly do that. We came to this conclusion 1) through simulations. So, we came up with the concept of mixability, in other words that the alleles that are favored are not the ones that have the best combinations, but the ones that have the best average performance. By analyzing fitness landscapes. Please, when we published our paper we got six reviews. Two of them, they could have been from that group [i.e., Sella and Hirsch]. One of them said that this is well known, and the other one said it is wrong. The point is that once you have to articulate the theory. Let's take Kimura's neutral theory. Of course you'll find hunters in the literature. The point is that theories are cheap. Coming up with a model that says "well we know physics, so let's apply the free energy principle to evolution". The point is that it's the force of argument informed by the theory that eventually becomes the cradle of science.
Me: But you don't even cite them, which is...
Papadimitriou: Yeah, we didn't know at the time. So the second part is where we explicitly say it's a derivation. It's a derivation from the equations of Fisher and Wright. In other words, its a proof. Not a postulation. You understand what I say?
Me: I Understand what you're saying, but it also rests on the fact that - something that biologists all agree on, which is that variation in a population is a good thing. And it's important for evolution. Without it evolution basically does not work, and you're saying that you are getting that through sex, but you're also ignoring mutations, which you said in the beginning as well. Everybody knows that this is something that happens as well, and especially in the bacterial populations that you were talking about where you said in the beginning that they are all sexual with conjugation and so on. But largely they are not. They are getting a lot of their variation from mutations, and this is known from experimental evolution as well.
[Here the moderator asked us to take it offline.]
Papadimitriou: So, mutations are paramount. Mutations in eukaryotes are also... relevant mutations are relevant. It's like meteorites: its important to understand what happens in everyday evolution, which means the evolution in populations. I'd be delighted to chat with you after the question session.
- variation drives evolution
- sexual reproduction increases variation through recombination
- free fitness is what is (attempted) optimized by populations
On his Berkeley homepage Papadimitriou writes this about the 2008 paper:
There had been no satisfactory explanation of the advantages of sex in evolution, and yet sex is almost ubiquitous among species despite its huge costs. Here we propose a novel explanation: Using standard models, we establish that, rather astonishingly, evolution of sexual species does not result in maximization of fitness, but in improvement of another important measure which we call mixability: The ability of a genetic variant to function adequately in the presence of a wide variety of genetic partners.So the claim to novelty remains, and that seemingly includes a rediscovery of epistasis (the genetic interaction between genes)!
As you can also see from this paragraph, the other part of the story is that mixability is touted as an explanation for the evolutionary origin of sex (i.e., recombination). To that I just want to say that if you postulate a model in which there are no mutations, then yes, recombination saves the day, as it is now the only source of variation. However, this is clearly unrealistic in the extreme, and evades the real question, namely how could sex evolve when clonal growth is so much more efficient and asexual populations (which do exist!) have been doing so well since the dawn of time?
Adit Livnat took everyone by storm (I think) by writing the following final paragraph in 2010:
If sex is tied to the nature of genes, then one may reconsider the question of the origin of sex. Although it is common to imagine evolution as an originally asexual process that became sexual at some point, it is possible that sex had existed in a primitive sense of mixing before the emergence of genes as we know them, and that the interaction of sex and natural selection played a role in the shaping of the genetic architecture .In other words - and I also have this from him verbally at the 2014 Evolution conference - Livnat thinks that sexual reproduction came first, followed by asexual reproduction later in the history of life. Papadimitriou mentioned this in his talk as well, saying that there are basically next to no species that are asexual - even bacteria have sex - and those that lost the ability to have sex are evolutionary dead ends. If you think evolution without sex is impossible, I dare you to explain why Lenski's E. coli populations - which do not exchange genetic material laterally (i.e., between individual cells) - have been successfully evolving and adapting since 1988 [source].
* I am not the only only one who thinks this track for submissions to PNAS has got to go, but do see this article  for another take.
** In researching this topic I also learned that the idea of free fitness originates with Iwasa (1988) .
Department of Biology
 Livnat A, Papadimitriou C, Dushoff J, and Feldman MW (2008). A mixability theory for the role of sex in evolution. Proceedings of the National Academy of Sciences of the United States of America, 105 (50), 19803-8 PMID: 19073912
 Livnat A, Papadimitriou C, Pippenger N, and Feldman MW (2010). Sex, mixability, and modularity. Proceedings of the National Academy of Sciences of the United States of America, 107 (4), 1452-7 PMID: 20080594
 Livnat A, Papadimitriou C, and Feldman MW (2011). An analytical contrast between fitness maximization and selection for mixability. Journal of theoretical biology, 273 (1), 232-4 PMID: 21130776
 Chastain E, Livnat A, Papadimitriou C, and Vazirani U (2014). Algorithms, games, and evolution. Proceedings of the National Academy of Sciences of the United States of America, 111 (29), 10620-3 PMID: 24979793
 Sella G, and Hirsh AE (2005). The application of statistical physics to evolutionary biology. Proceedings of the National Academy of Sciences of the United States of America, 102 (27), 9541-6 PMID: 15980155
 Rand DG, and Pfeiffer T (2009). Systematic differences in impact across publication tracks at PNAS. PloS one, 4 (12) PMID: 19956649
 Iwasa, Y. (1988). Free fitness that always increases in evolution Journal of Theoretical Biology, 135 (3), 265-281 DOI: 10.1016/S0022-5193(88)80243-1