Universality of fixation probabilities in randomly structured populations. Adlam B, Nowak MA - Sci Rep (2014) Bottom Line: The structure of the population is known to affect the dynamics and outcome of evolutionary processes, but analytical results for generic random structures have been lacking.The most general result so far, the isothermal theorem, assumes the propensity for change in each position is exactly the same, but realistic biological structures are always subject to variation and noise.Simulations of perturbed lattices, small-world networks, and scale-free networks behave similarly. View Article: PubMed Central - PubMed Affiliation: 1] Program for Evolutionary Dynamics, Harvard University, Cambridge MA 02138, USA [2] School of Engineering and Applied Science, Harvard University, Cambridge MA 02138, USA. ABSTRACTThe stage of evolution is the population of reproducing individuals. The structure of the population is known to affect the dynamics and outcome of evolutionary processes, but analytical results for generic random structures have been lacking. The most general result so far, the isothermal theorem, assumes the propensity for change in each position is exactly the same, but realistic biological structures are always subject to variation and noise. We consider a finite population under constant selection whose structure is given by a variety of weighted, directed, random graphs; vertices represent individuals and edges interactions between individuals. By establishing a robustness result for the isothermal theorem and using large deviation estimates to understand the typical structure of random graphs, we prove that for a generalization of the Erdős-Rényi model, the fixation probability of an invading mutant is approximately the same as that of a mutant of equal fitness in a well-mixed population with high probability. Simulations of perturbed lattices, small-world networks, and scale-free networks behave similarly. We conjecture that the fixation probability in a well-mixed population, (1 - r(-1))/(1 - r(-n)), is universal: for many random graph models, the fixation probability approaches the above function uniformly as the graphs become large. Show MeSH MajorModels, Theoretical*MinorAlgorithms © Copyright Policy - open-access Related In: Results  -  Collection License getmorefigures.php?uid=PMC4209402&req=5 .flowplayer { width: px; height: px; } f3: Small-world networks also show universal behavior.Representative Watts-Strogatz random graphs display increasing disorder as the rewiring probability β increases from 0 to 1, which may be viewed as an interpolation between an isothermal graph and an Erdős-Rényi random graph. For all values of β the correspondence to is striking but mathematical proof is lacking. Mentions: In addition to the generalized Erdős-Rényi random graphs, we also considered the Watts-Strogatz model and the Barabási-Albert model. The Watts-Strogatz model35 produces random graphs with small-world properties, that is, high clustering and short average path length. The model has three inputs: a parameter 0 ≤ β ≤ 1, the graph size n, and the mean degree 2k. Typically, the model produces random, undirected graphs, thus, to escape isothermality, it was modified slightly to produce weighted, directed graphs. We do this in the most natural way: we start with a directed 2k-regular graph where each node is connected to its 2k nearest neighbors if the graph is arranged on a cycle (Figure 3), and then we rewire each edge to a new vertex chosen uniformly at random with probability β independently. Since the number of edges leaving each vertex is fixed at 2k, the weight of each edge is exactly 1/(2k). Potentially, there can be multiple edges for one vertex to another, which we account for by summing the edge weights. The model may be viewed as an interpolation between an isothermal, 2k-regular graph and an Erdős-Rényi graph by the parameter β.

Universality of fixation probabilities in randomly structured populations.

Adlam B, Nowak MA - Sci Rep (2014)

Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC4209402&req=5

f3: Small-world networks also show universal behavior.Representative Watts-Strogatz random graphs display increasing disorder as the rewiring probability β increases from 0 to 1, which may be viewed as an interpolation between an isothermal graph and an Erdős-Rényi random graph. For all values of β the correspondence to is striking but mathematical proof is lacking.
Mentions: In addition to the generalized Erdős-Rényi random graphs, we also considered the Watts-Strogatz model and the Barabási-Albert model. The Watts-Strogatz model35 produces random graphs with small-world properties, that is, high clustering and short average path length. The model has three inputs: a parameter 0 ≤ β ≤ 1, the graph size n, and the mean degree 2k. Typically, the model produces random, undirected graphs, thus, to escape isothermality, it was modified slightly to produce weighted, directed graphs. We do this in the most natural way: we start with a directed 2k-regular graph where each node is connected to its 2k nearest neighbors if the graph is arranged on a cycle (Figure 3), and then we rewire each edge to a new vertex chosen uniformly at random with probability β independently. Since the number of edges leaving each vertex is fixed at 2k, the weight of each edge is exactly 1/(2k). Potentially, there can be multiple edges for one vertex to another, which we account for by summing the edge weights. The model may be viewed as an interpolation between an isothermal, 2k-regular graph and an Erdős-Rényi graph by the parameter β.

Bottom Line: The structure of the population is known to affect the dynamics and outcome of evolutionary processes, but analytical results for generic random structures have been lacking.The most general result so far, the isothermal theorem, assumes the propensity for change in each position is exactly the same, but realistic biological structures are always subject to variation and noise.Simulations of perturbed lattices, small-world networks, and scale-free networks behave similarly.

View Article: PubMed Central - PubMed

Affiliation: 1] Program for Evolutionary Dynamics, Harvard University, Cambridge MA 02138, USA [2] School of Engineering and Applied Science, Harvard University, Cambridge MA 02138, USA.

ABSTRACT
The stage of evolution is the population of reproducing individuals. The structure of the population is known to affect the dynamics and outcome of evolutionary processes, but analytical results for generic random structures have been lacking. The most general result so far, the isothermal theorem, assumes the propensity for change in each position is exactly the same, but realistic biological structures are always subject to variation and noise. We consider a finite population under constant selection whose structure is given by a variety of weighted, directed, random graphs; vertices represent individuals and edges interactions between individuals. By establishing a robustness result for the isothermal theorem and using large deviation estimates to understand the typical structure of random graphs, we prove that for a generalization of the Erdős-Rényi model, the fixation probability of an invading mutant is approximately the same as that of a mutant of equal fitness in a well-mixed population with high probability. Simulations of perturbed lattices, small-world networks, and scale-free networks behave similarly. We conjecture that the fixation probability in a well-mixed population, (1 - r(-1))/(1 - r(-n)), is universal: for many random graph models, the fixation probability approaches the above function uniformly as the graphs become large.

Show MeSH