7
$\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$

1 Answer 1

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$
2
  • $\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, 2015 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$ Apr 27, 2015 at 22:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .