860
edits
Spatial Moran process: Difference between revisions
From EvoLudo
no edit summary
mNo edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
[[Image:Circulation.svg|thumb|300px|Fairly generic sample population structure. Vertices represent individuals and links define their neighbourhood. A directed link indicates that one individual may be another's neighbour but not vice versa. Each link may have a weight, which indicates the propensity to be selected for reproduction. Reproduction occurs in the direction of the link. The depicted graph represents a [[#Circulation theorem|circulation]] and hence a mutant has the same fixation probability as in the original [[Moran process]] for unstructured populations.]] | [[Image:Circulation.svg|thumb|300px|Fairly generic sample population structure. Vertices represent individuals and links define their neighbourhood. A directed link indicates that one individual may be another's neighbour but not vice versa. Each link may have a weight, which indicates the propensity to be selected for reproduction. Reproduction occurs in the direction of the link. The depicted graph represents a [[#Circulation theorem|circulation]] and hence a mutant has the same fixation probability as in the original [[Moran process]] for unstructured populations.]] | ||
The spatial Moran process models stochastic evolution in structured populations. Population structure is represented by graphs where each vertex represents an individual and edges define the neighbourhood of each individual. The graph can have any structure – for example, square lattices describe spatially extended systems, small-world networks (Watts & Strogatz, 1998) or scale-free networks (Barabasí & Albert, 1999) model social structures – and links between nodes may have different strengths. Links can even be directed such that one individual is a neighbour of another but not vice versa. A fully connected graph, where each node is equally linked to every other node, is essentially equivalent to an unstructured population. Mathematically, the structure of the graph is determined by the adjacency matrix \(\mathbf{W} = [w_{ij}]\) where \(w_{ij}\) denotes the strength of the link between nodes \(i\) and \(j\). If \(w_{ij} =0\) and \(w_{ji} =0\) then the two nodes \(i\) and \(j\) are not connected. | The spatial Moran process models stochastic evolution in structured populations. Population structure is represented by graphs where each vertex represents an individual and edges define the neighbourhood of each individual. The graph can have any structure – for example, square lattices describe spatially extended systems, small-world networks ([[#References|Watts & Strogatz, 1998]]) or scale-free networks ([[#References|Barabasí & Albert, 1999]]) model social structures – and links between nodes may have different strengths. Links can even be directed such that one individual is a neighbour of another but not vice versa. A fully connected graph, where each node is equally linked to every other node, is essentially equivalent to an unstructured population. Mathematically, the structure of the graph is determined by the adjacency matrix \(\mathbf{W} = [w_{ij}]\) where \(w_{ij}\) denotes the strength of the link between nodes \(i\) and \(j\). If \(w_{ij} =0\) and \(w_{ji} =0\) then the two nodes \(i\) and \(j\) are not connected. | ||
The essential difference to the original [[Moran process]] that arises through the population structure is that the offspring of the focal individual replaces a random ''neighbor'' instead of a random member of the population. An additional minor difference is that the offspring cannot replace the focal individual but, in principle, this can be implemented by adding loops to each node. | The essential difference to the original [[Moran process]] that arises through the population structure is that the offspring of the focal individual replaces a random ''neighbor'' instead of a random member of the population. An additional minor difference is that the offspring cannot replace the focal individual but, in principle, this can be implemented by adding loops to each node. | ||
| Line 24: | Line 24: | ||
==Fixation probability== | ==Fixation probability== | ||
In contrast to unstructured (well-mixed) populations, the state of the population is not only determined by just the number of mutants (or residents) but rather needs to take the spatial distribution of mutants and residents into account. Rather surprisingly, however, it turns out that for a large class of graphs, called circulations, the spatial distribution of mutants and residents does not affect their fixation probabilities. This forms the basis for the conjecture by Maruyama (1970) and Slatkin (1981) speculating that population structure leaves fixation probabilities unchanged. Indeed this is true for structures as diverse as complete graphs (every vertex is connected to every other vertex), lattices or random regular graphs (see e.g. Bollobás, 1995). Further examples and interactive demonstrations are covered in [[Evolutionary graph theory/Moran graphs|Moran graphs]]. | In contrast to unstructured (well-mixed) populations, the state of the population is not only determined by just the number of mutants (or residents) but rather needs to take the spatial distribution of mutants and residents into account. Rather surprisingly, however, it turns out that for a large class of graphs, called circulations, the spatial distribution of mutants and residents does not affect their fixation probabilities. This forms the basis for the conjecture by [[#References|Maruyama (1970)]] and [[#References|Slatkin (1981)]] speculating that population structure leaves fixation probabilities unchanged. Indeed this is true for structures as diverse as complete graphs (every vertex is connected to every other vertex), lattices or random regular graphs (see e.g. [[#References|Bollobás, 1995]]). Further examples and interactive demonstrations are covered in [[Evolutionary graph theory/Moran graphs|Moran graphs]]. | ||
===Circulation graphs=== | ===Circulation graphs=== | ||
