July 10, 2014

Life as a kind of algorithm

Commentary by IST Austria Professor Nick Barton in this week’s PNAS reveals surprising parallels between computer science and evolutionary biology

In a commentary in this week’s edition of PNAS, Nicholas Barton, Professor at IST Austria, together with group members Sebastian Novak and Tiago Paixao, explores the background and meaning of a new publication on natural selection (doi:10.1073/pnas.1410107111). In the reviewed paper appearing in PNAS, Chastain et al. show that natural selection on populations in which alleles, the variants of genes, can mix (recombine) freely is equivalent to the multiplicative weights update algorithm (MWUA), an algorithm that has also been repeatedly discovered in computer science, statistics and economics.

In each generation or round of selection, we just multiply how often an allele occurs by its relative fitness, the advantage conferred by the allele compared to other alleles in the population. This is just the same as the MWUA, which is also useful for increasing your chances in betting on football.  To bet on football outcomes, you follow the advice of a panel of expert betters. For each game, you consider the advice of all experts, but you weigh how much to follow the opinion of each by how good their previous predictions were. Remarkably, the ultimate performance is close to that of the expert with the best total performance – but you wouldn’t have known from the outset who turns out best. The commentary points out that, as with many processes, selection can be understood in several different ways that are actually mathematically equivalent, for example as a diffusion of allele frequencies through time or the distribution of genealogies in the ancestral selection graph. Similarly, classical mechanics can be described either by Newton’s laws or by the principle of least action. Computer science and evolutionary biology may appear to be very different research fields, but if we think about natural selection as an algorithm by which a population can learn from its environment, surprisingly close parallels are revealed. Both evolutionary biology and computer science concern themselves with how rapidly an algorithm can act or how complex it is. As the theoretical structures of the two fields are very different, Barton et al. see ample opportunities for knowledge transfer, the analogy drawn by Chastain et al. between MWUA and population genetics being a first step.