- !” v-s ;\ r-n j I
2. a ".I ”a 1
f r.‘ "I’v‘.n '1“ Q. .4
gels Michigan state
U; .vssrszt

 

This is to certify that the
dissertation entitled

ON THE BENEFICIAL EFFECTS OF DELETERIOUS
MUTATIONS

presented by

Arthur W. Covert III

has been accepted towards fulfillment
of the requirements for the

Doctoral degree in Computer Science
Ecology, Evolutionary Biology
and Behavior

 

 

/(.,l’

 

Majo7(essor’s Signature
Date

MSU is an Affirmative Action/Equal Opportunity Employer

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5/08 K:IProlecc&Pres/ClRC/Date0ue indd

 

ON THE BENEFICIAL EFFECTS OF DELETERIOUS MUTATIONS
By

Arthur W. Covert III

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Computer Science
Ecology, Evolutionary Biology and Behavior

2010

Abstract
ON THE BENEFICIAL EFFECTS OF DELETERIOUS MUTATIONS
By
Arthur W. Covert III

This dissertation explores how deleterious mutations may become
beneficial via sign-epistatic mutations. While deleterious mutations may lower
fitness in the short-term, they have an expected half-life in the population during
which their initial fitness effect may be altered via a sign-epistatic compensatory
mutation. While the existence of compensatory mutations have been confirmed
in analytical, biological and in silico studies their long-term impact on adaptive

evolution has not been quantified.

Experiments presented here will show that deleterious mutations which
recover via sign-epistatic compensatory mutations have a major impact on long-
term evolution. This result is achieved primarily by disabling all deleterious
mutations before they can appear in evolving populations of digital organisms.
Fitness of populations without deleterious mutations is significantly lower than
control populations with all types of mutations, strongly indicating that deleterious
mutations were having a long-term positive impact on adaptive evolution. The
remainder of the dissertation explores the hypothesis that deleterious mutations
were enabling escape from isolated fitness peaks, via adaptive valleys. It is
shown that while fitness valleys are rarely traversed, their traversal is a

transformative event in the evolution of the population.

Deleterious mutations have long been thought to be unimportant, however
this view overlooks the pivotal role of epistasis. The unique experiments
presented here give new insights into the historical and highly contingent nature
of evolution. While evolution frequently finds a well adapted solution in the long-
term, evolving populations will frequently climb suboptimal peaks initially.
Deleterious mutations become useful because they aide evolution in reconciling

short-term and long-term adaptation.

Table of Contents

List of Tables ........................................................................................................... vi
List of Figures ....................................................................................................... viii
Chapter 1: Introduction and Background ................................................................ 1
1.1 A Brief Introduction to Fitness Landscapes .................................................. 2
1.2 Another Take on Deleterious Mutations as Stepping Stones: Wright's
Shifting Balance Theory (SBT) ........................................................................... 7
1.3 Island Models ................................................................................................ 8
1.4 Deleterious Mutations and Evolutionary History .......................................... 9
1.5 Deleterious Mutations vs. Neutral Mutations .............................................. 11
1.6 Compensatory Adaptations ........................................................................ 15
1.6.1 Biological Examples of Compensatory Adaptation ............................. 15
1.6.2 Analytical Examination of Compensatory Adaptations and their
Fixation Regimes .......................................................................................... 19
1.7 Artificial Life Experiments ........................................................................... 21
1.8 Discussion .................................................................................................. 23
Chapter 2: Tools .................................................................................................... 25
2.1 Avida ........................................................................................................... 25
2.1.1 Basic Layout of the Avida World ......................................................... 26
2.1.2 Self-Replication ................................................................................... 28
2.1.3 Variation ............................................................................................... 29
2.1.4 Fitness and the Life Cycle of Digital Organisms ................................. 31
2.1.5 Measuring the Success of Digital Organisms ..................................... 32
2.1.6 Epistasis and Experimental Evolution in Avida ................................... 33
2.2 Leveraging Avida in Experiments ............................................................... 35
2.2.1 Leveraging the Test CPU .................................................................... 35
2.2.2 Examining the Line of Descent ........................................................... 36
2.2.3 Testing Individual Mutations ................................................................ 37
2.3 Summary .................................................................................................... 37
Chapter 3: Reversion and Replacement of Mutation Classes .............................. 39
3.1 Methods and Experimental Setup .............................................................. 41
3.1.1 Reverting Mutations ............................................................................ 41
3.1.2 Replacing Mutations ............................................................................ 42
3.1.3 Side Effects of Replacement ............................................................... 44
3.1.4 Nearly Neutral Mutations ..................................................................... 45
3.1.5 Experimental Setup ............................................................................. 46
3.2 Results of Reverting and Replacing Mutations .......................................... 46
3.2.1 Reverting and Replacing Deleterious Mutations ................................. 48
3.2.2 Reverting and Replacing Neutral Mutations ....................................... 50
3.2.3 Reverting and Replacing Neutral and Deleterious Mutations ............. 53

3.2.4 Reverting and Replacing Lethal Mutations ......................................... 55

3.3 Discussion of Reversion and Replacement ............................................... 57
Chapter 4: Lineage Tracking ................................................................................. 59
4.1 Algorithm for Lineage Tracking ................................................................... 60
4.2 Examples of Possible Outcomes ................................................................ 63
4.2.1 Beneficial-Beneficial (BB) Outcome .................................................... 65
4.2.2 BeneficaI-Deleterious (BD) Outcome .................................................. 66
4.2.3 Deleterious-Beneficial (DB) Outcome ................................................. 67
4.2.4 Deleterious-Deleterious (DD) Outcome .............................................. 68
4.2.5 Neutral-Neutral (NN) Outcomes .......................................................... 68
4.3 Results ........................................................................................................ 69
4.3.1 Control Populations ............................................................................. 70
4.3.2 Populations Disabling Neutral Mutations ............................................ 72
4.4 Conclusions ................................................................................................ 74

Chapter 5: Replaying Evolved Genotypes to Distinguish Deleterious Stepping

Stones from Chance Events ................................................................................. 76
5.1 Test Case .................................................................................................... 78
5.2 Test Case Replays ...................................................................................... 80

5.2.1 Analysis of Path ll ................................................................................ 82
5.2.2 Analysis of Path Ill ............................................................................... 85
5.3 Replays of Deleterious Mutations ............................................................... 86
5.3.1 Beneficial-Beneficial Control Replays ................................................. 87
5.3.2 Neutral Control Replays ...................................................................... 91
5.3.3 Beneficial-Beneficial RpN-nn reruns ................................................... 92
5.4 Discussion .................................................................................................. 94

Chapter 6: Conclusions and Discussion ............................................................... 96

Appendix A: Glossary .......................................................................................... 103

Bibliography ......................................................................................................... 110

LiSt of Tables

Table 2.1: Rewards for performing nine one- and two input logic functions in the
standard logic-9 environment. The symbol '~' denotes negation. Digital
organisms have only the NAND operation with which to evolve the nine logic
functions, along with the appropriate input and output. Organisms are rewarded
for completing a logical task with an increase in merit, a unitless number
representing how fast the organism may run. Merit bonuses for each function
are the current merit times 2n were n is the number of logical gates required to
complete the function. This is the same environment used in most Avida
experiments including Lenski et al. (2003) ........................................................... 30

Table 3.1: Brief descriptions of each experimental treatment and their
abbreviation, these will be used throughout this dissertation. Abbreviations in
bold are used most frequently throughout this dissertation .................................. 48

Table 4.1: Tables depicting the outcome of all deleterious mutations from the 50
lines of descent that composed the control treatment. Only mutations with a
fitness effect greater than 1% were tracked. Table A shows the fate of all initially
deleterious mutations, table B shows the fate of only those initially deleterious
mutations that persisted until the end of the experiment. While the subset of all
mutations shows four prominent categories, DB, BB, DD, and, to a lesser extent,
NN, only those with a compensatory mutation that changed from deleterious to
beneficial (BB) are still represented in the final dominant genomes .................... 73

Table 4.2: Two tables depicting the outcome of all deleterious mutations from the
50 lines of descent that composed the RpN-nn treatment. Only mutations with a
fitness effect greater than 1% were tracked. Table A shows the fate of all
deleterious mutations, and table B shows only the fate of those deleterious
mutations that persisted until the end of the experiment. Substantially more BB
recoveries are observed here than in the control runs (both absolutely and
proportional). Neutral recoveries, both NN and BN, also occur more frequently.
.............................................................................................................................. 74

Table 5.1: Original line-of—descent showing the test case. Mutation labels are
consistent with Figure 5.1. Looking two steps back reveals that the “deleterious”
mutation actually took the place of a highly successful (over 10,000 total
genomes) copy-loop optimization, which reduced gestation time. Lowering
gestation time conferred a small fitness advantage, but made it difficult, if not
impossible, to evolve EQU .................................................................................... 80

Table 5.2: A table describing the three different paths the control reruns took to
EQU. The first column gives the minimum number of mutations to evolve EQU.
The next two columns list the fitness lost from the deleterious mutation, and
gained by the recovery, relative to the progenitor fitness. Finally, the last column

vi

lists how many replicates used each path. The relative recovery for path ”I
contains two values, one for the initial recovery, and another for the recovery to
EQU for which a deleterious mutation was required ............................................ 83

vii

List of Figures

Figure 1.1: Two examples of a sign-epistatic interaction. In example A, the
mutation Y is deleterious on the background x but beneficial on the background
X, and thus is considered sign-epistatic. ln example B, both mutations X and Y
are deleterious on the wildtype background, but beneficial on each others
background, both mutations are considered sign-epistatic .................................... 3

Figure 1.2: A sample fitness landscape, the changes in the genotype affect the
phenotype for some trait. Both peaks will theoretically act as attractors for an
evolving population. If the trait is stuck on peak A, then it may be difficult or
impossible to move to peak B through pure selection ............................................ 5

Figure 1.3: Wrights original definition of a fitness landscape (1932) included
many descriptions of how populations moved on and around fitness peaks,
culminating in his theory of shifting balance. Wright postulated that reducing
selective pressure by decreasing population size or increasing mutation rate
could cause populations to drift away from peaks (A); whereas the opposite
would attract populations more closely to their current peak (B). In Wright's SBT
if a population could escape one fitness peak through drift and find a new, higher
peak through selection, organisms at that new peak would likelysweep the local
deme; then the deme could send out migrants to spread the highly fit gene
throughout the population ....................................................................................... 7

Figure 1.4: Increases in fitness on the royal staircase with ditches requires a
neutral step to get a new punctuating A block, followed by a series of to
deleterious mutations to convert the old A block into a B block. While the X block
is in the deleterious state, a constant fitness penalty of h is applied. Thus, the
royal staircase with ditches provides a fitness landscape with fitness barriers of
tunable length and magnitude .............................................................................. 13

Figure 1.5: Atypical fitness landscape of antibiotic resistance (including those
seen by Schrag et al 1997). The wild type (or) and the compensatory strain (Cr)
are sensitive to the antibiotic, indicated by the red dots. Two genotypes exist that
are resistant to the antibiotic (cR and CR). When the compensatory mutation
(Cr) the bacteria is almost as fit as if there were no antibiotic present. It is
important to note that the environment has a significant impact on this fitness
landscape. The deleterious mutations (Cr and cR) are only deleterious when no
antibiotic is present (green dots). When antibiotic is present (red dots) the
landscape contains a hill to climb ......................................................................... 19

Figure 1.6: An example of lwasa et al.'s “Stochastic Tunneling”, White represents
the portion of the population with cell type a, red represents the deleterious cell
type b, and blue represents the beneficial cell type c. Time is increasing along
the X-axis, and the portion of the population at each cell type is represented on

viii

the Y—axis. As long as the mutation rate is sufficient, deleterious clades can
emerge and mutate to cell type c, without fixing in the population. Cell type b
may emerge several times before it acquires the deleterious mutation ............... 21

Figure 2.1: The Avida world is a toroidal grid, with each cell containing the virtual
hardware organisms need to run their genome .................................................... 28

Figure 3.1: Mutation distribution after reverting deleterious mutations. Each bar
represents the distribution of fitness effects for all possible single point mutations
in a hypothetical genome. The top bar shows the relative number of beneficial
(blue), neutral (green), deleterious (red), and lethal (black) mutations under
normal conditions. The lower bar shows the relative distribution of single point
mutations when deleterious mutations are reverted. Reverting the disabled class
lowers the effective mutation rate, because it eliminates an entire class of
mutations without replacement ............................................................................. 43

Figure 3.2: A flowchart of the replacement algorithm. Every time an organism is
ready to divide, there is a possibility of mutation. If the mutation is of a
disallowed class, then the offspring genome is reverted and mutated again until
an acceptable mutant is found. If the offspring genome has an unstable genome
it is sterilized before being placed in the population. The blue dotted portions of
the chart denote steps that are added by replacement, the black portions denote
steps that normally occur in Avida. Note that unstable genomes are sterilized in
control runs as well ............................................................................................... 44

Figure 3.3: Mutation distribution after replacing deleterious mutations. Each bar
represents the distribution of fitness effects for all possible single point mutations
in a hypothetical genome. The top bar shows the relative number of beneficial
(blue), neutral (green), deleterious (red), and lethal (black) mutations under
normal conditions. The lower bar shows the relative distribution of single point
mutations when deleterious mutations are replaced. We see that replacement of
the disabled class significantly increases the number of other mutations,

including lethal mutations, but does not lower the effective mutation rate ........... 45

Figure 3.4: Mutation distribution after replacing deleterious mutations but
protecting nearly neutral mutations. As in figure 3.3, deleterious mutations were
replaced on a hypothetical genome, but in this case, mutations with a fitness
effect less than 1% (represented by light pink) were considered effectively neutral
and not replaced ................................................................................................... 47

Figure 3.5: Final dominant fitness boxplots under six evolutionary treatments
each containing 50 replicate populations. All fitnesses are normalized by the
fitness of the ancestor. (C) All mutations enter the population normally. (RpD) All
deleterious mutations are replaced with a random beneficial, neutral or lethal
mutation. (RpDL) All deleterious and lethal mutations are replaced with a
random neutral or lethal mutation. (RvD) All deleterious mutations are simply
reverted, as if they never occurred. (RvD-nn) All deleterious mutations with a

fitness effect greater than 1% are reverted. (RpD-nn) All deleterious mutations
with a fitness effect greater than 1% are replaced with a beneficial, neutral or
lethal mutation. In all cases, the control treatment has significantly higher fitness
(see text for statistics) strongly indicating that the loss of deleterious mutations
impeded long-term adaptation .............................................................................. 50

Figure 3.6: Final dominant fitness under six evolutionary treatments each with 50
replicate populations. All fitnesses are normalized by the fitness of the ancestor.
(C) All mutations enter the population normally. (RpN) All neutral mutations are
replaced with a random beneficial, deleterious or lethal mutation. (RpNL) All
neutral and lethal mutations are replaced with a random neutral or lethal
mutation. (RvN) All neutral mutations are simply reverted, as if they never
occurred. (RvN-nn) All mutations with a fitness effect less than 1% are
considered effectively neutral and reverted. (RpN-nn) All mutations with a fitness
effect less than 1% are considered effectively neutral and replaced with a
beneficial, deleterious or lethal mutation. In three cases (RpN, RvN-nn and RpN-
nn), the control treatment has significantly higher fitness (see text for statistics)
strongly indicating that the loss of deleterious mutations impeded long-term
adaptation. In two cases (RpNL and RvN) median fitness of the control
population was not higher, this is discussed in the text ........................................ 52

Figure 3.7: Final dominant fitness under six evolutionary treatments, each with
50 replicate populations. All fitnesses are normalized by the fitness of the
ancestor. (C) All mutations enter the population normally. (RpND) All neutral and
deleterious mutations are replaced with a random beneficial, or lethal mutation.
(RpNDL) All neutral, deleterious and lethal mutations are replaced with a random
beneficial mutation. (RvND) All neutral and deleterious mutations are simply
reverted, as if they never occurred. (RvND-nn) All mutations with a fitness effect
less than 1% are considered effectively neutral and reverted along with
deleterious mutations. (RpND-nn) All mutations with a fitness effect less than 1%
are considered effectively neutral and replaced with a beneficial, or lethal
mutation. The control population has significantly higher fitness than all
experimental treatments ....................................................................................... 55

Figure 3.8: Final dominant fitnesses under three evolutionary treatments, each
with 50 replicate populations. All fitnesses are normalized by the fitness of the
ancestor. (C) All mutations enter the population normally. (RpL) All lethal
mutations are replaced with a random beneficial, deleterious, or lethal mutation.
(RvL) All lethal mutations are reverted, as if they never occurred. There were no
significant differences between these treatments ................................................. 57

Figure 4.1: Atheoretical lineage containing a deleterious mutation. Each circle
represents a genotype on the line of descent, differing by exactly one mutation
from its parent. P represents the progenitor of the deleterious genotype. d1 ...dn
are the n genotypes that carry the deleterious mutation. d' indicates the first
genotype without the deleterious mutation, FD is the final dominant genotype.
The color denotes change in fitness relative to the progenitor (equation 1); red

shades are deleterious (.4f<1), blue shades are beneficial (Af>1) and white
indicates neutral (Af=1), as indicated by the key above the lineage ..................... 62

Figure 4.2: A theoretical lineage paired with its alternate lineage. For every
genotype dk an alternate genotype rdk is created with mutation d reverted to the
progenitor state, but otherwise identical to the genotype on the actual line of
descent. The color of the alternate lineage represents change in fitness relative
to the paired genotype on the actual lineage (equation 2) and explicitly describes
the fitness effect of an individual mutation. Also note that f(rd1) is always equal
to the progenitors fitness (as they are the same genotype) ................................. 63

Figure 4.3: A grid representing all the possible fitness changes of an individual
deleterious mutation versus the fitness changes of the line of descent relative to
the progenitor. The horizontal axis represents the change in fitness effect of an
initially deleterious mutation, as indicated by the fitness changes in the alternate
line of descent (AAlternate LoD), determined by equation 2. The vertical axis
represents the fitness changes along the line of descent, relative to the
progenitor of the deleterious mutation (AfLoD), determined by equation 1. Five
possible extremes are highlighted: Deleterious-Beneficial (DB), Beneficial-
Beneficial (BB), Deleterious-Deleterious(DD), Beneficial-Deleterious (BD) and
Neutral-Neutral(NN). These extremes are fully described in the text, along with
example lineages .................................................................................................. 64

Figure 4.4: A theoretical lineage paired with an alternate lineage, as in Figure 4.2,
depicting a possible Beneficial-Beneficial outcome. The deleterious mutation
shifts its effect to beneficial via a sign-epistatic interaction and remains beneficial
until the end of the experiment. The example in Figure 4.2 is also BB, but that
sign-epistatic pair in that figure is eventually replaced by an even more beneficial
mutation before the end of the experiment. ......................................................... 66

Figure 4.5: Atheoretical lineage paired with an alternate lineage, as in Figure
4.2, depicting a possible Beneficial-Deleterious outcome. The deleterious
mutation is partially compensated for by a subsequent mutation at d3 which
conferred a compensatory mutation that ameliorates the deleterious effects of d1,
but in this case does not fully compensate for d1. Regardless, the genome is
more fit with both mutations than either one by themselves, indicating epistasis in
the magnitude of the fitness effects, but not altering the sign. In this case the
deleterious mutation is replaced with one that fully compensates for the fitness
loss initially incurred. It is also possible that the epsistatic mutations will be
joined by a third that is sign-epistatic with the first two, but this possibility was not
captured by this analysis ....................................................................................... 67

Figure 4.6: A theoretical lineage paired with an alternate lineage, as in Figure 4.2,
depicting a possible Deleterious- Beneficial outcome. Although the genomes on
the line of descent have fully recovered their lost fitness by d3, the alternate line
of descent reveals that they would still be more fit without the deleterious
mutation. Since the lineage would still be more beneficial without the deleterious

xi

mutation than with, the deleterious mutation has not altered the sign of its fitness
effect and is still deleterious. ................................................................................ 68

Figure 4.7: A theoretical lineage paired with an alternate lineage, as in Figure 4.2,
depicting a possible Deleterious-Deleterious outcome. The deleterious mutation
entered the population, but its fitness effect was never altered and it was
eventually replaced by a more fit mutation at the same site. Although in this case
the subsequent mutation that replaced the deleterious one was more fit, a simple
reversion or another mutation that was neutral relative to the progenitor would
have restored fitness ............................................................................................. 69

Figure 4.8: Atheoretical lineage paired with an alternate lineage, as in Figure 4.2,
depicting a possible Neutral-Neutral outcome. The deleterious mutation entered
the population, and persisted until it was joined by a second mutation that made
both fitness effects neutral with respect to the progenitor .................................... 70

Figure 4.9: Atheoretical lineage paired with an alternate lineage, as in Figure 4.2,
depicting a lineage in which deleterious mutation d, is replaced with another
deleterious mutation. The new mutation (n1) is neutral with respect to it's
immediate parent but deleterious with respect to the progenitor. When the
mutation is eventually compensated for, the end result is still passing through a
fitness valley. However, this case would have been overlooked by the analysis
presented in this chapter, because mutations were only classified as deleterious
relative to their immediate parent not genomes further back on the line of
descent .................................................................................................................. 75

Figure 5.1 : A test case that consisted of a 3 way interaction between a sign-
epistatic pair of mutations and one purely neutral mutation, which occurred
between them. (A) Four sequences were observed in the line of descent, the
other four sequences were constructed to reveal other possible epistatic
interactions. The relevant mutations in each sequence are colored. The
reconstruction shows that the neutral mutation (N) is truly neutral, and the
“Beneficial” mutation (a8) is actually lethal when isolated from the “deleterious”
mutation (Ab); only both mutations together (AB) are truly beneficial. (B) a
representation of the sign-epistatic interaction between the relevant gene
combinations; the neutral mutation was dropped form this figure because it had
no effect on the topology of the landscape ........................................................... 79

Figure 5.2: A test of a three-way interaction among mutations that conferred
EQU. The progenitor (xyz) is the same as the progenitor in figure 5.1, and again
three mutations lead to EQU, a deleterious (X), neutral (Y) and beneficial (Z).
However, in this case, reconstructions of all combinations revealed that the
“neutral” mutation was actually necessary for EQU. Dotted lines in the figure
above indicate all possible paths to EQU using these three mutations, the solid
line indicates the path that was actually taken in the replay. The table above lists
full reconstruction information for all possible combinations of the three

mutations ............................................................................................................... 84

xii

Figure 5.3: A scatter plot depicting the results for rerunning 36 pairs of treatments
seeded with either a deleterious mutant (vertical axis) or its immediate progenitor
(horizontal axis) and run under RpD conditions. Each point represents a pair of
median final dominant fitnesses from each treatment. Filled points represent
treatments where the deleterious mutant resulted in significantly higher fitness
than the immediate progenitor (p<0.05). The dotted line indicates where the
medians would be equal, points above the line favored the deleterious mutant,
points below favored the progenitor. The significance tests are discussed further
in the text ............................................................................................................... 89

Figure 5.4: A figure representing the fitness interaction of the tied replay. The
progenitor (dc) was only two mutations away from the genotype that performed
EQU (DC). Which order the mutations occurred in (Do first or dC first)
determined whether or not the path followed was deleterious or neutral. The
path taken by the original experiment is denoted by the solid line ....................... 91

xiii

Chapter 1: Introduction and Background

This dissertation will show that deleterious mutations can have a
transformative, positive effect on long-term adaptive evolution. It will be shown
that particular deleterious mutations serve as stepping stones, providing
populations with access to otherwise inaccessible peaks on the fitness
landscape. This introductory chapter will first examine fitness landscapes (1.1),
and Wright's Shifting Balance Theory (1.2), which is the only major theory in
population genetics that utilizes, as a key component, deleterious mutations to
cross fitness valleys. The next section (1.3) contains a survey of literature from
the computational realm, that exhibits the efficacy of Wright's theory through

practical application in Genetic Algorithms.

After a high-level discussion of Wright's theory and its computational
analogs, one of the central arguments against SBT will be examined, namely that
deleterious mutations are never needed to cross fitness valleys. In section 1.4,
theoretical reconstructions of narrow paths to high fitness peaks are described,
followed by a section on computational work (1.5), which tries to suggest that
paths of neutral mutations should always be “preferred” over deleterious paths
leading to the same peak. Section 1.6 discusses mounting evidence that
compensatory mutations, can not only bring populations to new fitness peaks,
but that they can fix in asexual populations, even under heavy selective pressure
that would normally purge deleterious mutations. Finally section 1.7 ties together
the computational and biological domains, by reviewing two anecdotal cases

where deleterious mutations served as stepping stones to new fitness peaks;

 

 

 

_ I ’OJ : :.
XV ' ' XV I xy I...
(D ' . . I s. '
g 2 . ‘e I.
u- ‘ e" ‘ a
> >
Genotype Space Genotype Space

Figure 1.1: Two examples of a sign-epistatic interaction. In example A, the
mutation Y is deleterious on the background x but beneficial on the background
X, and thus is considered sign-epistatic. In example B, both mutations X and Y
are deleterious on the wildtype background, but beneficial on each others
background, both mutations are considered sign-epistatic.

providing a motivation for the central question of this dissertation: do such

stepping stones constitute a major force of adaptive evolution or are they merely

interesting anecdotes?

1.1 A Brief Introduction to Fitness Landscapes
Sewall Wright described a “fitness landscape" as a plain of genotypes with

each gene combination plotted against fitness (Wright 1932). Wright recognized
that for each additional site of the genome mapped, the size of the landscape
increased exponentially, requiring a new dimension to fully describe. Despite
their complexity, the analogy of a fitness landscape is useful in illustrating the
fitness changes undergone by evolving populations. Even with only two

dimensions, such a landscape can be extremely rugged with high fitness peaks

separated by low fitness valleys.

Epistasis’ more specifically, sign-epistasis, has the strong potential to
create such isolated fitness peaks (Gillespe 1984, Whitlock et al 1995, Weinrich
et al 2005). Epistasis describes the different the fitness effects a particular
mutation has on different genetic backgrounds. Normally the changes in the
genetic background affect only the magnitude of the fitness effect. Sign-epistasis
however occurs when the changes in the genetic background effect the sign of
the mutation's fitness, changing it from deleterious to benefical (or vice-versa).
Such sign-epistatic mutations will often occur in pairs, but this is not a
requirement, and jointly beneficial but individually deleterious sign-epistatic pairs
are commonly thought of as the basis for a rugged fitness landscape (Gillespe
1984, Weinrich et al 2005).

The movement of populations through these landscapes and the role
deleterious mutations play, has been a point of great contention over the years
(Polewijick et al 2007, Weinrich et al. 2006, Weinrich et al. 2005, Whitlock et al
1995, Coyne et al 1997,Phillips 1996, Gillespe 1984). There is some debate as
to whether fitness peaks are ever truly isolated (Whitlock et al 1995, Polewjick et
al 2007). Narrow pathways of neutral mutations to high-fitness peaks have been
found, indicating that even a relatively isolated area of the fitness landscape may
be accessible by a connective ridge (Weinreich et al. 2005). It is impossible to
tell if a fitness peak is truly isolated by low fitness valleys (Whitlock et al 1995),

as current technology cannot reveal all possible gene combinations and their

 

1 For a definition of “epistasis” and other italicized terms throughout, please refer to the glossary
(page 103).

Fitness

Genotype

Figure 1.2: A sample fitness landscape, the changes in the genotype affect the
phenotype for some trait. Both peaks will theoretically act as attractors for an
evolving population. If the trait is stuck on peak A, then it may be difficult or
impossible to move to peak B through pure selection.

fitness interactions. Even the fitness landscape of a relatively simple in silico
model system is too complex to exhaustively map (Lenski et al 1999). However,
experiments with bacteria and phages have shown that when deleterious
mutations are intentionally introduced, the resulting populations evolve to
different fitness equilibria (Moore et al 2000, Burch and Chao 1999). These new
equilibria of varying fitness, would seem to indicate that the populations have
reached a new area of the fitness landscape that is effectively isolated. In

addition, other works have shown that narrow ridges of neutral mutations can be

difficult to traverse, since they are presumed to be surrounded by highly

deleterious and/or lethal mutations (van Nimwegen and Crutchfield 2000;
examined more throughly later in this chapter) Chapter 5.2 will also describe a
method of determining if a genotype is effectively isolated, and thus may be
presumed to be on a fitness peak. For the moment, it is important to clarify that
all references to a fitness peak, are intended to refer to a genotype, or set of
genotypes, that are at a fitness equilibrium they cannot escape from without a
loss of fitness.

ln Wright's original definition of a fitness landscape (1932), he theorized
that populations would primarily be limited to areas around a high fitness peak,
which act as attractors for the population (Figure 1.2). Wright postulated that
movement away from a peak would be governed by different combinations of
drift, selection, inbreeding, environmental change and population structure
(Figure 1.3). For example, increased mutation or decreased selective pressure
would result in drift away from the peak and allow a broader exploration of the
surrounding landscape (Figure 1.3A). Alternatively, increased selective pressure
or decreased mutation results in less drift, and thus less exploration around the
peak (Figure 1.3B). A reduction in population size can also induce drift strong
enough to push a population off a fitness peak. Wright's examples illustrate the
trade-off between drift through the fitness landscape (exploration) and selection
of small, highly fit areas of the fitness landscape (exploitation). On the one hand,
the existence of an exploitation vs. exploration trade-off (synonymous with
selection vs. drift) is widely acknowledged in Genetic Algorithm (GA) circles. GA

researchers try to strike a balance whereby new fitness peaks are explored,

 

 

 

 

 

 

 

 

Figure 1. 3: Wrights original definition of a fitness landscape (1 932) included
many descriptions of how populations moved on and around fitness peaks,
culminating in his theory of shifting balance. Wright postulated that reducing
selective pressure by decreasing population size or increasing mutation rate
could cause populations to drift away from peaks (A); whereas the opposite
would attract populations more closely to their current peak (8). In Wright's SBT
if a population could escape one fitness peak through drift and find a new, higher
peak through selection, organisms at that new peak would likelysweep the local
deme; then the deme could send out migrants to spread the highly fit gene
throughout the population.

while simultaneously making certain already discovered useful peaks are fully
exploited (Cantu-Paz, E. 1998). On the other hand, the drift vs. selection tradeoff
is still a point of disagreement among biologists (Coyne et al. 1997, van
Nimwegen and Crutchfield 2000, Polewjick et al 2007), insofar as it entails
moving through adaptive valleys. This disagreement reveals a bias against the
idea of deleterious stepping stones between high-fitness peaks, however, there is
a lack of empirical evidence one way or the other. One of the main goals of this
dissertation is to provide badly needed empirical evidence regarding the role of

deleterious mutations in evolution.

1.2 Another Take on Deleterious Mutations as Stepping
Stones: Wright's Shifting Balance Theory (831)

Wright's SBT holds that most populations of organisms are divided into
demes (subpopulations), which are connected by low levels of migration. The
shifting balance theory has been described as consisting of three phases (Coyne
et al. 1997, Wright 1932). Individual demes can, at times, be dominated by the
effects of drift (phase I, Figure 1.3A), which allows them to acquire deleterious
mutations and cross fitness valleys to find new adaptive peaks. Eventually
these newly discovered peaks will sweep through the deme (phase II, Figure
1.38). Finally, demes on different peaks compete at the meta-population level to

sweep through the entire population (phase III, Figure 1.3C).

Obviously, SBT is much more complicated than described above. Most
notably SBT requires, (1) deleterious mutations acting as stepping-stones

through fitness valleys, (2) drift strong enough to override selection of a fitness

peak, but not so strong that subpopulations cannot exploit a new, possibly more
fit peak, and (3) population level group selection that allows competition between
demes (Coyne et al. 1997). Coyne and colleagues, in addition to calling these
individual components into question, invoked an Occum's razor argument that
Fisher's theory of mass-selection explained movement through the fitness
landscape, without the elaborate population genetics machinery Wright
envisioned. The disagreement over the merits of SBT has been the cause of
much debate, to which a massive body of work has already been devoted. SBT
relevance to this dissertation lies in the importance it places on deleterious
mutations as stepping stones through adaptive valleys; a concept that has been

given a great deal of attention in the field of Genetic Algorithms (GA).

Wright's original formulation of SBT also called for highly beneficial traits to
be spread to new demes through sexual reproduction. Asexual populations,
such as the ones examined in the following chapters, might be able to leverage
the first two stages of SBT, but the third stage would be significantly different.
Under asexual reproduction, beneficial mutants that migrate to new
subpopulations would sweep the local deme, much as an invasive species
would. Asexual organisms sweeping local demes will still spread the beneficial

mutant, and may lead to the same end result as Wright's sexual SBT.

1.3 Island Models
Many GAs utilize SBT inspired “island models” to address the trade-off

between exploitation and exploration. Island models meet the basic assumptions

of Wright's SBT; they divide a standard GA population into a series of

subpopulations, and connect them through migration (Cantu-Paz, E. 1998). The

earliest island models (Grosso 1985 and Tanese 1989), emphasized the SBTs

role addressing “premature convergence”? the GA term for an entire population
becoming stuck on a suboptimal peak in the fitness landscape. Several studies
have confirmed that island models can ameliorate premature convergence,
relative to standard GAs of equal total population size (Cantu-Paz, E. 1998,
Tanese 1989, Belding 1995, Lin et al. 1998, Fernandez et al. 2003). It has also
been shown that the subdivided populations of island models find a greater
variety of unique solutions, in other words, increase in genetic diversity (Cantu-
Paz, E. 1998, Tanese 1989). Island Models provide an impressive example of

SBT models traversing a rugged fitness landscape.

1.4 Deleterious Mutations and Evolutionary History
Despite Wright's assertion that isolated fitness peaks do exist, along with

the impressive examples furnished by GAs, recent biological and computational
studies have argued that evolution often finds narrow ridges of neutral or
beneficial mutations through genotype space leading to high fitness peaks
without the need for deleterious mutations (Poelwijk 2007, Wienreich et al 2006,
Bridgham et al. 2006, Lunzer et al. 2005, van Nimwegen and Crutchfield 2000,
van Nimwegen et al. 1999). Many of these works focus on reconstructing
possible evolutionary paths to highly fit genotypes (Weinreich et al. 2006,.

Bridgham et al. 2006, Lunzer et al. 2005). Reconstruction studies, while labor

 

2 Other methods of eliminating premature convergence include, fitness sharing and niching,
these methods are called “diversity methods" because they split fitness rewards between
similar organisms.

intensive, allow for an empirical examination of the fitness landscape. However,
these studies discount the possibility of paths through deleterious mutations
whenever a beneficial or neutral path is found, even when that path is longer
because it relies on back-mutations (Poelwijk 2007, DePristo et al. 2007).
Weinreich et al. (2006), for example, reconstructed all painNise combinations of
the 5 mutations needed for the evolution of beta-lactamase antibiotic resistance
in Escherichia coli. Using this mutation information, Weinreich and colleagues
identified 18 paths consisting purely of neutral or beneficial mutations, then
computed the relative probability of each path, based on maximum likelihood.
Although Weinreich et al. discounted the possibility of pathways through
deleterious mutations as “inaccessible”, a follow up study (DePristo et al. 2007)
highlighted a small number of pathways that included back-mutations, mutations
that fixed and were subsequently removed.

DePristo and colleagues used extreme value theory to isolate 9 pathways

containing back-mutations, out of approximately 18 billion (109) permutations,
and labeled these pathways as “accessible”. These 9 pathways were highlighted
in DePristo et al. 2007, despite the author's own admission that they likely
account for only a small fraction of the total frequency distribution (~1%),
because they were indicative of the unusual paths an adaptive walk might take.
Other studies, that constructed and assayed intermediate genotypes to examine
the surrounding fitness landscape, have identified similarly constrained paths of
beneficial or neutral mutations leading to high fitness peaks (Bridgham et al.

2006, Lunzer et al. 2005). Pathway reconstruction studies highlight some of the

10

most circuitous paths evolution can possibly take; they discount the role of
deleterious mutations, while simultaneously maintaining that other transitory and
highly unlikely events, may play a role.

Poelwijk et al (2007) has argued that populations on any rugged
landscape, without beneficial pathways, can only move through “inaccessible”
paths by undergoing simultaneous multiple mutations, relaxed periods of
selection, or some form of recombination. While none of these mechanisms are
impossible, or unimportant, the mounting evidence for compensatory adaption (to
be discussed in 1.6) suggests that pathways containing deleterious mutations

should also be given serious consideration.

1.5 Deleterious Mutations vs. Neutral Mutations
There are only a handful of empirical studies that directly address the role

of deleterious mutations, one of which this section examines in detail. Van
Nimwegen and Crutchfield (2000) and van Nimwegen et al. (1999) identified
constrained paths between high-fitness peaks in neutral networks. In analytical
and computational studies van Nimwegen and colleagues used neutral networks
to distinguish two types of barriers to high fitness genotypes, which they termed
entropy barriers and fitness barriers. An entropy barrier is a narrow path of
mutations where fitness is not lost, but is surrounded by lethal or deleterious
mutations. Weinreich et al.'s paths to beta-lactamse evolution in E. coli would be
an example of an entropy barrier and these barriers are generally assumed to be
fairly rare. Fitness barriers are networks (or valleys) where fitness is lower than

the best fitness found so far. Both types of barrier and with a “portal genotype,” a

11

genotype that leads to a previouslyunexplored network of higher fitness. Entropy
barriers are hard to traverse, owing to their rarity and narrowness; fitness barriers
are hard to traverse owing to their decrease in relative fitness. In a study of
meta-stability dynamics, van Nimwegen and Crutchfield attempted to show that
entropy barriers took exponentially less time to traverse than fitness barriers and

thus should be “preferred” by evolution.\

 

A=III III
K
B=II... IIOO...OO
T (1)
—w w
X=lllOl+EDon'tCare
K

Experimentally, van Nimwegen and Crutchfield (2000) used a “royal
staircase with ditches” fitness function (Equ 1 and Figure 1.4), derived from the
classic “royal road” fitness function (Mitchell et al. 1992), to illustrate the
difference in crossing times between entropy and fitness barriers. Each GA
solution was made up of 3 types of binary digit blocks, named A, B and X (Equ
1). Type A blocks consisted of all ones, type B started with all ones and ended
with w zeros, and type X blocks included all remaining combinations of ones and
zeros. Solutions received fitness n for having n type B blocks followed by a type
A block, and fitness n — h (where h was some constant) for n type B blocks
followed by a type X and ending with type A block. Selection was proportional to
fitness and single point mutations were the only operators used. To increase
fitness, first an entropy barrier had to be traversed by converting the first type X
block into a type A block, requiring a sequence of neutral mutations. Second, the

fitness barrier had to be traversed, by converting the first type A block into a type

12

F=n

F=n Neutral

/_/

, Deleterious

 

f- Beneficial
l

.. 2
Figure 1.4: Increases in fitness on the royal staircase with ditches requires a
neutral step to get a new punctuating A block, followed by a series of a)
deleterious mutations to convert the old A block into a B block. While the X block
is in the deleterious state, a constant fitness penalty of h is applied. Thus, the
royal staircase with ditches provides a fitness landscape with fitness barriers of
tunable length and magnitude.
B block, invoking the n-h fitness penalty. At each step on the staircase, solutions
had to thread the needle through a single constrained path to higher fitness,
while avoiding lethal mutations (Figure 1.4).

By deriving equations based on binomial mutation probabilities, Van
Nimwegen and Crutchfield were able to analyze how long it should take to cross

entropy and fitness barriers. Analytically, they showed that the entropy barrier, a

13

neutral X block to A block conversion, took lesstime than the deleterious A block
to B block conversion. This was reflected in the actual GA experiments, which
had long periods of stasis between neutral networks. These long periods of
stasis were attributed by van Nimwegen and Crutchfield to the crossing time of
fitness barriers. From this they further inferred that when offered a choice of
entropy or fitness barriers, evolution should always prefer the non-deleterious
entropy barriers.

Individual solutions actually crossed the fitness barrier repeatedly, and in
relatively short amounts of time, but failed to fix only due to pervasive lethal
mutations (van Nimwegen and Crutchfield 2000). Van Nimwegen and Crutchfield
also overlooked experiments done by Belding (1995) with island models (the GA
cousin of Wright's SBT). Belding's work exhibited slower evolution, but arrived at
more fit solutions using the royal road fitness function, from which the royal road
which ditches is derived.

Another issue is that, van Nimwegen's experiments did not offer
populations a choice of barriers; all solutions had to pass through both a fitness
barrier and an entropy barrier. Therefore, these experiments lacked the inductive
power to infer which barrier should be "preferred”. The fixation of deleterious
mutations is obviously difficult, and is examined in detail onlly if the deleterious
mutation leads to a novel adaptation, usually due to a sign-epistatic
compensatory mutation. Compensatory adaptations are examined more closely
in the next section, looking at both analytical and empirical examples and leading

to the construction of a framework for new experiments looking at the long-term

14

effect of deleterious mutations and their role in evolution.

1.6 Compensatory Adaptations
Compensatory adaptations are one of four possible outcomes that can

arise after a deleterious mutation enters the population. Moore et al. (2000)

defined these outcomes as (1) extinction of the population, (2) indefinite

persistence3, (3) reversion to it's former state (back-mutation) or (4)
compensated for, i.e. acquiring a mutation at a different site that ameliorates the
deleterious effect. All of the previous biological studies, with the exception of van
Nimwegen, have assumed the first case, that deleterious mutations will go to
extinction. Mounting evidence, surveyed below, suggests that compensatory

adaptations play a more important role than previously thought.

1.6.1 Biological Examples of Compensatory Adaptation
Schrag et al. (1997) showed that E. Coli could acquire compensatory

mutations to negate almost the entire fitness cost of antibacterial resistance. In
addition, when the resistant strains were reverted to antibiotic sensitive
genotypes, the compensatory mutations themselves caused a reduction in
fitness. In other words, both the mutations conferring resistance and those
compensating for lost fitness were individually deleterious. Several other works
have shown similar effects in bacteria (Maisnier—Patin et al. 2002, see Lenski
1998, and Maisnier-Patin & Andersson 2004 for a review), viruses (Burch and
Chao 1999) and insects, (McKenzie 1982). Such compensatory adaptations are

often examples of sign-epistasis, that is, mutations that are individually

 

3 Deleterious mutations only persist indefinitely in small populations were drift may overcome
selection and allow the mutation to fix.

15

deleterious, but can be neutral or beneficial when combined (Weinrich et al.
2005).

Burch and Chao (1999) demonstrated that compensatory adaptations
could bring populations to rest on different peaks of the fitness landscape. They
introduced deleterious mutations into a phage by pushing populations through a
series of bottlenecks. They then observed re-evolution of the phage to different
stable fitness equilibria, indicating that the re-evolved populations lay on different
fitness peaks. Burch and Chao also asserted that these new fitness peaks were
conditionally adaptive, or sign-epistatic, since the original un-mutated phage did
not evolve when subjected to the same recovery phase. The claim of sign-
epistatic compensatory adaptation is, while compelling, a somewhat conjectural
argument in this case. The exact genomes were not sequenced and the
deleterious mutations were not identified. Conceivably, the exact deleterious
mutation could have been mutated to something else, that would have drawn the
genome to a new part of the fitness landscape and present the appearance of
conditional recovery. Burch and Chao however, were not specifically studying
compensatory adaptations, but examining evolutionary step size.

Moore et al. (2000), conducted a study of compensatory adaptation,
revealing that they were both rapid and pervasive in E. Coli, even for deleterious
mutations with particularly large effects. Moore's experiment was very similar to
Burch and Chao's, except that the deleterious mutations under study were
actually identified with southern blots in both the ancestor organism and the

derived population. Identifying the deleterious mutations allowed the researchers

16

FHness

 

 

s
7

Genetic Distance

Figure 1.5: A typical fitness landscape of antibiotic resistance (including those
seen by Schrag et al 199 7). The wild type (cr) and the compensatory strain (Cr)
are sensitive to the antibiotic, indicated by the red dots. Two genotypes exist that
are resistant to the antibiotic (CR and CR). When the compensatory mutation
(Cr) the bacteria is almost as fit as if there were no antibiotic present. It is
important to note that the environment has a significant impact on this fitness
landscape. The deleterious mutations (Cr and cR) are only deleterious when no
antibiotic is present (green dots). When antibiotic is present (red dots) the
landscape contains a hill to climb.

to confirm that compensatory adaptation was actually being observed. Moore et
al. found that most of the lines studied acquired compensatory mutations to all of
the effects of the deleterious mutations in less than 200 generations of evolution.
This compensation included not just single mutants, but double mutations with

both multiplicative and epistatic effects, demonstrating an amazing ability for

17

rapid compensatory adaptations. It is not clear if Moore et al.'s compensatory
adaptations were sign-epistatic, as the “compensatory” mutations may have been
unconditionally beneficial.

A similar study by Maisnier-Patin et al. 2002, this time looking at antibiotic
resistance in Salmonell typhimurium, confirmed the rapid and pervasive nature of
compensatory adaptations. Maisnier-Patin showed that when antibiotic sensitive
strains of S. typhimurium passed through a larger bottleneck, the rate of

compensatory adaptation increased dramatically. With two sizes of population

bottlenecks (103 and 106), only 2 out of 10 lines in the small bottleneck found a
compensatory adaptation in the population after 200 generations of evolution,
whereas 9 out of 10 of the populations in the large bottleneck found a
compensatory adaptation. It is important to note though that the proclivity for
compensatory adaptation in all of these experiments was biased by the fact that
the re-evolution phase of the experiment started with fixed deleterious mutations.
While none of the mutations underwent a reversion to the ancestral state, it is still
impossible to say that the compensatory mutations would have emerged without
first fixing in the population. Even if deleterious mutations lead to compensatory
stepping stones without fixation, the two mutations would reach fixation together
and both appear beneficial, since current technology allows us to observe only
the final result of evolution. However the empirical works here show a higher
tendency for compensatory adaptation then previously thought, and provides
grounds to reexamine the analytical basis for this belief, which shall be done in

the next subsection.

18

1.6.2 Analytical ExaminatiOn of Compensatory Adaptations and
their Fixation Regimes

Despite the aforementioned empirical examples of compensatory
adaptation, many biologists still believe they are important only when populations
are small enough to first allow deleterious mutations to overcome selection and
fix. Sequential fixation of such mutations is thought to be fairly common in small
populations, but more difficult in large ones (Gillespie 1984) as selection creates
a strong pressure to remove deleterious mutations before they can fix. Gillespie
(1984) argued that the rate of fixation of individually deleterious but jointly
beneficial pairs should decrease with increasing population size. However, if a
clade with a deleterious mutation acquires a compensatory adaptation before it is
driven to extinction, the sign-epistatic pair can reach fixation simultaneously
(lwasa et al. 2004, Weinrich and Chao 2005, and Carter and Wagner 2002).

lwasa et al. (2004), analytically examined compensatory adaptation, and
demonstrated that in sufficiently large finite populations, deleterious mutations
need not fix before a compensatory adaptation could be discovered; deleterious
mutants need only enough exploration to find a compensatory adaptation. lwasa
examined a network of three sequential mutations resulting in three different
types of cells: a, b and c. Cell type a has a fitness of one, cell type b has a
fitness less than one, and cell type c has a fitness greater than one. It requires
two mutations to move from cell type a to cell type c, and cell type b requires a
neutral or deleterious mutation (Figure 1.6). They mathematically show that
fixation of cell type b is not necessary to cross the fitness valley, even when type

b mutants are deleterious. This is just one example of an analytical study about

19

 

I

   
 

‘
«.

 

 

 

uortlsodwog uortojndod

y

 

Time
Figure 1.6: An example of lwasa et al. ’s “Stochastic Tunneling”, White represents
the portion of the population with cell type a, red represents the deleterious cell
type b, and blue represents the beneficial cell type c. Time is increasing along
the X-axis, and the portion of the population at each cell type is represented on
the Y-axis. As long as the mutation rate is sufficient, deleterious clades can
emerge and mutate to cell type 0, without fixing in the population. Cell type b
may emerge several times before it acquires the deleterious mutation.
the interaction between deleterious mutations and the compensatory adaptations
that may bring them to fixation. Other examples begin to build a clearer picture
of how this process works in both large and small populations.

Carter and Wagner (2002), also analyzed different fixation regimes of
compensated deleterious mutants; they modeled the fixation of cis-enhancer
elements as individually deleterious but jointly beneficial mutations. This model
was inspired by phylogenic data pointing to such fixations occurring as pairs of
mutations. Carter and Wagner found a monotonic relationship between
population size and rate of fixation of such mutations, but with a trough in certain
intermediate sizes, indicating a range of populations sizes where neither regime,

sequential nor simultaneous, played a predominant role in bringing individually

deleterious pairs of mutations to fixation. Carter and Wagner also found that

20

simultaneous fixation of deleterious/compensatory pairs occurred more rapidly at
higher mutation rates. Weinreich and Chao (2005) confirmed the results of
Carter and Wagner (2002), by deriving equations to predict the critical population
size when simultaneous fixation became more prevalent. Weinreich and Chao
ultimately concluded that rapid compensation of deleterious mutations could lead
to "evolutionary escape” from a sub-optimal fitness peak, and that such
occurrences were likely in large populations.

These analytical studies lend credence to the hypothesis that escape from
fitness valleys via sign-epistatic stepping stones is possible. However there is
little empirical evidence to quantify the role that individually deleterious, but jointly
beneficial mutations can play in nature. While an evolutionary path to antibiotic
resistance in E. coli can be reconstructed in the lab, it is impossible to determine
what path was actually followed by evolution. While sign-epistatic interactions in
compensatory adaptation can be isolated, there is insufficient evidence to
determine if they occur frequently enough to constitute a major evolutionary
trend. The search for such empirical data has led back to GA inspired
techniques that explore purely biological concepts in a computer. These in silico
approaches are known as “Artificial Life” (Adami 1998), and have already
revealed interesting examples of sign-epistatic compensatory adaptation acting

as stepping stones to high fitness.

1.7 Artificial Life Experiments
Lenski at al. (2003) found examples of deleterious stepping stones, which

21

aided the evolution of complex features from simple ones, using Avida4, a
platform for digital evolution. The Authors examined the evolution of the most
complex task in the standard Avida environment, “bit-wise equals” (EQU). This
work established that EQU could not evolve if it was not preceded by building
blocks in the form of simpler tasks. Of 23 replicate populations that evolved
EQU, 5 had a deleterious mutation immediately prior to its emergence. Those 5
mutations were reverted to their pre-deleterious state in the genotypes that first
performed EQU. These reversions eliminated the EQU operation in 3 of the 5
genotypes, indicating that those deleterious mutations were necessary for EQU
and raising the possibility that deleterious mutations were sometimes needed as
stepping stones to EQU. Lenski et al.'s analysis only examined the mutations
immediately prior to EQU; similar effects may have existed further back in the
lineage that evolved EQU.

The effect of sign-epistatic compensatory mutations was confirmed by
Cowperthwaite et al. (2006). They explored the effect of individual deleterious
mutations that had reached fixation in an asexual population of simulated RNA
sequences. Cowperthwaite et al. used a technique similar to the one used by
Lenski et al. (2003); reverting the site of a deleterious mutation to its previous
state, but expanded the analysis to every instance of the mutation in the lineage
of the most recent common ancestor. The change in fitness on the new genetic
background reveals whether or not the initially deleterious mutation now has a

different fitness effect. Cowperthwaite et al. (2006) found that a significant

 

4 Avida will be fully explained in chapter 2, the limited description here is given to explain the
significance of the work in Lenski et al. 2003.

22

portion of deleterious mutations that had fixed in the lineage to the most recent
common ancestor were able to acquire a beneficial fitness effect due to changes
in the genetic background. However, Cowperthwaite and colleagues were able
to show only a possible mechanism for fixation of deleterious mutations; they did
not identify a trend that would indicate such mutations had a significant impact on
the outcome of evolution. Also, they ignored mutations that did not fix, while
acknowledging that many deleterious mutations reversed their fitness effects
before reaching fixation, confirming the previous analytical finding that
deleterious pairs can fix when they are jointly beneficial (Weinrich and Chao

2005, lwasa et al. 2004, Carter and Wagner 2002 and Gillespe 1984).

1.8 Discussion

Taken as a whole there are many pieces of a puzzle that seems to point
towards an important role for deleterious mutations. Epistasis creates isolated
high fitness peaks accessible only via sign-epistatic compensatory adaptations.
These sign-epistatic pairs, if individually deleterious, but jointly beneficial, have
two theoretical fixation regimes, sequentially or simultaneously. Sequential
fixation of mutations is more likely to be useful under Wright's SBT, which relies
on drift in individual demes to move populations to new peaks. Simultaneous
fixation has been modeled mathematically and suggested as a possibility in large
populations, where sequential fixation is highly unlikely. Both fixation regimes
require compensatory adaptation, which recent research suggests is more
prevalent in nature than previously thought. In this light, the question seems to

be less a matter of wether sign-epistatic pairs of mutations can play a role in

23

evolution, but rather exploring their relevance in evolving systems. Do these
mutations indicate the presence of an isolated fitness peak? Does evolution take
these paths only when no beneficial or neutral path exists, or do both
mechanisms exist side by side? If so, does historical contingency play a role? In
light of these deleterious pathways and the usefulness of GA island models,
should we go back and reexamine the efficacy of Wright's Shifting Balance
Theory? The best way to begin addressing these‘ question is further in silico
experimental evolution, and the results may give modern day biologists reason to

reexamine their views of deleterious mutations.

24

Chapter 2: Tools

This chapter describes tools leveraged in later chapters to examine the
long-term impact of individually deleterious but jointly beneficial mutations.
These tools are based in the Avida digital evolution platform (Adami 1998, Ofria
and Wilke 2004) and are freely available. Sign-epistatic interactions, specifically
mutations that are individually deleterious but jointly beneficial, form the strongest
hypothesis for a mechanism by which deleterious mutations become stepping
stones. However, the evidence so far shows that sign-epistatic interactions are

part of evolutionary history, but not that they have any impact over the long-term.

Section 2.1, gives a brief description of the Avida digital evolution platform,
looking closely at the life cycle of the organisms that inhabit an Avida population.
The section ends with a discussion of how the success of digital organisms are
measured, and a brief discussion of how epistasis affects them. Section 2.2
details the two main tools in Avida, used to construct experiments examining the
impact of deleterious mutations. Finally, section 2.3 gives a broad overview of
the experiments and analysis contained in the experimental chapters of this

dissertation.

2. 1 Avida

Avida is a platform for digital evolution research, in which self-replicating
computer programs (herein refered to as digital organisms) compete for energy
and evolve to perform tasks in their environment (Ofria and Wilke 2004). Rather

then trying to model life and evolution as they occur in nature, Avida uses

25

computational concepts to instantiate the evolutionary process in a computer
(Pennock 2007). Avida combines the three essential ingredients for evolution: a
heritable medium, a source of variation, and selective pressure for adaptation to
the environment (Dennet 1995, Pennock 2007). Evolution in Avida is studied
purely as a process by instantiating Dennet's three components in a computer.
Avida gives us an entirely new ecosystem based in a computational realm, totally
separate from the Earth's biosphere. As such, Avida is essential an instance of
open-ended evolution that can be paused, modified and studied in ways organic
model systems could never be. This evolutionary system contained in the
computer, serves as a basis for comparison to evolution observed in the natural

world.

Avida has already been used to address questions about natural
evolution, without the overhead associated with natural organisms (Lenski et al
2003). Since Avida populations evolve in a computer, every step evolution takes
can be observed, and many aspects of the evolutionary process can be
manipulated, from the types of resources available in the environment down to
disallowing individual mutation effects. In short, Avida allows for experimental
evolution that lasts tens of thousands of generations, in a relatively short amount
of time, with almost total transparency and a high degree of replication.

2.1.1 Basic Layout of the Avida World
Almost every parameter in Avida may be set by the experimenter; the
number of possible configurations is staggering, and too extensive to discuss

exhaustively here. This description is limited to the default configuration and the

26

h-alloc h-alloc

dec ldec
set-flow , ,W set—flow
nop-A Vlrtual CPU . ‘
mov-head
nop-C -
push £3236 AX:01011...
dec . . W’ ,
lnstructlons

nop-C BX:11010...
I0 gemme cx:11110...

Output

11011".

 

Figure 2.1: The Avida world is a toroidal grid, with each cell containing the virtual
hardware organisms need to run their genome.

appropriate deviations for =the experiments in question. In Avida, organisms are
simple computer programs with genomes composed of computer code. Each
digital organism inhabits a cell in a virtual world. Individual organisms execute
their genomes on the virtual hardware found in each cell (Figure 2.1). The cells
are arranged into lattices, which can have a variety of different geometries, but
by default are arranged in a torus (doughnut shaped). Organisms execute their

genomes one line of code at a time, and each line of code requires a CPU cycle.

27

The total number of CPU cycles available to a population is capped, making it a
limited resource. Organisms are responsible for replicating their own genome to
create an offspring. The ability to replicate more quickly means a particular
genotype will be more successful than others, creating a selective pressure to
either acquire more CPU cycles, or to use available CPU cycles more efficiently.
2.1.2 Self-Replication

A key feature of Avida, like the Tierra system that inspired it (Ray 1992), is
that individual organisms must replicate their own genomes in order to create a
new offspring. During an organism's life cycle, it must allocate space for an
offspring genome, iteratively copy each instruction, and partition the offspring
genome into a new organism. The offspring is placed into the population, usually
in a cell adjacent to the parent, and the process of replication begins again in
both parent and offspring. This process consumes almost all of an organism's

energy, but is obviously a necessary component of evolution.

Avida experiments start with an ancestor organism that can do nothing but
replicate itself. The core of the code for self replication in the ancestor is
colloquially referred to as the copy-loop. Digital organisms experience selective
pressure to self-replicate faster in order to out—compete other organisms in the

population.

There are two ways organisms in Avida can increase their replication rate.
One is to replicate more efficiently by reducing the number of CPU cycles
needed to complete the copy-loop. The other, is to acquire more CPU cycles by

performing tasks in the environment that “metabolize” inputs (binary numbers)

28

into additional CPU cycles. In the default environment there are 9 tasks digital
organisms can perform. These tasks are simple bitwise logic operations; eight
two input logic operations and the only one input logical task are rewarded (Table
2.1). The number of CPU cycles a genome takes to produce a single offspring,
its gestation time, is almost always deterministic. In other words, we can predict
how quickly any given organism will reproduce, based on the organism's
gestation time, and bonuses from any logical tasks performed. This prediction of
replication rate serves as an estimation for fitness, and will be more throughly
discussed in subsections 2.1.4 and 2.1.5.
2.1.3 Variation

So far we have examined how Avida satisfies two of the three
requirements for an evolving system: inheritability and selection. Digital
organisms each have a genome containing all of the instructions needed to
acquire resources and make a copy of itself. Offspring are born into the
population with a copy of their parent's genome, making the genome an
inheritable substrate (inheritability). Populations of digital organisms are under
pressure to replicate as quickly as they can, so as to pass on their own genetic
material before they are overwritten by a neighboring organism (selection). Over
the long-term, organisms that replicate more quickly out-compete organisms that
replicate more slowly. However, we have not yet discussed one of Dennet's

three ingredients for evolution: variation.

Mutations are the main source of variation in Avida. Organisms may be

mutated at a specified rate during an experiment, either when they divide, or

29

 

Function Name Logic Operation ‘ Merit Bonus

 

 

 

 

 

 

 

 

 

NOT ~A; ~B x2

FNAND ‘ ~(Aand B) a ' i if * x2 " _
AND A and B x4

OR__N (A or ~B); (~A or B) x4

' OR A or B x8

KEEN F F i (A and ~i3); (:vA—aTnd l3) ” if 2 x8 F

* NOR T— ~A and ~B x16

IXOR (A and ~B) or (~A and B) x16

.EQU (A and B) or (~A and ~B) , x32

Table 2.1: Rewards for performing nine one- and two input logic functions in the
standard logic-9 environment. The symbol '~' denotes negation. Digital
organisms have only the NAND operation with which to evolve the nine logic
functions, along with the appropriate input and output. Organisms are rewarded
for completing a logical task with an increase in merit, a unitless number
representing how fast the organism may run. Merit bonuses for each function

are the current merit times 2" were n is the number of logical gates required to
complete the function. This is the same environment used in mostAvida
experiments including Lenski et al. (2003)

during their execution. The three primary types of mutations available are
insertions, deletions and point mutations. This dissertation deals exclusively with
single point mutations. Limiting variation to a single point mutation makes it a
simple matter to classify the fitness effect of individual mutations, and prevents
fitness valleys from being bypassed by rare double mutations. Point mutations
occur with a given probability when the organism divides. A single instruction in

the offpsing genome is changed to a different instruction from the set of all

instructions availablel.

Mutations in a offspring are classified relative to the fitness of the parent.

 

1 See the online Avida documentation for a summary of the Avida instruction set.
http://alice.cme.msu.edu/development/documentation/inst_set.html

3O

There are four different classes of fitness effects, a mutation may increase fitness

(beneficial mutation), it may lower fitness (deleterious mutation), it may leave

fitness unchanged (neutral mutationz), or it may leave the offspring unable to
replicate itself (lethal mutation). Offspring with beneficial mutations are more
likely to be successful, because they can produce progeny more quickly. By the
same logic, offspring with deleterious mutations are less likely to be successful.
The immediate fitness effect of a mutation is a strong predictor of its fate in the

population, but as discussed in chapter 1, it is not an irrevocable verdict.

Occasionally, one of the normal mutations in Avida will modify the copy-
loop in such a way that the offspring is no longer a perfect self-replicator. These
are called unstable genomes and lead to errors in replication, including insertions
and deletions. Unstable genomes are not immediately fatal, but can confound
both any effort to disable certain classes of mutation and the automatic
classification of mutation effects (these experiments will be discussed in chapters
3 and 4). To control for unstable genomes, any organism that carries one is
sterilized in these experiments, by methods discussed in chapter 3.

2.1.4 Fitness and the Life Cycle of Digital Organisms

Avida experiments are divided into discrete units of time called “updates”.
During each update, the population executes CPU cycles equal to 30 instructions
per living organism, divided proportionally among the organisms based on a unit-
less number called merit. Merit (M) is an expression of how fast an organism

should be allowed to execute its genome. Thus, if organism A has merit of 5 and

 

2 In chapter 3, nearly neutral mutations (Ohta 1992) will also be taken into account. These are
mutations with extremely small effects on fitness that may be considered neutral because they
do not substantially alter the organism's chances for survival.

31

organism B has merit of 10, then B will get twice as many CPU cycles every
update. However, just because an organism can execute twice as many
instructions, does not mean that the organism will replicate at twice the rate.
Depending on how evolution has unfolded, organisms in a single population may
have different gestation times. So, if A's gestation time is half of B's, A would be

able to replicate at the same rate as B, even though it executes only half as
many instructions in an update. Normalizing merit by gestation time (Gt) gives a

unit-less number representing the replication rate of an organism, which is used
as an estimation of fitness (f) in Avida (equation 1).
_ M »

f-a' (1)

1
2.1.5 Measuring the Success of Digital Organisms

Avida's measure of fitness is still only an estimate of an organism's long-
term performance. Fitness describes how frequently an organism will produce
an offspring under optimal conditions, but it does not account for how successful
the progeny will be. An organism with a beneficial mutation may be overwritten
before it can pass that mutation on, or an organism with a deleterious mutation
may last long enough to be compensated for. The number Avida calls “fitness” is
not a perfectly accurate prediction on the fate of a genotype, but rather a highly
educated guess based on the information available. As in real life, the impact of

chance events can play a deciding role in evolution (Blount et al. 2008).

Past studies with Avida have determined which organism was most
successful by examining the most abundant genotype present in the population

at the end of an experiment, the final dominant genotype. Regardless of what

32

else occurred on the lineage leading to the final dominant, that genotype
occupied the majority of the population at the end of an experiment. Throughout
this dissertation, treatments of Avida populations will be compared by examining
median final dominant fitness. When median final dominant fitness is statistically
significantly higher (at the P=0.05 level) in one treatment than it is in others, that

treatment will be said to have adapted faster.

The individual steps that lead to the final dominant genotype make up the
line of descent. As mentioned in chapter 1, some of these individual steps on the
line of descent are deleterious mutations (Lenski et al 2003). The experiments
described in this dissertation are focused on determining if these maladaptive
steps played a critical role in the success of the lineage leading to the final
dominant, or if they were merely obstacles to be overcome.

2.1.6 Epistasis and Experimental Evolution in Avida

Before examining the relevance of deleterious mutations directly, it is
important to review some prior works that describe the evolutionary pressures in
Avida. Epistatic interactions in Avida were examined in Lenski et al. (1999) and
Lenski et al. (2003). In particular, Lenski et al. (1999) showed that organisms
evolving in environments that rewarded the 9 standard logical tasks, evolved
significantly more epistatic interactions than environments with no tasks. In the
environment with no tasks, the only selective pressure on digital organisms is to
reduce gestation time and replicate as quickly as possible. The presence of high
levels of epistasis in more complex environments strongly indicates that digital

organisms exist on a highly rugged fitness landscape, and that the main source

33

of this ruggedness is the trade-off between optimizing gestation time and
performing tasks in the environment. It is still difficult to accurately gauge the
ruggedness of the fitness landscape (as was discussed in chapter 1). The
presence of high levels of epistasis does show that, like organisms found in
nature, Avida's digital organisms are highly sensitive to mutations, particularly in

more complex environments.

Unlike natural organisms, it is possible to trace the precise line of descent
in Avida, and reveal every evolutionary step that leads to the final dominant.
Furthermore, it is easy to examine alternate outcomes of evolution by
constructing genomes with combinations of mutations that did not occur in the
line of descent. In Lenski et al. (1999), millions of alternate genotypes were
constructed to measure the amount of epistasis in 87 different final dominants.
ln Lenski et al. (2003), only a handful of alternate genomes were constructed to
examine if particular deleterious mutations contributed to the evolution of highly

rewarded tasks.

Examining alternate combinations of mutations in natural organisms is
expensive, requiring a huge allotment of resources, and are very difficult to
repeat (Wlenrich et al. 2006, De Pristo et al. 2007, Poelwijik et al 2007). Avida
offers a unique opportunity for scientists studying evolution: an environment
where evolution occurs, but where every evolutionary step is recorded and can
be analyzed. The remainder of this chapter will describe how Avida was used to
test null hypotheses about the evolutionary processes acting on deleterious

mutations. The experiments and analyses performed yield highly repeatable,

34

statistically powerful results, and were not possible in experimental systems

based on living organisms.

2.2 Leveraging Avida in Experiments
2.2.1 Leveraging the Test CPU

One powerful tool for experimental evolution Avida provides is the Test
CPU. The Test CPU is a set of virtual hardware, identical to the hardware found
in the “real” Avida world, and is used to predict how a given organism will behave
during an experiment. Any organism's genome may be run on a Test CPU, to
predict not only merit and gestation time, but fitness and viability as well.
Previous works have used the Test CPU primarily as a post-experiment analysis
tool. Lenski et al. (2003) used the Test CPU to determine which mutations on the
line of descent were necessary for EQU. Lenski et al. (1999) used the Test CPU
to examine the effect of single and multiple mutations on fitness and used those
data to measure epistasis. While post-experiment analysis is useful, using the
Test CPU in populations that are still evolving allows for the construction of
experiments not possible in the natural world. While the Test CPU can be used
to test new hypotheses about evolution, running organisms through it during an
experiment significantly slows Avida. Due to the slowdown, the Test CPU is only

used during an experiment if the probative value outweighs the added time cost.

Running each newly created organism through the test CPU, yields a
prediction of what that organism's gestation time, merit, and fitness (via equ. 1)
will be before it actually enters the population. Using these estimations the

fitness effects of any mutations in the offspring can be classified by comparing it

35

to the observed fitness of the organism's immediate progenitor. Chapter 3 will
describe experiments that used the Test CPU to classify the effects of mutations
as they emerge, and to then disable particular types of mutations. The long term
impact of deleterious mutation can be studied by disabling deleterious mutations
and measuring the final dominant fitness of populations, relative to an unmodified
control. No organic experimental system exists that can address the clear-cut
question “How does evolution proceed when we turn deleterious mutations off?”,
and this dissertation describes experiments based on this question to shed
substantial light on the role of deleterious mutations as stepping stones.
2.2.2 Examining the Line of Descent

Another tool Avida possesses, is the ability to examine every mutational
step on the line of descent to the final dominant genotype. This type of analysis
has been performed in several computational systems, including those discussed
in chapter 1. Lenski et al. (2003) and Cowpethwatie et al. (2006) in particular
used the line of descent to identify deleterious mutations that recovered via sign-
epistasis. Chapter 4 will take previous work one step further, not only identifying
those deleterious mutations that recovered via a sign-epistatic interaction, but
also looking at all other deleterious mutants on the line of descent and
establishing their fates. Obviously, those few deleterious mutations that recover
via sign-epistasis are of the greatest interest. Other deleterious mutations may
be converted to neutral, or may hitchhike with a beneficial mutation that is not
epistatic. Most deleterious mutations, however, will simply remain deleterious

and be eliminated. Even those that do not undergo a sign-epistatic recovery may

36

have other interesting epistatic interactions that impact long-term adaptation.
2.2.3 Testing Individual Mutations

Simply identifying a deleterious mutation that underwent a sign-epistatic
recovery is not sufficient to say that it had a significant impact on long-term
evolution, it's success may have merely been a chance event. A method is
needed to test an individual deleterious mutation, measuring its long-term impact
on adaptation. Once genomes with deleterious mutations that underwent a sign-
epistatic conversion were identified, they were tested to see if the deleterious
mutation actually aided adaptive evolution. Replicate populations were reseeded
with deleterious mutants, and compared to controls seeded with the deleterious
mutant's immediate progenitor. Both treatments were run with deleterious
mutations “shut off”, so that no fitness valleys could be taken by the progenitor's
treatment, and no other fitness valley could be taken by the deleterious mutant's
treatment. If the deleterious mutation was actually a stepping stone, it was
expected that median final dominant fitness would be significantly higher in
replicates seeded with the deleterious mutation than without. If the deleterious
mutation originally observed was just a fortuitous accident, then the treatment
seeded without the deleterious mutation should have a higher fitness. Mutations
on the line of descent then tracked, and sorted into different categories based on
their recovery. Deleterious mutations in different categories were then tested to

see what impact impact they had, if any, on long-term evolution.

2.3 Summary
By utilizing Avida's Test CPU and line of descent, it is possible to address

37

not only if, but how, deleterious mutations contribute to adaptation. Comparing
runs with deleterious mutations shut off measured their net effect over
evolutionary timescales. Analyzing lines of descent will identify candidate
genomes containing deleterious mutations that were likely used as stepping
stones. Rerunning these genomes in treatments, paired with genomes lacking
the deleterious mutation, helped to distinguish those deleterious mutations that
consistently lead to novel adaptations, from those that were merely chance
events. These experiments were performed in silico, because they are simply
not possible in natural organisms. None-the-less, the results shed light on how

deleterious mutations impact the evolution of natural organisms.

38

Chapter 3: Reversion and Replacement of Mutation
Classes

This chapter describes experiments on populations in which mutations
with specific classes of fitness effects were disabled, in order to examine the
long-term impact of those mutations on evolution. These experiments test null-
hypotheses about different types of mutations by observing how evolving
populations, with those mutations removed, adapted differently relative to an
unmodified control. For example, the null hypothesis that deleterious mutations
do not aid adaptation in any way, can be tested by disabling them. The null
hypothesis could hold only when disabling deleterious mutations resulted in no
significant change in fitness, or if fitness in the experimental treatment was higher
than the control treatment. Alternatively the null-hypothesis should be rejected if
and only if fitness of the experimental treatment was significantly lower than the
control treatment. A lower fitness in the treatment disabling deleterious mutations
would strongly indicate that deleterious mutations do contribute to adaptive

evolution.

The same experimental design was then applied to neutral mutations,
which are widely thought to be a key component of adaptive evolution (Ohta
1992). The equivalent null-hypothesis can be tested for neutral mutations, by
disabling them to determine if they are unimportant. If fitness is significantly
reduced when these mutations are disabled, then the null-hypothesis should be
rejected in favor of the prior result: that neutral mutations play an important role

in adaptation. Treatments disabling neutral mutations were added primarily to

39

validate the method of disabling mutations. Since there is already evidence to
suggest that neutral mutations play a major role in adaptive evolution (Ohta
1992), disabling them should result in a significant reduction in long-term

evolution.

On the surface, it may seem trivial to disable a particular class of
mutations, and it is for many analytical and in silico models (such as Genetic
Algorithms). Digital organisms, however, are so complex that disabling specific
classes of mutations can trigger unanticipated responses. These side effects
were compensated for by using repeated treatments that disable mutations in a
variety of different ways, each of which addressed some of the concerns of the
others. If the preponderance of these experimental treatments rejected the null
hypothesis, then there would be compelling but not conclusive evidence, that the
class of mutations being tested plays a major role in adaptive evolution. The
complexity that arises from experiments disabling mutations in digital organisms
is a natural result of Avida's real, open-ended evolution, and not being simply an
evolutionary model (see discussion in chapter 2). Avida offers a unique platform
for this research, because it allows for the testing of hypotheses on an open-

ended evolving system, and not an analytical or in vitro approximation.

Section 3.1 deals with the methods for disabling different classes of
mutations, with an emphasis on deleterious mutations. In section 3.2 the results
of disabling deleterious mutations are discussed, followed by two more
experiments, one disabling only neutral, the other disabling both neutral and

deleterious mutations. The final section places the results in a larger context,

4O

discussing what these experiments do and do not tell us about the role of

deleterious mutations.

3.1 Methods and Experimental Setup
This section details the methods used to disable deleterious mutations.

While some components of these methods, such as the test CPU and
sterilization of unstable genomes, were already present in Avida, most of these
methods were implemented for this project. In particular, the method of replacing
disallowed mutations with random permitted mutations (subsection 3.1.2),
controlling for the side effects of replacement (subsection 3.1.3), and protecting
nearly neutral mutations during reversion and replacement(3.1.4) were
implemented specifically for this dissertation. Avida was already able to revert
mutations, but reversions alone are limited, as will be discussed in the subsection
3.1.1, and prior to this dissertation, no extensive research had been performed
disabling entire classes of mutational effects.
3.1.1 Reverting Mutations

During all experiments, point mutations probabilistically occurred when an
organism divided. If a mutation occurred the mutant offspring was run through
the Test CPU before entering the population. The test CPU determined the
organism's merit and gestation time, which were used to calculate fitness and
classify the effect of any mutations relative to the parent. When an offspring
carried a disallowed mutation, its genome was reverted to the parent genotype

before being placed in the population (Figure 3.1).

Reversions were a straightforward way to disable a class of mutations

41

 

I]

 

—r4 _.

Figure 3.1:‘ll7uta%n dis—triblmm afier rE/‘emfifi deleterious mutations. Each bar
represents the distribution of fitness effects for all possible single point mutations
in a hypothetical genome. The top bar shows the relative number of beneficial
(blue), neutral (green), deleterious (red), and lethal (black) mutations under
normal conditions. The lower bar shows the relative distribution of single point
mutations when deleterious mutations are reverted. Reverting the disabled class
lowers the effective mutation rate, because it eliminates an entire class of
mutations without replacement.
without altering the rate at which other classes of mutations entered the
population; however, reversions also reduced the effective mutation rate. In
other words, reverting certain mutations reduced the total amount of new genetic
variation that entered the population. If the disabled class of mutations had little
or no significance, than their contribution to genetic variance should have been
negligible; for example, if deleterious mutations were truly unimportant then
reverting them should have had no overall effect. However, lowering the
mutation rate could have resulted in slower adaptation, leading to lower fitness
and resulting in speciously rejecting the null-hypothesis. The only way to disable
a class of mutations while maintaining the same amount of new genetic variation
was to replace disallowed mutations with others from permitted classes.
3.1.2 Replacing Mutations

Replacement was another method of disabling mutations in Avida. (figure
3.2). As with reversions, each time an organism divided, its offspring was

examined in the test CPU and the fitness effect of any mutations was classified

relative to the parent. If the new mutation had a disallowed fitness effect, then

42

 

  
   
       
 

Organism
copies
genome

 

  

offspring in
population

No

 

 

 

 

 

 

Sterilize

Mutate F—> Offspring

\Allowed’P/ / Stable?
»
\ \ Not

\ I

~. \ Revert
\ Offspring
Genome

 

 

 

 

 

 

Figure 3. 2: A flowchart of the replacemenfaTgorithm. Every time an organism is
ready to divide, there is a possibility of mutation. If the mutation is of a
disallowed class, then the offspring genome is reverted and mutated again until
an acceptable mutant is found. If the offspring genome has an unstable genome
it is sterilized before being placed in the population. The blue dotted portions of
the chart denote steps that are added by replacement, the black portions denote
steps that normally occur in Avida. Note that unstable genomes are sterilized in
control runs as well.

the genome was reverted to its parent genome and the offspring was mutated
again. The new mutation was again tested in the test CPU; this cycle repeated
until an acceptable mutation was found. Every new organism could undergo one
hundred test, revert, mutate cycles in an attempt to find a mutation outside the
disabled class; in the rare case that no acceptable mutation was found, then the
offspring was sterilized. Thus, replacing a class of mutations disabled those
mutants, without altering the total number of new mutants that entered the

population (replacement kept the the effective mutation rate constant, see figure

3.3).

43

 

Figure 3. 3: Mutation distribution after replacing deleterious mutations. Each bar
represents the distribution of fitness effects for all possible single point mutations
in a hypothetical genome. The top bar shows the relative number of beneficial
(blue), neutral (green), deleterious (red), and lethal (black) mutations under
normal conditions. The lower bar shows the relative distribution of single point
mutations when deleterious mutations are replaced. We see that replacement of
the disabled class significantly increases the number of other mutations,
including lethal mutations, but does not lower the effective mutation rate.

3.1.3 Side Effects of Replacement
The largest draw-back to replacement is that other types of mutations

became over-represented(Figure 3.3). Since different types of mutations had
different fitness effects, these effects were also be over-represented as different
classes of mutations were called on to replace a disallowed class. In particular,
the load of lethal mutations was drastically increased whenever neutral or
deleterious mutations were replaced. An increased lethal load might have
slowed the rate of adaptation and obfuscated any test of the disabled class in
any simple replacement run. The only reliable way to replace mutations, without
increasing lethal load, was to also replace lethal mutations. When deleterious

and lethal mutations were replaced, we were left with a population of hill-
climbers‘. The population received only neutral or beneficial mutations, and no
maladaptive steps of any kind could have been taken.

Replacement of both deleterious and lethal mutations also had a major

side effect: it reduced the the number of alternate mutations to the two scarcest

1 “Hill-climbing" is a term used to describe a mathematical function that quickly finds the local
optimum by always ascending the closest peak on a landscape.

44

types, beneficial and neutral. Restricting alternate mutations to the scarcest
types made it less likely that the replacement algorithm would find an alternate
mutant within 100 iterations, and made it more likely that organisms were
sterilized because a replacement could not be found. When deleterious and
lethal mutations were replaced, 1,092,337 replacements were observed at 200
uniformly spaced updates across 50 replicate populations. Of those
replacements, only 281 (<0.03%) failed to replace the deleterious mutation and
were sterilized. Regardlessly, limiting evolution in this way, stacked the deck
heavily against any hypothesis supporting deleterious mutations, making any
result that rejects the null hypothesis that much more powerful.
3.1.4 Nearly Neutral Mutations

So far, all the experimental designs have relied on absolute definitions of
fitness effects. A mutation was either beneficial, neutral, deleterious or lethal,
and that was determined by being strictly greater than, less than, equal to the
parent's fitness or zero, respectively. The reality of the situation is less clear-cut.
Nearly neutral mutations, mutations that are slightly deleterious or slightly
beneficial, are thought to contribute greatly to evolution (Ohta 1992). Reverting
or replacing a deleterious mutation might also eliminate potentially useful

mutations of very slight effect, along with deleterious mutations of large effect.

Additional reversion and replacement treatments that treated all mutations
within 1% of neutral as effectively neutral were added (Figure 3.4). In these
treatments, only mutations that lowered fitness by more then 1% were disabled.

When reverting or replacing neutral mutations, treatments disabling both strictly

45

 

 

Fure 3.4: Mutation distribution after replacing deleterious mutations but
protecting nearly neutral mutations. As in figure 3. 3, deleterious mutations were
replaced on a hypothetical genome, but in this case, mutations with a fitness
effect less than 1% (represented by light pink) were considered effectively
neutral and not replaced.
neutral and nearly neutral (altered fitness less then 1%), were performed.
3.1.5 Experimental Setup

All experiments were performed in Avida version 2.6, which is freely

available online2. Replicate populations were run for 250,000 updates
(approximately 45,000 generations) starting from a single ancestral organism and
capped at a population size of 10,000. All populations had organisms with
unstable genomes sterilized, to ensure that only single point mutations entered
the population. Disallowing unstable genomes also made it possible to classify
mutational effects simply by comparing a mutated organism's fitness to its parent.
If unstable genomes had been allowed, multiple mutations could have occurred
each of which would have complicated the analysis. All organisms had a fixed
length of 50 instructions, with single point mutations introduced at a probability of
25% at each divide, for a per-site mutation rate of 0.005. All other settings were

left at the default Avida configuration.

3.2 Results of Reverting and Replacing Mutations
In each experimental treatment a class of mutations is disabled either by a

2 http://avida.devosoft.org/

46

 

Experiment h i i T Abbreviation—

 

 

 

 

 

 

 

 

 

 

 

Control 7 _ C
Replace Deleterious RpD
Replace Deletefiofind Lethal __- H Tm fimRfipDLflhi
Regve—rthTeleterious A — RvD i T
ReTeTtEeIetenoE protect nearly neutraF i T T if, WRngn ~
Replace Deleterious, protect nearly neutral RpD-nn
:Replace Neutral -2 I T T T T- _TRpI\T ______
Replace Neutral and Lethal T — i V TERM. — _.
Revert Neutral? -2 i ii v T ”T 7 W" it RvN
Revert Neutral, include nearly neutral RvN-nn
~R—eblaze—N—eEral, inddde—negly neutral _ _. _ — -— l—TRpN-nn- 7*“
Replace Neutral ahd Deleterious i T I _ VT T -RpNTD Th T
Replace Neutralk DgeTeTlcfis and Lethal _ i i T i L T ——_RFNEI _‘ w
Revert Neutral and Deleterious RvND
Revert Neutral and Delgerious, include nearly neutral 7 T ____. iii/W035 — T
Replace NeTJTraTand—Dfltelzgridusi iii—cTu—CIZrTea—rly—ngufiaT “T — RpND-nn
Replace Lethal _ i T A T T T T WRpL. TH“ E
Revert Lethal IRvL

 

Table 3. 1: Brief descriptions of each experimental treatment and their
abbreviation, these will be used throughout this dissertation. Abbreviations in
bold are used most frequently throughout this dissertation.

 

simple reversion or a replacement with a new mutation. As stated in section 3.1,
disabling mutations either via reversion or replacement tests the null hypothesis
that the disabled class does not contribute significantly to long-term evolution.
The null hypothesis will be rejected if treatments disabling certain mutations have

significantly lower final dominant fitness than control populations.

Deleterious mutations were tested first, to determine if they had any long-

term impact on evolving populations. Next, neutral mutations were tested,

47

primarily to provide context for the test of deleterious mutations. Neutral
mutations were already thought to be important, and were expected to have a
significant impact on long-term evolution, it should therefore be easy to reject the

null-hypothesis.

In experiments disabling either neutral or deleterious mutations, the
remaining classes of mutations will have more mutants in the population than
they would normally. Thus when neutral mutations were disallowed, deleterious
mutations occurred more frequently, and vice versa. Even reversion treatments
expressed other types of mutations more frequently simply because they did not
have as many dead or disabled organisms. In other words, although some types
of mutations were no longer present in the population, the total number of
genotypes did not decrease significantly. A third experiment was performed that
disabled both neutral and deleterious mutations at the same, to test if
experiments without neutral mutations were able to improve fitness by relying on
increased numbers of deleterious stepping stones. The final experiment in this
chapter reverted and replaced only lethal mutations, to confirm that they have no
significant impact on long-term evolution. All of the different treatments within
these four experiments are contained in Table 3.1.

3.2.1 Reverting and Replacing Deleterious Mutations

There were significant differences among the medians of all treatments

(Figure 3.5, Kurskal—Wallis test P-value<0.001, df=5, chi-sq=23.56), with the

control treatment being significantly different from all treatments without

48

 

 

 

 

10A8- ‘ ..
_!"' ¢
l T T . T
10A7- ' i l f -
10*6- ! i 1
l
8 l
0
5 l
E 10*5l- x -
2
g ‘
10A4- -
l
_l_ l i
i _l_ !
10A3- .1. l -
.1. __
10*2 ‘
Control RpD RpDL RvD RvD-nn RpD-nn
Treatment

Figure 3. 5: Final dominant fitness boxplots under six evolutionary treatments
each containing 50 replicate populations. All fitnesses are normalized by the
fitness of the ancestor. (C) All mutations enter the population normally. (RpD) All
deleterious mutations are replaced with a random beneficial, neutral or lethal
mutation. (RpDL) All deleterious and lethal mutations are replaced with a
random neutral or lethal mutation. (RvD) All deleterious mutations are simply
reverted, as if they never occurred. (RvD-nn) All deleterious mutations with a
fitness effect greater than 1% are reverted. (RpD-nn) All deleterious mutations
with a fitness effect greater than 1% are replaced with a beneficial, neutral or
lethal mutation. In all cases, the control treatment has significantly higher fitness
(see text for statistics) strongly indicating that the loss of deleterious mutations
impeded long-term adaptation.

49

deleterious mutations (all P< 0.05, Mann-Whitney U-test3). Differences among
reversion and replacement treatments were subtle, but ultimately insignificant
(KurskaI-Wallis test P=0.067, df=4, chi-sq=8.81). All hill-climbing treatments had
at least one replicate population that was able to achieve a maximum fitness
equivalent to the control, indicating that paths of neutral and beneficial mutations
leading to high-fitness peaks did exist. Adaptation was significantly slowed
across all treatments lacking deleterious mutations, regardless of outlying
populations that attained high fitness. In light of this decrease in the rate of
adaptation, the null-hypothesis can be rejected, indicating that deleterious
mutation did play a role in adaptive evolution. Populations of digital organisms
adapting to their environment may climb sub-optimal adaptive peaks for short-
term gain, but ultimately end up isolated on these peaks and unable to adapt
further without crossing a fitness valley. Testing this new hypothesis, for
deleterious mutations as stepping stones between fitness peaks, required follow
up experiments in chapters 4 and 5. These experiments examined the role of
deleterious mutations in the control population.
3.2.2 Reverting and Replacing Neutral Mutations

A second experiment that reverted and replaced neutral mutations was
also performed. Five additional treatments that disabled neutral mutations, in
ways analogous to the the disabling of deleterious mutations in the previous
experiment, were performed and compared to the control treatment. Significant

differences between experimental treatments and the control were found

 

3 A Bonferroni correction for repeated test by the Dunn-Sidak method was performed to adjust
the p-values (Ury 1976, Sokal and Rohlf 1995).

50

(Kruskal-Wallis test P<0.001, df=5, chi-sq=16.1), however the treatments
disabling neutral mutations were not significantly different from one another
(Kurskal-Wallis test P=O.121, df=4,chi-sq=7.3). These results were consistent
with the findings from the previous experiment. What was not consistent was
that while all treatments without neutral mutations have depressed median final
dominant fitnesses relative to the control, two of them, RpNL and RvN (Figure
3.6), were not significantly lower from the control population (Mann-Whitney U-

test P=0.383 and P=O.112 respectively).

The most likely cause for the discrepancy of pairwise tests of the median
final dominant fitness lay in the definition of neutral. In both of the treatments
that were not significantly lower than the control, only mutations that were exactly
equal to the parent's fitness were considered neutral thus leaving in the
population mutations of slight effect that are widely considered to be “effectively
neutral”. This supposition was bolstered by the fact that the RvN-nn and RpN-nn
treatments, which treated all mutations of effect size less than 1% as neutral, had
significantly lower fitness than the control population (Mann-Whitney U-test

P<0.05 for both).

For the RpNL treatment, another interesting possibility arose: as neutral
and lethal mutations were replaced, they may have been replaced with potential
deleterious stepping stones. Thus, even though fitness was reduced in the short-
term, deleterious stepping stones may have been leveraged to recover to even
higher fitness in the long-term. This speculation became more plausible when it

was noted that every experimental treatment had populations with fitness close

51

10*8l- -

T * T T T T
10A7- ' ' i -
— l
l l
l l
l .
1056- i
g i
go 10A5I- ‘ -
E g l l ‘
. I E
10A4- i g l g ! -
*L l l l l l
10A3. _L j- .

 

 

10‘2[ -

Control RpN RpNL RvN RvN-nn RpN-nn
Treatment

Figure 3. 6: Final dominant fitness under six evolutionary treatments each with
50 replicate populations. All fitnesses are normalized by the fitness of the
ancestor. (C) All mutations enter the population normally. (RpN) All neutral
mutations are replaced with a random beneficial, deleterious or lethal mutation.
(RpNL) All neutral and lethal mutations are replaced with a random neutral or
lethal mutation. (RvN) All neutral mutations are simply reverted, as if they never
occurred. (RvN-nn) All mutations with a fitness effect less than 1% are
considered effectively neutral and reverted. (RpN-nn) All mutations with a fitness
effect less than 1% are considered efiectively neutral and replaced with a
beneficial, deleterious or lethal mutation. In three cases (RpN, RvN-nn and RpN-
nn), the control treatment has significantly higher fitness (see text for statistics)
strongly indicating that the loss of deleterious mutations impeded long-term
adaptation. In two cases (RpNL and RvN) median fitness of the control
population was not higher, this is discussed in the text.

52

to the maximum achieved by populations in the control treatment. These
populations achieved such high fitness without any, or severely reduced, neutral
variation. Given the great importance placed on neutral variation, it seemed
highly unlikely that adaptation could have reached such high peaks without at

least some deleterious stepping stones.

Two methods were used to explore the hypothesis that deleterious
stepping stones played a critical role in maintaining the adaptability of
populations without neutral variation. One was to track all deleterious mutations
on the line of descent and count how many times they changed their fitness
effect from deleterious to neutral. Counting such changes and testing their
importance to evolution is the main topic of chapters 4 and 5, where stepping
stones in populations without neutral mutations are examined alongside the
control treatment. A second, more immediate approach, was to simply revert or
replace both neutral and deleterious mutations. If disabling both deleterious and
neutral mutations significantly reduces fitness relative to treatments where only
neutral mutations are disabled, it will provide evidence that populations without
neutral mutations are at least partially compensating for their loss by leveraging
deleterious stepping stones. Either way, there is still strong evidence that neutral
mutations are important for evolution, in particular those mutations that are nearly
neutral. This result helps to validate the methods used to disable mutations in

this chapter.
3.2.3 Reverting and Replacing Neutral and Deleterious

Mutations
The third set of experiments disabled both deleterious and neutral

53

I
1

10‘8

I
l

10""!

I
l

10*6

I
l

10*5

101w -

 

 

 

 

L091 0( Fitness)

 

I
1

10‘3

10*2

T

10‘1

 

‘- f ++§

9
t
+ ..
t

 

+ *
10*0 ' ‘

 

 

Control RpND RpNDL RvND RvND-nu RpND-nn
Treatment
Figure 3. 7: Final dominant fitness under six evolutionary treatments, each with
50 replicate populations. All fitnesses are normalized by the fitness of the
ancestor. (C) All mutations enter the population normally. (RpND) All neutral
and deleterious mutations are replaced with a random beneficial, or lethal
mutation. (RpNDL) All neutral, deleterious and lethal mutations are replaced with
a random beneficial mutation. (RvND) All neutral and deleterious mutations are
simply reverted, as if they never occurred. (RvND-nn) All mutations with a
fitness effect less than 1% are considered effectively neutral and reverted along
with deleterious mutations. (RpND-nn) All mutations with a fitness effect less
than 1% are considered effectively neutral and replaced with a beneficial, or
lethal mutation. The control population has significantly higher fitness than all
experimental treatments.

 

mutations, primarily to test the hypothesis that populations from the neutral
reversion and replacement experiments were leveraging deleterious mutations to
partially compensate for the lack of neutral variation. The results clearly showed
that median final dominant fitness were severally depressed in populations
without neutral or deleterious mutations. All populations were significantly less fit
than the control population (Mann-Whitney U-test P<<0.001 for all) and their
counter parts from the experiment disabling only neutral mutations (Mann-
Whitney U-test P<<0.001 for all). Even more striking is that populations that
replaced nearly neutral mutations had fitness even lower than their counterparts
with mutations of very small effect (Mann-Whitney U-test p<<0.001 for all). This

strongly indicated that nearly neutral mutations played a critical role.

Overall, these results strongly supported the hypothesis that deleterious
stepping stones partially compensated for the loss of neutral variation in
experiments from 3.2.2. The populations of strict hill climbers in this experiment
were unable to significantly adapt to their environment. Further study on the
timing and magnitude of individual stepping stones will be closely examined in
chapters 4 and 5, but one thing is immediately clear from these results: while
beneficial mutations are clearly necessary for evolution, they are often the last
step in a process that relies heavily on both neutral and deleterious changes in a
search for a well adapted phenotype.

3.2.4 Reverting and Replacing Lethal Mutations
In the final experiments, lethal mutations were disabled, to verify that

methods of replacement in previous experiments had no adverse effect. Lethal

55

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10*8 - -
10*7 - -

A 10*6 - .

8

o

5

E

2

§ ions. > < .
1OA4 h ——H——— "
1053 b -

Control RpL RvL
Treatment

Figure 3. 8: Final dominant fitnesses under three evolutionary treatments, each
with 50 replicate populations. All fitnesses are normalized by the fitness of the
ancestor. (C) All mutations enter the population normally. (RpL) All lethal
mutations are replaced with a random beneficial, deleterious, or lethal mutation.
(RvL) All lethal mutations are reverted, as if they never occurred. There were no
significant differences between these treatments.

mutations are generally thought to be relatively unimportant, and their reversion
or replacement should have had no negative impact on evolution. Experiments
that disabled lethal mutations were unable to reject the null hypothesis, as the

control population did not differ significantly from the RpL or RvL treatments,

56

(KurskaI-Wallis test p=0.1610, df=2, chi-sq = 3.65). This experiment clearly
illustrated that any significant differences relative to the control in the first three
experiments were not driven by a lack of lethal mutations. Disabling lethal
mutations, likely only sped up the inevitable outcome of purging dead organisms

from the population.

3.3 Discussion of Reversion and Replacement

Reverting and replacing mutations requires a great deal of effort. There is
not a switch to flip or a coefficient to set to zero; an instantiation of the
evolutionary process is being altered as it unfolds. Even in silico, there are
immense complications to disabling particular types of mutations. An entire
dissertation could be devoted to examining the secondary effects of reverting and
replacing mutations. The type of variation that may enter an evolving population
is being altered. If the eliminated variation was unimportant or detrimental, no
negative effects should have been observed. However, if that class of mutations
contributed to evolution in any way, then populations must find a way to
compensate for the loss. An example of this type of compensation was the
experiments that lacked neutral mutations; deleterious stepping stones might
have been leveraged more frequently in an attempt to ameliorate the loss of
neutral variation. If the lost variation could not be compensated for, then the null
hypothesis is rejected and we may assume that those mutations play a critical
role in evolution, even if they are not immediately adaptive. This was the case
with experiments that disabled deleterious mutations. Excluding side effects of

replacement or reversion, the most likely explanation for reduced fitness due to a

57

lack of deleterious mutations is an inability for populations to cross fitness valleys
and escape to more fit adaptive peaks. However, this alternative hypothesis for
the role of deleterious mutations is still just conjecture. Disentangling the
mechanism evolution uses to leverage maladaptive steps will require a set of
carefully designed analyses and follow up experiments, which will be described
in chapters 4 and 5. For now, it is clear that deleterious mutations play some
important role in evolution, and that role is one that cannot be fulfilled by other

types of mutation.

58

Chapter 4: Lineage Tracking

When a deleterious mutation enters the population, previous works have
assumed that it will be purged by selection before it can be joined by a second
mutation (Gillespe 1984). Numerous works on compensatory adaptation
(reviewed in chapter 1) have challenged Gillespe's assumption, strongly
indicating that genetic backgrounds are more fluid than previously thought. The
genetic background is a term used to describe the combined fitness effect of all
sites in the genome except the one that is under observation. The site under
observation usually contains a recent mutation; subsequent mutations in the
genetic background may or may not alter the fitness effect of the mutation being
examined. If every step along a lineage alters the genetic background, it
becomes impossible to say with absolute certainty that a deleterious mutation will

be purged form the population.

The shifting of genetic backgrounds might explain why deleterious
mutations sometime become useful, as was demonstrated in chapter 3.
Mutations that appear deleterious on the initial background may play a key role
on a nearby genetic background (a background separated by a small number of
mutations). The question becomes: how often do deleterious mutations have
their fitness effects altered by changes to the genetic background and how
important are such shifts to long-term evolution? The first step in addressing
these questions is to find a method of tracking the changes in the fitness effect of

an individual mutation.

In this chapter a series of analyses are discussed that examine how a

59

deleterious mutation may have its fitness effect altered by subsequent changes
to the genetic background. In order to determine how a given mutation's fitness
effect is altered through time, epistatic interactions between the mutation and the
genetic background must be tracked. Throughout this chapter, each mutation
under observation was initially deleterious, and the genetic background were all
other sites in the genome. Section 4.1 describes an algorithm for tracking
changes in the fitness effect of an individual mutation on the line of descent.
Section 4.2 examines a series of examples illustrating the possible fitness effect
changes that may be undergone. Finally, in section 4.3, lines of descent from the
control treatment, as well as the lineages from treatments reverting only neutral

mutations, will be analyzed using the methods described in sections 4.1 and 4.2.

4.1 Algorithm for Lineage Tracking

fir?) (1)
./ (dk)

 

Ark:

All of the populations from chapter 3 were limited to one point mutation per
divide, meaning that every offspring's genotype on the line of descent was
exactly one mutation away from its parent. Limiting reproduction to only one
mutation between parent and offspring made it easy to classify the fitness effect
of each mutation. To analyze the effect of deleterious mutations they first had to
be identified on the line of descent; any time a genome had a lower fitness
relative to its parent or “progenitor”, the mutation was classified as deleterious.

The progenitor (P) of the deleterious mutation was the anchor for analyzing how

60

fitness eventually recovered. The progenitor's fitness (denoted as f(P)) was the
fitness subsequent genomes had to reach to ameliorate the effect of the

deleterious mutation.

Once a deleterious mutation and its progenitor were identified (d1), every
subsequent genome on the line of descent that contained the deleterious

mutation was isolated. These subsequent mutations were labeled as d2...dn, and
the fitness of any deleterious genome k was labeled f(dk). The change in fitness

at each of the k genomes carrying the mutation (herein ./fk) was calculated

relative to the fitness of the progenitor, using the formula in equation 1 (illustrated
by Figure 4.1). Whenever the ratio was greater than 1, it indicated that the
lineage had fully recovered from the deleterious mutation. However, just looking
at overall fitness could not differentiate between a compensatory mutation that
was sign-epistatic with the deleterious, and a compensatory mutation that was
unconditionally beneficial. in other words, the deleterious mutation may only
have been hitchhiking on the fitness of a beneficial mutation, and not changing its
fitness epistatically. The only way to distinguish between these outcomes was to
construct a hypothetical lineage to find out what would have happened if the

deleterious mutation had never occurred.

wk)

A :—
f k f(rdk) (2)
To determine the role of the deleterious mutation, an alternate lineage
containing every genome that carried it was constructed. Each instance of the

deleterious mutation was reverted to its progenitor state, while its genetic

61

Af<l Af=l Af>l

0‘ H NH“ 3,. f“ J. ’1.
e e ..._, e-e

Figure 4. 1: A theoretical lineage containing a deleterious mutation. Each circle
represents a genotype on the line of descent, differing by exactly one mutation
from its parent. P represents the progenitor of the deleterious genotype. dud"

are the n genotypes that carry the deleterious mutation. d’ indicates the first
genotype without the deleterious mutation, PD is the final dominant genotype.
The color denotes change in fitness relative to the progenitor (equation 1); red
shades are deleterious (Af<1), blue shades are beneficial (Af> 1) and white
indicates neutral (Af=1), as indicated by the key above the lineage.

 

background remained unaltered. These n alternate genomes were labeled
rd1...rdn and a lineage was created showing how fitness at each step on the line

of descent would have be altered if the deleterious mutation had never occurred
(Figure 4.2). The change in fitness at each genome was calculated as the ratio
between fitness in the alternate genome over fitness of the actual genome
(Equation 2), revealing three qualitative outcomes, depending on the ratio of
equation 2. For values greater than one, reverting the deleterious mutation
raised the fitness of the alternate genome, signaling that the deleterious mutation
still reduced fitness. Values equal (or very close) to one signaled that the
mutation's fitness effect shifted to neutral. Values less than one meant that
reverting the mutation lowered fitness in the alternate genome, signaling that the
mutation now had a beneficial effect on the current genetic background. If the
analysis of the actual genome, relative to the progenitor, indicated that fitness
had more than fully recovered, then not only had the deleterious mutation
changed its fitness effect to beneficial, but it had changed in a way that improved
fitness relative to the progenitor. Such an improvement could only have been the

result of sign-epistasis between the “deleterious” mutation, and a compensatory

62

Af<l Af=l Af>l

Figure 4. 2: A theoretical lineage paired with its alternate lineage. For every
genotype dk an alternate genotype rdk is created with mutation d reverted to the
progenitor state, but othenrvise identical to the genotype on the actual line of
descent. The color of the alternate lineage represents change in fitness relative
to the paired genotype on the actual lineage (equation 2) and explicitly describes
the fitness effect of an individual mutation. Also note that f(rd1) is always equal

to the progenitors fitness (as they are the same genotype).

 

mutation on the genetic background. The compensatory mutation was only
compensatory in the presence of the deleterious mutation, and only once the two
mutations were combined did they improve fitness over the progenitor. More
broadly, this analysis shows how the fitness of the genetic background and the
fitness effect of an individual mutation can vary jointly, or independently of one

another.

4.2 Examples of Possible Outcomes
The table in figure 4.3 combines the analysies of both the genetic

background and the individual mutation and gives a snapshot of the fitness
effects at a specific point in time. The vertical axis of Figure 4.3 is mapped
directly from the analysis of the genetic background relative to the progenitor
(Figure 4.1 and Equation 1). The horizontal axis showes the fitness effect of an
individual mutation and is mapped directly from the analysis of those mutations
(Figure 4.2 and Equation 2). Thus, a fitness change along the vertical axis

indicates a shift in the fitness of the genetic background, while a fitness change

63

Fitness Change of Mutation
Af(Alternate LoD)

Del Neut Ben

leut_ IVN t g

A

 

 

 

 

 

 

Af(LoD)

 

 

 

 

 

Fitness Change of
Genetic Background

Figure 4. 3: A grid representing all the possible fitness changes of an individual
deleterious mutation versus the fitness changes of the line of descent relative to
the progenitor. The horizontal axis represents the change in fitness effect of an
initially deleterious mutation, as indicated by the fitness changes in the altemate
line of descent (AfAltemate LCD), determined by equation 2. The vertical axis

represents the fitness changes along the line of descent, relative to the
progenitor of the deleterious mutation (AfLoD), determined by equation 1. Five

possible extremes are highlighted: Deleterious-Beneficial (DB), Beneficial-
Beneficial (BB), Deleterious-Deleterious(DD), Beneficial-Deleterious (BD) and
Neutral-Neutral(NN). These extremes are fully described in the text, along with
example lineages.

in the horizontal axis represents a change in the fitness effect of an individual
mutation. As a deleterious mutation progresses down the line of descent, the
fitness effects of each axis could vary together or independently, but both fitness

effects are tracked together to reveal when, if ever, the deleterious mutation

became beneficial via a sign-epistatic interaction.

Figure 4.3 could be used to show the state of a mutation and its genetic
background at every step on the lineage. However this analysis was focused on
the fate of deleterious mutations based on three ending conditions. These
ending conditions are: the deleterious mutation was removed from the lineage by

a mutation at the same site, the lineage reached the final dominant, or the

64

deleterious mutation shifted its fitness effect to neutral or beneficial (moved on
the horizontal axis of Figure 4.3). The first two ending conditions are self-
evident, the mutation was either removed or no further changes were present on
the lineage, but the third requires more explanation. “Deleterious” mutations
were of interest only while they were deleterious. Once a deleterious mutation
shifted its effect to neutral or beneficial, its fate was the same as any other
neutral or beneficial mutation. The remainder of this section examines the five
most interesting types of changes in fitness effect, out of nine total outcomes.
These outcomes correspond to the labels on figure 4.3. The labels for each
extreme consist of two letters that describe the change in fitness effect for each
axis as either Beneficial, Neutral or Deleterious (abbreviated by B, N and D
respectively). The first letter describes the change in the initially deleterious
mutation's fitness effect (horizontal axis of Figure 4.3). The second letter
describes the net change in fitness relative to the progenitor (vertical axis of
Figure 4.3).
4.2.1 Beneficial-Beneficial (BB) Outcome

The Beneficial-Beneficial (BB) outcome was the most interesting, when
both the background and the mutation were beneficial together, but not
separately (Figure 4.4). For a BB outcome to have occurred there had to have
been a sign-epistatic interaction between the current genetic background and the
initially “deleterious” mutation. The sign-epistatic interaction may have been
between several mutations on the lineage and the “deleterious” mutation, or

simply between the deleterious and a single compensatory mutation. For the

65

l>

r>1

Figure 4.4.“ A theoretical lineage paired with an alternate lineage, as in Figure

4. 2, depicting a possible Beneficial-Beneficial outcome. The deleterious
mutation shifts its effect to beneficial via a sign-epistatic interaction and remains
beneficial until the end of the experiment. The example in Figure 4.2 is also BB,

but that sign-epistatic pair in that figure is eventually replaced by an even more
beneficial mutation before the end of the experiment.

Af<l Af=l

moment, the distinction between two mutations and a more complex interaction
involving more than two is irrelevant. The shift from deleterious to beneficial is of
the greatest significance, since these interactions are the most likely candidates
for deleterious mutations acting as stepping stones to higher fitness.
4.2.2 Benefical-Deleterious (BD) Outcome

In the beneficial-deleterious (BD) case, the deleterious mutation conferred
a beneficial fitness effect. Reverting the deleterious mutation would have
lowered fitness relative to the actual genome, and signaled that the initially
deleterious mutation was now beneficial (Figure 4.5). However, the fitness of the
genome had not yet fully recovered from the initial deleterious mutation. There
are two possible reasons why fitness had not fully recovered. One possibility is
that the initially deleterious mutation had been fully compensated for, but a
second deleterious mutation joined the genome. The mutation that partially
compensated for the initial fitness loss caused further fitness loss without the
original deleterious mutation, and was only beneficial relative to its immediate
parent, not the progenitor. The interaction was still epistatic, both mutations were

initially deleterious, but they were less deleterious together than they would have

66

Af<l Af=l Af>1

Figure 4.5: A theoretical lineage paired with an alternate lineage, as in Figure
4.2, depicting a possible Beneficial-Deleterious outcome. The deleterious
mutation is partially compensated for by a subsequent mutation at d3 which

conferred a compensatory mutation that ameliorates the deleterious effects of d1,
but in this case does not fully compensate for d1. Regardless, the genome is

more fit with both mutations than either one by themselves, indicating epistasis in
the magnitude of the fitness effects, but not altering the sign. In this case the
deleterious mutation is replaced with one that fully compensates for the fitness
loss initial/y incurred. It is also possible that the epsistatic mutations will be
joined by a third that is sign-epistatic with the first two, but this possibility was not
captured by this analysis.

 

been apart. However, the epistasis only altered the magnitude of the fitness
effects, not the sign. Unless these mutations were eventually joined by one that
fully compensated for the fitness loss, they were still maladaptive and would
likely have been purged from the population.
4.2.3 Deleterious-Beneficial (DB) Outcome

The beneficial background, deleterious mutation case is simply a
deleterious mutation that hitchhiked on the success of a subsequent beneficial
mutation (Figure 4.6). The deleterious mutation was not fully compensated for,
but a beneficial mutation had entered the genome, which was unconditionally
beneficial relative to the deleterious. The deleterious mutation no longer
lowered fitness, relative to the progenitor, but removing it would have conferred a
selective advantage. Any hitchhiking mutations revealed by this analysis would
most likely have been purged from the population. Since the tracking of fitness

effects ended when the the deleterious mutation's effect changed, hitchhikers

67

Af<l Af=l Af>l

Figure 4. 6: A theoretical lineage paired with an alternate lineage, as in Figure
4.2, depicting a possible Deleterious- Beneficial outcome. Although the
genomes on the line of descent have fully recovered their lost fitness by d3, the

alternate line of descent reveals that they would still be more fit without the
deleterious mutation. Since the lineage would still be more beneficial without the
deleterious mutation than with, the deleterious mutation has not altered the sign
of its fitness effect and is still deleterious.

 

revealed by this analysis were either present until the end of the experiment, or
eventually removed from the population. A distinction between the two remaining
possibilities will be made in the section 4.3 by looking at just those mutations that
were present in the final dominant.
4.2.4 Deleterious-Deleterious (DD) Outcome

The deleterious-deleterious case, is an uncompensated deleterious
mutation against a deleterious background (Figure 4.7). The genome was being
weighed down by the deleterious mutation and only recovered when the
deleterious mutation was removed from the population. In most instances, these
mutations were removed from the population before they could be joined by an
epistatic mutation. This scenario accounts for the majority of observed
deleterious mutations.
4.2.5 Neutral-Neutral (NN) Outcomes

Initially deleterious mutations may sometimes be compensated for by an
epistatic mutation that simply restores the progenitor fitness. In this case, the

presence or absence of the deleterious mutation makes no difference, since

68

Af<l Af=l Af>l

rd1 —- rd2 — rd3

 

Figure 4. 7: A theoretical lineage paired with an alternate lineage, as in Figure

4. 2, depicting a possible Deleterious-Deleterious outcome. The deleterious
mutation entered the population, but its fitness effect was never altered and it
was eventually replaced by a more fit mutation at the same site. Although in this
case the subsequent mutation that replaced the deleterious one was more fit, a
simple reversion or another mutation that was neutral relative to the progenitor
would have restored fitness.

reverting it had no impact on fitness (Figure 4.8). It is unclear if these types of
recovery can have any long-term impact on evolution. Since the compensatory
mutation was neutral with or without the deleterious, it is unlikely that the
progenitor was completely isolated, rather the neutral mutation represented a
connective ridge between the progenitor and a genotype with higher fitness.
While neutral drift was shown in chapter 3 to be a key factor in evolution, the
number of deleterious mutations that recover to neutral was unlikely to be of
significance, since neutral drift presumably could have found the same solution
without a deleterious step. Still, the additional robustness conferred by any
recovery from a deleterious mutation would aid evolution in the short-term.

Experiments in chapter 5 will shed more light on the role these mutations play in

evolution.

4.3 Results
It is important to reiterate that this analysis captured only the final effect of

an initial deleterious mutation while it remained deleterious, or until it left the

lineage. For example, while a mutation may certainly have been a hitchhiker for

69

Af<l Af=l Af>l

"assesseoe

Figure 4. 8: A theoretical lineage paired with an alternate lineage, as in Figure
4. 2, depicting a possible Neutral-Neutral outcome. The deleterious mutation
entered the population, and persisted until it was joined by a second mutation
that made both fitness effects neutral with respect to the progenitor.

 

a short time before being a part of a sign-epistatic interaction, any mutations that
are labeled as hitchhikers (BD) here, were labeled so because they were
hitchhikers for their duration in the population. Many different combinations of
fates are possible; some deleterious mutations may recover to neutral fitness, but
these transitions are less interesting because their eventual fate would be no
different from any other neutral mutation. While this analysis was able to
comment on other fates of deleterious mutations, the most significant are those
that may have acted as stepping stones (BB), i.e. those that underwent a sign-
epistatic change to yield a net benefit.
4.3.1 Control Populations

The lines of descent for 50 control populations contained a grand total of
22,263 mutations, of which 1,746 were deleterious (7.8%) and 626 caused a
fitness loss greater than 1%, these are listed in Table 4.1A. The four most
observed fates were hitchhiking (BD), failure to recover (DD), recovery to neutral
(NN), and recovery via a sign-epistatic interaction (BB); these four fates account

for more than three quarters (75%) of the highly deleterious mutations observed.

Every genome on the line of descent that contained a particular

70

Af(Alternate LoD)

Af(Alternate LoD)

 

 

 

 

A Del Nest Ben l B Del Neut Ben
’0; Ben 158 30 106 , Ben 1 1 36
53, Mei 34 6O 26 l 31*. o 1 2
<‘ Del 146 34 32 , Del 2 4 6

 

 

 

 

 

 

 

 

 

 

Table 4.1: Tables depicting the outcome of all deleterious mutations from the 50
lines of descent that composed the control treatment. Only mutations with a
fitness effect greater than 1% were tracked. Table A shows the fate of all initially
deleterious mutations, table B shows the fate of only those initially deleterious
mutations that persisted until the end of the experiment. While the subset of all
mutations shows four prominent categories, DB, BB, DD, and, to a lesser extent,
NN, only those with a compensatory mutation that changed from deleterious to
beneficial (BB) are still highly represented in the final dominant genomes.
deleterious mutation was counted, to measure how long the deleterious mutation
was a part of the lineage. Both deleterious mutations that failed to recover (DD)
or hitchhiked (BD) were present in the line of descent for only a brief period of
time, a median of 4 and 2 steps respectively (these two classes were not
significantly different form one another). Neutral recoveries (NN) lasted
significantly longer with a median of 9.5 steps on the line of descent. Sign-
epistatic recoveries (BB) lasted a median of 30 steps, and persisted significantly
longer than any other type of deleterious recovery (P<<0.001, Mann-Whitney U-

test).

Beneficial-beneficial recoveries were also by far the most prevalent type of
deleterious mutations that fixed and persisted until the final dominant genotypes
(Table 4.18), accounting for more than two thirds of all deleterious mutations in
final dominant genotypes (68%). The number of initially deleterious, but

ultimately beneficial mutations that fixed in final dominant genotypes strongly

indicated that they played an important role in the adaptation of these

71

populations. At the least, these mutations helped enhance the robustness of the
lineage by turning a deleterious mutation into something useful; at the most they
were actually stepping stones between adaptive peaks. Distinguishing between
these two possibilities required testing of individual deleterious mutations to

examine what their long-term impact on the lineage really was.

The same comment about robustness may also apply to the deleterious
mutations that recovered to neutral (NN and BN). These mutations became
neutral, which was established in chapter 3 as a class of mutation that
contributes to adaptation. However, neutral recoveries were not conserved in the
final dominants, and did not persist as long in the lineage. The relatively large
number of neutral mutations already available to an organism, may diminish the
importance of individual neutral recoveries. Again, further testing in chapter 5 will
shed light on the relative importance of each class of deleterious recovery.

4.3.2 Populations Disabling Neutral Mutations

Out of the 5 treatments reverting or replacing neutral mutations, all
exhibited more deleterious mutations, but also disproportionately more
deleterious mutations that altered their fitness effects via an epistatic interaction.
Focusing on the RpN-nn treatment from chapter 3 (Table 4.2), sign-epistatic
conversions from deleterious to beneficial were not only more numerous than the
control runs (424 vs. 106), but also made up a larger proportion of BB mutations
that fixed in the final dominant (58% vs. 34%). In addition, epistatic conversions
from deleterious to neutral (NN and BN) were also more numerous and fixed in

larger proportions than in the control populations.

72

Af(Alternate LoD)

Af(Alternate LoD)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A _De|___ Neut ”Bin 4 B_F_De|_+ Neut Ben
53; Ben 213 134 424 Ben 17 23 247
:3 rig-.1 37 181 68 1 37 42
<’ Del 87 35 54 Del 2 11 20

 

 

Table 4.2: Two tables depicting the outcome of all deleterious mutations from the
50 lines of descent that composed the RpN—nn treatment. Only mutations with a
fitness effect greater than 1% were tracked. Table A shows the fate of all
deleterious mutations, and table B shows only the fate of those deleterious
mutations that persisted until the end of the experiment. Substantially more BB
recoveries are observed here than in the control runs (both absolutely and
proportional). Neutral recoveries, both NN and BN, also occur more frequently.
While it is not surprising to find an increased number of deleterious
mutations in a treatment that replaces all neutral mutations, it is surprising to see
that proportionally more of them are present in final dominant genomes. The
dramatic jump in the number of BB interactions supports the hypotheses from
chapter 3, that they were partially compensating for the loss of neutral variation.
These data also indicate that evolving populations may have more ways to
recover from a deleterious mutation then previously thought (as was hinted at in
Moore et al. 2000 and discussion on compensatory mutation in chapter 1). Many
of these sign-epistatic recoveries are likely not explored in the presence of
neutral mutations, since neutral variation carries no fitness cost and could have
lead to the same results. However, when all neutral variation is eliminated,
deleterious mutations will be expressed much more frequently, if only for a brief
amount of time. The large number of epistatic recoveries not withstanding, this

analysis does not indicate that they were easy or even advantageous over the

long-term, just that they happened.

73

4.4 Conclusions
The analysis presented in this chapter reveals the likely candidates for a

deleterious mutation acting as a stepping stone to high fitness. It is important to
stress that these are only the most likely candidates. A mutation could
theoretically undergo any number of transitions from one fitness effect to another.
For example, a deleterious mutation may hitchhike on a subsequent beneficial
mutation, and then be compensated for. These types of multiple transitions are
not explicitly tracked by this analysis. Cases where a deleterious mutation is
replaced by a mutation that is still deleterious relative to the progenitor, but
neutral relative to the initial deleterious mutation, were also overlooked. If the
second deleterious mutation receives a sign-epistatic interaction that is more fit
than the progenitor (Figure 4.9), the end result is still passage through a fitness

valley leading to a new adaptive peak.

The cases this analysis overlooks obviously require a deleterious mutation
of some kind and were implicitly quantified by reversion and replacement runs.

Other stepping stones that took a more circuitous route are overlooked by this
Af<l Af=l Af>l

o a 0 j ‘v
, ,4—4. m. w - _

Figure 4. 9: A theoretical lineage paired with an alternate lineage, as in Figure
4. 2, depicting a lineage in which deleterious mutation d, is replaced with another
deleterious mutation. The new mutation (n 1) is neutral with respect to it's

immediate parent but deleterious with respect to the progenitor. When the
mutation is eventually compensated for, the end result is still passing through a
fitness valley. However, this case would have been overtooked by the analysis
presented in this chapter, because mutations were only classified as deleterious
relative to their immediate parent not genomes further back on the line of
descent.

 

74

explicit analysis for now, but will be a major focus of future work. The purpose of
the analysis presented here is to find the deleterious mutations that allowed for
passage through fitness valleys to new adaptive peaks. This analysis
established the presence of such a passage in the line of descent, and these

candidate stepping stones will be more thoroughly examined in chapter 5.

Overall, any mutation identified by this analysis as having shifted it's
fitness effect from deleterious to neutral or beneficial was almost certainly useful
to evolution in some way. Even mutations that are not outright stepping stones
became a part of an epistatic interaction that either maintained or increased the
fitness of the organisms on the dominant lineage. While only a few BB
interactions found themselves fixed in final dominant populations, these were
likely essential to evolution and there is little doubt that their absence was at the
least partially responsible for the reduced fitnesses observed in chapter 3. What
is less clear is the role of interactions that recovered to fitness other than
beneficial, in particular those that recovered to neutral fitness. While these
neutral recoveries (NN and BN) obviously aided the lineages that eventually
produced the final dominant, it is unclear how important these particular
mutations were. Could neutral drift have carried these lineages to the same
highly adapted peaks, or would the outcome of evolution be irrevocably altered in

their absence?

75

Chapter 5: Replaying Evolved Genotypes to
Distinguish Deleterious Stepping Stones from Chance
Events

Evolutionary history is often made up of historic and chance events, as
was discussed briefly in chapter 1. The goal of the experiments discussed in this
chapter was to explore whether the deleterious mutations isolated in chapter 4
were chance events, or enabled the escape of populations from relatively
isolated suboptimal peaks. It is important to again reiterate that while high
dimensionality of genotypes space may create neutral ridges between fitness
peaks, those peaks may still be considered effectively isolated if evolution is
unable to follow the ridge between peaks. Analyses of neutral networks has
already shown that populations tend to cluster around highly connected areas of
the neutral network, to avoid lethal mutations. Van Nimwegen and Crutchfield
called these entropy barriers and assumed that they were difficult for evolution to
traverse because of their rarity and the load of lethal mutations. Given an infinite
population and unlimited time, evolution may have been able to escape from
from isolated peaks without passing through a fitness valley. However, it is

unlikely that evolution would be able to proceed in this fashion in the wild.

The results of these experiments depended on the actual topology of the
fitness landscape, which is nearly impossible to fully define (see discussion in
Chapter 1). If certain parts of a landscape are effectively isolated, except by
deleterious mutations, then a deleterious mutation would always be needed for
the population to escape and achieve higher fitness. When a deleterious

mutation allows for escape from a sub-optimal peak it is said to be a “stepping

76

stone” to higher fitness. The experiments presented in this chapter, explored
how often these two outcomes occurred in the sign-epistatic interactions

identified in chapter 4.

Thus far, the experiments presented in chapter 3 have confirmed that
deleterious mutations play an important role in adaptive evolution, and the
analysis in chapter 4 has identified deleterious mutations with sign-epistatic
recoveries that may have been stepping stones. These sign-epistatic deleterious
mutations provided a plausible explanation for the importance of deleterious
mutations. However, direct evidence was needed to link the two results. The
sign-epistatic recoveries may simply have been chance events, and the results of

chapter 3 may have been driven by some other phenomena.

This chapter describes experiments that focused on testing the hypothesis
that deleterious mutations enabled escape from suboptimal peaks via adaptive
valleys. One test case, out of the 36 sign-epistatic pairs identified at the end of
chapter 4, was selected as a case sudy to examine how these mutations
behaved, and to develop a test of their relevance. Section 5.1 describes the test
case in detail, examining not only the deleterious mutation in question, but the

evolutionary trade-offs that made it a useful stepping stone. Section 5.2

describes an experiment that determined if the progenitor1 of the deleterious
mutation could have escaped from the local optimum without a deleterious
mutation. Finally, 5.3 expands the experiment from 5.2, to all deleterious

mutations that recovered to beneficial and neutral in the control treatment, and

 

1 As in chapter 4, the “progenitof’ in this chapter always refers to a genome whose offspring
received a deleterious mutation.

77

beneficial recoveries in the RpN-nn treatment.

5.1 Test Case

One sign-epistatic transition from individually deleterious to jointly
beneficial was selected as a test case. This test case (Figure 5.1) closely
examines three mutations starting with the progenitor (ab), and a deleterious
mutation (Ab). The deleterious mutation (Ab) reduced fitness by 9%, and was
followed by a neutral mutation, before a beneficial mutation (AB) finally occurred.
The beneficial mutation (AB), conferred an eight fold fitness increase by allowing
the organism to perform EQU, the most complex task in Avida (see description of
Avida's environment form chapter 2.1.4). Lineage analysis reveled that the
beneficial mutation was not unconditionally beneficial, but sign-epistatic with the
“deleterious” mutation (Ab). Not only was the test case a sign-epistatic transition,
but it was also one of the 36 potential stepping stones that survived to the end of
the control runs. Of the three mutations (eight possible permutations), four
permutations appeared in the line of descent, the other four were reconstructed
to reveal what other epistatic interactions might have taken place (Figure 5.1A).
The neutral mutation remained neutral against all possible backgrounds. The
“beneficial” mutation (aB), caused a 99% fitness reduction when it was isolated

from the “deleterious” mutation (Ab), rendering it effectively lethal.

Looking back further along the line of descent, shows that the “deleterious”

mutation actually reversed an extremely successful2 copy-loop optimization that

 

2 “Extremely successful” here is a genome that was observed in over 10,000 organisms on the
line-of—descent alone. This genome likely also spawned other briefly successful clades, off the
line of descent, separated by only a few mutations.

78

A Actual Line of Descent
abn) irza...tnkq...pqqcyb...1nva -
Abn) irza...tnkq...pqqcib...1nva -
AbN) irza...tneq...pqqcib...1nva -
ABN) irza...tnsq...pqgcib...lnva -

