Evolutionary graph theory - Revision history

Hauert at 18:06, 13 October 2023

2023-10-13T18:06:36Z

← Older revision		Revision as of 11:06, 13 October 2023
Line 13:		Line 13:
	Population structure can be modelled by arranging individuals on a graph such that each individual is represented by a vertex and its neighbourhood is defined through links connecting it to other individuals. Interestingly, for the [[spatial Moran process]] 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 modelled by arranging individuals on a graph such that each individual is represented by a vertex and its neighbourhood is defined through links connecting it to other individuals. Interestingly, for the [[spatial Moran process]] 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
	\begin{align}		\begin{align}
	\rho_1 = \frac{\displaystyle 1-\frac1r}{\displaystyle 1-\frac1{r^N}}		\qquad\rho_1 = \frac{\displaystyle 1-\frac1r}{\displaystyle 1-\frac1{r^N}}
	\end{align}		\end{align}
	and is even the same regardless of the initial location of the mutant. This applies, for example, for the fixation probabilities of mutants on the complete graph where every vertex is connected to every other one, on cycles, on lattices, on random regular graphs, and many more. Interestingly, however, the same is not true for fixation times. In fact, fixation times sensitively depend on the details of the population structure. However, sufficiently [[Graph symmetries\|symmetrical graphs]] can at least ensure that the fixation time does not depend on the initial location of a mutant.		and is even the same regardless of the initial location of the mutant. This applies, for example, for the fixation probabilities of mutants on the complete graph where every vertex is connected to every other one, on cycles, on lattices, on random regular graphs, and many more. Interestingly, however, the same is not true for fixation times. In fact, fixation times sensitively depend on the details of the population structure. However, sufficiently [[Graph symmetries\|symmetrical graphs]] can at least ensure that the fixation time does not depend on the initial location of a mutant.
Line 22:		Line 22:
	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
	\begin{align}		\begin{align}
	\rho_0 = \frac1N,		\qquad\rho_0 = \frac1N,
	\end{align}		\end{align}
	irrespective of \(r\). The chain is an example of a simple population structure which eliminates selection and whose dynamic is determined by random drift.		irrespective of \(r\). The chain is an example of a simple population structure which eliminates selection and whose dynamic is determined by random drift.
Line 31:		Line 31:
	Interestingly, it is also possible to create population structures that amplify selection and suppress random drift. For example, on the star graph, 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 graph, where all nodes are connected to a central hub and vice versa, the fixation probability of a single, randomly placed mutant becomes
	\begin{align}		\begin{align}
	\rho_2 = \frac{\displaystyle 1-\frac1{r^2}}{\displaystyle 1-\frac1{r^{2N}}}		\qquad\rho_2 = \frac{\displaystyle 1-\frac1{r^2}}{\displaystyle 1-\frac1{r^{2N}}}
	\end{align}		\end{align}
	for large \(N\). Thus, any selective difference \(r\) is amplified to \(r^2\). Even more intriguingly, population structures exist that act as arbitrarily strong amplifiers of selection and suppressors of random drift. However, note that amplification has its price in that the average fixation time goes to infinity as the amplification increases.		for large \(N\). Thus, any selective difference \(r\) is amplified to \(r^2\). Even more intriguingly, population structures exist that act as arbitrarily strong amplifiers of selection and suppressors of random drift. However, note that amplification has its price in that the average fixation time goes to infinity as the amplification increases.

Hauert: /* Evolutionary amplifiers */

2023-10-12T07:19:28Z

Evolutionary amplifiers

← Older revision		Revision as of 00:19, 12 October 2023
Line 30:		Line 30:
	[[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. The simplest example is the star graph, which consists of a single, central hub that is (bidirectionally) connected to all other vertices.]]		[[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. The simplest example is the star graph, which consists of a single, central hub that is (bidirectionally) connected to all other vertices.]]
	Interestingly, it is also possible to create population structures that amplify selection and suppress random drift. For example, on the star graph, 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 graph, where all nodes are connected to a central hub and vice versa, the fixation probability of a single, randomly placed mutant becomes
	\[		\begin{align}
	\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}}}
	\]		\end{align}
	for large \(N\). Thus, any selective difference \(r\) is amplified to \(r^2\). Even more intriguingly, population structures exist that act as arbitrarily strong amplifiers of selection and suppressors of random drift. However, note that amplification has its price in that the average fixation time goes to infinity as the amplification increases.		for large \(N\). Thus, any selective difference \(r\) is amplified to \(r^2\). Even more intriguingly, population structures exist that act as arbitrarily strong amplifiers of selection and suppressors of random drift. However, note that amplification has its price in that the average fixation time goes to infinity as the amplification increases.
	{{-}}		{{-}}

