862
edits
Evolutionary graph theory: Difference between revisions
From EvoLudo
no edit summary
No edit summary |
No edit summary |
||
| Line 14: | Line 14: | ||
== [[Evolutionary graph theory/Moran graphs|Moran graphs]] == | == [[Evolutionary graph theory/Moran graphs|Moran graphs]] == | ||
[[Image:Moran graph (lattice).png|thumb|200px|On lattices a single mutant has the same fixation probability as in an unstructured population.]] | [[Image:Moran graph (lattice).png|thumb|200px|On lattices a single mutant has the same fixation probability as in an unstructured population.]] | ||
Population structure can be introduced by assuming that the individuals occupy the nodes of a graph. The adjacency matrix \(W = [w_{ij}]\) then determines the structure of the graph, where \(w_{ij}\) denotes the probability that individual \(i\) places its offspring into node \(j\). If \(w_{ij} = w_{ji} = 0\) then the nodes \(i\) and \(j\) are not connected. Interestingly, the fixation probability remains unaffected for a large class of population structures (graphs known as circulations), i.e. is the same as for the original [[#Moran process|Moran process]] in unstructured populations | Population structure can be introduced by assuming that the individuals occupy the nodes of a graph. The adjacency matrix \(W = [w_{ij}]\) then determines the structure of the graph, where \(w_{ij}\) denotes the probability that individual \(i\) places its offspring into node \(j\). If \(w_{ij} = w_{ji} = 0\) then the nodes \(i\) and \(j\) are not connected. Interestingly, the fixation probability remains unaffected for a large class of population structures (graphs known as circulations), i.e. is the same as for the original [[#Moran process|Moran process]] in unstructured populations. For a single mutant this is | ||
\[ | \[ | ||
\rho_1 = \frac{\displaystyle 1-\frac1r}{\displaystyle 1-\frac1{r^N}}. | \rho_1 = \frac{\displaystyle 1-\frac1r}{\displaystyle 1-\frac1{r^N}}. | ||
| Line 23: | Line 23: | ||
== [[Evolutionary graph theory/Evolutionary suppressors|Evolutionary suppressors]] == | == [[Evolutionary graph theory/Evolutionary suppressors|Evolutionary suppressors]] == | ||
[[Image:Evolutionary suppressor (chain).png|thumb|200px|Evolutionary suppressors are structures that reduce selection and enhance random drift, i.e. the fixation probability of advantageous (deleterious) mutants is decreased (increased) as compared to unstructured populations.]] | [[Image:Evolutionary suppressor (chain).png|thumb|200px|Evolutionary suppressors are structures that reduce selection and enhance random drift, i.e. the fixation probability of advantageous (deleterious) mutants is decreased (increased) as compared to unstructured populations.]] | ||
The characteristic balance between selection and drift in Moran graphs can tilt to either side for graphs that are not circulations. For example, suppose \(N\) individuals are arranged in a linear chain. Each individual places its offspring into the position immediately to its right. The leftmost individual is never replaced. The mutant can only reach fixation if it arises in the leftmost position, which happens with probability \(1/N\), but then it will eventually reach fixation with certainty. Clearly, for such one-rooted graphs the fixation probability of a randomly placed mutant is | The characteristic balance between selection and drift in Moran graphs can tilt to either side for graphs that are not circulations. For example, suppose \(N\) individuals are arranged in a linear chain. Each individual places its offspring into the position immediately to its right. The leftmost individual is never replaced. The mutant can only reach fixation if it arises in the leftmost position, which happens with probability \(1/N\), but then it will eventually reach fixation with certainty. Clearly, for such one-rooted graphs the fixation probability of a single, randomly placed mutant is | ||
\[ | \[ | ||
\rho_0 = \frac1N, | \rho_0 = \frac1N, | ||
| Line 32: | Line 32: | ||
== [[Evolutionary graph theory/Evolutionary amplifiers|Evolutionary amplifiers]] == | == [[Evolutionary graph theory/Evolutionary amplifiers|Evolutionary amplifiers]] == | ||
[[Image:Evolutionary amplifier (star).png|thumb|200px|Evolutionary amplifiers are structures that enhance (suppress) the fixation probability of advantageous (deleterious) mutants as compared to unstructured populations.]] | [[Image:Evolutionary amplifier (star).png|thumb|200px|Evolutionary amplifiers are structures that enhance (suppress) the fixation probability of advantageous (deleterious) mutants as compared to unstructured populations.]] | ||
Interestingly, it is also possible to create population structures that amplify selection and suppress random drift. For example, on the star structure, where all nodes are connected to a central hub and vice versa, the fixation probability of a randomly placed mutant becomes | Interestingly, it is also possible to create population structures that amplify selection and suppress random drift. For example, on the star structure, where all nodes are connected to a central hub and vice versa, the fixation probability of a single, randomly placed mutant becomes | ||
\[ | \[ | ||
\rho_2 = \frac{\displaystyle 1-\frac1{r^2}}{\displaystyle 1-\frac1{r^{2N}}}. | \rho_2 = \frac{\displaystyle 1-\frac1{r^2}}{\displaystyle 1-\frac1{r^{2N}}}. | ||
| Line 76: | Line 76: | ||
==Publications== | ==Publications== | ||
#Lieberman, E., Hauert, C. & Nowak, M. (2005) Evolutionary dynamics on graphs ''Nature'' '''433''' 312-316 [http://dx.doi.org/10.1038/nature03204 doi: 10.1038/nature03204]. | #Lieberman, E., Hauert, C. & Nowak, M. (2005) Evolutionary dynamics on graphs ''Nature'' '''433''' 312-316 [http://dx.doi.org/10.1038/nature03204 doi: 10.1038/nature03204]. | ||
#Hauert, C. (2008) Evolutionary Dynamics p. 11-44 in ''Evolution from cellular to social scales'' eds. Skjeltorp, A. T. & Belushkin, A. V., Springer Dordrecht NL. | |||
#Jamieson-Lane, A. & Hauert, C. (2015) Fixation probabilities on superstars, revisited and revised ''J. Theor. Biol.'' '''382''' 44-56 [http://dx.doi.org/10.1016/j.jtbi.2015.06.029 doi: 10.1016/j.jtbi.2015.06.029]. | #Jamieson-Lane, A. & Hauert, C. (2015) Fixation probabilities on superstars, revisited and revised ''J. Theor. Biol.'' '''382''' 44-56 [http://dx.doi.org/10.1016/j.jtbi.2015.06.029 doi: 10.1016/j.jtbi.2015.06.029]. | ||