Construc d n m s
aBN) irza...tneq...pqgcyb...lnva -

aBn) irza...tnkq...pqgcyb...lnva -

abN) irza...tnsq...pqqcyb...1nva -

 

ABn) irza. . . tnkq. . .pqgcib. . . lnva - W=8.00

Genotype Space

Figure 5. 1: A test case that consisted of a 3 way interaction between a sign-
epistatic pair of mutations and one purely neutral mutation, which occurred
between them. (A) Four sequences were observed in the line of descent, the
other four sequences were constructed to reveal other possible epistatic
interactions. The relevant mutations in each sequence are colored. The
reconstruction shows that the neutral mutation (N) is truly neutral, and the
“Beneficial” mutation (a B) is actually lethal when isolated from the “deleterious”
mutation (Ab); only both mutations together (AB) are truly beneficial. (B) a
representation of the sign-epistatic interaction between the relevant gene
combinations; the neutral mutation was dropped form this figure because it had
no effect on the topology of the landscape.

occurred two mutations earlier (Table 5.1). It is possible that the original
deleterious mutation (Ab), and subsequent compensatory mutation (AB), actually
pushed the population off a suboptimal peak. The suboptimal peak was
optimizing for gestation time, and the sign—epistatic interaction allowed the
population to transition to a peak with EQU. However, it is impossible to be
certain that evolution would not have eventually found a path with no deleterious
mutations that optimized for both gestation time and complex features, because
enumerating all possible mutational pathways is intractable (even in silico);

