Exploring and mapping the universe of evolutionary graphs identifies structural properties affecting fixation probability and time.

Population structure can be modeled by evolutionary graphs, which can have a substantial influence on the fate of mutants. Individuals are located on the nodes of these graphs, competing to take over the graph via the links. Applications for this framework range from the ecology of river systems and cancer initiation in colonic crypts to biotechnological search for optimal mutations. In all these applications, both the probability of fixation and the associated time are of interest. We study this problem for all undirected and unweighted graphs up to a certain size. We devise a genetic algorithm to find graphs with high or low fixation probability and short or long fixation time and study their structure searching for common themes. Our work unravels structural properties that maximize or minimize fixation probability and time, which allows us to contribute to a first map of the universe of evolutionary graphs.

Computation and Simulation of Evolutionary Game Dynamics in Finite Populations.

The study of evolutionary dynamics increasingly relies on computational methods, as more and more cases outside the range of analytical tractability are explored. The computational methods for simulation and numerical approximation of the relevant quantities are diverging without being compared for accuracy and performance. We thoroughly investigate these algorithms in order to propose a reliable standard. For expositional clarity we focus on symmetric 2 × 2 games leading to one-dimensional processes, noting that extensions can be straightforward and lessons will often carry over to more complex cases. We provide time-complexity analysis and systematically compare three families of methods to compute fixation probabilities, fixation times and long-term stationary distributions for the popular Moran process. We provide efficient implementations that substantially improve wall times over naive or immediate implementations. Implications are also discussed for the Wright-Fisher process, as well as structured populations and multiple types.

Evaluating the maintenance of disease-associated variation at the blood group-related gene B4galnt2 in house mice.

BACKGROUND: B4galnt2 is a blood group-related glycosyltransferase that displays cis-regulatory variation for its tissue-specific expression patterns in house mice. The wild type allele, found e.g. in the C57BL/6 J strain, directs intestinal expression of B4galnt2, which is the pattern observed among vertebrates, including humans. An alternative allele class found in the RIIIS/J strain and other mice instead drives expression in blood vessels, which leads to a phenotype similar to type 1 von Willebrand disease (VWD), a common human bleeding disorder. We previously showed that alternative B4galnt2 alleles are subject to long-term balancing selection in mice and that variation in B4galnt2 expression influences host-microbe interactions in the intestine. This suggests that the costs of prolonged bleeding in RIIIS/J allele-bearing mice might be outweighed by benefits associated with resistance against gastrointestinal pathogens. However, the conditions under which such trade-offs could lead to the long-term maintenance of disease-associated variation at B4galnt2 are unclear. RESULTS: To explore the persistence of B4galnt2 alleles in wild populations of house mice, we combined B4galnt2 haplotype frequency data together with a mathematical model based on an evolutionary game framework with a modified Wright-Fisher process. In particular, given the potential for a heterozygote advantage as a possible explanation for balancing selection, we focused on heterozygous mice, which express B4galnt2 in both blood vessels and the gastrointestinal tract. We show that B4galnt2 displays an interesting spatial allelic distribution in Western Europe, likely due to the recent action of natural selection. Moreover, we found that the genotype frequencies observed in nature can be produced by pathogen-driven selection when both heterozygotes and RIIIS/J homozygotes are protected against infection and the fitness cost of bleeding is roughly half that of infection. CONCLUSION: By comparing the results of our models to the patterns of polymorphism at B4galnt2 in natural populations, we are able to recognize the long-term maintenance of the RIIIS/J allele through host-pathogen interactions as a viable hypothesis. Further, our models identify that a putative dominant-, yet unknown protective function of the RIIIS/J allele appears to be more likely than a protective loss of intestinal B4galnt2 expression in RIIIS/J homozygotes.

Should tissue structure suppress or amplify selection to minimize cancer risk?

BACKGROUND: It has been frequently argued that tissues evolved to suppress the accumulation of growth enhancing cancer inducing mutations. A prominent example is the hierarchical structure of tissues with high cell turnover, where a small number of tissue specific stem cells produces a large number of specialized progeny during multiple differentiation steps. Another well known mechanism is the spatial organization of stem cell populations and it is thought that this organization suppresses fitness enhancing mutations. However, in small populations the suppression of advantageous mutations typically also implies an increased accumulation of deleterious mutations. Thus, it becomes an important question whether the suppression of potentially few advantageous mutations outweighs the combined effects of many deleterious mutations. RESULTS: We argue that the distribution of mutant fitness effects, e.g. the probability to hit a strong driver compared to many deleterious mutations, is crucial for the optimal organization of a cancer suppressing tissue architecture and should be taken into account in arguments for the evolution of such tissues. CONCLUSION: We show that for systems that are composed of few cells reflecting the typical organization of a stem cell niche, amplification or suppression of selection can arise from subtle changes in the architecture. Moreover, we discuss special tissue structures that can suppress most types of non-neutral mutations simultaneously. REVIEWERS: This article was reviewed by Benjamin Allen, Andreas Deutsch and Ignacio Rodriguez-Brenes. For the full reviews, please go to the Reviewers' comments section.

Exact numerical calculation of fixation probability and time on graphs.

The Moran process on graphs is a popular model to study the dynamics of evolution in a spatially structured population. Exact analytical solutions for the fixation probability and time of a new mutant have been found for only a few classes of graphs so far. Simulations are time-expensive and many realizations are necessary, as the variance of the fixation times is high. We present an algorithm that numerically computes these quantities for arbitrary small graphs by an approach based on the transition matrix. The advantage over simulations is that the calculation has to be executed only once. Building the transition matrix is automated by our algorithm. This enables a fast and interactive study of different graph structures and their effect on fixation probability and time. We provide a fast implementation in C with this note (Hindersin et al., 2016). Our code is very flexible, as it can handle two different update mechanisms (Birth-death or death-Birth), as well as arbitrary directed or undirected graphs.

Most Undirected Random Graphs Are Amplifiers of Selection for Birth-Death Dynamics, but Suppressors of Selection for Death-Birth Dynamics.

We analyze evolutionary dynamics on graphs, where the nodes represent individuals of a population. The links of a node describe which other individuals can be displaced by the offspring of the individual on that node. Amplifiers of selection are graphs for which the fixation probability is increased for advantageous mutants and decreased for disadvantageous mutants. A few examples of such amplifiers have been developed, but so far it is unclear how many such structures exist and how to construct them. Here, we show that almost any undirected random graph is an amplifier of selection for Birth-death updating, where an individual is selected to reproduce with probability proportional to its fitness and one of its neighbors is replaced by that offspring at random. If we instead focus on death-Birth updating, in which a random individual is removed and its neighbors compete for the empty spot, then the same ensemble of graphs consists of almost only suppressors of selection for which the fixation probability is decreased for advantageous mutants and increased for disadvantageous mutants. Thus, the impact of population structure on evolutionary dynamics is a subtle issue that will depend on seemingly minor details of the underlying evolutionary process.

Counterintuitive properties of the fixation time in network-structured populations.

Evolutionary dynamics on graphs can lead to many interesting and counterintuitive findings. We study the Moran process, a discrete time birth-death process, that describes the invasion of a mutant type into a population of wild-type individuals. Remarkably, the fixation probability of a single mutant is the same on all regular networks. But non-regular networks can increase or decrease the fixation probability. While the time until fixation formally depends on the same transition probabilities as the fixation probabilities, there is no obvious relation between them. For example, an amplifier of selection, which increases the fixation probability and thus decreases the number of mutations needed until one of them is successful, can at the same time slow down the process of fixation. Based on small networks, we show analytically that (i) the time to fixation can decrease when links are removed from the network and (ii) the node providing the best starting conditions in terms of the shortest fixation time depends on the fitness of the mutant. Our results are obtained analytically on small networks, but numerical simulations show that they are qualitatively valid even in much larger populations.