ACADEMIA

Algorithm helps explain sex in evolution

What do you get when you mix theorists in computer science with evolutionary biologists? You get an algorithm to explain sex.

It turns out that 155 years after Charles Darwin first published "On the Origin of Species," vexing questions remain about key aspects of evolution, such as how sexual recombination and natural selection produced the teeming diversity of life that exists today.

The answer could lie in the game that genes play during sexual recombination, and computer theorists at the University of California, Berkeley, have identified an algorithm to describe the strategy used by these genes in this game.

Their proposal, described in a paper to be published the week of June 16 in the online Early Edition of the Proceedings of the National Academy of Sciences, addresses the dueling evolutionary forces of survival of the fittest and of diversity.

"There is a paradox in evolution," said study co-author Umesh Vazirani, UC Berkeley professor of electrical engineering and computer sciences and director of the Berkeley Quantum Computation Center. "Suppose the mixing of genes through sexual recombination helps create a perfect individual. That perfection gets lost in the next generation because with sex, the offspring only inherits half the perfect parent's genes. If sexual recombination speeds up the rate at which good solutions are found, it also speeds up the rate at which those solutions are broken apart."

In this scenario, it becomes difficult to explain the role of sex when it comes to evolution, and to understand how natural selection leads to desirable genetic variations that persist over time.

Computer theorists join biologists

This question was among many challenges in evolutionary biology tackled this past spring at the Simons Institute for the Theory of Computing at UC Berkeley. The institute brought together theoretical computer scientists with researchers from evolutionary biology, physics, probability, and statistics to look at evolution through the lens of computation.

The other authors on the paper are Christos Papadimitriou, UC Berkeley professor of electrical engineering and computer sciences and senior scientist at the Simons Institute; Erick Chastain, graduate student in computer science at Rutgers University; and Adi Livnat, assistant professor of biological sciences at Virginia Tech. All the authors on this paper participated in the spring program, which was co-organized by Papadimitriou.

"The key to this work is the making of a connection between three theoretical fields: algorithms, game theory and evolutionary theory," said Livnat. "This new bridge is an uncommon advance that opens up possibilities for cross-fertilization between the fields in the future."

Although the study authors began looking at algorithms to explain evolutionary biology more than a year ago, they credit discussions made possible by the spring program at the Simons Institute for helping them finalize their work.

Hedging genetic bets

The scientists focused on weak selection in evolution, when one phenotype is just slightly advantageous over another. Weak selection is considered the dominant framework by which most genetic variation occurs. Instead of an environmental change that forces a make-or-break adaptation, for instance, many changes have no strong benefit or disadvantage. They are neutral.

"We noticed that with variation, genes have a preference for a 50-50 distribution rather than a 90-10 distribution," said Papadimitriou, a giant in the field of computational complexity. "If we use a gambling analogy, genes don't want to go all-in. They want to hedge their bets. Even if there is an extremely successful genetic trait, evolution doesn't want to let the genes for the other traits go extinct in case they're needed later."

While the genetic success of any random individual seems fleeting in this framework, the entire mix of genes gets better over time.

"Because genes are mixing so quickly, you can't think of evolution as acting on individuals," said Vazirani. "You must think of a soup consisting of genes of all individuals in a particular species. Evolution makes that soup better and better over time, regardless of what happens to any individual ingredient."

The scientists said this action for the greater good is, in effect, a coordination game.

"As far as games go, coordination games are the most boring because there is no conflict," said Papadimitriou. "All players have a common rating for each particular outcome, and they just have to agree upon which outcome to go for."

There's an algorithm for that

To describe the rules of this game, the scientists identified a powerful algorithm that has turned up time and again over the past half century in different fields of study. Called multiplicative weight update algorithm (MWUA), it works by maximizing the trade-off between going all-in on a successful genetic trait and hedging its bets by minimizing its commitment to any one trait.

The algorithm has been used in finance as a method for managing stock portfolios. The idea is to have a fairly distributed investment in many stocks, and to continually adjust the holdings in each to reflect performance. For stocks that do well, the investor increases the holdings in proportion to how well they did. Likewise, stock holdings are decreased in proportion to how badly they performed.

Surprisingly, such slow, patient adjustments lead to portfolios that perform nearly as well as lucky strategies that presciently invest heavily in a select few successful stocks, the authors said.

The function of sexual recombination in distributing genes becomes analogous to this patiently managed stock portfolio.

"It is tempting to say that the role of sex is to enable this algorithm," joked Papadimitriou.

He added that the multiplicative weight updates algorithm "is amazingly effective, and where it's been used in computer science it does wonders. Now we're noticing that nature uses this algorithm in evolution. It makes it easier to understand why evolution has been so successful."