860
edits
Evolutionary graph theory: Difference between revisions
From EvoLudo
no edit summary
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{InCharge|author1=Christoph Hauert}} | {{InCharge|author1=Christoph Hauert}} | ||
__NOTOC__ | |||
Evolutionary dynamics act on populations. Neither genes, nor cells, nor individuals but populations evolve. In small populations, random drift dominates, whereas large populations are sensitive to subtle differences in selective values. Traditionally, evolutionary dynamics was studied in the context of well-mixed or spatially extended populations. Here we generalize population structure by arranging individuals on a graph. Each vertex represents an individual. The fitness of an individual denotes its reproductive rate, which determines how often offspring is placed into adjacent vertices. | Evolutionary dynamics act on populations. Neither genes, nor cells, nor individuals but populations evolve. In small populations, random drift dominates, whereas large populations are sensitive to subtle differences in selective values. Traditionally, evolutionary dynamics was studied in the context of well-mixed or spatially extended populations. Here we generalize population structure by arranging individuals on a graph. Each vertex represents an individual. The fitness of an individual denotes its reproductive rate, which determines how often offspring is placed into adjacent vertices. | ||
| Line 13: | Line 13: | ||
== [[Evolutionary graph theory/Moran graphs|Moran graphs]] == | == [[Evolutionary graph theory/Moran graphs|Moran graphs]] == | ||
[[Image:Moran graph (lattice).png|thumb| | [[Image:Moran graph (lattice).png|thumb|300px|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]] in unstructured populations. For a single mutant this is | 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]] in unstructured populations. For a single mutant this is | ||
\[ | \[ | ||
| Line 22: | Line 22: | ||
== [[Evolutionary graph theory/Evolutionary suppressors|Evolutionary suppressors]] == | == [[Evolutionary graph theory/Evolutionary suppressors|Evolutionary suppressors]] == | ||
[[Image:Evolutionary suppressor (chain).png|thumb| | [[Image:Evolutionary suppressor (chain).png|thumb|300px|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 single, 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 | ||
\[ | \[ | ||
| Line 31: | Line 31: | ||
== [[Evolutionary graph theory/Evolutionary amplifiers|Evolutionary amplifiers]] == | == [[Evolutionary graph theory/Evolutionary amplifiers|Evolutionary amplifiers]] == | ||
[[Image:Evolutionary amplifier (star).png|thumb| | [[Image:Evolutionary amplifier (star).png|thumb|300px|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 single, 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 | ||
\[ | \[ | ||
