Universality classes of interaction structures for NK fitness landscapes
arXiv:1708.06556 · doi:10.1007/s10955-018-1979-z
Abstract
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 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 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 , and identify two different universality classes of interaction structures that display different asymptotics of this quantity for large . Moreover, we show that the probability that the fitness landscape can be traversed along an accessible path decreases exponentially in 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.
arXiv comment61 pages, 9 figures
References in corpus (29)
- The large deviation approach to statistical mechanics
- Quantitative analyses of empirical fitness landscapes
- Evolutionary accessibility of mutational pathways
- The context-dependence of mutations: a linkage of formalisms
- Persistent memory in athermal systems in deformable energy landscapes
- Impact of Epistasis and Pleiotropy on Evolutionary Adaptation
- The speed of evolution in large asexual populations
- Adaptation in tunably rugged fitness landscapes: The Rough Mount Fuji Model
- Complex-network analysis of combinatorial spaces: The NK landscape case
- Exact Results for Amplitude Spectra of Fitness Landscapes
- Genotypic complexity of Fisher's geometric model
- Adaptive walks and extreme value theory
- On the existence of accessible paths in various models of fitness landscapes
- Evolutionary accessibility of modular fitness landscapes
- The number of accessible paths in the hypercube
- Analysis of adaptive walks on NK fitness landscapes with different interaction schemes
- Optimal adaptive performance and delocalization in NK fitness landscapes
- Evolutionary accessibility in tunably rugged fitness landscapes
- Phase transition in random adaptive walks on correlated fitness landscapes
- Greedy adaptive walks on a correlated fitness landscape
- Metastable states of spin glasses on random thin graphs
- Multidimensional epistasis and the transitory advantage of sex
- More rigorous results on the Kauffman-Levin model of evolution
- Accessibility percolation on n-trees
- Adaptive walks on time-dependent fitness landscapes
- Number of adaptive steps to a local fitness peak
- Metastable States in High Order Short-Range Spin Glasses
- -exceedance records and random adaptive walks
- Length of adaptive walk on uncorrelated and correlated fitness landscapes
Cited by in corpus (9)
- Evolving generalists via dynamic sculpting of rugged landscapes
- Accessibility Percolation on Cartesian Power Graphs
- Distribution of the number of fitness maxima in Fisher's Geometric Model
- Evolutionary accessibility of random and structured fitness landscapes
- Impact of population size on early adaptation in rugged fitness landscapes
- The surprising little effectiveness of cooperative algorithms in parallel problem solving
- Getting higher on rugged landscapes: Inversion mutations open access to fitter adaptive peaks in NK fitness landscapes
- Complexity and accessibility of random landscapes
- Branching with selection and mutation I: Mutant fitness of Fréchet type