Fitness landscapes as mental and mathematical models of evolution

A figure from Wright's 1932 paper introducing fitness landscapes. I am surprised at how modern it looks.

A figure from Wright’s 1932 paper introducing fitness landscapes. I am surprised at how modern it looks.

As Jacob Scott pointed out, everybody — theorist or experimentalist — “has a logical construct (a model) in his or her head” when studying anything. This model might be mathematically explicit or implicit in the mind, but it is there and if the world is mechanistic (or if we only want to consider mechanistic theories of the world) then so is the model. One of the goals of philosophy (as well as theoretical parts of science) is to study these implicit (or explicit) models and understand if they have any fundamental limitations or introduce biases that might be independent of the empirical world that we hope they represent. Since theoretical computer science is a natural extension of the analytic approach to philosophy, and since it is perfectly adapted for studying abstract mechanistic models, it is my hope to use computer science to enlighten our understanding of our mental models. In the case of evolution, the prevalent mental (and later mathematical) model that I want to study was introduced in 1932 by Sewall Wright — the fitness landscape.

I’ve discussed this model in passing when talking about frequency-independent selection. The central idea is that we have a genetic or phenotypic space where each node is a possible genotype (or phenotype, depending on type of model) and an edge exists between two nodes if a single mutation transforms one node into the other. The easiest model to think about in this case (and which is sufficient for the rigorous qualitative features that we will care about) is the biallelic system. In this case we have n loci, at each of which it is possible to have one of two alleles, thus our space is the n-bit binary strings \{0,1\}^n. A mutation can flip any loci from one allele to the other, thus two strings x,y \in \{0,1\}^n are adjacent if they differ in exactly one bit or — said more formally — are at Hamming distance one. This makes the landscape an n-dimensional hypercube with the strings corresponding to genotypes as vertexes. The last ingredient – fitness — is given by a function that maps each string to a real number.

Individual organisms can be thought of as inhabiting the vertexes of the landscape corresponding to their genotype. The probability of each organism reproducing or its reproductive rate is given by the fitness value of its vertex. Note that this fitness is independent of the distribution of other agents, and hence this model is only valid for frequency-independent selection. This is an overreach of reductionism in ignoring the distribution of the whole population, but one that can sometimes be theoretically justified and at other times is conceptually or empirically convenient. In practice, this makes the model only valid on relatively short timescales since organisms tend to change their environment and thus selective pressures over extremely long timescales. The model was also not designed to incorporate frequency-dependent strategic interactions between organisms. As such, it is not useful in evolutionary game theory, although I will discuss a way to modify the model to be partially useful in a future post.

Wright’s original formulation considered a population of sexually reproducing organisms distributed over the landscape. Modern treatments, however, have usually concentrated on asexual populations. In an asexual populations with sufficiently low mutations, the probability of a double (or more) mutation during reproduction is so low that it can be ignored and only point mutations matter. In this setting, an organism’s offspring will be in the same or an adjacent vertex as its parent. Gillespie (1983; 1984) took this to the extreme by showing that in a population a mutation rate u and effective population size M, if M \log M < < 1/u then a beneficial mutation goes to fixation in the population before the next one can occur. This assumption is known as strong-selection weak-mutation (SSWM) and allows us to coarse-grain our scales to model the monomorphic population as a single point on the landscape, and evolutionary dynamics as steps from a vertex of lower fitness to an adjacent vertex of higher fitness. This hill climbing view of evolution has been very useful for proving mathematical results, but has also unfortunately led to a view of evolution as an optimization procedure and corresponding teleological conclusions.

Notice that in the SSWM model, the exact quantitative fitness differences between adjacent genotypes don’t matter; what matters is the qualitative feature of the difference being positive or negative. As such, it is tempting to replace the fitness function by a flow on the graph: instead of undirected edges between vertexes, we will direct the edges from the lower to the higher fitness genotype. Assuming that no two adjacent genotypes have exactly the same fitness then as long as the resulting directed graph is acyclic then it is possible to define some fitness function. This can be viewed as a biological analog to a von Neumann-Morgenstern rationality assumption on the landscape (with fitness interpreted as utility). Crona, Greene, & Barlow (2013) introduced this representation into theoretical biology as fitness graphs, but they have been used previously in empirical studies of fitness landscapes (De Visser et al. 2009; Franke et al., 2011; Goulart et al., 2013; Szendro et al., 2013). This approach is particularly useful empirically because it is difficult to quantitatively compare fitnesses across experiments. In theoretic work, the fitness graph approach has made the proofs of some classical theorems relating local structure to global properties easier.

A population will move along the flow on the fitness landscape from lower to higher fitness vertexes, reaching equilibrium only if it ever reaches a local or global peak (a sink in the flow model). The fact that (in finite fitness landscapes) it eventually has to reach a peak has been taken by biologists as justification for assuming that the population is already at a peak. In fact, from the earliest days to today, investigations in biology had the form (Wright, 1932):

In a rugged field of this character selection will easily carry the species to the nearest peak, but there may be innumerable other peaks which are higher but which are separated by “valleys.” The problem of evolution as I see it is that of a mechanism by which the species may continually find its way from lower to higher peaks in such a field.

