Date Published: November 26, 2018
Publisher: Public Library of Science
Author(s): Fernando Alcalde Cuesta, Pablo González Sequeiros, Álvaro Lozano Rojo, Lucas Lacasa.
The evolutionary dynamics of a finite population where resident individuals are replaced by mutant ones depends on its spatial structure. Usually, the population adopts the form of an undirected graph where the place occupied by each individual is represented by a vertex and it is bidirectionally linked to the places that can be occupied by its offspring. There are undirected graph structures that act as amplifiers of selection increasing the probability that the offspring of an advantageous mutant spreads through the graph reaching any vertex. But there also are undirected graph structures acting as suppressors of selection where this probability is less than that of the same individual placed in a homogeneous population. Here, firstly, we present the distribution of these evolutionary regimes for all undirected graphs with N ≤ 10 vertices. Some of them exhibit transitions between different regimes when the mutant fitness increases. In particular, as it has been already observed for small-order random graphs, we show that most graphs of order N ≤ 10 are amplifiers of selection. Secondly, we describe examples of amplifiers of order 7 that become suppressors from some critical value. In fact, for graphs of order N ≤ 7, we apply computer-aided techniques to symbolically compute their fixation probability and then their evolutionary regime, as well as the critical values for which they change their regime. Thirdly, the same technique is applied to some families of highly symmetrical graphs as a mean to explore methods of suppressing selection. The existence of suppression mechanisms that reverse an amplification regime when fitness increases could have a great interest in biology and network science. Finally, the analysis of all graphs from order 8 to order 10 reveals a complex and rich evolutionary dynamics, with multiple transitions between different regimes, which have not been examined in detail until now.
In recent times the evolutionary theory on graphs has become a key field to understand biological systems. Although evolutionary dynamics has been classically studied for homogeneous populations, there is now a wide interest in the evolution of populations arranged on graphs after mutant spread. The process transforming vertices occupied by residents into vertices occupied by mutants is described by the Moran model. Introduced by Moran  as the Markov chain that counts the number of invading mutants in a homogeneous population, it was adapted to subdivided population by Maruyama [2, 3] and rediscovered by Lieberman et al.  for general graphs. For undirected graphs where edges have no orientation, mutants will either become extinct or take over the whole population, reaching one of the two absorbing states, extinction or fixation. The fixation probability is the fundamental quantity in the stochastic evolutionary analysis of a finite population.
In , we presented an extremely precise database of fixation probabilities for all undirected graphs of order 10 or less for fitness values r varying from 0.25 to 10 with step size of 0.25 (see details below). From the analysis of this database, we firstly detected suppressors described in , and later regime transitions described here. Initially, we identified two amplifiers of order 7 with a transition to the suppression regime at some rc ≤ 10. Then we envisaged to describe the complete distribution of the different evolutionary regimes (isothermal, amplifier, and suppressor) of all graphs of order 10 or less using the barcode technique. This has revealed that undirected graphs have a complex and rich evolutionary dynamics that are worth studying in detail. We have also adapted the technique described in  (implementing it in C++, see S1 File) to symbolically compute the fixation probability Φ(r) of all graphs of order 7 or less determining their evolutionary regime for any fitness value r > 1 (see also details below). Thus, we have found a third example of order 7 with a transition from amplifier to suppressor at some rc > 10, and we have proved that these three examples really have a unique transition. The same method has been also applied to some graphs of greater order generalizing suppressors and amplifiers that change into suppressors in order to detect some possible suppression mechanisms. When they have not enough symmetries to symbolically compute their fixation probability, we have proceed according to , but solving the system of linear equations for additional fitness values from 10 to 2,000 with step size of 1).
As explained by Hindersin and Traulsen in , the early constructed examples of amplifiers and suppressors seem suggest that it could be easier to construct suppressors of selection than amplifiers of selection. It is true when one focuses on directed graphs, but as shown in , most undirected (Erdös-Rényi) random graphs of small order are amplifiers of selection under Birth-Death updating. Here, we corroborate this observation by showing that most undirected graphs of order N ≤ 10 are amplifiers of selection for fitness values r ≤ 10. Furthermore, we describe the distribution of isothermal graphs, amplifiers of selection, and suppressors of selection for fitness values varying from 0.25 to 10 with step size of 0.25. In fact, for the 996 graphs of order 7 or less, the fixation probability has been symbolically computed (see Computation Method). Results are gathered in Table 1, which is one of our main results. The number, type and place of transitions for all graphs of order 7 or less are given in S1 Table. We can observe that transitions do not only occur at high values of the fitness, but also at values close to r = 1. On the other hand, to confirm the number of transitions in greater orders, we have enlarge the range of fitness values (varying now from 10 to 2,000 with step size of 1) for which the system of linear equations Eq 6 is solved. Even so, as we have specified in the introduction, the number of amplifiers and suppressors of selection is only apparent since the fitness values are limited to a more or less large interval.
Initially motivated by our interest in the robustness of biological and technological networks against invasion , we decided to compute the fixation probability of all graphs with 10 vertices or less, totaling 11,989,764 graphs, to facilitate general searches without specific aims. As explained in Materials and Methods, we solved (by Gaussian elimination) the system of linear equations Eq 6 for each graph and for each fitness value varying from 0.25 to 10 with step size of 0.25. Collected data has been published in  and details has been explained in .