therefore another approach was required, which utilized hypothesis testing.

79

     

L m g C m

95 "B E To

B E 23. g g

f3 B 8 < UJ

- 10547 251 3.21E6 1.28E4 1 1 1 1 1 1 1 0 0

abn 907 251 3.21E6 1.28E4 1 1 1 1 1 1 1 0 0
Abn 1 282 3.28E6 1.16E4 1 1 1 1 1 1 1 0 0
AbN 28 282 3.28E6 1.16E4 1 1 , 1 1 1 1 1 0 0
ABN 26140 282 2.62E7 9.30E4 1 1 ‘ 1 1 1 1 0 ‘ v—‘

 

- irzavcaschocgtggbtnpqppctqtjaofbpqqcybcqptyvslnva
abn irzavcaschocgtggbtnkqppctqtjaofbpqqcybcqptyvslnva
Abn irzavcaschocgtggbtnkqppctqtjaofbpqqcibcqptyvslnva
AbN irzavcaschocgtggbtnsqppctqtjaofbpqqcibcqptyvslnva
ABN irzavcaschocgtggbtnsqppctqtjaofbpqgcibcqptyvslnva

Table 5.1: Original line-of-descent showing the test case. Mutation labels are
consistent with Figure 5.1. Looking two steps back reveals that the “deleterious”
mutation actually took the place of a highly successful (over 10, 000 total
genomes) copy-loop optimization, which reduced gestation time. Lowering
gestation time conferred a small fitness advantage, but made it difficult, if not
impossible, to evolve EQU.

