@article{6637, abstract = {The environment changes constantly at various time scales and, in order to survive, species need to keep adapting. Whether these species succeed in avoiding extinction is a major evolutionary question. Using a multilocus evolutionary model of a mutation‐limited population adapting under strong selection, we investigate the effects of the frequency of environmental fluctuations on adaptation. Our results rely on an “adaptive‐walk” approximation and use mathematical methods from evolutionary computation theory to investigate the interplay between fluctuation frequency, the similarity of environments, and the number of loci contributing to adaptation. First, we assume a linear additive fitness function, but later generalize our results to include several types of epistasis. We show that frequent environmental changes prevent populations from reaching a fitness peak, but they may also prevent the large fitness loss that occurs after a single environmental change. Thus, the population can survive, although not thrive, in a wide range of conditions. Furthermore, we show that in a frequently changing environment, the similarity of threats that a population faces affects the level of adaptation that it is able to achieve. We check and supplement our analytical results with simulations.}, author = {Trubenova, Barbora and Krejca, Martin and Lehre, Per Kristian and Kötzing, Timo}, journal = {Evolution}, number = {7}, pages = {1356--1374}, publisher = {Wiley}, title = {{Surfing on the seascape: Adaptation in a changing environment}}, doi = {10.1111/evo.13784}, volume = {73}, year = {2019}, } @article{723, abstract = {Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of tunable difficulty by considering their length, representing the Hamming path between the two optima and their depth, the drop in fitness. For this function class we present a runtime comparison between stochastic search algorithms using different search strategies. The (1+1) EA is a simple and well-studied evolutionary algorithm that has to jump across the valley to a point of higher fitness because it does not accept worsening moves (elitism). In contrast, the Metropolis algorithm and the Strong Selection Weak Mutation (SSWM) algorithm, a famous process in population genetics, are both able to cross the fitness valley by accepting worsening moves. We show that the runtime of the (1+1) EA depends critically on the length of the valley while the runtimes of the non-elitist algorithms depend crucially on the depth of the valley. Moreover, we show that both SSWM and Metropolis can also efficiently optimise a rugged function consisting of consecutive valleys.}, author = {Oliveto, Pietro and Paixao, Tiago and Pérez Heredia, Jorge and Sudholt, Dirk and Trubenova, Barbora}, journal = {Algorithmica}, number = {5}, pages = {1604 -- 1633}, publisher = {Springer}, title = {{How to escape local optima in black box optimisation when non elitism outperforms elitism}}, doi = {10.1007/s00453-017-0369-2}, volume = {80}, year = {2018}, } @article{1111, abstract = {Adaptation depends critically on the effects of new mutations and their dependency on the genetic background in which they occur. These two factors can be summarized by the fitness landscape. However, it would require testing all mutations in all backgrounds, making the definition and analysis of fitness landscapes mostly inaccessible. Instead of postulating a particular fitness landscape, we address this problem by considering general classes of landscapes and calculating an upper limit for the time it takes for a population to reach a fitness peak, circumventing the need to have full knowledge about the fitness landscape. We analyze populations in the weak-mutation regime and characterize the conditions that enable them to quickly reach the fitness peak as a function of the number of sites under selection. We show that for additive landscapes there is a critical selection strength enabling populations to reach high-fitness genotypes, regardless of the distribution of effects. This threshold scales with the number of sites under selection, effectively setting a limit to adaptation, and results from the inevitable increase in deleterious mutational pressure as the population adapts in a space of discrete genotypes. Furthermore, we show that for the class of all unimodal landscapes this condition is sufficient but not necessary for rapid adaptation, as in some highly epistatic landscapes the critical strength does not depend on the number of sites under selection; effectively removing this barrier to adaptation.}, author = {Heredia, Jorge and Trubenova, Barbora and Sudholt, Dirk and Paixao, Tiago}, issn = {00166731}, journal = {Genetics}, number = {2}, pages = {803 -- 825}, publisher = {Genetics Society of America}, title = {{Selection limits to adaptive walks on correlated landscapes}}, doi = {10.1534/genetics.116.189340}, volume = {205}, year = {2017}, } @article{1169, abstract = {Dispersal is a crucial factor in natural evolution, since it determines the habitat experienced by any population and defines the spatial scale of interactions between individuals. There is compelling evidence for systematic differences in dispersal characteristics within the same population, i.e., genotype-dependent dispersal. The consequences of genotype-dependent dispersal on other evolutionary phenomena, however, are poorly understood. In this article we investigate the effect of genotype-dependent dispersal on spatial gene frequency patterns, using a generalization of the classical diffusion model of selection and dispersal. Dispersal is characterized by the variance of dispersal (diffusion coefficient) and the mean displacement (directional advection term). We demonstrate that genotype-dependent dispersal may change the qualitative behavior of Fisher waves, which change from being “pulled” to being “pushed” wave fronts as the discrepancy in dispersal between genotypes increases. The speed of any wave is partitioned into components due to selection, genotype-dependent variance of dispersal, and genotype-dependent mean displacement. We apply our findings to wave fronts maintained by selection against heterozygotes. Furthermore, we identify a benefit of increased variance of dispersal, quantify its effect on the speed of the wave, and discuss the implications for the evolution of dispersal strategies.}, author = {Novak, Sebastian and Kollár, Richard}, issn = {00166731}, journal = {Genetics}, number = {1}, pages = {367 -- 374}, publisher = {Genetics Society of America}, title = {{Spatial gene frequency waves under genotype dependent dispersal}}, doi = {10.1534/genetics.116.193946}, volume = {205}, year = {2017}, } @article{696, abstract = {Mutator strains are expected to evolve when the availability and effect of beneficial mutations are high enough to counteract the disadvantage from deleterious mutations that will inevitably accumulate. As the population becomes more adapted to its environment, both availability and effect of beneficial mutations necessarily decrease and mutation rates are predicted to decrease. It has been shown that certain molecular mechanisms can lead to increased mutation rates when the organism finds itself in a stressful environment. While this may be a correlated response to other functions, it could also be an adaptive mechanism, raising mutation rates only when it is most advantageous. Here, we use a mathematical model to investigate the plausibility of the adaptive hypothesis. We show that such a mechanism can be mantained if the population is subjected to diverse stresses. By simulating various antibiotic treatment schemes, we find that combination treatments can reduce the effectiveness of second-order selection on stress-induced mutagenesis. We discuss the implications of our results to strategies of antibiotic therapy.}, author = {Lukacisinova, Marta and Novak, Sebastian and Paixao, Tiago}, issn = {1553734X}, journal = {PLoS Computational Biology}, number = {7}, publisher = {Public Library of Science}, title = {{Stress induced mutagenesis: Stress diversity facilitates the persistence of mutator genes}}, doi = {10.1371/journal.pcbi.1005609}, volume = {13}, year = {2017}, } @article{1336, abstract = {Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.}, author = {Paixao, Tiago and Pérez Heredia, Jorge and Sudholt, Dirk and Trubenova, Barbora}, issn = {01784617}, journal = {Algorithmica}, number = {2}, pages = {681 -- 713}, publisher = {Springer}, title = {{Towards a runtime comparison of natural and artificial evolution}}, doi = {10.1007/s00453-016-0212-1}, volume = {78}, year = {2017}, } @article{1351, abstract = {The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs—an important problem of interest in evolutionary biology—more efficiently than the classical simulation method. We specify the property in linear temporal logic. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.}, author = {Giacobbe, Mirco and Guet, Calin C and Gupta, Ashutosh and Henzinger, Thomas A and Paixao, Tiago and Petrov, Tatjana}, issn = {00015903}, journal = {Acta Informatica}, number = {8}, pages = {765 -- 787}, publisher = {Springer}, title = {{Model checking the evolution of gene regulatory networks}}, doi = {10.1007/s00236-016-0278-x}, volume = {54}, year = {2017}, } @article{910, abstract = {Frequency-independent selection is generally considered as a force that acts to reduce the genetic variation in evolving populations, yet rigorous arguments for this idea are scarce. When selection fluctuates in time, it is unclear whether frequency-independent selection may maintain genetic polymorphism without invoking additional mechanisms. We show that constant frequency-independent selection with arbitrary epistasis on a well-mixed haploid population eliminates genetic variation if we assume linkage equilibrium between alleles. To this end, we introduce the notion of frequency-independent selection at the level of alleles, which is sufficient to prove our claim and contains the notion of frequency-independent selection on haploids. When selection and recombination are weak but of the same order, there may be strong linkage disequilibrium; numerical calculations show that stable equilibria are highly unlikely. Using the example of a diallelic two-locus model, we then demonstrate that frequency-independent selection that fluctuates in time can maintain stable polymorphism if linkage disequilibrium changes its sign periodically. We put our findings in the context of results from the existing literature and point out those scenarios in which the possible role of frequency-independent selection in maintaining genetic variation remains unclear. }, author = {Novak, Sebastian and Barton, Nicholas H}, journal = {Genetics}, number = {2}, pages = {653 -- 668}, publisher = {Genetics Society of America}, title = {{When does frequency-independent selection maintain genetic variation?}}, doi = {10.1534/genetics.117.300129}, volume = {207}, year = {2017}, } @article{954, abstract = {Understanding the relation between genotype and phenotype remains a major challenge. The difficulty of predicting individual mutation effects, and particularly the interactions between them, has prevented the development of a comprehensive theory that links genotypic changes to their phenotypic effects. We show that a general thermodynamic framework for gene regulation, based on a biophysical understanding of protein-DNA binding, accurately predicts the sign of epistasis in a canonical cis-regulatory element consisting of overlapping RNA polymerase and repressor binding sites. Sign and magnitude of individual mutation effects are sufficient to predict the sign of epistasis and its environmental dependence. Thus, the thermodynamic model offers the correct null prediction for epistasis between mutations across DNA-binding sites. Our results indicate that a predictive theory for the effects of cis-regulatory mutations is possible from first principles, as long as the essential molecular mechanisms and the constraints these impose on a biological system are accounted for.}, author = {Lagator, Mato and Paixao, Tiago and Barton, Nicholas H and Bollback, Jonathan P and Guet, Calin C}, issn = {2050084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{On the mechanistic nature of epistasis in a canonical cis-regulatory element}}, doi = {10.7554/eLife.25192}, volume = {6}, year = {2017}, } @article{1191, abstract = {Variation in genotypes may be responsible for differences in dispersal rates, directional biases, and growth rates of individuals. These traits may favor certain genotypes and enhance their spatiotemporal spreading into areas occupied by the less advantageous genotypes. We study how these factors influence the speed of spreading in the case of two competing genotypes under the assumption that spatial variation of the total population is small compared to the spatial variation of the frequencies of the genotypes in the population. In that case, the dynamics of the frequency of one of the genotypes is approximately described by a generalized Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP equation with (nonlinear) frequency-dependent diffusion and advection terms admits traveling wave solutions that characterize the invasion of the dominant genotype. Our existence results generalize the classical theory for traveling waves for the F–KPP with constant coefficients. Moreover, in the particular case of the quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we study in detail the influence of the variance in diffusion and mean displacement rates of the two genotypes on the minimal wave propagation speed.}, author = {Kollár, Richard and Novak, Sebastian}, journal = {Bulletin of Mathematical Biology}, number = {3}, pages = {525--559}, publisher = {Springer}, title = {{Existence of traveling waves for the generalized F–KPP equation}}, doi = {10.1007/s11538-016-0244-3}, volume = {79}, year = {2017}, } @inproceedings{1349, abstract = {Crossing fitness valleys is one of the major obstacles to function optimization. In this paper we investigate how the structure of the fitness valley, namely its depth d and length ℓ, influence the runtime of different strategies for crossing these valleys. We present a runtime comparison between the (1+1) EA and two non-elitist nature-inspired algorithms, Strong Selection Weak Mutation (SSWM) and the Metropolis algorithm. While the (1+1) EA has to jump across the valley to a point of higher fitness because it does not accept decreasing moves, the non-elitist algorithms may cross the valley by accepting worsening moves. We show that while the runtime of the (1+1) EA algorithm depends critically on the length of the valley, the runtimes of the non-elitist algorithms depend crucially only on the depth of the valley. In particular, the expected runtime of both SSWM and Metropolis is polynomial in ℓ and exponential in d while the (1+1) EA is efficient only for valleys of small length. Moreover, we show that both SSWM and Metropolis can also efficiently optimize a rugged function consisting of consecutive valleys.}, author = {Oliveto, Pietro and Paixao, Tiago and Heredia, Jorge and Sudholt, Dirk and Trubenova, Barbora}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference 2016 }, location = {Denver, CO, USA}, pages = {1163 -- 1170}, publisher = {ACM}, title = {{When non-elitism outperforms elitism for crossing fitness valleys}}, doi = {10.1145/2908812.2908909}, year = {2016}, } @article{1359, abstract = {The role of gene interactions in the evolutionary process has long been controversial. Although some argue that they are not of importance, because most variation is additive, others claim that their effect in the long term can be substantial. Here, we focus on the long-term effects of genetic interactions under directional selection assuming no mutation or dominance, and that epistasis is symmetrical overall. We ask by how much the mean of a complex trait can be increased by selection and analyze two extreme regimes, in which either drift or selection dominate the dynamics of allele frequencies. In both scenarios, epistatic interactions affect the long-term response to selection by modulating the additive genetic variance. When drift dominates, we extend Robertson ’ s [Robertson A (1960) Proc R Soc Lond B Biol Sci 153(951):234 − 249] argument to show that, for any form of epistasis, the total response of a haploid population is proportional to the initial total genotypic variance. In contrast, the total response of a diploid population is increased by epistasis, for a given initial genotypic variance. When selection dominates, we show that the total selection response can only be increased by epistasis when s ome initially deleterious alleles become favored as the genetic background changes. We find a sim- ple approximation for this effect and show that, in this regime, it is the structure of the genotype - phenotype map that matters and not the variance components of the population.}, author = {Paixao, Tiago and Barton, Nicholas H}, journal = {PNAS}, number = {16}, pages = {4422 -- 4427}, publisher = {National Academy of Sciences}, title = {{The effect of gene interactions on the long-term response to selection}}, doi = {10.1073/pnas.1518830113}, volume = {113}, year = {2016}, } @inproceedings{1835, abstract = {The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs –an important problem of interest in evolutionary biology– more efficiently than the classical simulation method. We specify the property in linear temporal logics. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.}, author = {Giacobbe, Mirco and Guet, Calin C and Gupta, Ashutosh and Henzinger, Thomas A and Paixao, Tiago and Petrov, Tatjana}, location = {London, United Kingdom}, pages = {469 -- 483}, publisher = {Springer}, title = {{Model checking gene regulatory networks}}, doi = {10.1007/978-3-662-46681-0_47}, volume = {9035}, year = {2015}, } @article{1542, abstract = {The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields. }, author = {Paixao, Tiago and Badkobeh, Golnaz and Barton, Nicholas H and Çörüş, Doğan and Dang, Duccuong and Friedrich, Tobias and Lehre, Per and Sudholt, Dirk and Sutton, Andrew and Trubenova, Barbora}, journal = { Journal of Theoretical Biology}, pages = {28 -- 43}, publisher = {Elsevier}, title = {{Toward a unifying framework for evolutionary processes}}, doi = {10.1016/j.jtbi.2015.07.011}, volume = {383}, year = {2015}, } @inproceedings{1430, abstract = {Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.}, author = {Paixao, Tiago and Sudholt, Dirk and Heredia, Jorge and Trubenova, Barbora}, booktitle = {Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation}, location = {Madrid, Spain}, pages = {1455 -- 1462}, publisher = {ACM}, title = {{First steps towards a runtime comparison of natural and artificial evolution}}, doi = {10.1145/2739480.2754758}, year = {2015}, }