Evolutionary regime transitions in structured populations

RESEARCH ARTICLE Evolutionary regime transitions in structured populations Fernando Alcalde CuestaID 1,5☯ *, Pablo Gonza ´lez Sequeiros 2,5☯ , A ´lvaro Lozano Rojo 3,4,5☯ 1Instituto de Matema ´ticas, Universidade de Santiago de Compostela, E-15782 Santiago de Compostela, Spain, 2Departamento de Dida ´cticas Aplicadas, Facultade de Formacio ´n do Profesorado, Universidade de Santiago de Compostela, Avda. Ramo ´n Ferreiro s/n, E-27002 Lugo, Spain, 3Centro Universitario de la Defensa, Academia General Militar, Ctra. Huesca s/n, E-50090 Zaragoza, Spain, 4IUMA, Universidad de Zaragoza, Pedro Cerbuna 12, E-50009 Zaragoza, Spain, 5GeoDynApp - ECSING Group, E-15782 Santiago de Compostela, Spain ☯These authors contributed equally to this work. *[email protected] Abstract 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 smallorder 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. PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 1 / 18 a1111111111 a1111111111 a1111111111 a1111111111 a1111111111 OPEN ACCESS Citation: Alcalde Cuesta F, Gonza ´lez Sequeiros P, Lozano Rojo A ´(2018) Evolutionary regime transitions in structured populations. PLoS ONE 13 (11): e0200670. https://doi.org/10.1371/journal. pone.0200670 Editor: Lucas Lacasa, Queen Mary University of London, UNITED KINGDOM Received: June 26, 2018 Accepted: November 4, 2018 Published: November 26, 2018 Copyright: ©2018 Alcalde Cuesta et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Data Availability Statement: All relevant data are within the paper and its Supporting Information files. Funding: This work was supported by the Agencia Estatal de Investigacion (Grant MTM2016-77642C2-2-P) and the European Regional Development Fund grant MTM2016-77642-C2-2-P to FAC, PGS and ALR. ALR was also supported by the Ministerio de Educacion, Cultura y Deporte (Jose Castillejos Grant CAS17/00258), the Gobierno de Aragon and the European Regional Development Fund (Grant E15 Geometra). The funders had no Introduction 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 [1] 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. [4] 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. If the population is homogeneous, at the beginning, one single vertex is chosen at random to be occupied by a mutant individual among a population of Nresident individuals. Afterwards, an individual is randomly chosen for reproduction, with probability proportional to its reproductive advantage (1 for residents and r�1 for mutants), and its clonal offspring replaces another individual chosen at random. In this case, the fixation probability is given by F0ðrÞ ¼ 1r1 1rN¼rN1 rN1þrN2þ���þrþ1:ð1Þ If the population is arranged on vertices of an undirected graph, the replacements are limited to the vertices that are connected by edges. According to the Isothermal Theorem [2–4], the fixation probability F(r) = F 0 (r) if and only if the graph is isothermal (i.e. the temperature T i =∑ j*i 1/d j of any vertex iis constant, where jis a neighbor of iand d j is the number of neighbors of j), or equivalently regular (i.e. the degree d i of any vertex iis constant). But there are graph structures altering substantially the fixation chances of mutant individuals depending on their fitness. As showed in [4], there are graph structures that amplify this advantage. This means the fixation probability function F(r)>F 0 (r) for all r>1 for the same order N. Notice that F(1) = 1/Nand the inequality must be reversed for r<1. Due to the exact analytical computation of the probability F(r) given by Monk et al. [5], it is known that star and complete bipartite graphs are amplifiers of natural selection whose fixation functions are bounded from above by F2ðrÞ ¼ F0ðr2Þ ¼ 1r2 1r2N:ð2Þ On the other hand, there are also graph structures that suppress the reproductive advantage of mutant individuals so that F(r)<F 0 (r) for all r>1. Examples of this kind of graph structures were known for some fitness values (see [6]). In [7], we presented examples of suppressors of natural selection of order 6, 8 and 10, denoted by ‘ 6 ,‘ 8 and ‘ 10 , whose fixation probabilities remain smaller than F 0 (r) for every r>1 (see Fig 1). The analysis of disadvantageous mutants (with r<1) is also interesting when comparing amplification and suppression of selection for graphs, but here, for simplicity, we focus on the case of advantageous mutant (with r>1). On the other hand, different initialization and updating types have been also considered in [8] and [9], see also [10] for a comparative analysis of update mechanisms. If the initial distribution is uniform (i.e. the probability that a vertex will be occupied by the initial mutant is equal for all the vertices) and the graph evolves under Birth-Death updating, Hindersin and Traulsen showed in [9] that almost all small undirected graphs are amplifiers of selection. Assuming both conditions and focusing on the Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 2 / 18 role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. Competing interests: The authors have declared that no competing interests exist. advantageous case, we distinguish two different evolutionary regimes (out of the isothermal one): given values 1 �r 0 <r 1 �+1, a graph is an amplifier of selection for r 2(r 0 ,r 1 ) if the fixation probability function F(r)>F 0 (r) and a suppressor of selection for r 2(r 0 ,r 1 ) if F(r)< F 0 (r) for all r 0 <r<r 1 . Star and bipartite complete graphs are amplifiers for r2(1, +1) and graphs ‘ 6 ,‘ 8 and ‘ 10 are suppressors for r2(1, +1). There are also suppressors that become amplifiers from some critical value r c >1 (see Fig 2). In this case, we say r c is a transition between both evolutionary regimes. In general, we say that the evolutionary dynamics of a Fig 1. Suppressors of order 6, 8 and 10 for any fitness value. In [7], we called ‘-graph the undirected graph of even order N= 2n+ 2 �6 obtained from the clique K 2n by dividing its vertex set into two halves with n�2 vertices and adding 2 extra vertices. Each of them is connected to one of the halves of K 2n and with the other extra vertex. The ‘-graphs ‘ 6 ,‘ 8 , and ‘ 10 are shown in the figure, together with the functions F(r)−F 0 (r) which have been symbolically computed to evidence the suppression of selection. https://doi.org/10.1371/journal.pone.0200670.g001 Fig 2. Suppressors that become amplifiers. (A) Examples of order 6 from [11] with a unique transition at r c �2.82 and r c �4.56 respectively. (B) Examples of order 7 from [6] having a unique transition at r c �79.15 and r c �1.98 respectively. In both cases, we use identification numbers from [11] to facilitate any search in our database. Each graph is shown with the function F(r)−F 0 (r), which has been symbolically computed. https://doi.org/10.1371/journal.pone.0200670.g002 Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 3 / 18 structured population presents a transition at r c >1 if there are values 1 �r 0 <r 1 �+1such that the graph is a suppressor (resp. an amplifier) for r2(r 0 ,r c ) and an amplifier (resp. a suppressor) for r2(r c ,r 1 ). In this paper, we show the complete distribution of the three evolutionary regimes (isothermal, amplifier and suppressor) for all graphs of order 10 or less, exactly for order 7 or less and extremely accurate for fitness values varying from 0.25 to 10 with step size of 0.25 for other orders. In particular, we corroborate a previous observation by Hindersin and Traulsen [9] on random graphs of small order by showing that most graphs of order 10 or less are amplifiers or suppressors that become amplifiers from a unique transition r c >1. The exhaustive identification of suppressors in order 6 and 7 allows us to describe a suppression mechanism similar to that of ‘-graphs [7] and clique-wheels [12]. The existence of topological configurations favoring the suppression of selection opens the way to the search of specific suppression mechanisms in biological networks. We also exhibit two other types of transitions which might also have important consequences: • There are amplifiers of order greater or equal to 7 that become suppressors from a unique transition r c >1. • There are graphs of order greater or equal to 8 exhibiting more than one transition. For finite populations, it has been suggested that results obtained for weak selection may remain valid when the selection is no longer weak. However, in [13], Wu et al. showed that this is no the case for homogeneous populations under frequency dependent selection. Here, we show that the phenomenon can happen in a structured population even when the selection is frequency independent. Moreover, the fact that the survival chances of mutant individuals may decrease with respect to a homogeneous population when their fitness increases might have interesting biological consequences. In fact, a family of graphs of order �12 that change from amplifier into suppressor as r increases has recently been shown in [14] by using numerical simulation. But, for the three graphs of order 7 that exhibit this change of regime, we know that there is a unique transition as we have symbolically computed their fixation probability for any r>1. We focus on two graphs which are constructed from the same building blocks and we analyze some possible generalizations by computing the fixation probability, either symbolically when they have enough symmetries or solving the system of linear equations (with extreme precision for a large range of fitness values) otherwise. Because of the expected properties of the rational functions F 0 (r) and F(r) (as monotonically increasing functions with decreasing derivatives), the last two results were not exactly expected. But the existence of multiple crosses for these curves leads us to consider these properties that will be commented in the discussion section (see also S1 Text). The non-uniqueness of transitions also implies that numerical simulation is not enough to determine the evolutionary regime of a graph. Indeed, if there are no transitions or if there is only one transition, we can infer the regime of a graph of the simulation for a narrow range of fitness values. But if there are graphs with multiple changes of regime, it is not possible. Materials and methods In [11], we presented an extremely precise database of fixation probabilities for all undirected graphs of order 10 or less for fitness values rvarying 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 [7], and later regime transitions described here. Initially, we identified two amplifiers of order Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 4 / 18 7 with a transition to the suppression regime at some r c �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 [7] (implementing it in C++, see S1 File) to symbolically compute the fixation probability F(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 r c >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 [11], but solving the system of linear equations for additional fitness values from 10 to 2,000 with step size of 1). Mathematical model Let Gbe an undirected graph with vertex set V= {1, . . .,N}. In fact, all graphs considered here will be assumed connected. Denote by d i the degree of the vertex i. The Moran process on Gis a Markov chain X n whose states are the vertex sets Sinhabited by mutant individuals at each time step n. The transition probabilities are obtained from the matrix W= (w ij ) given by w ij = 1/d i if iand jare neighbors and w ij = 0 otherwise. More precisely, for each fitness value r>0, the transition probability between Sand S0is given by PS;S0ðrÞ ¼ rPi2Swij wSðrÞif S0S¼ fjg; Pi2VnSwij wSðrÞif SS0¼ fjg; rPi;j2Swij þPi;j2VnSwij wSðrÞif S¼S0; 0otherwise; 8 > > > > > > > > > > > > < > > > > > > > > > > > > : ð3Þ where wSðrÞ ¼ rX i2SX j2V wij þX i2VnSX j2V wij ¼rjSjþN jSjð4Þ is the total reproductive weight of resident and mutant individuals. The fixation probability of each subset S�Vinhabited by mutant individuals FSðrÞ ¼ P½9n�0 : Xn¼VjX0¼S� ð5Þ is a solution of the system of 2 N linear equations FSðrÞ ¼ X S0 PS;S0FS0ðrÞð6Þ with boundary conditions F ; (r) = 0 and F V (r) = 1. The (average) fixation probability is given by FðrÞ ¼ 1 NX N i¼1 FfigðrÞ:ð7Þ Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 5 / 18 Denoting by P(r) = (P S,S 0 (r)) the transition matrix, Eq 6 can be written as P(r)¢©(r)= 10 0 b(r)Q(r)c(r) 0 0 1 ¢0 @ 0 ª(r) 1 1 A=0 @ 0 ª(r) 1 1 A=©(r), ð8Þ with respect to the block decomposition of P(r) and Φ(r) obtained from the decomposition of the power set PðVÞinto absorbing states S=;,Vand non-absorbing states S6¼;,V. In other words, Φ(r) = (0, Ψ(r), 1) is the vector with coordinates F S (r), (1, b(r), 0) is the vector with coordinates P S,; (r), and (0, c(r), 1) is the vector with coordinates P S,V (r) for any subset S�V. It can be also rewritten as ðIQðrÞÞ�ΨðrÞ ¼ cðrÞ;ð9Þ where Iis the identity matrix of size 2 N −2. This equation has a unique solution Ψ(r) whose coordinates are rational functions on rwith rational coefficients [7,S1 Text]. But considering Eq 3, we can multiply the equation associated to each state Sby w S (r) reducing Eq 9 to Q�ðrÞ�ΨðrÞ ¼ c�ðrÞ;ð10Þ where the entries of Q�(r) and c�(r) are now degree one polynomials with rational coefficients. Database In [11], we presented an accurate database of the fixation probabilities for all connected undirected graphs with 10 or less vertices, which means 11,989,763 graphs excluding the trivial one with one single vertex. The generation of the edge lists was done with SageMath, whereas the computation of F(r) was written in the C programming language. Firstly, we compute the matrix Q�(r) and the vector c�(r). Since their entries are polynomials of degree one with rational and positive coefficients, they can be represented as two pairs of 64 bits integers. Therefore there is no precision loss in this step. Next, we evaluate Q�(r) and c�(r) for each fitness value r varying from 0.25 to 10 with step size of 0.25, and solve Eq 10 with a high relative precision LU decomposition algorithm (relative errors for isothermal and complete bipartite graphs, used as benchmarks, are less that 10 14 , see [11] for details). Each graph is identified (up to isomorphism) with a unique 64 bits unsigned integer, which allows us to recover the edge list without previous knowledge of its order or size, see again [11] and references therein for details. The database is available from [15]. Computation method A method to compute the exact (average) fixation probability F(r) of graphs of small order with symmetries was described in [7]. As we already said, F(r) = F0(r)/F00(r) is a rational function where the numerator F0ðrÞ ¼ Pd i¼0airiand the denominator F00ðrÞ ¼ Pd i¼0biriare polynomials with rational coefficients of degree d�2 N −2. Symmetries are used to bound the degree dand therefore the number 2(d+ 1) of coefficients involved in the computation of F(r). Since F(r) converges to 1 as r!+1, we can assume a d =b d = 1 and then Eq 6 can be replace with a system of 2dlinear equations X d i¼0 airi¼FðrÞðX d i¼0 biriÞ ð11Þ that arise from evaluating F(r) for fitness values r2{1, . . .,d+ 1, 1/2, . . ., 1/d}. There is some Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 6 / 18 sort of indetermination on the system due to the fact that F0(r) and F00(r) may have common factors. Then, one could pick up any solution of the system (they are different representations of the same rational function) or reduce the bound of duntil one have one single solution (corresponding to the canonical representation of the rational function with coprime numerator and denominator). We developed a C++ program with this algorithm, available from S1 File, which allows us to symbolically • compute the fixation probability F(r) for these values, and • solve the reduced linear system Eq 11. Once F(r) has been computed solving this system, we can determine the regimes and the transitions of the graph by computing the sign and zeros of the rational function F(r)−F 0 (r). Results As explained by Hindersin and Traulsen in [9], 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 [9], most undirected (Erdo¨s-Re ´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 Table 1. Number and percentage of isothermal and suppressor graphs, as well as graphs exhibiting one or more transitions. Graphs are determined up to isomorphism, so any graph cannot be mapped to each other via a permutation of vertices and edges. For graphs of order 6 and 7, the fixation probability has been symbolically computed to exactly give type and place of each transition. These data are gathered in S1 Table. All exact results are marked in bold. However, for graphs of order 8 and more, we must distinguished between suppressors and ‘apparent suppressors’ as fitness values only vary between 1 and 10. Despite this, additional computations for some higher values of the fitness r(varying from 10 to 2,000 with step size of 1) seem exclude more than two transitions in order 8 and 9 and more than three transitions in order 10. N # Iso Sup 1 Trans 2 Trans 3 Trans 6 112 5 (4.46%) 1 (0.89%) 6 S/A (5.36%) 7 853 4 (0.47%) 3 (0.35%) 52 S/A (6.10%) 3 A/S (0.35%) 8 11,117 17 (0.15%) 90 (0.81%) 427 S/A (3.84%) 36 A/S (0.32%) 3 S/A/S (0.03%) 9 261,080 11 (<0.01%) 1,951 (0.75%) 9,489 S/A (3.63%) 854 A/S (0.33%) 43 S/A/S (0.02%) 6 A/S/A (<0.01%) 10 11,716,571 167 (<0.01%) 91,110 (0.78%) 407,001 S/A (3.47%) 40,974 A/S (0.35%) 3,086 S/A/S (0.03%) 578 A/S/A (<0.01%) 19 S/A/S/A (<0.01%) N= Order, #= Number, Isotherm = Isothermal, Sup = Suppressor, Trans = Transition, S/A = Transition from suppressor to amplifier, A/S = Transition from amplifier to suppressor, S/A/S = Double transition Suppressor/Amplifier/Suppressor, A/S/A = Double transition Amplifier/Suppressor/Amplifier, S/A/S/A = Triple transition Suppressor/Amplifier/Suppressor/Amplifier. https://doi.org/10.1371/journal.pone.0200670.t001 Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 7 / 18 number of amplifiers and suppressors of selection is only apparent since the fitness values are limited to a more or less large interval. Thus, in order 6, there are exactly one suppressor of selection, namely the graph ‘ 6 described in [7] (see Fig 1), five isothermal graphs, and six suppressors that become amplifiers from a unique critical value. The remaining 100 graphs are amplifiers of selection. Two of suppressors changing into amplifiers was already described in [11] (see Fig 2(A)). All the graphs portrayed in the paper are gathered in S1 and S2 Figs with indication of their identification numbers, names, regimes and transitions. Amplifiers and suppressors of order 7 A close look to the barcode diagram for the 853 graphs of order 7 (as shown in Fig 3) reveals a new phenomenon: we distinguish two amplifiers that become suppressors from a critical value r c �10. From the symbolic computation of the fixation probability F(r), we find three suppressors of selection, namely Id 1134281908237, Id 1134281902105, and Id 1151998128135, and a number of suppressors that later become amplifiers of selection, namely 52, including the suppressors presented in [6] and depicted in Fig 2(B). Moreover, we find indeed three amplifiers Id 1151592835082, Id 1151860745228, and Id 1151592837126 becoming suppressors at r c �4.98, r c �6.37 and r c �24.79 respectively. A quantitative resume is given in Table 1. Is the suppression of selection a specific property of each of graphs listed above? Or can one infer some suppression mechanism that could even reverse an amplification regime? To answer these questions, at least partially, we have focused on some of these graphs showing certain similarities. Regime transitions for ℓ-graphs The two first suppressors Id 1134281908237 and Id 1134281902105 are shown in Fig 4. For reasons of convenience, we have added a third graph Id 1151998648333 with a unique transition from the suppression to the amplification regime at r c �5.17. Their construction is very similar to ‘-graphs defined in [7]. Recall that ‘N¼‘n;n Nis an undirected graph of even order N= 2n+ 2 �6 obtained from the clique K 2n by dividing its vertex set into two halves with n�2 vertices and adding 2 extra vertices. Each of them is connected to one of the halves of K 2n and with the other extra vertex (see Fig 1). More generally, we denote by ‘n;m Nthe undirected graph obtained adding two interconnected extra vertices to the clique K N−2 and connecting each one to disjoint families of vertices in the clique having nand melements with n+m�N−2. We say that ‘n;m Nis balanced if n=mand unbalanced otherwise. As is also Fig 3. Barcodes describing regime transition of graphs of order 7. Each horizontal line corresponds to a graph, and color represents the evolutionary regime for the given fitness: blue color corresponds to the suppression regime and red color to the amplification regime. (A) Unsorted data for suppressors and graphs with one transition. (B) Sorted data for suppressors and graphs with one transition. https://doi.org/10.1371/journal.pone.0200670.g003 Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 8 / 18 established in S1 Fig, the third graph depicted in Fig 4 is precisely ‘2;2 7. Notice also that only the case n+m=N−2 was considered in [7]. For the three graphs in Fig 4, the suppression mechanism seems directly related to the suppressor nature of ‘-graphs [7] and clique-wheels [12]. Indeed, on a star graph, it is more likely that a peripheral mutant survives and reproduces occupying the central vertex. On the contrary, on a complete graph, it is much more unlikely that the initial mutant will survive surrounded by residents. But in ‘-graphs and clique-wheels, the survival chances of the mutants placed at the central clique are reduced by its connection with peripheral vertices occupied by residents, as well those of the peripheral mutants connected with central residents, although a subtle balance seems to be needed to suppress the reproductive advantage of mutant individuals. To confirm this idea, we explore evolutionary regimes and transitions of some balanced and unbalanced ‘-graphs. In [7], we saw that a subtle balance in the peripheral connections was necessary to the global suppression. More precisely, some unbalanced ‘-graphs of order 7, namely ‘1;4 7and ‘2;3 7, were studied in [7] using Monte Carlo simulation. Both are suppressors: the first one changes into amplifier from a relatively small fitness value, whereas the second one remains a suppressor for any fitness value r�10. Now, due to the new symbolic computation, we know that both present a unique transition (from the suppression to the amplification regime) at r c �1.80 and r c �25.47 respectively. Therefore, we can surmise that only the balanced ‘-graphs with n+ m= 2n=N−2 are global suppressors. In order 8, we consider the graphs ‘2;2 8,‘2;3 8, and ‘1;4 8which are represented in Fig 5. They still are suppressors that become amplifiers from critical values r c �4.15, r c �5.32 and r c �1.89 respectively. Due to the symmetries, the symbolic computation is also applicable to the graphs ‘2;2 Nwhen Nvaries from 6 to 15. The exact differences F(r)−F 0 (r) are depicted in Fig 6 although the monotonous behavior of transitions can be better seen in S2 Table. As before, all these graphs are suppressors with a unique transition to the amplification regime. In summary, there are reasons to accept the existence of a suppression mechanism shared by ‘-graphs and clique-wheels (in the sense of [12] and [14]), although we think that new techniques of potential theory on directed graphs will be probably required to identify any mathematical underlying principle. For this purpose, ‘-graphs have some interest since their state spaces (described explicitly in [7]) are simpler than those of the family of clique-wheels. We ignore if this particular mechanism could has biological interest (although somewhat similar rules have been detected in neural networks), but we think that the existence of suppression mechanisms (especially those that reverse the amplification of selection when the fitness increases) has a real interest in biology and network science. Fig 4. Suppressors for weak selection and beyond. From the symbolic computation of the differences F(r)−F 0 (r), we know that the graphs Id 1134281908237 and Id 1134281902105 are suppressors for any fitness value, while Id 1151998648333 exhibit a unique transition Suppressor/Amplifier at r c �5.17. https://doi.org/10.1371/journal.pone.0200670.g004 Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 9 / 18 graphs, including all graphs of 7 or less vertices. Available from https://bitbucket.org/ geodynapp/fixationfunctions. (ZIP) S1 Table. Regime transitions from order 2 to order 7. Number, place, and type of transitions for all connected graphs of order 7 or less. (PDF) S2 Table. Regime transitions for graphs ℓ2;2 Nfrom order 6 to order 15. (PDF) S1 Fig. Suppressors for weak selection (and beyond). All the figures representing suppressors are gathered with indication of their identification numbers, names, regimes and transitions. (EPS) S2 Fig. Friendship cycles, ribbons and stars. Some friendship cycles FCm N, stars FSm N, and ribbons FRm Nof order N= 7 and 10 are compared. (EPS) S3 Fig. Barcodes describing regime transitions of graphs of order 8. Each horizontal line corresponds to a graph, and color represents the evolutionary regime for the given fitness: blue color corresponds to the suppression regime and red color to amplification regime. (EPS) S4 Fig. Barcodes describing regime transitions of graphs of order 9. Each horizontal line corresponds to a graph, and color represents the evolutionary regime for the given fitness: blue color corresponds to the suppression regime and red color to amplification regime. (EPS) S5 Fig. Barcodes describing regime transitions of graphs of order 10. Each horizontal line corresponds to a graph, and color represents the evolutionary regime for the given fitness: blue color corresponds to the suppression regime and red color to amplification regime. (EPS) S6 Fig. Graphs of order 8 with a double transition of type Suppressor/Amplifier/Suppressor. (EPS) Author Contributions Conceptualization: Fernando Alcalde Cuesta, Pablo Gonza ´lez Sequeiros, A ´lvaro Lozano Rojo. Data curation: A ´lvaro Lozano Rojo. Formal analysis: Fernando Alcalde Cuesta, Pablo Gonza ´lez Sequeiros, A ´lvaro Lozano Rojo. Funding acquisition: Fernando Alcalde Cuesta. Investigation: Fernando Alcalde Cuesta, Pablo Gonza ´lez Sequeiros, A ´lvaro Lozano Rojo. Methodology: Fernando Alcalde Cuesta, Pablo Gonza ´lez Sequeiros, A ´lvaro Lozano Rojo. Project administration: Fernando Alcalde Cuesta. Resources: Fernando Alcalde Cuesta, A ´lvaro Lozano Rojo. Software: A ´lvaro Lozano Rojo. Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 16 / 18 Supervision: Fernando Alcalde Cuesta. Validation: Fernando Alcalde Cuesta, Pablo Gonza ´lez Sequeiros, A ´lvaro Lozano Rojo. Visualization: Fernando Alcalde Cuesta, A ´lvaro Lozano Rojo. Writing – original draft: Fernando Alcalde Cuesta, Pablo Gonza ´lez Sequeiros, A ´lvaro Lozano Rojo. Writing – review & editing: Fernando Alcalde Cuesta, Pablo Gonza ´lez Sequeiros, A ´lvaro Lozano Rojo. References 1. Moran PAP. Random processes in genetics. Proc Cambridge Philos Soc. 1958; 54:60–71. https://doi. org/10.1017/S0305004100033193 2. Maruyama T. On the fixation probability of mutant genes in a subdivided population. Genetical Research. 1970; 15(2):221–225. https://doi.org/10.1017/S0016672300001543 PMID: 5480754 3. Maruyama T. A simple proof that certain quantities are independent of the geographical structure of population. Theoretical Population Biology. 1974; 5(2):148–154. https://doi.org/10.1016/0040-5809(74) 90037-9 PMID: 4825532 4. Lieberman E, Hauert C, Nowak MA. Evolutionary dynamics on graphs. Nature. 2005; 433(7023):312– 316. https://doi.org/10.1038/nature03204 PMID: 15662424 5. Monk T, Green P, Paulin M. Martingales and fixation probabilities of evolutionary graphs. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. 2014; 470 (2165). https://doi.org/10.1098/rspa.2013.0730 6. Broom M, Rychta ´řJ, Stadler BT. Evolutionary dynamics on graphs—the effect of graph structure and initial placement on mutant spread. J Stat Theory Pract. 2011; 5(3):369–381. https://doi.org/10.1080/ 15598608.2011.10412035 7. Alcalde Cuesta F, Gonza ´lez Sequeiros P, Lozano Rojo A. Suppressors of selection. PLOS ONE. 2017; 12(7):1–11. https://doi.org/10.1371/journal.pone.0180549 8. Adlam B, Chatterjee K, Nowak MA. Amplifiers of selection. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. 2015; 471 (2181). https://doi.org/10.1098/rspa. 2015.0114 9. Hindersin L, Traulsen A. Most Undirected Random Graphs Are Amplifiers of Selection for Birth-Death Dynamics, but Suppressors of Selection for Death-Birth Dynamics. PLoS Comput Biol. 2015; 11(11):1– 14. https://doi.org/10.1371/journal.pcbi.1004437 10. Kaveh K, Komarova NL, Kohandel M. The duality of spatial death–birth and birth–death processes and limitations of the isothermal theorem. Royal Society Open Science. 2015; 2(4). https://doi.org/10.1098/ rsos.140465 PMID: 26064637 11. Alcalde Cuesta F, Gonza ´lez Sequeiros P, Lozano Rojo A ´, Vigara Benito R. An Accurate Database of the Fixation Probabilities for All Undirected Graphs of Order 10 or Less. In: Rojas I, Ortuño F, editors. Bioinformatics and Biomedical Engineering: 5th International Work-Conference, IWBBIO 2017, Granada, Spain, April 26–28, 2017, Proceedings, Part II. Cham: Springer International Publishing; 2017. p. 209–220. 12. Mertzios GB, Nikoletseas S, Raptopoulos C, Spirakis PG. Natural models for evolution on networks. Theoretical Computer Science. 2013; 477(Supplement C):76–95. https://doi.org/10.1016/j.tcs.2012.11. 032 13. Wu B, Garcı ´a J, Hauert C, Traulsen A. Extrapolating Weak Selection in Evolutionary Games. PLOS Computational Biology. 2013; 9(12):1–7. https://doi.org/10.1371/journal.pcbi.1003381 14. Choi JO, Yu U. Fixation probability on clique-based graphs. Physica A: Statistical Mechanics and its Applications. 2018; 492:2129–2135. https://doi.org/10.1016/j.physa.2017.11.131. 15. Alcalde Cuesta F, Gonza ´lez Sequeiros P, Lozano Rojo A ´, Vigara Benito R. An accurate database of the fixation probabilities for all undirected graphs of order 10 or less, Mendeley Data, v2; 2017. Available from: https://data.mendeley.com/datasets/587bnf6mt3/2. 16. Alcalde Cuesta F, Gonza ´lez Sequeiros P, Lozano Rojo A ´. Exploring the topological sources of robustness against invasion in biological and technological networks. Scientific Reports. 2016; 6:20666 EP –. Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 17 / 18 17. Hindersin L, Werner B, Dingli D, Traulsen A. Should tissue structure suppress or amplify selection to minimize cancer risk? Biology Direct. 2016; 11(1):41. https://doi.org/10.1186/s13062-016-0140-7 PMID: 27549612 18. Perin R, Berger TK, Markram H. A synaptic organizing principle for cortical neuronal groups. Proceedings of the National Academy of Sciences. 2011; 108(13):5419–5424. https://doi.org/10.1073/pnas. 1016051108 19. Azulay A, Itskovits E, Zaslaver A. The C. elegans Connectome Consists of Homogenous Circuits with Defined Functional Roles. PLOS Computational Biology. 2016; 12(9):1–16. https://doi.org/10.1371/ journal.pcbi.1005021 20. Voorhees B, Murray A. Fixation probabilities for simple digraphs. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. 2013; 469 (2154). https://doi.org/10. 1098/rspa.2012.0676 21. Shakarian P, Roos P, Moores G. A novel analytical method for evolutionary graph theory problems. Biosystems. 2013; 111(2):136–144. https://doi.org/10.1016/j.biosystems.2013.01.006 PMID: 23353025 Evolutionary regime transitions in structured populations PLOS ONE | https://doi.org/10.1371/journal.pone.0200670 November 26, 2018 18 / 18