5.2 Test Case Replays

Experiments were performed to determine if the deleterious mutation from
the test case was a stepping stone to EQU. Two treatments of 20 replicates
each were seeded with either the progenitor (ab) or the initial deleterious mutant
(Ab). Both treatments were run for 20,000 updates under RpD conditions, so that
no new deleterious mutations could emerge, which forced the progenitor
treatment to evolve differently than it did in the original control replicate. If the
progenitor genome was isolated on an adaptive peak, it would have needed a
deleterious mutation to escape, thus under RpD conditions the progenitor

treatment would not have been able to evolve higher fitness, since deleterious

80

mutations were disallowed. Furthermore, since the two treatments differed only
by a single deleterious mutation in the seed genome, any significant differences
between their adaptive evolution could only have been attributed directly to that
mutation. Thus, if significantly more replicates in the deleterious seed's
treatment evolved EQU, then the presence of the deleterious mutation clearly
increased the probability of evolving EQU. The opposite would also have been
true, if the treatment with the deleterious mutation evolved EQU fewer times,
then the deleterious mutation must have impeded the evolution of EQU, and the
sequence of mutations in the original line of descent was simply a fortuitous
event. Since the progenitor treatment has only neutral and beneficial mutations,
and is not weighted down by a known deleterious mutation, the null-hypothesis is
that it will ultimately end up at higher fitness. Again, as with the original reversion
and replacement treatments in chapter 3, the experiment is stacked heavily