Note that in the above passage, Wright implicitly assumes that a population starting away from equilibrium will get to a peak in a reasonable amount of time. However, this is an assumption computer scientists can question by asking what features of a fitness landscape allow evolution to find a peak faster than exhaustive search; this is the question both Chaitin (2009) and Valiant (2009) ask.

The simplest landscape to think about is the Mt. Fuji landscape. In this case, each locus contributes independently to fitness, there is no between locus interactions – called epistasis by biologists – in the genome. Mathematically, this means that we can write the fitness function f: \{0,1\}^n \rightarrow \mathbb{R} as f(x_1x_2...x_n) = \sum_{k = 1}{k = n}f_k(x_k) where each f_k is a function of a single bit with f_k(0) \neq f_k(1) – finding the optimal genotype is a matter of setting each bit x_k to the position (0 or 1) that maximizes f_k. In the landscape metaphor this is a smooth increasing hill towards the one maximum given by each locus set to the higher fitness allele; every shortest path is an adaptive path.

In this landscape, evolution is exponentially faster than exhaustive search. This speed up is easy to see, because in this case evolution is analogous to finding a marked element in a sorted list using binary search. If the organism is currently at a suboptimal genotype x then a candidate mutation samples a random bit k and if f(x_k) < f(\bar{x_k}) then an adaptive step is possible and the population “moves up” the landscape (else it samples another bit) and in the process it eliminates half of the possible remaining genotypes (i.e. all y with y_k = x_k) from further consideration — just like binary search. It is clear that if the optimal genotype is x^* then evolution will reach it in t steps where t is the number of bits on which x^* and x differ; i.e. their Hamming distance m = ||x^* - x||_1. Note that this is also the least number of steps possible for an asexual population, and even a designer can’t do better than m steps if constrained to point-mutations. Of course, evolution will try and reject some non-adaptive mutations and the expected number of mutations evolution considers will set the time t and be upper bounded by:

t \leq \frac{n}{m} + \frac{n}{m - 1} + ... + \frac{n}{1} \leq nm \leq n^2

This is polynomial in n — the size of the genome — and exponentially faster than exhaustive search, which would need to look at all (or most) of the 2^n possible genotypes. Notice the similarity to Chaitin’s results, this is because his ‘general abstract’ model only considers a Mt. Fuji landscape, and biologists have known since at least Kauffman & Levin (1987) that evolution on such simple landscapes is efficient. Unsurprisingly, this model is considered too simple to capture the nuances of real biological systems.

Of course, it is also not hard to see that there are landscapes where evolution — or actually any algorithm (except quantum ones, where Grover search allows a quadratic speed up, but that is still just a crawling slow 2^{n/2}) — will be as slow as exhaustive search. Simply select one genotype x^* \in \{0,1\}^n to have fitness 1 and all other 2^n - 1 strings to have fitness 0. Now, starting at a random point in this landscape and trying to find the fitness peak is equivalent to searching an unordered list of exponential size. Thus, the fitness landscape model has to be more carefully specified on what we consider to be biologically plausible landscapes.

This is the first of a series of posts on computational considerations of empirical and theoretical fitness landscapes.

References

Chaitin, G. (2009). Evolution of Mutating Software. EATCS Bulletin, 97: 157-164

Crona, K., Greene, D., & Barlow, M. (2013). The peaks and geometry of fitness landscapes. Journal of Theoretical Biology, 317: 1-10.

de Visser, J.A.G.M., Park, S.C., & Krug, J. (2009). Exploring the effect of sex on empirical fitness landscapes. The American Naturalist.

Franke, J., Klozer, A., de Visser, J.A.G.M., & Krug, J. (2011). Evolutionary accessibility of mutation pathways. PLoS Comp. Biol. 7(8): e1002134.

Gillespie, J.H. (1983). A simple stochastic gene substitution model. Theor. Pop. Biol. 23, 202.

Gillespie, J.H. (1984). Molecular evolution over the mutational landscape. Evolution 38, 1116.

Goulart, C.P., Mentar, M., Crona, K., Jacobs, S.J., Kallmann, M., Hall, B.G., Greene, D., Barlow, M. (2013). Designing antibiotic cycling strategies by determining and understanding local adaptive landscapes. PLoS ONE 8(2): e56040.

Kauffman, S., & Levin, S. (1987). Towards a general theory of adaptive walks on rugged landscapes. Journal of Theoretical Biology, 128(1): 11-45.

Szendro, I.G., Schenk, M.F., Franke, J., Krug, J., de Visser, J.A.G.M. (2013). Quantitative analyses of empirical fitness landscapes. J. Stat. Mech. P01005.

Valiant, L.G. (2009). Evolvability. Journal of the ACM 56(1): 3.

Wright, S. (1932). The roles of mutation, inbreeding, crossbreeding, and selection in evolution. Proceedings of the Sixth International Congress of Genetics, 356-366

About these ads