Hauert: /* Evolutionary suppressors */

2023-10-12T07:18:53Z

Evolutionary suppressors

← Older revision		Revision as of 00:18, 12 October 2023
Line 21:		Line 21:
	[[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 simplest example is a linear chain with directed links all pointing in the same direction.]]		[[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 simplest example is a linear chain with directed links all pointing in the same direction.]]
	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
	\[		\begin{align}
	\rho_0 = \frac1N,		\rho_0 = \frac1N,
	\]		\end{align}
	irrespective of \(r\). The chain is an example of a simple population structure which eliminates selection and whose dynamic is determined by random drift.		irrespective of \(r\). The chain is an example of a simple population structure which eliminates selection and whose dynamic is determined by random drift.
	{{-}}		{{-}}

Hauert at 04:19, 29 August 2016

2016-08-29T04:19:06Z

← Older revision		Revision as of 21:19, 28 August 2016
Line 12:		Line 12:
	[[Image:Moran graph (lattice).png\|thumb\|300px\|On lattices the [[spatial Moran process]] results in the same fixation probability of a single (or several) mutants as the original [[Moran process]] in unstructured populations.]]		[[Image:Moran graph (lattice).png\|thumb\|300px\|On lattices the [[spatial Moran process]] results in the same fixation probability of a single (or several) mutants as the original [[Moran process]] in unstructured populations.]]
	Population structure can be modelled by arranging individuals on a graph such that each individual is represented by a vertex and its neighbourhood is defined through links connecting it to other individuals. Interestingly, for the [[spatial Moran process]] 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 modelled by arranging individuals on a graph such that each individual is represented by a vertex and its neighbourhood is defined through links connecting it to other individuals. Interestingly, for the [[spatial Moran process]] 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
	\[		\begin{align}
	\rho_1 = \frac{\displaystyle 1-\frac1r}{\displaystyle 1-\frac1{r^N}}		\rho_1 = \frac{\displaystyle 1-\frac1r}{\displaystyle 1-\frac1{r^N}}
	\]		\end{align}
	and is even the same regardless of the initial location of the mutant. This applies, for example, for the fixation probabilities of mutants on the complete graph where every vertex is connected to every other one, on cycles, on lattices, on random regular graphs, and many more. Interestingly, however, the same is not true for fixation times. In fact, fixation times sensitively depend on the details of the population structure. However, sufficiently [[Graph symmetries\|symmetrical graphs]] can at least ensure that the fixation time does not depend on the initial location of a mutant.		and is even the same regardless of the initial location of the mutant. This applies, for example, for the fixation probabilities of mutants on the complete graph where every vertex is connected to every other one, on cycles, on lattices, on random regular graphs, and many more. Interestingly, however, the same is not true for fixation times. In fact, fixation times sensitively depend on the details of the population structure. However, sufficiently [[Graph symmetries\|symmetrical graphs]] can at least ensure that the fixation time does not depend on the initial location of a mutant.
	{{-}}		{{-}}
Line 31:		Line 31:
	Interestingly, it is also possible to create population structures that amplify selection and suppress random drift. For example, on the star graph, 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 graph, 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}}}
	\]		\]
	for large \(N\). Thus, any selective difference \(r\) is amplified to \(r^2\). Even more intriguingly, population structures exist that act as arbitrarily strong amplifiers of selection and suppressors of random drift. However, note that amplification has its price in that the average fixation time goes to infinity as the amplification increases.		for large \(N\). Thus, any selective difference \(r\) is amplified to \(r^2\). Even more intriguingly, population structures exist that act as arbitrarily strong amplifiers of selection and suppressors of random drift. However, note that amplification has its price in that the average fixation time goes to infinity as the amplification increases.

Hauert at 22:47, 23 August 2016

2016-08-23T22:47:56Z