against any result favoring the presence of a deleterious mutation.

In the test case, all 20 replicates seeded with the deleterious mutation
(Ab), evolved EQU, while none of the replicates seeded with the progenitor (ab)
evolved EQU. This result strongly indicated that the progenitor was stuck on a
suboptimal fitness peak, and that the only means of escape was through a
deleterious valley (p<<0.001, Fisher's Exact Test). To further examine the
alternative hypotheses that deleterious mutations were the only means of escape
for the progenitor, another treatment of 20 replicate populations was run: this
time seeded with the progenitor genotype. However, these new replicates were

run under control conditions, which allowed deleterious mutations, to see both

81

how frequently EQU evolved and how often such evolution required a deleterious

stepping stone.

Out of the 20 replicates seeded with a progenitor genotype under control
conditions, 13 (65%) re-evolved EQU (Table 5.2). All 13 replicates required
deleterious mutation to reach EQU, but not necessarily the same stepping-stone
from the control run. Nine of the 13 followed the same path as the original
population (Path l) and of those nine only one contained an extra, superfluous,
neutral mutation. Of the remaining 4 replicates to evolve EQU, 3 contained a 3-
way interaction (Path II), and any combination of the three mutations was
deleterious (Figure 5.2). The remaining population contained a more complex

interaction involving at least 6 mutations (Path Ill).

 

 

 

 

Number of Relative *‘ Relative A 0 Number Of
Mutations Fitness Cost Fitness Replicates
_ f ‘ f Recovery Present
Path | 2 0.09 x 8.00 9
Path || _. _ 3 0.05 6.99 _ _ 3 __
Path m 5 0.05 1.04(8.87) - 1

Table 5. 2: A table describing the three different paths the control reruns took to
EQU. The first column gives the minimum number of mutations to evolve EQU.
The next two columns list the fitness lost from the deleterious mutation, and
gained by the recovery, relative to the progenitor fitness. Finally, the last column
lists how many replicates used each path. The relative recovery for path lll
contains two values, one for the initial recovery, and another for the recovery to
EQU for which a deleterious mutation was required.

5.2.1 Analysis of Path ll

Path II, which contained the 3-way interaction, at first looked very much

like the original replicate. Path ll mutated away from a the progenitor3 (now

 

3 It is important to remember that the progenitor in all three paths is the same, only the notation
differs for the different mutations that occurred latter on in each path.

82

labled xyz to denote that we are examining a different stepping-stone) with a
deleterious mutation (Xyz), then a neutral mutation (XYZ) and ending with a
beneficial mutation (XYZ), which conferred EQU. Unlike the test case, where the
neutral mutation was not related to the evolution of EQU, reverting any of the
three mutations (including the neutral mutation) in the organism that performed
EQU caused the task to be lost. Reconstructing the alternate permutations of
these three mutations revealed that both the beneficial (xyZ) and neutral (sz)
mutations were actually deleterious on their own. Not only were those mutations
deleterious in isolation, but they each reduced fitness by well over 50% (Figure
5.2). The beneficial mutation also continued to reduce fitness when present with
just the deleterious mutation (XyZ), meaning that the path followed by evolution

to EQU, in all three cases, was the shallowest adaptive valley possible.

What is most interesting about Path II, is that it seems to confirm the
observation by van Nimwegen and Crutchfield (2000) that the length, rather than

the depth of the adaptive valley, is the most important factor in determining which

path evolution is likely to take4. Here, Path II has a shallower valley but a longer
path than Path I, and as such was represented less frequently in the replays,
possibly because following a longer deleterious path is more difficult, especially
when a shorter path is present. However, this effect may also have been due to
the fact that permutations other then the one actually observed resulted in even
greater fitness-losses, which could have also made Path II more difficult to follow

then Path I. This potential for increasing fitness loss in the adaptive valley was

 

4 van Nimwegen and Crutchfield also excluded the possibility

83

     
  

Path ||

A—L—l—lAA—AA
A—l—I—L—l—l—L—l
_L_l_\_l_L.-l_l._l
A—L—k—l—LA—A—l

       

Ffiness

 

Genetic Distance

Figure 5. 2: A test of a three-way interaction among mutations that conferred
EQU. The progenitor (xyz) is the same as the progenitor in figure 5.1, and again
three mutations lead to EQU, a deleterious (X), neutral (Y) and beneficial (2).
However, in this case, reconstructions of all combinations revealed that the
“neutral” mutation was actually necessary for EQU. Dotted lines in the figure
above indicate all possible paths to EQU using these three mutations, the solid
line indicates the path that was actually taken in the replay. The table above lists
full reconstruction information for all possible combinations of the three
mutations.

not accounted for by van Nimwegen and Crutchfield and clearly warrants further

study.

5.2.2 Analysis of Path Ill

Path lll contained a 6-way interaction that was more complex than the first
two paths; while a deleterious mutation did occur, it was fully compensated for
and mutated away before EQU entered the population. The deleterious and
compensatory mutations were sign-epistatic. However, the beneficial mutation
that compensated for the deleterious loss was not only lethal without the initial
deleterious, but was also required for EQU later on. EQU emerged when the
beneficial compensatory mutation was joined by two subsequent neutral
mutations (one of which replaced the initially deleterious mutation) and a third
purely beneficial mutation. Thus, while the majority of this path was essentially
hill climbing, the hill started in the trough of an adaptive valley. The deleterious
mutation actually enabled a mutation that was necessary for EQU, but lethal on

the progenitor's genetic background.

Path lll took a minimum of 6 steps and was observed only once, which
also seems to agree with van Nimwegen and Crutchfield's result, as did Path ll
above. However, this path is also one that was not anticipated by van Nimwegen
and Crutchfield, where the initially deleterious mutation is resolved early on, yet
climbing the fitness peak was effectively a series of beneficial and neutral
mutations. In other words, Path III, with the shallowest deleterious mutation and
then a series of neutral and beneficial mutations, was taken less frequently then
Paths l and II which were shorter but had larger up-front fitness costs. While the
length of the path still seems to be the critical factor, how the composition of the

path's mutations affects long-term evolution is an area that requires further study

85

(this will be explored more in section 5.4 and chapter 6).

What is clear from these replays is that a deleterious mutation was
necessary for the progenitor genotype to escape from a local fitness peak.
Furthermore, the escape via stepping stones through an adaptive valley was
highly repeatable and occurred with greater frequency than expected by random
chance. While it might have been possible to simply perform a landscape
analysis of all single, double and triple point mutations to see if any lead to EQU,
such an analysis would not have directly revealed what is most interesting: which
paths evolution was most likely to take. Also, the rerun experiments depicted
here were computationally easier to expand to the remaining 35 potential
stepping stones from the control runs than extensively landscaping each
candidate stepping stone would have been. Such landscaping would be

computationally expensive, and would likely miss cases such as Path III

5.3 Replays of Deleterious Mutations

In the previous section two treatments were performed to test if the
deleterious mutation from the test case was actually a stepping stone to EQU.
Each treatment was seeded with either the deleterious mutant, or its progenitor
and run for an additional 20,000 updates. RpD was used in both treatments to
prevent new deleterious mutations from emerging. The results clearly showed
that the deleterious mutation was a stepping stone, as only the treatment with it

evolved EQU.

This section describes experiments that expanded the design from the last

section to all initially deleterious mutations in the control replicates, that

86

recovered to Beneficial-Beneficial, as well as other types of recoveries. As with
the test case, for each mutation tested, paired treatments with 20 replicates each
were seeded with either the deleterious mutant or its progenitor. Each replicate
was run for 20,000 updates, after which median final dominant fitness could be
plotted for each pair treatment. These, final dominant fitnesses for all deleterious
treatments were compared to their paired progenitor treatments and a paired
Wilcoxin signed-rank test was applied to determine if the treatments differed
significantly over all. If a significant difference was found between the paired
medians then a Mann-Whitney U-test (adjusted with a Bonforenni correction by
the Dunn-Sidack method) was applied to each pair of treatments to determine if

each differed significantly, and which treatments were favored.

If no significant differences had been observed, then it would have
suggested that the progenitors were not on fully-isolated local fitness peaks, and
that paths of neutral or beneficial mutations were far more accessible. However,
if the significant differences favored the deleterious mutants, it would have
provided strong evidence that the progenitor genotype was stuck on a suboptimal
peak and required a deleterious stepping stone to escape. This test was first
applied to the 36 BB mutations identified from the final dominants in the control
runs (including the test case).

5.3.1 Beneficial-Beneficial Control Replays

First, the 36 Beneficial-Beneficial recoveries from chapter 4 were tested

using paired reruns (Figure 5.3). These were mutations that initially caused a

fitness loss greater than 1% but recovered via a sign-epistatic mutation, and both

87

mutations fixed in the final dominant genotype. Replays of these stepping stones
showed a significant difference between treatments seeded with deleterious
mutations, over those seeded without them (P=0.0218, two-tailed paired

Wilcoxon signed-ranks test).

Among those pairs of treatments, 11 were significantly in favor of the the
deleterious mutation (P<0.05, Mann-Whitney U-test adjusted by a Bonforreni
correction by the Dunn—Sidak method) and none significantly favored the
progenitor. Of the 11 significant deleterious treatments, 6 had fitness that was at
least an order of magnitude greater than their progenitor counterparts. These
drastic differences in resulted because six treatments had significant task
evolution. The remaining 5 treatments had smaller, but no less significant,
improvements in fitness, which were due to optimizations in gestation time.
These gestation time optimizations were made significantly more likely with their

associated deleterious mutations.

Of the 25 mutations that were not significantly different, 13 of the medians
favored the deleterious mutant, 11 favored the progenitor, one treatment was a
tie (The tie is analyzed in depth below). The other 24 non-significant mutations
show that while the progenitor genotypes were not effectively isolated by
adaptive valleys, the non-deleterious paths were no easier for evolution to follow
to higher fitness. Overall, many genomes in this case were not only able to
evolve significantly in the presence of deleterious mutations but were also

frequently aided by the presence of a brief maladaptive step.

88

4.5 r

log 1o(Median Deleterious Final Domlnant Fitness)
L4

‘ ——————— X=Y
a p>0.05
l l I _E 4 4 L .l “0.05 J
2'35" 73 _* 3.5 4 4.5 5 5.5 6 6.5 7
log1o(Medlan Progenitor Final Dominant Fitness)
Figure 5. 3: A scatter plot depicting the results for rerunning 36 pairs of treatments
seeded with either a deleterious mutant (vertical axis) or its immediate progenitor
(horizontal axis) and run under RpD conditions. Each point represents a pair of
median final dominant fitnesses from each treatment. Filled points represent
treatments where the deleterious mutant resulted in significantly higher fitness
than the immediate progenitor (p<0.05). The dotted line indicates where the
medians would be equal, points above the line favored the deleterious mutant,
points below favored the progenitor. The significance tests are discussed further
in the text.
In Depth Analysis of the Tied Replay

The tie in one paired treatment occurred because the sign-epistatic

 

interaction was not deleterious if the mutations occurred in a different order

(Figure 5.4). In other words, the progenitor (dc) was two mutations away from

89

Funess

 

 

‘
x
7

 

Genotype Space
Figure 5. 4: A figure representing the fitness interaction of the tied replay. The

progenitor (dc) was only two mutations away from the genotype that performed
EQU (DC). Which order the mutations occun'ed in (DC first or dC first) determined
whether or not the path followed was deleterious or neutral. The path taken by
the original experiment is denoted by the solid line.

EQU, when those mutations occurred in one order they were deleterious
(reducing fitness by approximately 4%) and then compensatory (Dc and DC), in
the opposite order they were neutral, and then unconditionally beneficial(dc and
DC). Both orderings conferred EQU and both replay treatments were able to
evolve EQU in all 20 replicates by following either the deleterious or neutral path.
This replay presented an interesting scenario, one with two pathways of equal
length to a complex feature, one of which is deleterious and the other neutral.

That the deleterious mutant is expressed on the line of descent raises two

immediately interesting questions. One question is how frequently either path to

90

EQU is followed, the other is howmany other fitness landscapes such as this
one (Figure 5.4), but were overlooked because the neutral mutation was taken,
or because the deleterious mutation did not survive to the final dominant. The
second question is much harder to address because it would require analysis of
all neutral mutations, however the first question can be quickly addressed using a

method similar to the replays done on the test case in 5.2.

The progenitor (dc) from the tied replay was run again for 20,000 updates,
but this time under control conditions so that both deleterious and neutral
mutations could occur. The number of replicates that took either the deleterious
or the neutral path were then counted to obtain an estimate of the likelihood each
path had of being taken. Of 50 replicate populations, EQU was re-evolved 49
times, 21 times via the neutral path (dc) and 19 times via the deleterious path
(Dc), indicating that either path was almost equally likely to be followed. Of the 9
additional replicates that evolved EQU via a different series of mutations, 7 of the
9 paths involved a sign-epistatic interaction, whereas 2 of the 9 were simple
neutral paths. Overall, 26 of the replicates to evolve EQU did so via a
deleterious mutation, whereas only 23 did so via a neutral path. Again, these
results indicate that deleterious paths may be followed even in the presence of a
neutral path. Much work remains to be done to examine what factors impact the
likelihood of a particular path being taken, and these questions will be a major
thrust of future work discussed in chapter 6.

5.3.2 Neutral Control Replays

Recoveries from deleterious to neutral mutations could not have acted as

91

stepping stones. Deleterious “stepping stones” have been explicitly and implicitly
defined as maladaptive steps taken to escape from isolated fitness peaks. Thus,
neutral recoveries were disqualified because the transition from one genotype to
another could have been pure neutral drift, had the mutations appeared in a
slightly different order. Still, even if the deleterious mutation was not necessary,
the ability to traverse multiple paths to a different region of genotype space would
have made it more likely that adaptive evolution would be able to reach it. The
use of multiple paths to high fitness was illustrated by the analysis of the tied
replay above. Recoveries from deleterious to neutral were replayed as in the
previous subsection. Whereas before replays were done to test if the mutations
were stepping stones, the replays here were done to see if the deleterious
mutations significantly slowed the progress of adaptive evolution, or if they simply

furnished alternate paths to neutral genotypes.

Replicate replay populations were again seeded with a deleterious
mutation or its progenitor and run under RpD conditions, with all 60 mutations
that originally recovered to Neutral-Neutral (NN) and 30 of Beneficial-Neutral
(BN). In these experiments, differences between the final dominant fitnesses
were not significantly different in either the NN replays (p=0.40, paired Wilcoxon
signed-rank test) or the BN replays (p=0.64 paired Wilcoxon signed-rank tests).
The lack of significance here indicates that while deleterious mutations that
recovered to neutral did not significantly slow or speed up adaptation, they did

provide alternate means to reach a neutral area of the genotype space.

92

5.3.3 Beneficial-Beneficial RpN-nn reruns
Finally, BB recoveries from the RpN-nn (replace neutral, include nearly

neutral) treatment were replayed. This treatment from chapter 3.2.2 had
significantly lower fitness than the control experiment, but not dramatically lower,
as was initially expected from reverting all neutral and nearly neutral mutations.
This gave rise to the hypothesis that deleterious mutations were being utilized to
recover from the loss of neutral variation. This hypothesis was bolstered by data
from chapter 4.3.2 showing that all deleterious recoveries were not only more
numerous, but also fixed in final dominant genotypes more frequently. Despite
this evidence, replays were needed to determine if these mutations were actually
useful deleterious stepping stones, or more circuitous paths that were only viable

because of a lack of neutral variation.

Replicate paired treatments were seeded with one of 247
deleterious/progenitor pairs of genomes from the original RpN-nn treatment that
recovered to BB and fixed in the final population. As before, all treatments were
run under RpD conditions so that no new deleterious mutations could enter the
population. However, unlike previous experiments, these organisms originally
evolved in populations without neutral mutations, and were then moved into
replay experiments with neutral mutations. This change in the make up of
mutations means that progenitor seeds could leverage previously inaccessible
paths of neutral mutations. The presence of hitherto inaccessible neutral paths,
gave cause to suspect that fewer deleterious mutations would be actual stepping

stones then might be expected proportionally from the results of the BB control

93

replays.

The change in the composition of mutations was clear in the results.
Overall, final dominant fitnesses were significantly in favor of the deleterious
treatment (P<0.01, Wilcoxon signed-rank test) with 141 pairs in favor of the
deleterious mutant, and 101 in favor of the progenitor treatment. Individual tests
of the paired treatments revealed that 23 of the 141 (16%) of the treatments
favoring the deleterious were significantly different under individual Mann-
Whitney U-tests (p<0.05, adjusted by a Bonforeni correction by the Dunn-Sidak
method). Only 8 of the 101 (8%) progenitor treatments were significantly

different under individual tests (p<0.05).

These results show that while deleterious recoveries in runs without
neutral mutations are more numerous, several of the deleterious mutations were
significantly worse when neutral mutations were present. Still, these experiments
also show that many more accessible paths of deleterious mutations are present,
than were initially observed in the control treatment. The critical question then
becomes, not if a deleterious path is accessible or useful—there is strong

evidence that they are--but when the deleterious path will be taken.

5.4 Discussion

This chapter presented results demonstrating that deleterious mutations
could act as stepping stones to enable escape from effectively isolated
suboptimal fitness peaks. Even when the deleterious mutations were not needed
for escape from suboptimal adaptive peaks, deleterious paths were sometimes

taken over neutral paths with no long-term cost to adaptation. The question is no

94

longer whether deleterious mutatiOns can be useful. Experiments in the last
three chapters have shown that deleterious mutations are used to escape these
effectively isolated suboptimal fitness peaks. The major new question that arises
is why paths containing deleterious mutations are sometimes taken when a path
of neutral mutations is also present, such as in the case of the NN or BN
recoveries and the tied replay. Some evidence from the test case in this chapter
suggests that the answer may lie in van Nimwegen and Crutchfields' theory that
the length rather than the depth of the fitness valley is the key deciding factor.
Thus short paths of deleterious mutations may be able to short circuit longer
paths of neutral mutations at no, or very little, long-term cost to adaptive
evolution. However, much more work is needed on this theory. For the time
being it is sufficient to conclude that deleterious mutations can, and do, act as
stepping stones in adaptive evolution, and that these stepping stones are a

critical part of the process of adaptive evolution.

95

Chapter 6: Conclusions and Discussion

The three chapters previous have described experiments which explored
the interactions between, epistasis, fitness landscapes, and adaptive evolution.
Disabling deleterious mutations (see chapter 3) lowered the overall fitness in
evolving populations of digital organisms. The long-term reductions in fitness
pointed to a trade-off between short-term fitness loss for long-term adaptive
success. The crossing of so-called “fitness valleys” is the most likely hypothesis
that furnishes an explanation for the usefulness of deleterious mutations. While
a fitness landscape may be a strained analogy (as was discussed in chapter 1),
some genomes maybe easier to reach by hill-climbing than others. When these
highly accessible genomes are arrived at, further evolution is possible only via a

brief maladaptive step.

Analysis presented in chapter 4 confirmed the presence of these brief
maladaptive steps, on the line of descent to the final dominant of replicate control
populations. The analysis identified deleterious mutations that underwent a sign-
epistatic interaction, switching their fitness effects from deleterious to beneficial.
However, the mere presence of a brief maladaptive step does not provide causal
evidence that they were a useful or necessary component of the adaptive walk

leading to the final dominant.

Further experiments in chapter 5 suggested that some sub-optimal fitness
peaks were isolated and could only be crossed by a deleterious mutation
undergoing a sign-epistatic interaction. One pair of mutations used as a test

case, consisting of a deleterious mutation and it's immediate progenitor, were

96

replayed in two different treatments, without additional deleterious mutations.
Populations seeded with the progenitor were unable to evolve further without a
deleterious mutation; whereas all populations seeded with the “deleterious”
mutant managed to evolve EQU. A second experiment was then run, replaying
the progenitor genotype under control conditions. The only replicate populations
in the second experiment to evolve EQU contained a deleterious mutation along
the line of descent. These results indicated that the progenitor genotype was on
a relatively isolated sub-optimal peak, which evolution could not escape from
without at least a brief maladaptive step. While the analogy of a fitness
landscape may break down at high dimensions, the inability of evolution to reach
a more fit phenotype without deleterious mutations clearly indicates that some
areas of the fitness landscape are surrounded by mutations that decrease fitness

—in other words a fitness valley.

The experiments in chapters 3 and 4 clearly showed that deleterious
mutations improved long-term evolution, and provided evidence for the existence
of suboptimal fitness peaks that could only be escaped via deleterious mutations.
However, there was still no direct link between the fitness improvement observed
when deleterious mutations were present, and crossing fitness valleys. The test
case was just that, a single instance that provided an existence proof for the
original hypotheses; the test case itself may have just been a coincidence, and

not a broader trend.

A final experiment was done to see if deleterious mutations were driving

populations to higher fitness by escaping from suboptimal fitness peaks via brief

97

maladaptive steps. All deleterious mutations of large effect (fitness loss greater
than 1%) that were present in the final dominant genomes were replayed in
replicate populations with additional deleterious mutations disabled. Each of
these treatments were compared with a paired treatment, which replayed the
progenitor genotype. Of the 36 paired replays, the treatment that replayed the
deleterious mutation was favored 11 times, the other 25 pairs had no significant
differences between the treatments. This final experiment demonstrated that
these sign-epistatic recoveries are aiding adaptive evolution by providing

adaptations that were otherwise unattainable by evolution.

Each of these experiments provided a new piece of a puzzle, and pointed
to a key roll for deleterious stepping stones in adaptive evolution. In chapter 3,
disabling all deleterious mutations reduced long-term fitness relative to
unmodified control populations. Every deleterious mutation from the control runs
was then tracked and revealed many final dominant genomes contained
deleterious mutations that had undergone a sign-epistatic transition. Finally, it
was shown that some of these deleterious mutations conferred adaptations that
could not be achieved by direct Danrvinian evolution. In other words, deleterious
mutations do sometimes serve as stepping stones across otherwise implacable

fitness valleys.

Although the main result of this dissertation addresses deleterious
mutations as stepping stones, there are other, slightly less interesting results to
consider. In chapter 3, runs reverting and replacing neutral mutations were also

performed. These runs also exhibited the reduced fitness expected from a loss

98

of neutral variation, however two treatments were not significantly different from
the control. Further analysis in chapters 4 and 5 showed that at least one of
these treatments had substantially more deleterious mutations, and sign-epistatic
recoveries, than the original control treatment. This result seemed to indicate
that deleterious mutations were a viable alternative path when neutral mutations
were unavailable. It is also possible that there were many accessible paths
containing deleterious mutations, and that these paths were simply not taken
because paths of neutral mutations were easier for evolution to traverse. The
results presented here are an important reminder that evolution is fundamentally,
a directed random search. While evolution frequently leads to a well adapted
solution, it may arrive there through a circuitous path of neutral and deleterious

mutations.

Another interesting result was found in the test case replays. The original
replays showed that the progenitor was unable to evolve EQU without a
deleterious mutation. This was achieved by replaying the progenitor in an
environment with no deleterious mutations, and an environment identical to the
control treatment. In the control replay, deleterious mutations were a necessary
part of every path leading to EQU, and appeared on three types of unique paths.
Of the deleterious paths taken, the shortest path was taken three quarters of the
time, even though it had a greater initial fitness cost. This supports a theory
proffered by van Nimwegen and Crutchfield (2000), that the probability of an

adaptive path being followed is indicated by the length of that path.

There are a number of distinct follow ups to the research described in this

99

dissertation. The most obvious avenue for future work would be to add sexual
recombination to the existing project. Although sex has already been added to

Avida, by recombining the genomes of two offspring to create two new offspring

(haploid sexual recombination‘), disabling deleterious mutations becomes more
complicated. While individual mutations could be reverted or replaced in each of
the gametes (assuming fitness of the gametes was classified relative to their
parents), recombination would obviously have its own fitness effect. Alternatively,
mutations could be introduced after recombination and fitness effects defined by
a comparison to the fitness of the unmutated recombined genome, which could
be obtained from the test CPU. Either way, tracking the lineage of an individual
deleterious mutations becomes more difficult when every offspring has two
parents. Assuming all of these problems are overcome (or alternatives are
divesed), examining deleterious mutations in sexual organisms would shed light
on whether epistatic fluctuations are driven by tightly linked mutations, mutations

recombining sexually or both.

Related to the role of sexual recombination, is Wrights Shifting Balance
Theory (refer to chapter 1 for a detailed description of Wright's SBT). Wright
postulated that fitness valleys could be crossed if a population was structured
into a series of subpopulations, connected by low levels of migration. Wright's
theory was predicated on the idea that it was necessary to cross fitness valleys,
this idea has been widely disputed through time (Coyne et al. 1997). However,

the research presented in this dissertation illustrates that crossing fitness valleys

 

1 For a more detailed discussion of sexual reproduction in Avida, see Misevic et al 2005.

100

sometimes forms that basis of critical adaptations in the life history of a
population. In light of this new evidence, and the ability to disable deleterious
mutations in both sexual and asexual populations, it suddenly becomes pertinent
to reexamine Wright's Theory of Shifting Balance. Disabling deleterious
mutations, in both sexual and asexual populations, allows us to draw strong

conclusions on the efficacy of Wright's theory.

Finally, the test case presented in chapter 5 suggests that a number of
routes from a given starting point can lead to the same highly fit phenotype. This
finding is supported by reconstructions of known mutational paths to Beta-
Lactamase resistance in E. Coli (Weinreich et al 2005). However, Weinreich's
work focused on only one set of mutations found leading to antibiotic resistance,
whereas my test case actually found new paths to the same phenotypic traits.
By automating the process of isolating paths taken on the line of descent to a
particular phenotype, it would be possible to replay the progenitors of many fit
phenotypes and observe the roles that deleterious mutations play in their
reevolution, and the properties of alternative paths not observed in the original
population. These experiments will serve to elucidate the stochastic nature of
evolution by natural selection, and further elucidate which types of paths to high

fitness are most frequently leveraged.

These experiments have illustrated that deleterious mutations can play a
key role in adaptive evolution. More broadly, these experiments suggest that
adaptive evolution does not proceed directly, or even efficiently to the fittest

solution on the adaptive landscape, passing through successive beneficial

101

mutations on the way. Evolution instead proceeds circuitously through neutral
and deleterious mutations, and beneficial mutations are merely the crowning
achievement on the long and winding road of a stochastic search. The
experiments proposed as future work above will shed further light on how
evolution consistently arrives at a well adapted solution, via different evolutionary

paths.

102

Appendix A: Glossary

Definitions of terms and concepts frequently used in this dissertation.

Artificial Life
Agent based systems that instantiate biological principles to address

questions about natural life (Adami 1999). These systems may range from
simple genetic algorithms, to more complex systems such as Avida, which can
actually instantiate evolutionary processes (Ofria and Wilke 2004, Lenski et al

2003)

Copy-loop
A copy-loop is a piece of code in a digital organisms that makes an exact

duplicate of the organism. If the copy-loop fails to produce an exact copy then

the genome is considered unstable.

Deme

A deme is a sub-population of a single species, which occupies a
particular geographic area. Demes may be isolated from the total population,
and the degree of this isolation may result in differing selective pressure due to
increased levels of inbreeding in smaller populations. In asexual populations, the

differing selective pressure is due exclusively to population size.

Digital Evolution
Digital Evolution is a broad term which may refer to systems that utilize some

form of evolutionary search, such as genetic algorithms. In this dissertation,

digital evolution refers to an instantiation of the evolutionary process in the

103

computer. That is, an in silico system which implements inheritablity, variation,
and selection, as self-replicating computer programs. Tierra and Avida are

examples of systems that instantiate Digital Evolution.

Digital Organisms

Digital Organisms are self-replicating computer programs which inhabit the Avida

world.

Epistasis
Epistasis occurs when the fitness effect of two or more mutations (a and b)

are different when they are present in the same genome, ie the selective
coefficient acting on a particular mutation differs depending on the mutational
background. (Wienrich et al 2005). Most scientific works consider any variation
of the selective coefficient on genetic backgrounds as epistasis, or more exactly
magnitude epistasis (for examples see: Moore et al 2000, Lenski et al 1999,
Whitlock et al 1995). This dissertation deals with the most extreme form of
epistasis, sign-epistatic interactions, or mutations whose net fitness effect
changes sign when they are combined (Wienriech and Chao 2005, Whitlock et al
1995). Sign-epistasis may occur irregardless of any other magnitude effects.
For example, mutations a and b are deleterious individually, but beneficial when
present in the same genome, the magnitude of the both the beneficial and

deleterious fitness effects is irrelevant.

Entropy Barrier
An entropy barrier is a network of genotypes where fitness is not lost, but

104

that narrows surrounded by lethal or deleterious mutations. Entorpy barriers,
take more time to traverse then a purely neutral or ascending landscape owing to
their rarity and narrowness, but are thought to be less difficult to cross than a
fitness barrier (Van Nimwegen and Crutchfield 2000). Both Entorpy and fitness
barriers end with a “portal genotype”, 3 genotype that leads to a previously

unexplored network of higher fitness.

Final Dominant Genotype

The most abundant, and thus most successful, genotype present in the

population at the end of an Avida experiment.

Fitness Barrier
Fitness barriers are networks of genotypes where fitness is lower than the

best network found so far, sometimes these are called fitness pleatus or fitness
valleys. Fitness barriers are hard to traverse owing to their decrease in relative

fitness (Van Nimwegen and Crutchfield 2000).

Fitness Landscape
A fitness landscape referees to a topographic representation of all possible

gene combinations graded with respect to fitness. In this dissertation, we will
assume that individual genotypes occupy a single point on the fitness landscape.
We also define movement through the landscape as the lineage of the most
abundant genotype. This assumption overlooks phenotypic plasticity, and the
alternative view that populations actually occupy a single point, based of the

frequency of different genotypes in the population.

105

Genetic Algorithm
Genetic algorithms incorporate evolutionary principles of selection,

variation and inheritance to solve intractable computational problems. GAs,
utilize a population of solutions that are evaluated against some kind of man-
made fitness function in order to estimate how well that solution addresses the
particular problem. The best solutions undergo mutation, and form a new
population. Crossover, or the exchanging of genetic material between solutions,
is also used in addition to mutation, but is often thought of as disruptive.
Evolution over the fitness landscape poses the same challenges to GA solutions
as it does to natural genotypes. GA is best used to solve computationally
intractable problems and, just as in nature, one is never certain about the
topology of a fitness landscape. Therefore, lessons learned from our models of
natural fitness landscape exploration will directly inform and improve our GA

models, and vic-versa.

Genetic Background
The term genetic background generally refers to the state of a genome that a

mutation appears on. A mutation may have a different fitness effect on two
different genetic backgrounds. Throughout this dissertation genetic backgrounds
are assumed to be changing, raising the possibility that a mutation's fitness effect

may be alter in the population.

Genotype
The genetic makeup of digital organism; different genotypes may be separated

by a as little as a single mutation, and may also be phenotypically identical (see

106

also: Final Dominant Genotype). Typically, more than one organism will have the

same genotype.

Gestation Time
In Avida, gestation time is the number of CPU cycles a digital organism

requires to make a copy of itself and to place that copy into the population. In
general, there is strong selective pressure to make the copy-loop as short as

possible.

Group Selection
Group selection, is a process whereby alleles fix in a population based on

the affect they have on the group as a whole, not on the individual. In Wright's
Shifting Balance Theory, group selection was the process by which highly fit
alleles would spread from a local population were they where fixed, into other

local populations, driving out less fit alleles in other local populations.

Line of Descent
The line of descent is a lineage of all genomes that started at the original

ancestor and lead to the final dominant genotype. The lineage contains every

single mutation that lead to the final dominant.

Merit

In Avida, Merit is a unit-less number which represents an organism's
scheduling priority. An organism's merit is used to determine how many CPU
cycles it will receive in a given update, by awarding it cycles proportional to its

share of the population's total merit. This method of scheduling is approximate to

107

fitness proportional selection in GAs, however because Avida’s digital organisms

are self-replicating, there is additional selection pressure on gestation time..

Mutations

In biology, a mutation generally reefers to a non-synonymous amino acid
substitution, with one of four distinct effects on fitness. A mutation may be lethal,
in which case the organism with the mutation is unable to reproduce. A
deleterious mutation (DM) reduces fitness relative to the parent organism(s), but
is not immediately lethal; DMs in and of themselves have 4 different possible
outcomes, which are discussed in the section on compensatory
adaptation(Section 1.6, Page 15). A neutral mutation has no effect on fitness
relative to the parent. Except where otherwise noted, I assume that neutral and
nearly neutral mutations (relative fitness change less than the inverse of the
effective population size, Ohta 1992) are equivalent. Finally, beneficial mutations

raise fitness relative to the parent, but are extremely rare.

Neutral Network
A neutral network is a network of network of genotypes separated by

edges which represent mutations. Normally, the edges represent single point
mutations, however an edge could also represent multiple mutations. These
networks are frequently used to model neutral drift, as they were in van

Nimwegen and Crutchfield (2000).

Test CPU
The Test CPU is an isolated environment in Avida that contains a single instance

108

of the virtual hardware found on a single cell of the Avida world. The Test CPU
runs a single organism to obtain an estimation of how it will perform in the actual

population.

109

Bibliography
1. Adami, C. 1998 Introduction to Artificial Life. Springer, New York.

2. Belding TC, 1995 The distributed genetic algorithm revisited. In
Eschelman L. Ed., Proceedings of the Sixith lntemational Conference on
Genetic Algorithms,114-121, Morgan Kaufmann San Fransico.

3. Blount, Z. D., Borland, C. Z., and Lenski, R. E., Historical contingency and
the evolution of a key innovation in an experimental population of Escherichia
coli . Proc. Natl. Acad. Sci. 105, 7899-7906 (DOI
10.1073.pnas.0803151105)

4. Bridgham, J. T., Carroll, S. M. & Thornton, J. W. 2006 Evolution of
hormone-receptor complexity by molecular exploitation. Science 312, 97-101.
(DOI 10.1126/science.1123348)

5. Burch C. L. and Chao. L. 1999 Evolution by Small Steps and Rugged
Landscapes in the RNA Virus 06. Genetics 151, 921—927.

6. Carter, A. J. R. & Wagner, G. P. 2002 Evolution of functionally conserved
enhancers can be accelerated in large populations: a population-genetic
model. Proc. R. Soc. London B 269, 953-960. (DOI 10.1098lrspb.2002.1968)

7. Cantfi-Paz, E. 1998 A survey of parallel genetic algorithms. Calculateurs
Paralleles, Reseaux et Systems Repartis. 10, 141-171.

8. Coyne, J. A., Barton, N. H. & Turelli, M. 1997 Perspective: a critique of
Sewall Wright's shifting balance theory of evolution. Evolution 51, 643-671
(DOI 10.2307/2411143)

9. Cowperthwaite, M. C., Bull, J. J. & Meyers, L. A. 2006 From bad to good:
Fitness reversals and the ascent of deleterious mutations. PLOS Comp. Biol.
2, 1292-1300. (DOI 10.1371ljournal.pcbi.0020141)

10.Dennett, D. C. 1997 Darwin’s Dangerous Idea. Simon & Schuster, New
York.

11. DePristo, M. A., Hartl, D. L., & Weinreich, D. M. 2007 Mutational
Reversions During Adaptive Protein Evolution. Mol. Biol. Evol. 24, 1608-1610.
(DOI 10.1093/molbev/msm118)

12.Elena, S. F., Wilke, C. O., Ofria, C. & Lenski, R. E. 2007 Effects of
population size and mutation rate on the evolution of mutational robustness.
Evolution 61, 666-674. (DOI 10.1111/j.1558-5646.2007.00064.x )

13.Fernandez, F., Tomassini, M., & Vanneschi, L. 2003 An empirical study of
multipopulation genetic programing. Genetic Programing and Evolvable

110

Machines 4, 21-51. (DOI 10.1023/Ai1021873026259)

14.Gillespie J. H. 1984 Molecular Evolution Over the Mutational Landscape.
Evolution 38, 1116-1129. (DOI 10.2307/2408444)

15.Grosso PB. 1985 Computer simulations of genetic adaptation : Parallel
subcomponent interaction in a multilocus model. Doctoral Dissertation. The
University of Michigan, Ann Arbor .University Microfilms No. 8520908.

16.Holm, S. 1979 A simple sequentially rejective multiple test procedure
Scand. J. Stat. 6, 65-70.

17.lwasa, Y., Michor, F., Nowak, M. A., 2004 Stochastic tunnels in
evolutionary dynamics. Genetics 1 66, 1571 -1 579. (DOI
10.1534/genetics.166.3.1571)

18. Lenski, R. E. 1998 Bacterial evolution and the cost of antibiotic resistance.
lntematl. Microbiol. 1, 265-270.

19.Lenski, R. E., Ofria, C., Collier, T. C., & Adami, C. 1999 Genome
complexity, robustness and genetic interactions in digital organisms. Nature
400, 661-664. (DOI 10.1038/23245)

20.Lenski, R. E., Ofria, C., Pennock, R. T. & Adami, C. 2003 The evolutionary
origin of complex features. Nature 423, 139-144. (DOI 10.1038lnature01568 )

21.Lin, S. C., Punch, W. F., & Goodman, E. D. 1994 Coarse-grain parallel
gentic algrorithms: categorization and new approach. Proceedings of the
Sixith IEEE Symposium on Parallel and Distributed Processing. 28-37, IEEE
(DOI 10.1109/SPDP.1994.346184)

22.Lunzer, M., Milter, S. P., Felsheim, R. & Antony, D. M. 2005 The
biochemical architecture of an ancient adaptive landscape. Science 310, 499-
501. (DOI 10.1126/science.1115649)

23.Maisnier-Patin, S., Andersson, D. I. 2004 Adaptation to the deleterious
effects of antimicrobial drug resistance mutations by compensatory evolution.
Res. Microbiol. 155, 360-369 (DOI 10.1016/j.resmic.2004.01.019)

24.Maisnier—Patin, S.,Berg, O. G., Liljas, L. & Andersson, D. I. 2002
Compensatory adaptation to the deleterious effect of antibiotic resistance in
Salmonella typhimurium. J. Mol. Biol 46, 355-366. (DOI 10.1046/j.1365-
2958.2002.03173.x)

25.McKenzie, J. A., Whitten, M. J. & Adena, M. A. 1982 The effect of genetic
background on the fitness of diazinon resistance genotypes of the Australian
sheep blowfly, Lucilia cuprina. Heredity 49, 1-9. (DOI 10.1038/hdy.1982.60)

26.Misevic D., Ofria C. A., Lenski, R. E., 2006 Sexual reproduction reshapes

111

the genetic architecture of digital organisms. Proc. R. Soc. London B 273,
457464. (DOI 10.1098lrspb.2005.3338)

27.Mitchel| M., Forrest 8., Holland J. H. The Royal Road for Genetic
Algorithms: Fitness Landscapes and GA Performance, Towards a Practice of
Autonomous Systems: Proceedings of the First European Conference on
Artificial Life. Varela FJ, Bourgine P, eds. The MIT Press Cambridge.

28.Moore, F. B. G., Rozen D. E., and Lenski, R. E., 2000 Pervasive
compensatory adaptation in Escherichia Coll. Proc. R. Soc. London B 267,
515-522. (DOI 10.1098lrspb.2000.1030)

29.0fria, C. & Wilke, C. O. 2004 Avida: a software platform for research in
computational evolutionary biology. J. Artif. Life 10, 191-229. (DOI
10.1162/106454604773563612)

30.0hta T., 1992 The Nearly Neutral Theory of Evolution. Annu. Rev. Ecol.
Syst. 23 263-286 (DOI 10.1146/annurev.es.23.110192.001403)

31.Pennock, R. Models, Simulations, lnstantiations and Evidence: The Case
of Digital Evolution. 2007 J. Exper. and Theo. Artif. Intel. 19, 29-42. (DOI
10.1080/09528130601116113)

32.Provine, W. B. 1986 Sewall Wright and Evolutionary Biology. The
University of Chicago Press, Chicago and London.

33. Poelwijk, F. J., Kiviet, D. J., Weinreich, D. M., & Tans, S. J. 2007 Empirical
fitness landscapes reveal accessible evolutionary paths. Nature 445, 383-
386. (DOI 10.1038/nature05451)

34.Ray T. S. 1992 An approach to the synthesis of life. Proceedings of
Artificial Life ll. Addison-Wesley, Redwood City, CA.

35.Schrag, S. J., Perrot, V., 8 Levin, B. R. 1997 Adaptation to the fitness
costs of antibiotic resistance in Escherichia coli. Proc. R. Soc. London B 264,
1287-1291. (DOI 10.1098lrspb.1997.0178)

36.Tanese R. 1989 Distributed genetic algorithms for function optimization.
Doctoral dissertation, University of Michigan, Ann Arbor.

37.Ury, H. K. 1976 A comparison of Four Procedures for Multiple
Comparisons among means (painivise contrasts) for arbitrary sample sizes.
Technometrics 18, 89-97. (DOI 10.2307/1267921)

38.Weinreich, D. M., Delaney, N. F., DePristo, M. A. & Hartl, D. L. 2006
Darwinian evolution can follow only very few mutational paths to fitter
proteins. Science 312, 111-114. (DOI 10.1126/science.1123539)

39.Weinreich, D. M, 8 Chao, L. 2005 Rapid evolutionary escape by large

112

populations from local fitness peaks is likely in nature. Evolution 59, 1175-
1182. (DOI 10.1554/04-392)

40.Weinreich, D. M., Watson, R. A. & Chao, L. 2005 Perspective: Sign
epistasis and genetic constraint on evolutionary trajectories. Evolution 59,
1165-1174. (DOI 10.1554/04-272).

41.van Nimwegen, E., Crutchfield, J. P. & Huynen, M. 1999 Neutral evolution
of mutational robustness. Proc. Natl. Acad. Sci. USA 96, 9716-9720. (DOI
10.1073lpnas.96.17.9716)

42.van Nimwegen, E. 8. Crutchfield, J. P. 2000 Metastable evolutionary
dynamics: Crossing fitness barriers or escaping via neutral paths? Bull. Math.
Biol. 62, 799-848. (DOI 10.1006/bulm.2000.0180)

43. Wilke C. O. 2001 Adaptive evolution on neutral networks. Bull. Math. Biol.
63, 715-730. (DOI 10.1006/bulm.2001.0244)

44.Wright S, 1932 The roles of mutation, inbreeding, crossbreeding and

selection in evolution. Proceedings of the Sixth International Congress on
Genetics. 1 356-366

113

"'11111111111111111111111111s