860
edits
Moran graphs: Difference between revisions
From EvoLudo
m
→Fixation probability on circulation graphs
No edit summary |
|||
| (2 intermediate revisions by the same user not shown) | |||
| 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 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 and hence a mutant has the same fixation probability as in the original [[Moran process]] for unstructured populations.]] | ||
Moran graphs mark | Moran graphs mark an important reference point in [[evolutionary graph theory]] because they maintain the balance between selection and random drift of the original [[Moran process]]. For those graphs the [[spatial Moran process]] leaves the fixation probabilities of a mutant unchanged and identical to the original [[Moran process]] in unstructured, well-mixed populations. Rather surprisingly it turns out that this applies to a large class of graphs, called circulations. | ||
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 pointing from vertex \(i\) to vertex \(j\). If \(w_{ij} =0\) and \(w_{ji} =0\) then the two vertices \(i\) and \(j\) are not connected. In order to characterize circulations, let us introduce the flux through each vertex. The sum of the weights of the incoming links \(f_i^\text{in}=\sum_j w_{ji}\) denotes the flux entering vertex \(i\). \(f_i^\text{in}\) relates to a temperature because it indicates the rate at which the occupant of vertex \(i\) gets replaced. ‘Hot’ vertices are frequently replaced and ‘cold’ vertices are only rarely updated. In analogy, the sum of the weights of the outgoing links \(f_i^\text{out}=\sum_j w_{ij}\) denotes the flux leaving vertex \(i\). \(f_i^\text{out}\) determines the impact of vertex \(i\) on its neighborhood. All graphs, which satisfy \(f_i^\text{in}=f_i^\text{out}\) for all vertices, are circulations. With this we can state a remarkable theorem: | 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 pointing from vertex \(i\) to vertex \(j\). If \(w_{ij} =0\) and \(w_{ji} =0\) then the two vertices \(i\) and \(j\) are not connected. In order to characterize circulations, let us introduce the flux through each vertex. The sum of the weights of the incoming links \(f_i^\text{in}=\sum_j w_{ji}\) denotes the flux entering vertex \(i\). \(f_i^\text{in}\) relates to a temperature because it indicates the rate at which the occupant of vertex \(i\) gets replaced. ‘Hot’ vertices are frequently replaced and ‘cold’ vertices are only rarely updated. In analogy, the sum of the weights of the outgoing links \(f_i^\text{out}=\sum_j w_{ij}\) denotes the flux leaving vertex \(i\). \(f_i^\text{out}\) determines the impact of vertex \(i\) on its neighborhood. All graphs, which satisfy \(f_i^\text{in}=f_i^\text{out}\) for all vertices, are circulations. With this we can state a remarkable theorem: | ||
| Line 76: | Line 76: | ||
==Fixation times on Moran graphs== | ==Fixation times on Moran graphs== | ||
According to their definition, mutations on Moran graphs maintain the same fixation probabilities as in the original Moran process in unstructured populations. However, this has no implications on the fixation times of a mutant or on the absorption time, i.e. the time until the population reaches either one of the absorbing states with all mutants or all residents. In fact, fixation and absorption times vary greatly even between different circulation graphs, as illustrated with the following simulations for diverse examples of circulations. Even though to date rigorous connections between structural features and fixation times are lacking, the [https://en.wikipedia.org/wiki/Distance_(graph_theory) diameter of a graph] correlates with fixation times. The diameter of a graph \(d\) is defined as the longest shortest path between any two vertices and provides a measure for how many updates are at least required until the progeny of any one particular vertex could occupy any other vertex. Other, related measures such as the [https://en.wikipedia.org/wiki/Distance_(graph_theory) radius of a graph] or the average [https://en.wikipedia.org/wiki/Shortest_path_problem shortest distance] seem to work equally well. | According to their definition, mutations on Moran graphs maintain the same fixation probabilities as in the original Moran process in unstructured populations. However, this has no implications on the fixation times of a mutant or on the absorption time, i.e. the time until the population reaches either one of the absorbing states with all mutants or all residents. In fact, fixation and absorption times vary greatly even between different circulation graphs, as illustrated with the following simulations for diverse examples of circulations. Moreover, even on circulation graphs fixation times in general also depend on the location of the initial mutant. Only sufficiently [[Graph symmetries|symmetrical graphs]] can at least ensure that fixations times do not depend on the location of the initial mutant. However, even then fixation times differ between different graphs. | ||
Even though to date rigorous connections between structural features and fixation times are lacking, the [https://en.wikipedia.org/wiki/Distance_(graph_theory) diameter of a graph] correlates with fixation times. The diameter of a graph \(d\) is defined as the longest shortest path between any two vertices and provides a measure for how many updates are at least required until the progeny of any one particular vertex could occupy any other vertex. Other, related measures such as the [https://en.wikipedia.org/wiki/Distance_(graph_theory) radius of a graph] or the average [https://en.wikipedia.org/wiki/Shortest_path_problem shortest distance] seem to work equally well. | |||
<div class="lab_description Moran"> | <div class="lab_description Moran"> | ||
| Line 112: | Line 114: | ||
Recall that the number of mutants in the population changes only if a replacement occurs along any link that connects residents with mutants or vice versa. Because the Moran process essentially selects links with a probability proportional to the link weight and the fitness of the vertex at its tail, it follows that for each subset, the probability that another mutant is added is simply given by \(r/(1 + r)\) and the complementary probability to remove one mutant is \(1/(1 + r)\). Since this holds for each subset, it also holds for the entire population and is independent of the number, size, shape and distribution of mutant subsets. This invariance applies only if the circulation theorem is satisfied. Consequentially, the fixation probability on circulation graphs reduces to the recursive equation derived for the original [[Moran process]]. | Recall that the number of mutants in the population changes only if a replacement occurs along any link that connects residents with mutants or vice versa. Because the Moran process essentially selects links with a probability proportional to the link weight and the fitness of the vertex at its tail, it follows that for each subset, the probability that another mutant is added is simply given by \(r/(1 + r)\) and the complementary probability to remove one mutant is \(1/(1 + r)\). Since this holds for each subset, it also holds for the entire population and is independent of the number, size, shape and distribution of mutant subsets. This invariance applies only if the circulation theorem is satisfied. Consequentially, the fixation probability on circulation graphs reduces to the recursive equation derived for the original [[Moran process]]. | ||
Note that even though the fixation probabilities remain unchanged on circulation graphs, the corresponding fixation times are very sensitive to the details of the population structure and pose a much harder problem. The circulation theorem only ensures that the ''ratio'' of the transition probabilities \(T^+/T^− = r\) remains unchanged, i.e. independent of the number and distribution of residents and mutants, but even on circulation graphs \(T^+\) and \(T^−\) depend not only on the number but also on the distribution of mutants. Generally, population structures tend to substantially increase the fixation times because the structure limits the possibilities for mutants to conquer new vertices. | Note that even though the fixation probabilities remain unchanged on circulation graphs, the corresponding fixation times are very sensitive to the details of the population structure and pose a much harder problem. Moreover, fixation times generally depend on the location of the initial mutant. Only additional [[Graph symmetries|structural symmetries]] can ensure that the fixation times are independent of the location on one graph but not across different graphs. The circulation theorem only ensures that the ''ratio'' of the transition probabilities \(T^+/T^− = r\) remains unchanged, i.e. independent of the number and distribution of residents and mutants, but even on circulation graphs \(T^+\) and \(T^−\) depend not only on the number but also on the distribution of mutants. Generally, population structures tend to substantially increase the fixation times because the structure limits the possibilities for mutants to conquer new vertices. | ||
{{-}} | {{-}} | ||
