C3: Publications
Universality Classes of Interaction Structures for NK Fitness Landscapes
Hwang S., Schmiegelt B., Ferretti L., Krug J., 13. Feb. 2018, J. Stat. Phys. 172:226-278, https://doi.org/10.1007/s10955-018-1979-z
Kauffman’s NK-model is a paradigmatic example of a class of stochastic models of genotypic fitness landscapes that aim to capture generic features of epistatic interactions in multilocus systems. Genotypes are represented as sequences of L binary loci. The fitness assigned to a genotype is a sum of contributions, each of which is a random function defined on a subset of k≤L
k≤L loci. These subsets or neighborhoods determine the genetic interactions of the model. Whereas earlier work on the NK model suggested that most of its properties are robust with regard to the choice of neighborhoods, recent work has revealed an important and sometimes counter-intuitive influence of the interaction structure on the properties of NK fitness landscapes. Here we review these developments and present new results concerning the number of local fitness maxima and the statistics of selectively accessible (that is, fitness-monotonic) mutational pathways. In particular, we develop a unified framework for computing the exponential growth rate of the expected number of local fitness maxima as a function of L, and identify two different universality classes of interaction structures that display different asymptotics of this quantity for large k. Moreover, we show that the probability that the fitness landscape can be traversed along an accessible path decreases exponentially in L for a large class of interaction structures that we characterize as locally bounded. Finally, we discuss the impact of the NK interaction structures on the dynamics of evolution using adaptive walk models
Adaptive benefits from small mutation supplies in an antibiotic resistance enzyme
Salverda M.L.M., Koomen J., Koopmanschap B., Zwart M.P., de Visser J.A.G.M., 28. Nov. 2017, Proc. Natl. Acad. Sci. USA 114:12773-12778, https://doi.org/10.1073/pnas.1712999114
Populations with large mutation supplies adapt via the “greedy” substitution of the fittest genotype available, leading to fast and repeatable short-term responses. At longer time scales, smaller mutation supplies may in theory lead to larger improvements when distant high-fitness genotypes more readily evolve from lower-fitness intermediates. Here we test for long-term adaptive benefits from small mutation supplies using in vitro evolution of an antibiotic-degrading enzyme in the presence of a novel antibiotic. Consistent with predictions, large mutant libraries cause rapid initial adaptation via the substitution of cohorts of mutations, but show later deceleration and convergence. Smaller libraries show on average smaller initial, but also more variable, improvements, with two lines yielding alleles with exceptionally high resistance levels. These two alleles share three mutations with the large-library alleles, which are known from previous work, but also have unique mutations. Replay evolution experiments and analyses of the adaptive landscape of the enzyme suggest that the benefit resulted from a combination of avoiding mutational cohorts leading to local peaks and chance. Our results demonstrate adaptive benefits from limited mutation supplies on a rugged fitness landscape, which has implications for artificial selection protocols in biotechnology and argues for a better understanding of mutation supplies in clinical settings.
Mutation supply and the repeatability of selection for antibiotic resistance.
Van Dijk T., Hwang S., Krug J., de Visser J.A.G.M., Zwart M.P., 21. Aug. 2017, Phys. Biol. 14:055005, DOI: 10.1088/1478-3975/aa7f36
Whether evolution can be predicted is a key question in evolutionary biology. Here we set out to better understand the repeatability of evolution, which is a necessary condition for predictability. We explored experimentally the effect of mutation supply and the strength of selective pressure on the repeatability of selection from standing genetic variation. Different sizes of mutant libraries of antibiotic resistance gene TEM-1 β-lactamase in Escherichia coli, generated by error-prone PCR, were subjected to different antibiotic concentrations. We determined whether populations went extinct or survived, and sequenced the TEM gene of the surviving populations. The distribution of mutations per allele in our mutant libraries followed a Poisson distribution. Extinction patterns could be explained by a simple stochastic model that assumed the sampling of beneficial mutations was key for survival. In most surviving populations, alleles containing at least one known large-effect beneficial mutation were present. These genotype data also support a model which only invokes sampling effects to describe the occurrence of alleles containing large-effect driver mutations. Hence, evolution is largely predictable given cursory knowledge of mutational fitness effects, the mutation rate and population size. There were no clear trends in the repeatability of selected mutants when we considered all mutations present. However, when only known large-effect mutations were considered, the outcome of selection is less repeatable for large libraries, in contrast to expectations. We show experimentally that alleles carrying multiple mutations selected from large libraries confer higher resistance levels relative to alleles with only a known large-effect mutation, suggesting that the scarcity of high-resistance alleles carrying multiple mutations may contribute to the decrease in repeatability at large library sizes.
Genotypic Complexity of Fisher’s Geometric Model
Sungmin Hwang, Su-Chan Park, Joachim Krug, GENETICS, 2017 vol. 206 no. 2 1049-1079, 1. June 2017, https://doi.org/10.1534/genetics.116.199497
Fisher’s geometric model was originally introduced to argue that complex adaptations must occur in small steps because of pleiotropic constraints. When supplemented with the assumption of additivity of mutational effects on phenotypic traits, it provides a simple mechanism for the emergence of genotypic epistasis from the nonlinear mapping of phenotypes to fitness. Of particular interest is the occurrence of reciprocal sign epistasis, which is a necessary condition for multipeaked genotypic fitness landscapes. Here we compute the probability that a pair of randomly chosen mutations interacts sign epistatically, which is found to decrease with increasing phenotypic dimension n, and varies nonmonotonically with the distance from the phenotypic optimum. We then derive expressions for the mean number of fitness maxima in genotypic landscapes comprised of all combinations of L random mutations. This number increases exponentially with L, and the corresponding growth rate is used as a measure of the complexity of the landscape. The dependence of the complexity on the model parameters is found to be surprisingly rich, and three distinct phases characterized by different landscape structures are identified. Our analysis shows that the phenotypic dimension, which is often referred to as phenotypic complexity, does not generally correlate with the complexity of fitness landscapes and that even organisms with a single phenotypic trait can have complex landscapes. Our results further inform the interpretation of experiments where the parameters of Fisher’s model have been inferred from data, and help to elucidate which features of empirical fitness landscapes can be described by this model.
Diminishing-returns epistasis among random beneficial mutations in a multicellular fungus
Schoustra S, Hwang S, Krug J, de Visser JAGM. Diminishing-returns epistasis among random beneficial mutations in a multicellular fungus. Proc. R. Soc. B 283: 20161376. (2016)
Adaptive evolution ultimately is fuelled by mutations generating novel gen- etic variation. Non-additivity of fitness effects of mutations (called epistasis) may affect the dynamics and repeatability of adaptation. However, under- standing the importance and implications of epistasis is hampered by the observation of substantial variation in patterns of epistasis across empirical studies. Interestingly, some recent studies report increasingly smaller benefits of beneficial mutations once genotypes become better adapted (called diminishing-returns epistasis) in unicellular microbes and single genes. Here, we use Fisher’s geometric model (FGM) to generate analytical predictions about the relationship between the effect size of mutations and the extent of epistasis. We then test these predictions using the multicellular fungus Aspergillus nidulans by generating a collection of 108 strains in either a poor or a rich nutrient environment that each carry a beneficial mutation and constructing pairwise combinations using sexual crosses. Our results support the predictions from FGM and indicate negative epistasis among beneficial mutations in both environments, which scale with mutational effect size. Hence, our findings show the importance of diminishing-returns epistasis among beneficial mutations also for a multicellular organism, and suggest that this pattern reflects a generic constraint operating at diverse levels of biological organization.
Evolution of coexistence in a crowded microplate well
De Visser JAGM, Proceedings of the National Academy of Sciences USA, 112, 11148-11149 (2015)
Understanding what causes the emergence and maintenance of biological diversity has been a central aim in biology ever since the dawn of the discipline. The realization that diversity in microbial communities, such as those living in our guts and on our bodies, may affect our health and that of the agricultural systems on which we depend has generated substantial recent efforts to describe the extraordinary diversity of microbial communities. However, efforts to understand the ecological and evolutionary mechanisms responsible for generating and maintaining all this diversity have severely lagged behind those to describe it. This is unfortunate and unnecessary. Microbes offer a great opportunity to rigorously test hypotheses about these mechanisms in real time in controlled experiments in the laboratory. As Frenkel et al. (1) show in PNAS, such experiments may also reveal novel mechanisms of diversification and coexistence—in their case one where the avoidance of crowding plays a key role.
The origin and maintenance of biological diversity requires natural selection operating in heterogeneous environments (2, 3). In homogeneous environments with a single limiting resource equally accessible to all individuals, natural selection will remove all but the most superior competitor (4). However, in environments with temporal or spatial variation in the type or amount of limiting resource, fitness trade-offs between adaptations to different niches may lead to the stable maintenance of different genotypes through negative frequency-dependent selection (5).
An important lesson from laboratory evolution studies with microbes is that virtually all environments, even those designed to be homogeneous, such as chemostats, are heterogeneous at the scale relevant for microbes. For instance, temporal variation in resource availability occurs in serial transfer experiments in batch cultures with the opportunity for specialist adaptation (6), potential resources inaccessible at the start of the experiment may become available after evolutionary changes in the …
Dynamics of adaptation in experimental yeast populations exposed to gradual and abrupt change in heavy metal concentration
Gorter FA, Aarts MMG, Zwaan BJ, de Visser JAGM, The American Naturalist, in press (2015)
Phase transition in random adaptive walks on correlated fitness landscapes
Su-Chan Park, Ivan G. Szendro, Johannes Neidhart and Joachim Krug, Physical Revivew E 91, 042707 (2015)
We study biological evolution on a random fitness landscape where correlations are introduced through a linear fitness gradient of strength c. When selection is strong and mutations rare the dynamics is a directed uphill walk that terminates at a local fitness maximum. We analytically calculate the dependence of the walk length on the genome size L. When the distribution of the random fitness component has an exponential tail, we find a phase transition of the walk length D between a phase at small c, where walks are short (D∼lnL), and a phase at large c, where walks are long (D∼L). For all other distributions only a single phase exists for any c>0. The considered process is equivalent to a zero temperature Metropolis dynamics for the random energy model in an external magnetic field, thus also providing insight into the aging dynamics of spin glasses.
Analysis of adaptive walks on NK fitness landscapes with different interaction schemes
Stefan Nowak and Joachim Krug, J. Stat. Mech. (2015) P06014
Fitness landscapes are genotype to fitness mappings commonly used in evolutionary biology and computer science which are closely related to spin glass models. In this paper, we study the NK model for fitness landscapes where the interaction scheme between genes can be explicitly defined. The focus is on how this scheme influences the overall shape of the landscape. Our main tool for the analysis are adaptive walks, an idealized dynamics by which the population moves uphill in fitness and terminates at a local fitness maximum. We use three different types of walks and investigate how their length (the number of steps required to reach a local peak) and height (the fitness at the endpoint of the walk) depend on the dimensionality and structure of the landscape. We find that the distribution of local maxima over the landscape is particularly sensitive to the choice of interaction pattern. Most quantities that we measure are simply correlated to the rank of the scheme, which is equal to the number of nonzero coefficients in the expansion of the fitness landscape in terms of Walsh functions.
Negative Epistasis and Evolvability in TEM-1 β-Lactamase—The Thin Line between an Enzyme's Conformational Freedom and Disorder
Dellus-Gur E, Elias M, Caselli E, Prati F, Salverda MLM, de Visser JAGM, Fraser JS, Tawfik DS, Journal of Molecular Biology, 427, 2396-2409 (2015)
Epistasis is a key factor in evolution since it determines which combinations of mutations provide adaptive solutions and which mutational pathways toward these solutions are accessible by natural selection. There is growing evidence for the pervasiveness of sign epistasis—a complete reversion of mutational effects, particularly in protein evolution—yet its molecular basis remains poorly understood. We describe the structural basis of sign epistasis between G238S and R164S, two adaptive mutations in TEM-1 β-lactamase— an enzyme that endows antibiotics resistance. Separated by 10 Å, these mutations initiate two separate trajectories toward increased hydrolysis rates and resistance toward second and third-generation cephalosporins antibiotics. Both mutations allow the enzyme's active site to adopt alternative conformations and accommodate the new antibiotics. By solving the corresponding set of crystal structures, we found that R164S causes local disorder whereas G238S induces discrete conformations. When combined, the mutations in 238 and 164 induce local disorder whereby nonproductive conformations that perturb the enzyme's catalytic preorganization dominate. Specifically, Asn170 that coordinates the deacylating water molecule is misaligned, in both the free form and the inhibitor-bound double mutant. This local disorder is not restored by stabilizing global suppressor mutations and thus leads to an evolutionary cul-de-sac. Conformational dynamism therefore underlines the reshaping potential of protein's structures and functions but also limits protein evolvability because of the fragility of the interactions networks that maintain protein structures.
Adaptation in tunably rugged fitness landscapes: The Rough Mount Fuji Model
Johannes Neidhart, Ivan G. Szendro and Joachim Krug Genetics 198, 699-721 (2014)
Much of the current theory of adaptation is based on Gillespie’s mutational landscape model (MLM), which assumes that the fitness values of genotypes linked by single mutational steps are independent random variables. On the other hand, a growing body of empirical evidence shows that real fitness landscapes, while possessing a considerable amount of ruggedness, are smoother than predicted by the MLM. In the present article we propose and analyze a simple fitness landscape model with tunable ruggedness based on the rough Mount Fuji (RMF) model originally introduced by Aita et al. in the context of protein evolution. We provide a comprehensive collection of results pertaining to the topographical structure of RMF landscapes, including explicit formulas for the expected number of local fitness maxima, the location of the global peak, and the fitness correlation function. The statistics of single and multiple adaptive steps on the RMF landscape are explored mainly through simulations, and the results are compared to the known behavior in the MLM model. Finally, we show that the RMF model can explain the large number of second-step mutations observed on a highly fit first-step background in a recent evolution experiment with a microvirid bacteriophage.
Multidimensional epistasis and the transitory advantage of sex
Nowak S, Neidhart J, Szendro IG, Krug J, PLOS Computational Biology 10(9): e1003836 (2014)
Identifying and quantifying the benefits of sex and recombination is a long-standing problem in evolutionary theory. In particular, contradictory claims have been made about the existence of a benefit of recombination on high dimensional fitness landscapes in the presence of sign epistasis. Here we present a comparative numerical study of sexual and asexual evolutionary dynamics of haploids on tunably rugged model landscapes under strong selection, paying special attention to the temporal development of the evolutionary advantage of recombination and the link between population diversity and the rate of adaptation. We show that the adaptive advantage of recombination on static rugged landscapes is strictly transitory. At early times, an advantage of recombination arises through the possibility to combine individually occurring beneficial mutations, but this effect is reversed at longer times by the much more efficient trapping of recombining populations at local fitness peaks. These findings are explained by means of well-established results for a setup with only two loci. In accordance with the Red Queen hypothesis the transitory advantage can be prolonged indefinitely in fluctuating environments, and it is maximal when the environment fluctuates on the same time scale on which trapping at local optima typically occurs.
Role of pleiotropy during adaptation of TEM-1 β-lactamase to two novel antibiotics
Schenk MF, Witte S, Salverda MLM, Koopmanschap B, Krug J, de Visser JAGM, Evolutionary Applications, early view (2014)
Pleiotropy is a key feature of the genotype–phenotype map, and its form and extent have many evolutionary implications, including for the dynamics of adaptation and the evolution of specialization. Similarly, pleiotropic effects of antibiotic resistance mutations may affect the evolution of antibiotic resistance in the simultaneous or fluctuating presence of different antibiotics. Here, we study the role of pleiotropy during the in vitro adaptation of the enzyme TEM-1 β-lactamase to two novel antibiotics, cefotaxime (CTX) and ceftazidime (CAZ). We subject replicate lines for four rounds of evolution to selection with CTX and CAZ alone, and in their combined and fluctuating presence. Evolved alleles show positive correlated responses when selecting with single antibiotics. Nevertheless, pleiotropic constraints are apparent from the effects of single mutations and from selected alleles showing smaller correlated than direct responses and smaller responses after simultaneous and fluctuating selection with both than with single antibiotics. We speculate that these constraints result from structural changes in the oxyanion pocket surrounding the active site, where accommodation of CTX and the larger CAZ is balanced against their positioning with respect to the active site. Our findings suggest limited benefits from the combined or fluctuating application of these related cephalosporins for containing antibiotic resistance.
Clonal interference and Muller's ratchet in spatial habitats
Otwinowski J, Krug J, Physical Biology 11:056003 (2014)
Competition between independently arising beneficial mutations is enhanced in spatial populations due to the linear rather than exponential growth of clones. Recent theoretical studies have pointed out that the resulting fitness dynamics is analogous to a surface growth process, where new layers nucleate and spread stochastically, leading to the build up of scale-invariant roughness. This scenario differs qualitatively from the standard view of adaptation in that the speed of adaptation becomes independent of population size while the fitness variance does not. Here we exploit recent progress in the understanding of surface growth processes to obtain precise predictions for the universal, non-Gaussian shape of the fitness distribution for one-dimensional habitats, which are verified by simulations. When the mutations are deleterious rather than beneficial the problem becomes a spatial version of Muller's ratchet. In contrast to the case of well-mixed populations, the rate of fitness decline remains finite even in the limit of an infinite habitat, provided the ratio [Formula: see text] between the deleterious mutation rate and the square of the (negative) selection coefficient is sufficiently large. Using, again, an analogy to surface growth models we show that the transition between the stationary and the moving state of the ratchet is governed by directed percolation.
Empirical fitness landscapes and the predictability of evolution
de Visser JAGM, Krug J, Nature Reviews Genetics, Nature Reviews Genetics 15, 480-490 (2014)
The genotype–fitness map (that is, the fitness landscape) is a key determinant of evolution, yet it has mostly been used as a superficial metaphor because we know little about its structure. This is now changing, as real fitness landscapes are being analysed by constructing genotypes with all possible combinations of small sets of mutations observed in phylogenies or in evolution experiments. In turn, these first glimpses of empirical fitness landscapes inspire theoretical analyses of the predictability of evolution. Here, we review these recent empirical and theoretical developments, identify methodological issues and organizing principles, and discuss possibilities to develop more realistic fitness landscape models.
Evolutionary Accessibility of Modular Fitness Landscapes
Schmiegelt B, Krug J, Journal of Statistical Physics, October 2013, 1-22 (2013)
A fitness landscape is a mapping from the space of genetic sequences, which is modeled here as a binary hypercube of dimension L, to the real numbers. We consider random models of fitness landscapes, where fitness values are assigned according to some probabilistic rule, and study the statistical properties of pathways to the global fitness maximum along which fitness increases monotonically. Such paths are important for evolution because they are the only ones that are accessible to an adapting population when mutations occur at a low rate. The focus of this work is on the block model introduced by A.S. Perelson and C.A. Macken (Proc. Natl. Acad. Sci. USA 92:9657, 1995) where the genome is decomposed into disjoint sets of loci (‘modules’) that contribute independently to fitness, and fitness values within blocks are assigned at random. We show that the number of accessible paths can be written as a product of the path numbers within the blocks, which provides a detailed analytic description of the path statistics. The block model can be viewed as a special case of Kauffman’s NK-model, and we compare the analytic results to simulations of the NK-model with different genetic architectures. We find that the mean number of accessible paths in the different versions of the model are quite similar, but the distribution of the path number is qualitatively different in the block model due to its multiplicative structure. A similar statement applies to the number of local fitness maxima in the NK-models, which has been studied extensively in previous works. The overall evolutionary accessibility of the landscape, as quantified by the probability to find at least one accessible path to the global maximum, is dramatically lowered by the modular structure.
Rate of Adaptation in Sexuals and Asexuals: A Solvable Model of the Fisher–Muller Effect
Park SC, Krug J, Genetics November 1, 2013 vol. 195 no. 3 941-955 (2013)
The adaptation of large asexual populations is hampered by the competition between independently arising beneficial mutations in different individuals, which is known as clonal interference. In classic work, Fisher and Muller proposed that recombination provides an evolutionary advantage in large populations by alleviating this competition. Based on recent progress in quantifying the speed of adaptation in asexual populations undergoing clonal interference, we present a detailed analysis of the Fisher–Muller mechanism for a model genome consisting of two loci with an infinite number of beneficial alleles each and multiplicative (nonepistatic) fitness effects. We solve the deterministic, infinite population dynamics exactly and show that, for a particular, natural mutation scheme, the speed of adaptation in sexuals is twice as large as in asexuals. This result is argued to hold for any nonzero value of the rate of recombination. Guided by the infinite population result and by previous work on asexual adaptation, we postulate an expression for the speed of adaptation in finite sexual populations that agrees with numerical simulations over a wide range of population sizes and recombination rates. The ratio of the sexual to asexual adaptation speed is a function of population size that increases in the clonal interference regime and approaches 2 for extremely large populations. The simulations also show that the imbalance between the numbers of accumulated mutations at the two loci is strongly suppressed even by a small amount of recombination. The generalization of the model to an arbitrary number L of loci is briefly discussed. If each offspring samples the alleles at each locus from the gene pool of the whole population rather than from two parents, the ratio of the sexual to asexual adaptation speed is approximately equal to L in large populations. A possible realization of this scenario is the reassortment of genetic material in RNA viruses with L genomic segments.
Patterns of Epistasis between Beneficial Mutations in an Antibiotic Resistance Gene
Schenk MF, Szendro IG, Salverda ML, Krug J, de Visser JA, Mol Biol Evol 30 (8): 1779-1787 (2013)
Understanding epistasis is central to biology. For instance, epistatic interactions determine the topography of the fitness landscape and affect the dynamics and determinism of adaptation. However, few empirical data are available, and comparing results is complicated by confounding variation in the system and the type of mutations used. Here, we take a systematic approach by quantifying epistasis in two sets of four beneficial mutations in the antibiotic resistance enzyme TEM-1 β-lactamase. Mutations in these sets have either large or small effects on cefotaxime resistance when present as single mutations. By quantifying the epistasis and ruggedness in both landscapes, we find two general patterns. First, resistance is maximal for combinations of two mutations in both fitness landscapes and declines when more mutations are added due to abundant sign epistasis and a pattern of diminishing returns with genotype resistance. Second, large-effect mutations interact more strongly than small-effect mutations, suggesting that the effect size of mutations may be an organizing principle in understanding patterns of epistasis. By fitting the data to simple phenotype resistance models, we show that this pattern may be explained by the nonlinear dependence of resistance on enzyme stability and an unknown phenotype when mutations have antagonistically pleiotropic effects. The comparison to a previously published set of mutations in the same gene with a joint benefit further shows that the enzyme's fitness landscape is locally rugged but does contain adaptive pathways that lead to high resistance.
Exact results for the amplitude spectra of fitness landscapes
Neidhart J, Szendro I G, Krug J, J. Theor. Biol., Volume 332, 7 September 2013, Pages 218–227 (2013)
Starting from fitness correlation functions, we calculate exact expressions for the amplitude spectra of fitness landscapes as defined by P.F. Stadler [J. Math. Chem. 20, 1 (1996)] for common landscape models, including Kauffman's NK-model, rough Mt. Fuji landscapes and general linear superpositions of such landscapes. We further show that correlations decaying exponentially with Hamming distance yield exponentially decaying spectra similar to those reported recently for a model of molecular signal transduction. Finally, we compare our results for the model systems to the spectra of various experimentally measured fitness landscapes. We claim that our analytical results should be helpful when trying to interpret empirical data and guide the search for improved fitness landscape models.
Predictability of evolution depends nonmonotonically on population size.
Szendro IG, Franke J, de Visser JAGM, Krug J, Proceedings Of The National Academy Of Sciences Of The United States Of America 110, 571-576 (2013)
To gauge the relative importance of contingency and determinism in evolution is a fundamental problem that continues to motivate much theoretical and empirical research. In recent evolution experiments with microbes, this question has been explored by monitoring the repeatability of adaptive changes in replicate populations. Here, we present the results of an extensive computational study of evolutionary predictability based on an experimentally measured eight-locus fitness landscape for the filamentous fungus Aspergillus niger. To quantify predictability, we define entropy measures on observed mutational trajectories and endpoints. In contrast to the common expectation of increasingly deterministic evolution in large populations, we find that these entropies display an initial decrease and a subsequent increase with population size N, governed, respectively, by the scales Nμ and Nμ(2), corresponding to the supply rates of single and double mutations, where μ denotes the mutation rate. The amplitude of this pattern is determined by μ. We show that these observations are generic by comparing our findings for the experimental fitness landscape to simulations on simple model landscapes.
Quantitative analyses of empirical fitness landscapes
Szendro IG, Schenk MF, Franke J, Krug J, de Visser JAGM, Journal Of Statistical Mechanics, P01005 (2013)
The concept of a fitness landscape is a powerful metaphor that offers insight into various aspects of evolutionary processes and guidance for the study of evolution. Until recently, empirical evidence on the ruggedness of these landscapes was lacking, but since it became feasible to construct all possible genotypes containing combinations of a limited set of mutations, the number of studies has grown to a point where a classification of landscapes becomes possible. The aim of this review is to identify measures of epistasis that allow a meaningful comparison of fitness landscapes and then apply them to the empirical landscapes to discern factors that affect ruggedness. The various measures of epistasis that have been proposed in the literature appear to be equivalent. Our comparison shows that the ruggedness of the empirical landscape is affected by whether the included mutations are beneficial or deleterious and by whether intra- or intergenic epistasis is involved. Finally, the empirical landscapes are compared to landscapes generated with the Rough Mt.\ Fuji model. Despite the simplicity of this model, it captures the features of the experimental landscapes remarkably well.
Evolutionary Accessibility in Tunably Rugged Fitness Landscapes
Franke J, Krug J, Journal of Statistical Physics, Volume 148, Issue 4, pp 705-722 (2012)
The adaptive evolution of a population under the influence of mutation and selection is strongly influenced by the structure of the underlying fitness landscape, which encodes the interactions between mutations at different genetic loci. Theoretical studies of such landscapes have been carried out for several decades, but only recently experimental fitness measurements encompassing all possible combinations of small sets of mutations have become available. The empirical studies have spawned new questions about the accessibility of optimal genotypes under natural selection. Depending on population dynamic parameters such as mutation rate and population size, evolutionary accessibility can be quantified through the statistics of accessible mutational pathways (along which fitness increases monotonically), or through the study of the basin of attraction of the optimal genotype under greedy (steepest ascent) dynamics. Here we investigate these two measures of accessibility in the framework of Kauffman's LK-model, a paradigmatic family of random fitness landscapes with tunable ruggedness. The key parameter governing the strength of genetic interactions is the number K of interaction partners of each of the L sites in the genotype sequence. In general, accessibility increases with increasing genotype dimensionality L and decreases with increasing number of interactions K. Remarkably, however, we find that some measures of accessibility behave non-monotonically as a function of K, indicating a special role of the most sparsely connected, non-trivial cases K=1 and 2. The relation between models for fitness landscapes and spin glasses is also addressed.
Quantifying the adaptive potential of an antibiotic resistance enzyme.
Schenk MF, Szendro IG, Krug J, de Visser JAGM, PLoS Genetics 8, e1002783 (2012)
For a quantitative understanding of the process of adaptation, we need to understand its "raw material," that is, the frequency and fitness effects of beneficial mutations. At present, most empirical evidence suggests an exponential distribution of fitness effects of beneficial mutations, as predicted for Gumbel-domain distributions by extreme value theory. Here, we study the distribution of mutation effects on cefotaxime (Ctx) resistance and fitness of 48 unique beneficial mutations in the bacterial enzyme TEM-1 β-lactamase, which were obtained by screening the products of random mutagenesis for increased Ctx resistance. Our contributions are threefold. First, based on the frequency of unique mutations among more than 300 sequenced isolates and correcting for mutation bias, we conservatively estimate that the total number of first-step mutations that increase Ctx resistance in this enzyme is 87 [95% CI 75-189], or 3.4% of all 2,583 possible base-pair substitutions. Of the 48 mutations, 10 are synonymous and the majority of the 38 non-synonymous mutations occur in the pocket surrounding the catalytic site. Second, we estimate the effects of the mutations on Ctx resistance by determining survival at various Ctx concentrations, and we derive their fitness effects by modeling reproduction and survival as a branching process. Third, we find that the distribution of both measures follows a Fréchet-type distribution characterized by a broad tail of a few exceptionally fit mutants. Such distributions have fundamental evolutionary implications, including an increased predictability of evolution, and may provide a partial explanation for recent observations of striking parallel evolution of antibiotic resistance.
Correlations of record events as a test for heavy-tailed distributions.
Franke J, Wergen G, Krug J, Physical Review Letters 108, 064101 (2012)
A record is an entry in a time series that is larger or smaller than all previous entries. If the time series consists of independent, identically distributed random variables with a superimposed linear trend, record events are positively (negatively) correlated when the tail of the distribution is heavier (lighter) than exponential. Here we use these correlations to detect heavy-tailed behavior in small sets of independent random variables. The method consists of converting random subsets of the data into time series with a tunable linear drift and computing the resulting record correlations.
Adaptive walks and extreme value theory.
Neidhart J, Krug J, Physical Review Letters 107, 178102 (2011)
We study biological evolution in a high-dimensional genotype space in the regime of rare mutations and strong selection. The population performs an uphill walk which terminates at local fitness maxima. Assigning fitness randomly to genotypes, we show that the mean walk length is logarithmic in the number of initially available beneficial mutations, with a prefactor determined by the tail of the fitness distribution. This result is derived analytically in a simplified setting where the mutational neighborhood is fixed during the adaptive process, and confirmed by numerical simulations.
The causes of epistasis (Review)
de Visser JAGM, Cooper TF, Elena SF, Proc. R. Soc. B vol. 278 3617-3624 (2011)
Since Bateson's discovery that genes can suppress the phenotypic effects of other genes, gene interactions-called epistasis-have been the topic of a vast research effort. Systems and developmental biologists study epistasis to understand the genotype-phenotype map, whereas evolutionary biologists recognize the fundamental importance of epistasis for evolution. Depending on its form, epistasis may lead to divergence and speciation, provide evolutionary benefits to sex and affect the robustness and evolvability of organisms. That epistasis can itself be shaped by evolution has only recently been realized. Here, we review the empirical pattern of epistasis, and some of the factors that may affect the form and extent of epistasis. Based on their divergent consequences, we distinguish between interactions with or without mean effect, and those affecting the magnitude of fitness effects or their sign. Empirical work has begun to quantify epistasis in multiple dimensions in the context of metabolic and fitness landscape models. We discuss possible proximate causes (such as protein function and metabolic networks) and ultimate factors (including mutation, recombination, and the importance of natural selection and genetic drift). We conclude that, in general, pleiotropy is an important prerequisite for epistasis, and that epistasis may evolve as an adaptive or intrinsic consequence of changes in genetic robustness and evolvability.
Evolutionary accessibility of mutational pathways.
Franke J, Klözer A, de Visser JAGM, Krug J, PLoS Computational Biology 7, e1002134 (2011)
Functional effects of different mutations are known to combine to the total effect in highly nontrivial ways. For the trait under evolutionary selection ('fitness'), measured values over all possible combinations of a set of mutations yield a fitness landscape that determines which mutational states can be reached from a given initial genotype. Understanding the accessibility properties of fitness landscapes is conceptually important in answering questions about the predictability and repeatability of evolutionary adaptation. Here we theoretically investigate accessibility of the globally optimal state on a wide variety of model landscapes, including landscapes with tunable ruggedness as well as neutral 'holey' landscapes. We define a mutational pathway to be accessible if it contains the minimal number of mutations required to reach the target genotype, and if fitness increases in each mutational step. Under this definition accessibility is high, in the sense that at least one accessible pathway exists with a substantial probability that approaches unity as the dimensionality of the fitness landscape (set by the number of mutational loci) becomes large. At the same time the number of alternative accessible pathways grows without bounds. We test the model predictions against an empirical 8-locus fitness landscape obtained for the filamentous fungus Aspergillus niger. By analyzing subgraphs of the full landscape containing different subsets of mutations, we are able to probe the mutational distance scale in the empirical data. The predicted effect of high accessibility is supported by the empirical data and is very robust, which we argue reflects the generic topology of sequence spaces. Together with the restrictive assumptions that lie in our definition of accessibility, this implies that the globally optimal configuration should be accessible to genome wide evolution, but the repeatability of evolutionary trajectories is limited owing to the presence of a large number of alternative mutational pathways.
Evolutionary advantage of small populations on complex fitness landscapes.
Jain K, Krug J, Park S, Evolution 65, 1945-1955 (2011)
Recent experimental and theoretical studies have shown that small asexual populations evolving on complex fitness landscapes may achieve a higher fitness than large ones due to the increased heterogeneity of adaptive trajectories. Here, we introduce a class of haploid three-locus fitness landscapes that allow the investigation of this scenario in a precise and quantitative way. Our main result derived analytically shows how the probability of choosing the path of the largest initial fitness increase grows with the population size. This makes large populations more likely to get trapped at local fitness peaks and implies an advantage of small populations at intermediate time scales. The range of population sizes where this effect is operative coincides with the onset of clonal interference. Additional studies using ensembles of random fitness landscapes show that the results achieved for a particular choice of three-locus landscape parameters are robust and also persist as the number of loci increases. Our study indicates that an advantage for small populations is likely whenever the fitness landscape contains local maxima. The advantage appears at intermediate time scales, which are long enough for trapping at local fitness maxima to have occurred but too short for peak escape by the creation of multiple mutants.
Evolutionary genetics: evolution with foresight.
Salverda MLM, de Visser JAGM, Current Biology 21, R398-400 (2011)
Evolution has no foresight, but produces ad hoc solutions by tinkering with available variation. A new study demonstrates how evolution nevertheless prepares organisms for the future by increasing their evolvability.
Bistability in two-locus models with selection, mutation, and recombination.
Park S, Krug J, Journal Of Mathematical Biology 62, 763-788 (2011)
The evolutionary effect of recombination depends crucially on the epistatic interactions between linked loci. A paradigmatic case where recombination is known to be strongly disadvantageous is a two-locus fitness landscape displaying reciprocal sign epistasis with two fitness peaks of unequal height. Although this type of model has been studied since the 1960s, a full analytic understanding of the stationary states of mutation-selection balance was not achieved so far. Focusing on the bistability arising due to the recombination, we consider here the deterministic, haploid two-locus model with reversible mutations, selection and recombination. We find analytic formulae for the critical recombination probability r ( c ) above which two stable stationary solutions appear which are localized on each of the two fitness peaks. We also derive the stationary genotype frequencies in various parameter regimes. In particular, when the recombination rate is close to r ( c ) and the fitness difference between the two peaks is small, we obtain a compact description in terms of a cubic polynomial which is analogous to the Landau theory of physical phase transitions.
Initial mutations direct alternative pathways of protein evolution.
Salverda MLM, Dellus E, Gorter FA, Debets AJM, van der Oost J, Hoekstra RF, Tawfik DS, de Visser JAGM, PLoS Genetics 7, e1001321 (2011)
Whether evolution is erratic due to random historical details, or is repeatedly directed along similar paths by certain constraints, remains unclear. Epistasis (i.e. non-additive interaction between mutations that affect fitness) is a mechanism that can contribute to both scenarios. Epistasis can constrain the type and order of selected mutations, but it can also make adaptive trajectories contingent upon the first random substitution. This effect is particularly strong under sign epistasis, when the sign of the fitness effects of a mutation depends on its genetic background. In the current study, we examine how epistatic interactions between mutations determine alternative evolutionary pathways, using in vitro evolution of the antibiotic resistance enzyme TEM-1 β-lactamase. First, we describe the diversity of adaptive pathways among replicate lines during evolution for resistance to a novel antibiotic (cefotaxime). Consistent with the prediction of epistatic constraints, most lines increased resistance by acquiring three mutations in a fixed order. However, a few lines deviated from this pattern. Next, to test whether negative interactions between alternative initial substitutions drive this divergence, alleles containing initial substitutions from the deviating lines were evolved under identical conditions. Indeed, these alternative initial substitutions consistently led to lower adaptive peaks, involving more and other substitutions than those observed in the common pathway. We found that a combination of decreased enzymatic activity and lower folding cooperativity underlies negative sign epistasis in the clash between key mutations in the common and deviating lines (Gly238Ser and Arg164Ser, respectively). Our results demonstrate that epistasis contributes to contingency in protein evolution by amplifying the selective consequences of random mutations.
Rare events in population genetics: stochastic tunneling in a two-locus model with recombination.
Altland A, Fischer A, Krug J, Szendro IG, Physical Review Letters 106, 088101 (2011)
We study the evolution of a population in a two-locus genotype space, in which the negative effects of two single mutations are overcompensated in a high-fitness double mutant. We discuss how the interplay of finite population size N and sexual recombination at rate r affects the escape times t(esc) to the double mutant. For small populations demographic noise generates massive fluctuations in t(esc). The mean escape time varies nonmonotonically with r, and grows exponentially as lnt(esc)∼N(r-r(*))(3/2) beyond a critical value r(*).
Records and sequences of records from random variables with a linear trend
Franke J, Wergen G, Krug J, J. Stat. Mech. P10013 (2010)
We consider records and sequences of records drawn from discrete time series of the form $X_{n}=Y_{n}+cn$, where the $Y_{n}$ are independent and identically distributed random variables and $c$ is a constant drift. For very small and very large drift velocities, we investigate the asymptotic behavior of the probability $p_n(c)$ of a record occurring in the $n$th step and the probability $P_N(c)$ that all $N$ entries are records, i.e. that $X_1 < X_2 < ... < X_N$. Our work is motivated by the analysis of temperature time series in climatology, and by the study of mutational pathways in evolutionary biology.
The speed of evolution in large asexual populations
Park S, Simon D, Krug J, J. Stat. Phys. 138, 381-410 (2010)
We consider an asexual biological population of constant size N evolving in discrete time under the influence of selection and mutation. Beneficial mutations appear at rate U and their selective effects s are drawn from a distribution g(s). After introducing the required models and concepts of mathematical population genetics, we review different approaches to computing the speed of logarithmic fitness increase as a function of N, U and g(s). We present an exact solution of the infinite population size limit and provide an estimate of the population size beyond which it is valid. We then discuss approximate approaches to the finite population problem, distinguishing between the case of a single selection coefficient, g(s)=δ(s−s b ), and a continuous distribution of selection coefficients. Analytic estimates for the speed are compared to numerical simulations up to population sizes of order 10^300.
Exploring the effect of sex on empirical fitness landscapes.
de Visser JAGM, Park S, Krug J, The American Naturalist 174 Suppl 1, S15-30 (2009)
The nature of epistasis has important consequences for the evolutionary significance of sex and recombination. Recent efforts to find negative epistasis as a source of negative linkage disequilibrium and associated long-term advantage to sex have yielded little support. Sign epistasis, where the sign of the fitness effects of alleles varies across genetic backgrounds, is responsible for the ruggedness of the fitness landscape, with several unexplored implications for the evolution of sex. Here, we describe fitness landscapes for two sets of strains of the asexual fungus Aspergillus niger involving all combinations of five mutations. We find that approximately 30% of the single-mutation fitness effects are positive despite their negative effect in the wild-type strain and that several local fitness maxima and minima are present. We then compare adaptation of sexual and asexual populations on these empirical fitness landscapes by using simulations. The results show a general disadvantage of sex on these rugged landscapes, caused by the breakdown by recombination of genotypes on fitness peaks. Sex facilitates movement to the global peak only for some parameter values on one landscape, indicating its dependence on the landscape's topography. We discuss possible reasons for the discrepancy between our results and the reports of faster adaptation of sexual populations.
Reentrant phase transition in a predator-prey model.
Sung-Guk H, Park S, Jun KB, Physical Review. E 79, 066114 (2009)
We numerically investigate the six-species predator-prey game in complex networks as well as in d -dimensional regular hypercubic lattices with d=1,2,...,6 . The food-web topology of the six species contains two directed loops, each of which is composed of cyclically predating three species. As the mutation rate is lowered below the well-defined phase transition point, the Z2 symmetry related with the interchange in the two loops is spontaneously broken, and it has been known that the system develops the defensive alliance in which three cyclically predating species defend each other against the invasion of other species. In the Watts-Strogatz small-world network structure characterized by the rewiring probability alpha , the phase diagram shows the reentrant behavior as alpha is varied, indicating a twofold role of the shortcuts. In d -dimensional regular hypercubic lattices, the system also exhibits the reentrant phase transition as d is increased. We identify universality class of the phase transition and discuss the proper mean-field limit of the system.
Robustness and epistasis in mutation-selection models.
Wolff A, Krug J, Physical Biology 6, 036007 (2009)
We investigate the fitness advantage associated with the robustness of a phenotype against deleterious mutations using deterministic mutation-selection models of a quasispecies type equipped with a mesa-shaped fitness landscape. We obtain analytic results for the robustness effect which become exact in the limit of infinite sequence length. Thereby, we are able to clarify a seeming contradiction between recent rigorous work and an earlier heuristic treatment based on mapping to a Schrödinger equation. We exploit the quantum mechanical analogy to calculate a correction term for finite sequence lengths and verify our analytic results by numerical studies. In addition, we investigate the occurrence of an error threshold for a general class of epistatic landscapes and show that diminishing epistasis is a necessary but not sufficient condition for error threshold behaviour.
Dynamic correlation between intrahost HIV-1 quasispecies evolution and disease progression.
Lee HY, Perelson AS, Park S, Leitner T, PLoS Computational Biology 4, e1000240 (2008)
Quantifying the dynamics of intrahost HIV-1 sequence evolution is one means of uncovering information about the interaction between HIV-1 and the host immune system. In the chronic phase of infection, common dynamics of sequence divergence and diversity have been reported. We developed an HIV-1 sequence evolution model that simulated the effects of mutation and fitness of sequence variants. The amount of evolution was described by the distance from the founder strain, and fitness was described by the number of offspring a parent sequence produces. Analysis of the model suggested that the previously observed saturation of divergence and decrease of diversity in later stages of infection can be explained by a decrease in the proportion of offspring that are mutants as the distance from the founder strain increases rather than due to an increase of viral fitness. The prediction of the model was examined by performing phylogenetic analysis to estimate the change in the rate of evolution during infection. In agreement with our modeling, in 13 out of 15 patients (followed for 3-12 years) we found that the rate of intrahost HIV-1 evolution was not constant but rather slowed down at a rate correlated with the rate of CD4+ T-cell decline. The correlation between the dynamics of the evolutionary rate and the rate of CD4+ T-cell decline, coupled with our HIV-1 sequence evolution model, explains previously conflicting observations of the relationships between the rate of HIV-1 quasispecies evolution and disease progression.
Evolution in random fitness landscapes: the infinite sites model
Park S, Krug J, J. Stat. Mech. P04014 doi:10.1088/1742-5468/2008/04/P04014 (2008)
We consider the evolution of an asexually reproducing population in an uncorrelated random fitness landscape in the limit of infinite genome size, which implies that each mutation generates a new fitness value drawn from a probability distribution g(w). This is the finite population version of Kingman's house of cards model (Kingman 1978 J. Appl. Probab. 15 1). In contrast to Kingman's work, the focus here is on unbounded distributions g(w) which lead to an indefinite growth of the population fitness. The model is solved analytically in the limit of infinite population size and simulated numerically for finite N. When the genome-wide mutation probability U is small, the long-time behavior of the model reduces to a point process of fixation events, which is referred to as a diluted record process (DRP). The DRP is similar to the standard record process except that a new record candidate (a number that exceeds all previous entries in the sequence) is accepted only with a certain probability that depends on the values of the current record and the candidate. We develop a systematic analytic approximation scheme for the DRP. At finite U the fitness frequency distribution of the population decomposes into a stationary part due to mutations and a traveling wave component due to selection, which is shown to imply a reduction of the mean fitness by a factor of 1−U compared to the limit.
Clonal interference in large populations.
Park S, Krug J, Proceedings Of The National Academy Of Sciences Of The United States Of America 104, 18135-18140 (2007)
Clonal interference, the competition between lineages arising from different beneficial mutations in an asexually reproducing population, is an important factor determining the tempo and mode of microbial adaptation. The standard theory of this phenomenon neglects the occurrence of multiple mutations as well as the correlation between loss by genetic drift and clonal competition, which is questionable in large populations. Working within the Wright-Fisher model with multiplicative fitness (no epistasis), we determine the rate of adaptation asymptotically for very large population sizes and show that the standard theory fails in this regime. Our study also explains the success of the standard theory in predicting the rate of adaptation for moderately large populations. Furthermore, we show that the nature of the substitution process changes qualitatively when multiple mutations are allowed for, because several mutations can be fixed in a single fixation event. As a consequence, the index of dispersion for counts of the fixation process displays a minimum as a function of population size, whereas the origination process of fixed mutations becomes completely regular for very large populations. We find that the number of mutations fixed in a single event is geometrically distributed as in the neutral case. These conclusions are based on extensive simulations combined with analytic results for the limit of infinite population size.
Deterministic and stochastic regimes of asexual evolution on rugged fitness landscapes.
Jain K, Krug J, Genetics 175, 1275-1288 (2007)
We study the adaptation dynamics of an initially maladapted asexual population with genotypes represented by binary sequences of length L. The population evolves in a maximally rugged fitness landscape with a large number of local optima. We find that whether the evolutionary trajectory is deterministic or stochastic depends on the effective mutational distance d(eff) up to which the population can spread in genotype space. For d(eff) = L, the deterministic quasi-species theory operates while for d(eff) < 1, the evolution is completely stochastic. Between these two limiting cases, the dynamics are described by a local quasi-species theory below a crossover time T(x) while above T(x) the population gets trapped at a local fitness peak and manages to find a better peak via either stochastic tunneling or double mutations. In the stochastic regime d(eff) < 1, we identify two subregimes associated with clonal interference and uphill adaptive walks, respectively. We argue that our findings are relevant to the interpretation of evolution experiments with microbial populations.
back to project area C