← Older revision		Revision as of 15:47, 23 August 2016
Line 9:		Line 9:
	In the following, we study the simplest possible question: what is the probability that a single mutant generates a lineage that takes over the entire population? This fixation probability determines the rate of evolution. The higher the correlation between the mutant's fitness and its probability of fixation, the stronger the effect of natural selection; if fixation is largely independent of fitness, drift dominates. Interestingly, it turns out that a large class of population structures maintains a characteristic balance between selection and random drift and leaves the fixation probability unchanged, i.e. identical to unstructured populations. Those graphs are called circulations. However, other graphs can have tremenduous effects on the fixation probability of mutants, ranging from complete suppression of selection to complete suppression of random drift, i.e. amplification of selection.		In the following, we study the simplest possible question: what is the probability that a single mutant generates a lineage that takes over the entire population? This fixation probability determines the rate of evolution. The higher the correlation between the mutant's fitness and its probability of fixation, the stronger the effect of natural selection; if fixation is largely independent of fitness, drift dominates. Interestingly, it turns out that a large class of population structures maintains a characteristic balance between selection and random drift and leaves the fixation probability unchanged, i.e. identical to unstructured populations. Those graphs are called circulations. However, other graphs can have tremenduous effects on the fixation probability of mutants, ranging from complete suppression of selection to complete suppression of random drift, i.e. amplification of selection.

	== [[~~Evolutionary graph theory/Moran graphs\|~~Moran graphs]] ==		== [[Moran graphs]] ==
	[[Image:Moran graph (lattice).png\|thumb\|300px\|On lattices the [[spatial Moran process]] results in the same fixation probability of a single (or several) mutants as the original [[Moran process]] in unstructured populations.]]		[[Image:Moran graph (lattice).png\|thumb\|300px\|On lattices the [[spatial Moran process]] results in the same fixation probability of a single (or several) mutants as the original [[Moran process]] in unstructured populations.]]
	Population structure can be modelled by arranging individuals on a graph such that each individual is represented by a vertex and its neighbourhood is defined through links connecting it to other individuals. Interestingly, for the [[spatial Moran process]] 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 modelled by arranging individuals on a graph such that each individual is represented by a vertex and its neighbourhood is defined through links connecting it to other individuals. Interestingly, for the [[spatial Moran process]] 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 18:		Line 18:
	{{-}}		{{-}}

	== [[~~Evolutionary graph theory/Evolutionary suppressors\|~~Evolutionary suppressors]] ==		== [[Evolutionary suppressors]] ==
	[[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 simplest example is a linear chain with directed links all pointing in the same direction.]]		[[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 simplest example is a linear chain with directed links all pointing in the same direction.]]
	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 27:		Line 27:
	{{-}}		{{-}}

	== [[~~Evolutionary graph theory/Evolutionary amplifiers\|~~Evolutionary amplifiers]] ==		== [[Evolutionary amplifiers]] ==
	[[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. The simplest example is the star graph, which consists of a single, central hub that is (bidirectionally) connected to all other vertices.]]		[[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. The simplest example is the star graph, which consists of a single, central hub that is (bidirectionally) connected to all other vertices.]]
	Interestingly, it is also possible to create population structures that amplify selection and suppress random drift. For example, on the star graph, 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 graph, where all nodes are connected to a central hub and vice versa, the fixation probability of a single, randomly placed mutant becomes
Line 43:		Line 43:
	===Press & News===		===Press & News===
	# Guimerà, R. & Sales-Pardo, M. (2006) Form follows function: the architecture of complex networks ''Molecular Systems Biology'' '''2''' 42 [http://dx.doi.org/10.1038/msb4100082 doi: 10.1038/msb4100082].		# Guimerà, R. & Sales-Pardo, M. (2006) Form follows function: the architecture of complex networks ''Molecular Systems Biology'' '''2''' 42 [http://dx.doi.org/10.1038/msb4100082 doi: 10.1038/msb4100082].

			[[Category:Evolutionary graph theory]][[Category:Tutorial]]

Hauert at 17:22, 23 August 2016

2016-08-23T17:22:36Z

← Older revision		Revision as of 10:22, 23 August 2016
Line 5:		Line 5:
	Popular population structures include well-mixed (or 'unstructured') populations, which correspond to fully connected (or complete) graphs or populations with spatial dimensions that are represented by lattices. Other, more general population structures include small-world or scale-free networks.		Popular population structures include well-mixed (or 'unstructured') populations, which correspond to fully connected (or complete) graphs or populations with spatial dimensions that are represented by lattices. Other, more general population structures include small-world or scale-free networks.

	The stochastic dynamics of selection and random drift is traditionally modelled by the [[Moran process]] for finite, unstructured (well-mixed) populations. This process has the nice, i.e. mathematically convenient, feature that the population size is preserved and is easily adapted to model evolutionary processes in structured populations, the [[~~Spatial~~ Moran process]].		The stochastic dynamics of selection and random drift is traditionally modelled by the [[Moran process]] for finite, unstructured (well-mixed) populations. This process has the nice, i.e. mathematically convenient, feature that the population size is preserved and is easily adapted to model evolutionary processes in structured populations, the [[spatial Moran process]].

	In the following, we study the simplest possible question: what is the probability that a single mutant generates a lineage that takes over the entire population? This fixation probability determines the rate of evolution. The higher the correlation between the mutant's fitness and its probability of fixation, the stronger the effect of natural selection; if fixation is largely independent of fitness, drift dominates.		In the following, we study the simplest possible question: what is the probability that a single mutant generates a lineage that takes over the entire population? This fixation probability determines the rate of evolution. The higher the correlation between the mutant's fitness and its probability of fixation, the stronger the effect of natural selection; if fixation is largely independent of fitness, drift dominates. Interestingly, it turns out that a large class of population structures maintains a characteristic balance between selection and random drift and leaves the fixation probability unchanged, i.e. identical to unstructured populations. Those graphs are called circulations. However, other graphs can have tremenduous effects on the fixation probability of mutants, ranging from complete suppression of selection to complete suppression of random drift, i.e. amplification of selection.

	A large class of ~~graphs exhibit~~ a characteristic balance between selection and drift ~~as characterised by~~ the ~~circulation theorem~~. ~~Nevertheless~~, ~~the structure of the~~ graphs can have tremenduous effects on the fixation probability of ~~mutant~~ ranging from complete suppression of selection to complete suppression of random drift, i.e. amplification of selection. If, in addition, individuals interact with their neighbors, reflecting frequency dependent fitness, the dynamics becomes very complicated but first studies show very interesting and counterintuitive results.

	== [[Evolutionary graph theory/Moran graphs\|Moran graphs]] ==		== [[Evolutionary graph theory/Moran graphs\|Moran graphs]] ==
	[[Image:Moran graph (lattice).png\|thumb\|300px\|On lattices ~~a single mutant has~~ the same fixation probability as in an unstructured ~~population~~.]]		[[Image:Moran graph (lattice).png\|thumb\|300px\|On lattices the [[spatial Moran process]] results in the same fixation probability of a single (or several) mutants as the original [[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]] in unstructured populations. For a single mutant this is		Population structure can be modelled by arranging individuals on a graph such that each individual is represented by a vertex and its neighbourhood is defined through links connecting it to other individuals. Interestingly, for the [[spatial Moran process]] 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
	\[		\[
	\rho_1 = \frac{\displaystyle 1-\frac1r}{\displaystyle 1-\frac1{r^N}}.		\rho_1 = \frac{\displaystyle 1-\frac1r}{\displaystyle 1-\frac1{r^N}}
	\]		\]
	and ~~does not depend on~~ the initial location of the mutant. This applies, for example, for the fixation probabilities of mutants on lattices.		and is even the same regardless of the initial location of the mutant. This applies, for example, for the fixation probabilities of mutants on the complete graph where every vertex is connected to every other one, on cycles, on lattices, on random regular graphs, and many more. Interestingly, however, the same is not true for fixation times. In fact, fixation times sensitively depend on the details of the population structure. However, sufficiently [[Graph symmetries\|symmetrical graphs]] can at least ensure that the fixation time does not depend on the initial location of a mutant.
	{{-}}		{{-}}

Hauert: /* Evolutionary suppressors */

2016-08-23T02:07:31Z

Evolutionary suppressors

← Older revision		Revision as of 19:07, 22 August 2016
Line 21:		Line 21:

	== [[Evolutionary graph theory/Evolutionary suppressors\|Evolutionary suppressors]] ==		== [[Evolutionary graph theory/Evolutionary suppressors\|Evolutionary suppressors]] ==
	[[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.]]		[[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 simplest example is a linear chain with directed links all pointing in the same direction.]]
	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
	\[		\[

Hauert: /* Evolutionary amplifiers */

2016-08-23T02:05:48Z

Evolutionary amplifiers

← Older revision		Revision as of 19:05, 22 August 2016
Line 30:		Line 30:

	== [[Evolutionary graph theory/Evolutionary amplifiers\|Evolutionary amplifiers]] ==		== [[Evolutionary graph theory/Evolutionary amplifiers\|Evolutionary amplifiers]] ==
	[[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.]]		[[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. The simplest example is the star graph, which consists of a single, central hub that is (bidirectionally) connected to all other vertices.]]
	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 graph, 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}}}.

Hauert at 02:00, 23 August 2016

2016-08-23T02:00:27Z

← Older revision		Revision as of 19:00, 22 August 2016
Line 1:		Line 1:
	{{InCharge\|author1=Christoph Hauert}}		{{InCharge\|author1=Christoph Hauert}}__NOTOC__
	__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.

Hauert at 03:01, 22 August 2016

2016-08-22T03:01:23Z

← Older revision		Revision as of 20:01, 21 August 2016
Line 1:		Line 1:
	{{InCharge\|author1=Christoph Hauert}}		{{InCharge\|author1=Christoph Hauert}}
	~~{{TOCright}}~~		__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\|~~200px~~\|On lattices a single mutant has the same fixation probability as in an unstructured population.]]		[[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\|~~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\|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\|~~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\|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
	\[		\[