6
$\begingroup$

BACKGROUND

The NK model of fitness landscape considers N states which can interact with K other states. For example N is the total number of genes in a haploid genome and K is the number of other genes that each gene may interact with.

In this article Kaufman says:

The fully connected NK model yields a completely random fitness landscape. For K = N - 1, the fitness contribution of each site depends on all of the other sites in the sequence and therefore altering any site from one to the other value, 0-1, alters the fitness contribution of each site to a new random value. Thus the fitness of any 1-mutant neighboring sequence is completely random with respect to the initial sequence. The landscape is fully random. As was shown in Kauffman & Levin (1987), Weinberger (1988), and Macken & Pereison (1989), such random landscapes have very many local optima, on average, 2N/(N +1).

I did not read the references mentioned in the text but I read the related section in Kaufman's book: Origins of Order: Self-Organization and Selection in Evolution.

In the book he says that the fitness of a genotype can be ordered and given ranks; the probability that a genotype is fitter than its neighbours (local optima) is same as its probability of ranking higher than its N neighbours. So this probability:

$$P_m=\frac{1}{N+1}$$

and if each gene can have only two states lets say on or off then the expected number of optima with respect to one-mutants (i.e. the difference between a gene and its neighbour is just one mutation) would be:

$$M_1=\frac{2^N}{N+1}$$

What I don't understand is the role of K in this expression. This reason should be valid for any number of K (See the quote above). Even in the book this explanation is given in the case where K is maximum i.e. N-1. I can understand that K can affect the ruggedness of the landscape but can anyone explain how K affects the number of optima? (or are they just two separate statements written together, which is confusing me)

$\endgroup$
2
$\begingroup$

Let's take the opposite extreme, $K=0$, so that each site has an independent effect on fitness. Without loss of generality, we can say that at each locus $n$, the $1$ allele confers an advantage $s_n$ over the $0$ allele. Then there is just one local optimum, the global optimum, at $\vec{1}$, so $M_1=1$ (and $P_m=2^{-N}$).

The key difference is that in the $K=0$ case each fitness comparison of a focal genotype with a neighbor is independent of the rest: the fact that mutating the first gene decreases fitness, for instance, doesn't make it any more likely that mutating the second gene will decrease fitness. For any $K$, it is necessarily true that the focal genotype has a probability $1/(N+1)$ of being fitter than all of a set of $N$ other randomly chosen genotypes, but we're interested in comparing it to its neighbors, which are not a random selection, and are only equivalent to a random selection when $K=N-1$.

$\endgroup$
  • $\begingroup$ Thanks Daniel. Sorry I for the late response. Was out of town and didn't check. So except for the N=0 case, it is not straightforward to predict the number of optima from the value of K or is it monotonously increasing? $\endgroup$ – WYSIWYG Apr 27 '15 at 12:52
  • $\begingroup$ No need to apologize! I think that it's monotonously increasing, but I'm not sure if it's been proved in general. There are a couple of papers by Vlada Limic in Ann. Prob. (2003 with Rick Durrett, 2004 with Robin Pemantle) that look at related questions. $\endgroup$ – Daniel Weissman Apr 27 '15 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.