NK model

A plasmid is a small circle of DNA inside certain cells that can replicate independently of their host cells. Suppose we wish to study the fitness of plasmids.

For simplicity, we model a plasmid as a ring of N possible genes, always in the same order, and each can have two possible states (active or inactive, type X or type Y, etc...). Then the plasmid is modelled by a binary string with length N, and so the fitness function is ${\displaystyle F:\{0,1\}^{N}\to \mathbb {R} }$.

The simplest model would have the genes not interacting with each other, and so we obtain

$${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1})+f_{2}(S_{2})+\cdots +f_{N}(S_{N})}$$

where each ${\displaystyle f_{i}(S_{i})}$ denotes the contribution to fitness of gene ${\displaystyle S_{i}}$ at location ${\displaystyle i}$. To model epistasis, we introduce another factor K, the number of other genes that a gene interacts with. It is reasonable to assume that on a plasmid, two genes interact if they are adjacent, thus giving

$${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1},S_{2})+f_{2}(S_{2},S_{3})+\cdots +f_{N-1}(S_{N-1},S_{N})+f_{N}(S_{N},S_{1})}$$

For example, when K = 1, and N = 5,

${\displaystyle F(00101)=f_{1}(0,0)+f_{2}(0,1)+f_{3}(1,0)+f_{4}(0,1)+f_{5}(1,0)}$

The NK model generalizes this by allowing arbitrary finite K, N, as well as allowing arbitrary definition of adjacency of genes (the genes do not necessarily lie on a circle or a line segment).

The NK model defines a combinatorial phase space, consisting of every string (chosen from a given alphabet) of length ${\displaystyle N}$. For each string in this search space, a scalar value (called the fitness) is defined. If a distance metric is defined between strings, the resulting structure is a landscape.

Fitness values are defined according to the specific incarnation of the model, but the key feature of the NK model is that the fitness of a given string ${\displaystyle S}$ is the sum of contributions from each locus ${\displaystyle f_{i}(S)}$ in the string:

${\displaystyle F(S)=\sum _{i}{\tilde {f}}_{i}(S),}$

and the contribution from each locus in general depends on its state and the state of ${\displaystyle K}$ other loci,:

${\displaystyle {\tilde {f}}_{i}(S)=f_{i}(S_{i},S_{k_{i1}},\dots ,S_{k_{iK}}),}$

where ${\displaystyle k_{ij}}$ is the index of the ${\displaystyle j}$th neighbor of locus ${\displaystyle i}$.

Hence, the fitness function ${\displaystyle f_{i}}$ is a mapping between strings of length K + 1 and scalars, which Weinberger's later work calls "fitness contributions". Such fitness contributions are often chosen randomly from some specified probability distribution.

Visualization of two dimensions of a NK fitness landscape. The arrows represent various mutational paths that the population could follow while evolving on the fitness landscape

Example: the spin glass models

The 1D Ising model of spin glass is usually written as

$${\displaystyle H=-\sum _{i=1}^{N}J_{i,i+1}S_{i}S_{i+1}-\mu \sum _{i=1}^{N}h_{i}S_{i}}$$

where ${\displaystyle H}$ is the Hamiltonian, which can be thought as energy. We can reformulate it as a special case of the NK model with K=1:

$${\displaystyle H=F(S)=\sum _{i,j}f_{i,j}(S_{i},S_{j})}$$

by defining

$${\displaystyle f_{i}(S_{i},S_{i+1})=-J_{ij}S_{i}S_{i}-\mu h_{i}S_{i}}$$

In general, the m-dimensional Ising model on a square grid ${\displaystyle \{1,2,...,n\}^{m}}$ is an NK model with ${\displaystyle N=n^{m},K=m}$.

Since K roughly measures "ruggedness" of the fitness landscape (see below), we see that as the dimension of Ising model increases, its ruggedness also increases.

When ${\displaystyle \mu =0}$, this is the Edwards–Anderson model, which is exactly solvable.

The Sherrington–Kirkpatrick model generalizes the Ising model by allowing all possible pairs of spins to interact (instead of a grid graph, use the complete graph), thus it is also an NK model with ${\displaystyle K=N-1}$.

Allowing all possible subsequences of spins to interact, instead of merely pairs, we obtain the infinite-range model, which is also an NK model with ${\displaystyle K=N-1}$.

Illustration of tunable topology in the NK model. Nodes are individual binary strings, edges connect strings with a Hamming distance of exactly one. (left) N = 5, K = 0. (centre) N = 5, K = 1. (right) N = 5, K = 2. The colour of a node denotes its fitness, with redder values having higher fitness. The embedding of the hypercube is chosen so that the fitness maximum is at the centre. Notice that the K = 0 landscape appears smoother than the higher-K cases.

The value of K controls the degree of epistasis in the NK model, or how much other loci affect the fitness contribution of a given locus. With K = 0, the fitness of a given string is a simple sum of individual contributions of loci: for nontrivial fitness functions, a global optimum is present and easy to locate (the genome of all 0s if f(0) > f(1), or all 1s if f(1) > f(0)). For nonzero K, the fitness of a string is a sum of fitnesses of substrings, which may interact to frustrate the system (consider how to achieve optimal fitness in the example above). Increasing K thus increases the ruggedness of the fitness landscape.

In 1991, Weinberger published a detailed analysis[6] of the case in which ${\displaystyle 1<<k\leq N}$ and the fitness contributions are chosen randomly. His analytical estimate of the number of local optima was later shown to be flawed . However, numerical experiments included in Weinberger's analysis support his analytical result that the expected fitness of a string is normally distributed with a mean of approximately

${\displaystyle \mu +\sigma {\sqrt {{2\ln(k+1)} \over {k+1}}}}$

and a variance of approximately

${\displaystyle {{(k+1)\sigma ^{2}} \over {N[k+1+2(k+2)\ln(k+1)]}}}$.

The NK model has found use in many fields, including in the study of spin glasses, collective problem solving,[7] epistasis and pleiotropy in evolutionary biology, and combinatorial optimisation.