About Artem Kaznatcheev
From the ivory tower of the School of Computer Science and Department of Psychology at McGill University, I marvel at the world through algorithmic lenses. My specific interests are in quantum computing, evolutionary game theory, modern evolutionary synthesis, and theoretical cognitive science. Previously I was at the Institute for Quantum Computing and Department of Combinatorics & Optimization at the University of Waterloo and a visitor to the Centre for Quantum Technologies at the National University of Singapore.

17 Responses to Fitness landscapes as mental and mathematical models of evolution

  1. Pingback: Fitness landscapes as mental and mathematical m...

  2. Pingback: Epistasis and empirical fitness landscapes | Theory, Evolution, and Games Group

  3. Bill Tozier says:

    One of the deep problems I’ve run into with “folk” fitness landscapes—and I’m going to describe something all of my colleagues and I suffered from, back when I worked for Stu Kauffman at SFI and all day every day people worked on fitness landscapes—is this long-entrenched habit of seeing them as being some kind of simple x-y-plane-maps-to-z “mountains” and “plains”.

    Somewhere in making the jump from formal combinatorial-hypergraphs-with-arbitrarily-labeled-vertices to bumpy-discrete-surfaces-with-heights, we all seem to fall into a trap.

    It’s a complicated trap, and probably has something to do with these formal structures getting ridiculously complicated very quickly, but in every case I’ve ever watched it leads to either crumpling the models themselves up as “intractable” or hand-waving away crucial structures. Or (perhaps the worst) writing papers about how “counterintuitive” the observed behavior of artificial populations on synthetic landscapes is, compared with our folk images….

    So there’s the fact that crossover (or any interaction between “parents”) leads to a hypergraph structure where hyperedges connect multiple nodes, which can’t honestly be represented as any graph without giving up crucial information. There’s the fact that most evaluations of “fitness”, or any real engineering problems, are multiobjective and context-dependent. There’s the trick of shoving a probabilistic model down into a discrete simulation and not bothering to examine either relative likelihoods of outcomes, or the general problem-appropriate classes they might fall into. There’s the nasty little problem of defining “ruggedness” in anisotropic systems.

    And so on.

    Don’t get me wrong: fitness landscapes are awesome and extremely flexible models, and can lead to deep insights into the observed behavior of synthetic systems. But they can also be devilishly tricky, sophisticated professionals can be misled into imagining they “grok” them when they really don’t… and unfortunately they rely on 50 years of social and cultural habits in science and engineering, which sacrificed utility for tractability and really never looked back.

    • Thanks for that comment; you make an extremely good point. I agree, that some papers on landscapes feel pretty silly, and it is obvious that the authors are not comfortable with basic combinatorics. Carneiro & Hartl (2010) have a nice closing line to the same effect: “Fitness landscapes should not be abandoned, but rather studied in less picturesque but more quantitative ways.”

      Unfortunately, most of the ‘quantitative’ approaches to landscapes are still ignorant of combinatorics and this seems to be a cultural thing because most work is done by physicists and biologists that don’t receive a discrete structures course early in their education. That is why I am advocating for more theoretical computer scientists (as opposed to the usual engineering variety) to look closely at fitness landscapes. This is especially important given how independent of empirical data most models seem to be.

  4. Pingback: Black swans and Orr-Gillespie theory of evolutionary adaptation | Theory, Evolution, and Games Group

  5. Jon Awbrey says:

    Re: Everybody — theorist or experimentalist — “has a logical construct (a model) in his or her head” when studying anything.

    The question of “mental models” has occupied my thoughts for quite a while.

    As intelligent agents with a capacity for inquiry, we have ways of maintaining and modifying independent representations of “reality” — that is, the impressions that persist in impressing themselves on us that we provisionally sort into our external and internal worlds.

    As social agents with a capacity for communication, we have ways of impressing our personal representations on external media and sharing them with others, with all the contingencies and difficulties that attend on that partly phylogenetic and partly ontogenetic capacity for signing.

    I tend to come at this from a system-theoretic direction, asking “Where in what state space is the threshold of system-theoretic complexity that must be crossed to achieve the first signs of these capacities?”

  6. Pingback: Where Is Fancy Bred? | Inquiry Into Inquiry

  7. Pingback: NK and block models of fitness landscapes | Theory, Evolution, and Games Group

  8. Pingback: Computational complexity of evolutionary equilibria | Theory, Evolution, and Games Group

  9. Pingback: Semi-smooth fitness landscapes and the simplex algorithm | Theory, Evolution, and Games Group

  10. Pingback: Bounded rationality: systematic mistakes and conflicting agents of mind | Theory, Evolution, and Games Group

  11. Pingback: John Maynard Smith introducing games animals play | Theory, Evolution, and Games Group

  12. Pingback: Software through the lens of evolutionary biology | Theory, Evolution, and Games Group

  13. Pingback: Cataloging a year of blogging: the algorithmic world | Theory, Evolution, and Games Group

  14. Pingback: Phenotypic plasticity, learning, and evolution | Theory, Evolution, and Games Group

  15. Pingback: Computational theories of evolution | Theory, Evolution, and Games Group

  16. Pingback: Algorithmic Darwinism | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,104 other followers