Abstract
The rate of biological evolution depends on the fixation probability and on the fixation time of new mutants. Intensive research has focused on identifying population structures that augment the fixation probability of advantageous mutants. But these amplifiers of natural selection typically increase fixation time. Here we study population structures that achieve a tradeoff between fixation probability and time. First, we show that no amplifiers can have an asymptotically lower absorption time than the well-mixed population. Then we design population structures that substantially augment the fixation probability with just a minor increase in fixation time. Finally, we show that those structures enable higher effective rate of evolution than the well-mixed population provided that the rate of generating advantageous mutants is relatively low. Our work sheds light on how population structure affects the rate of evolution. Moreover, our structures could be useful for lab-based, medical, or industrial applications of evolutionary optimization.
The Evolutionary Dilemma
In the study of evolutionary dynamics, two metrics are paramount: fixation probability (the likelihood that a single mutant takes over the entire population) and fixation time (the duration of that takeover). Standard "well-mixed" populations, represented by complete graphs where every individual interacts with every other, serve as the baseline for these metrics.
Researchers have long identified "amplifiers of natural selection"—population structures like the star graph that boost the fixation probability of beneficial mutations. However, these amplifiers often come with a significant "speed penalty," drastically increasing the time required for fixation. This paper addresses whether a fundamental speed limit exists for such amplifiers and if structures can be designed to balance these competing factors.
Mapping the Tradeoff and the Pareto Front
To understand the relationship between probability and time, the researchers conducted an exhaustive numerical analysis of all 11,117 possible undirected connected graphs for a population size of $N=8$. By plotting fixation probability against fixation time, they identified a "Pareto front"—a boundary representing the optimal possible tradeoffs where one metric cannot be improved without degrading the other.
As shown in Figure 6, the complete graph (well-mixed population) sits at the low-probability, low-time end of the spectrum, while the star graph sits at the high-probability, high-time end. The researchers proved a critical theoretical limit: no amplifier can have an absorption time asymptotically lower than the well-mixed population ($O(N \log N)$). Essentially, the complete graph represents the "speed limit" for evolutionary processes.
Designing Efficient Amplifiers: The Bipartite Solution
While the star graph is a powerful amplifier, its fixation time scales as $O(N^2 \log N)$, making it prohibitively slow for large populations. To bridge this gap, the authors introduced a new class of structures: $\alpha$-Balanced bipartite graphs.
These graphs consist of two sets of nodes: a large group of size $N$ and a smaller "hub" group of size $N^{1-\alpha}$. This architecture mimics the hub-and-spoke logic of a star graph but distributes the hub's role across multiple nodes. This design maintains high fixation probability while significantly reducing fixation time to $O(N^{1+\alpha} \log N)$. By adjusting the parameter $\alpha$, one can tune the population structure to achieve star-like amplification with near-well-mixed speed.
The Effective Rate of Evolution
The "best" population structure is not universal; it depends on the mutation rate. The authors defined the "effective rate of evolution" as a combination of how often mutations appear and how likely they are to fixate.
- Rare Mutations: When mutations are infrequent, fixation probability is the primary bottleneck. In this regime, structures like the star graph are superior.
- Frequent Mutations: When mutations are common, the speed of fixation becomes the bottleneck to prevent clonal interference. Here, the well-mixed complete graph is optimal.
- Intermediate Regime: The newly designed $\alpha$-Balanced bipartite graphs dominate the intermediate regime, providing a higher effective rate of evolution than both the complete and star graphs for a wide range of mutation rates.
Conclusion
This research provides a comprehensive framework for understanding how population structure dictates the pace of evolution. By identifying the Pareto front and designing $\alpha$-Balanced bipartite graphs, the authors have provided tools to optimize evolutionary processes. These findings have practical implications for "directed evolution" in laboratory settings, where researchers aim to accelerate the development of improved enzymes, microbes, or other biological products through iterative selection.
Summary updated