ON THE EVOLUTION OF MUTATION BIAS IN
DIGITAL ORGANISMS
By
Matthew Rupp

A DISSERTATION
Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of
DOCTOR OF PHILOSOPHY
Computer Science
&
Ecology, Evolutionary Biology, and Behavior
2011

ABSTRACT
ON THE EVOLUTION OF MUTATION BIAS IN
DIGITAL ORGANISMS
By
Matthew Rupp

Mutation is one of the primary drivers of genetic change. In this work I study mutation
biases, which are sets of diﬀerent genetic-state inﬂow probabilities. Mutation biases have
the potential to change the composition of genomes over time, leading to divergent shortand long-term evolutionary outcomes. I use digital organisms, self-replicating computer
programs, to explore whether or not mutation biases are capable of altering the long-term
adaptive behavior of populations; whether mutation biases can be competitive traits; and
whether mutation biases can evolve.
I ﬁnd that mutation biases can alter the long-term adaptive behavior of mutation biasobligate populations in terms of both mean ﬁtness and complex trait evolution. I also
ﬁnd that mutation biases can compete against one another under a variety of conditions,
meaning mutation bias can selectable over relatively-short periods of time. The competitive
success of a mutation bias does not always depend upon the presence of beneﬁcial mutations,
implicating an increase in the probability of neutral mutations as a suﬃcient mechanism for
bias selection. Finally, I demonstrate that by giving organisms a mutable mutation bias
allele, populations preferentially evolve to possess speciﬁc biases over others.
Overall, this work shows that mutation bias can act as a selectable trait, inﬂuencing the
evolution of populations with regard to both their internal-genetic and external environments.

Copyright by
MATTHEW RUPP
2011

I dedicate this work to my friends, family, and the individuals of Michigan
State University, past and present, who continue to inspire me.

iv

ACKNOWLEDGMENTS

I would like to thank my two co-advisors: Dr. Eric Torng and Dr. Charles Ofria who
brought me into the Digital Evolution (DEVO) Lab as an undergraduate and contributed
greatly to my academic upbringing. Throughout the years, they have not only provided me
with sound advice but also served as role models.
I thank the two other members of my committee, Dr. Thomas M. Schmidt and Dr.
William F. Punch. Dr. Schmidt introduced me to the world of microbiology and was a major
reason I straddle the lines of computer computer science and biology. He provided insightful
feedback for the experiments in this work and helpful suggestions on how to communicate my
eﬀorts to a wider audience. Dr. Punch provided needed perspective on the computer science
applications of this work as well as guidance on some of the experiment conﬁgurations.
The advice and conversations of past and present members of the DEVO Lab contributed
greatly to my understanding of this material. The now graduated members of DEVO Lab:
Dr. Arthur Covert, Dr. Sherri Goings, Dr. Jeﬀ Clune, Dr. Ben Beckman, Dr. Laura
Grabowski, Dr. Dusan Misevic, Dr. Gabriel Yedid, Dr. Wei Huang, Dr. Dehua Huang, and
Mr. Jason Stredwick provided me with great conversation and feedback on my work over
the years. I also am grateful to all those present members of the lab (and aﬃliates) who
continue to provide me with insight especially: Drs. Heather Goldsby and David Knoester;
Rosangela Canino-Koning, David Bryson, Mairin Chesney, Brian Connelly, Anu Pakanati,
Mike Wiser, Bess Walker, and Luis Zaman. Lastly, I would like to especially thank Brian
Baer for all of the work he’s done to keep the lab’s research infrastructure in shape over the
years.
My parents Kathy and Kirk Rupp and grandparents Carol and Richard Whelton have
supported me greatly through out the years. I give them my heartfelt thanks.
Jennie Gies, Heather Rickets, Lisa Asmus, Emily Barry, and F. Amelia Howes have my

v

lasting gratitude. Their supportive friendship kept me motivated, grounded, and entertained.
Finally, I especially thank Jason Moon. His love and support were invaluable during this
endeavor.

vi

TABLE OF CONTENTS

LIST OF TABLES

ix

LIST OF FIGURES

x

1 An
1.1
1.2
1.3
1.4

.
.
.
.

1
1
2
3
6

.
.
.
.
.
.

8
9
10
12
16
18
21

Introduction to Mutation Biases
What is a mutation bias? . . . . . . . . . . . . .
Is mutation bias an adaptation for evolvability?
Previous work on mutation bias . . . . . . . . .
Can mutation biases confer evolvability? . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

2 Avida: A Digital Life Model
2.1 Avida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Avidians: genomes and life-cycles . . . . . . . . . . . . . .
2.1.2 The Avida population, environment, and organism ﬁtness .
2.1.3 Instructions, mutations, and mutation biases . . . . . . . .
2.2 An Avida experiment . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Experiment-speciﬁc features . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

3 The Adaptive Consequences of Mutation Bias
3.1 Creating a favorable mutation bias . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Dayhoﬀ PAM-like matrix . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Further simpliﬁcations of biases . . . . . . . . . . . . . . . . . . . . .
3.1.3 The INST-3 spectrum . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Mutation biases can change the evolutionary trajectory of obligate populations.
3.2.1 The eﬀects of mutation bias on task adaptation . . . . . . . . . . . .
3.2.2 Mutation bias can alter evolutionary trajectory of adapted populations
3.2.3 Mutation bias can allow for the evolution of complex tasks de novo .
3.3 Other eﬀects of mutation bias . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22
22
23
25
27
28
29
31
33
37
38

4 Selecting a Mutation Bias
4.1 Mutation bias may be visible to selection . . . . . . . . . . . . . . . . . . . .
4.1.1 Baseline competition results . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 The eﬀect of population size on the relative selectability of mutation
bias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3 Population structure is an important factor in the selection of mutation
biases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Does adaptation inﬂuence the selection of a mutation bias? . . . . . . . . . .
4.2.1 Mutation bias is still selectable with an evolved genotype. . . . . . .
4.2.2 Mutation bias is selectable using additional evolved genotypes. . . . .

41
43
44

vii

47
50
53
53
56

4.3

4.4

Why are mutation biases selected? . . . . . . . . . . . . . . . .
4.3.1 Mutation bias can be selected in the absence of beneﬁcial
4.3.2 Mutation bias selection can be historically-contingent. . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Evolving Mutation Bias
5.1 How to represent a mutation bias . . . . . .
5.2 Mutation biases can evolve using demes. . .
5.2.1 What are demes? . . . . . . . . . . .
5.2.2 Mutation bias can evolve with demes.
5.3 Mutation biases can evolve without demes. .
5.4 Why are mutation biases selected? . . . . .
5.5 Summary . . . . . . . . . . . . . . . . . . .

. . . . . .
mutation.
. . . . . .
. . . . . .

.
.
.
.

59
61
63
66

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

70
70
72
73
75
78
79
84

6 Discussion and Further Avenues to Explore
6.1 The role of synonymous mutations . . . . . . . . . . .
6.2 The role of the environment . . . . . . . . . . . . . . .
6.3 The role of mutation bias in warping ﬁtness landscapes
6.4 Allowing the evolution of arbitrary mutation biases . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

85
85
86
87
87

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

APPENDICES

90

A Avida Virtual CPU Instructions

91

B Experiment Settings
95
B.1 Common Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
B.2 Calibration Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
BIBLIOGRAPHY

101

viii

LIST OF TABLES

1.1

Selectionist and neutralist hypotheses for GC:AT biases. Broadly,
there are two diﬀerent ideas about the importance of composition biases: selectionist and neutralist. Selectionists argue that composition biases of genomes
serve an adaptive purpose. Neutralists believe that composition diﬀerences
are the consequence of selectively-neutral processes. . . . . . . . . . . . . . .

3

Environment reward structures used in this chapter. Rewards are
applied multiplicatively when an organism divides and is contingent on successful demonstration of the displayed Boolean logic operations on bit-strings
provided by the environment. . . . . . . . . . . . . . . . . . . . . . . . . . .

29

A.1 Description of default Avida virtual CPU instructions. . . . . . . . .

92

B.1 Common experimental settings used in this work. . . . . . . . . . . .

95

3.1

B.2 Deviant calibration experiment settings. . . . . . . . . . . . . . . . . . 100

ix

LIST OF FIGURES

2.1

2.2

3.1

3.2

3.3

The genome of a default Avidian. Execution of instructions begins at
the pentagram and proceeds counter-clockwise. Forward movement of the
instruction pointer is shown in blue; backward movement is shown in red.
Sites comprising the nop-C backbone are in gray. For interpretation of the
references to color in this and all other ﬁgures, the reader is referred to the
electronic version of this dissertation. . . . . . . . . . . . . . . . . . . . . . .

13

Evolutionary trajectory of an Avida experiment. A. A ﬂame graph
showing the abundance of organisms at diﬀerent phylogenetic depths over
time. Abundances increase from black through red to yellow. The trajectory
of the PLoD is plotted as a cyan color line. B. The ﬁtness trajectory of
the PLoD over time. The color of the markers indicate the stochasticity of
phenotypes as measured in the test environment. . . . . . . . . . . . . . . .

20

Transition matrices. Letters along the axes correspond to virtual-CPU
instructions in Appendix A. A. A Markov transition matrix generated from
point and insertion mutations accumulated during the course of evolution in
the Logic-9 reward structure. B. The near-saturation state of this matrix. . .

26

A comparison of the saturation values of the transition matrix and
corresponding simpliﬁed values used in the INST-3 mutation bias
spectrum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

The evolution of tasks under diﬀerent mutation biases and environment reward structures. A. The number of replicates acquiring each task
under mutation biases: yellow, POS; blue, UNB; red, NEG. B. The distribution
of the number of genetic steps from the ancestor genotype to the ﬁrst acquisition of EQU along the PLoD. Colored boxes show the the inner quartiles; the
median is shown by a gray line. The upper and lower range of the distribution
is shown by dotted lines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

x

3.4

3.5

3.6

4.1

4.2

The distribution of ﬁnal population average ﬁtnesses under diﬀerent
treatments in the Logic-9 environment reward structure. Asterix
markers show distributions signiﬁcantly diﬀerent from the UNB treatment using
a 2-tailed Mann-Whitney U-Test. POS, NEG, and UNB are treatments where
populations are forced to use one mutation bias; the remaining treatments
switch biases from UNB to POS en masse at the times indicated. . . . . . . . .

32

The acquisition frequency of EQU. Colored horizontal lines show the fraction of replicates that evolved EQU in populations that experienced only one
mutation bias (yellow=POS, blue=UNB, red=NEG). Dashed colored lines show
the fraction of replicates that have evolved EQU over time. Green horizontal
bars show the fraction of replicates that have demonstrated EQU at each of
the ﬁve updates during which a switch from POS to UNB occurred. Vertical
green bars show the additional fraction of treatment replicates that acquired
EQU after the swap from UNB to the POS. Treatments that swapped from UNB
to POS where signiﬁcantly more replicates acquired EQU after the swap than
the UNB-only treatment are indicated with an asterisk. . . . . . . . . . . . . .

34

Population-wide genetic composition changes over time relative to
POS and UNB mutation biases. The colored lines show diﬀerent obligate
treatments: blue=UNB only; yellow=POS only; red=NEG only; green=swap
from UNB to POS. Green triangle markers show the point at which the mutation
bias switched for each bias-swap treatment. . . . . . . . . . . . . . . . . . . .

39

Baseline competition results. In the absence of selective pressure, competition outcome will be based solely upon the initial frequency that a particular
bias has in the population. Results that fall above the diagonal line show evidence of positive selection (“wins”) relative to a peer subpopulation; outcomes
below the line show evidence for a selective disadvantage (“losses”) relative
to a peer subpopulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

Competition against UNB in an unstructured population. Initial
competitor abundances (πt ) are shown against competitive success (Ωt ). Yellow, blue, and red lines indicate competitions between UNB and POS, UNB, and
NEG, respectively. Treatments signiﬁcantly diﬀerent than chance (p < 0.05,
2-tailed Binomial Test) are shown by triangle markers; competitions not different than chance are shown by crosses. Dashed lines connecting treatments
are shown to contrast outcome against the neutral expectation. . . . . . . .

46

xi

4.3

4.4

4.5

4.6

Mutation bias competitions with diﬀerent population sizes. Initial
competition seed frequency (πt ) is plotted against the fraction of competitors
that drove UNB competitors to extinction (Ωt ). POS competitions are in yellow; NEG are in red. Lighter colored lines competed in a population of size
3600 whereas darker colored lines competed in a population of size 10, 000.
Unstructured (mass action) and structured (local replacement) populations
are distinguished by dashed and solid lines, respectively. Competition results
that signiﬁcantly diﬀer from chance (p < 0.05, 2-tailed Fisher’s Exact Test)
between population sizes for the same replication method are shown by a
triangle; insigniﬁcant results are shown by a circle. . . . . . . . . . . . . . .

49

Competitions with diﬀerent population structure. Each line above
shows the outcome a series of competition experiments over initial abundance
(πt ) of mutation biases with yellow, blue, and red coloring showing competition between POS, UNB, and NEG biases against UNB, respectively. Experiments
with outcomes signiﬁcantly diﬀerent between structured (local replacement)
and unstructured (mass action) populations (p < 0.05, 2-tailed Fisher’s Exact
Test) are shown by square markers; insigniﬁcant results are shown by crosses.

52

Unevolved and evolved genotype bias competition results. Colored
lines show the results of competition of POS, NEG (yellow and red, respectively)
against UNB. Darker colored lines show competitions using a genotype evolved
under UNB. Lighter colored lines show results from competitions using the
default ancestor. Solid lines show competitions that were structured; dashed
lines show competitions which were unstructured. Triangle markers show
competitions where population structure signiﬁcantly altered outcome (p <
0.05, 2-tailed Fisher’s Exact Test); square markers show competitions where
population structure did not change outcome. . . . . . . . . . . . . . . . . .

54

Competition results using evolved genotypes as compared to neutral outcome. 30 ﬁnal dominant genotypes were taken from experiments
in Section 3.2.1, with 10 from each mutation bias background. Yellow, blue,
and red markers show the outcome of 100 competitions against UNB for POS,
UNB, and NEG, respectively. Each treatment began with the population being
evenly divided between the test bias and UNB. Signiﬁcant wins or losses are
shown by diamond markers (p < 0.05, 2-tailed Binomial Test); ties are shown
by a plus marker. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

xii

4.7

4.8

4.9

Competition results of evolved genotypes under diﬀerent population
structures. Each plot shows the outcomes of competitions for a genotypes
evolved in a particular mutation bias. The color of the markers in each plot
identify the bias being competed against UNB: yellow, POS; blue, UNB; red, NEG.
Genotypes where population structure mattered are shown with a diamond
marker (p < 0.05, 2-tailed Fisher’s Exact Test); unevolved genotypes are
shown with a circle and are signiﬁcant for diﬀerences in outcome between
population structures for POS and NEG competitions. . . . . . . . . . . . . .

60

Mutation bias competitions of evolved ancestors in the presence and
absence of beneﬁcial mutations. Each plot distinguishes competitions for
genotypes evolved in a particular mutation bias background. The color of
the markers indicate the bias competed against UNB: yellow, POS; blue, UNB;
red, NEG. Horizontal axes give the frequency of successful competitions against
UNB in environments with beneﬁcial mutations present; vertical axes show results from environments where beneﬁcial mutants are sterilized. Points falling
within the vertical and horizontal bars about the middle of the plot are not
signiﬁcantly diﬀerent than a chance outcome for competitions with beneﬁcial
and no beneﬁcial mutations, respectively (p < 0.05, 2-tailed Binomial Test,
N =100). Diamond markers indicate where there is a signiﬁcant diﬀerence between outcomes when beneﬁcial mutations are or are not present for a single
genotype (p < 0.05, 2-tailed Fisher’s Exact Test, uncorrected.). . . . . . . . .

62

Comparison of competition winners against mutation bias background of evolved seed genotypes. p-values shown are from 1-tailed
Mann-Whitney U-Tests of same-as-competition background genotypes competition wins compared to wins of evolved genotypes from other mutation bias
backgrounds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

4.10 Correlation of KL-Distance of evolved seed genotypes to competition outcomes. Each plot shows competition results of POS or NEG against
UNB. Beneﬁcial mutations were either allowed or disallowed for each set of
competitions. The color of the markers indicate which background the genotypes evolved under (yellow, POS; blue, UNB; red, NEG). KL-distance is based
on the composition of the genotypes relative to the bias in which they competed, measured in bits. Correlation coeﬃcients (r) and signiﬁcance measures
(p) are shown with each ﬁgure along with a least-squares ﬁt line to the points. 67

5.1

The six-bias mutation spectrum. All biases are derived by modifying
the relative distance between instructions in POS or NEG relative to UNB by a
particular factor, identiﬁed in the legend. . . . . . . . . . . . . . . . . . . . .

xiii

73

5.2

5.3

5.4

5.5

5.6

5.7

Calibration experiments to ﬁnd a good pair of deme size and competition length. Populations of four diﬀerent sizes evolved under each bias
in the three-bias mutational spectrum. How signiﬁcantly diﬀerent the average
population ﬁtnesses are between each bias-treatment using a 1-tailed U-Test
is shown along the vertical axis for each population size (N). Comparisons
between POS and NEG treatments are not shown. . . . . . . . . . . . . . . . .

75

Deme competitions beginning with diﬀerent initial conditions. The
ﬁgures above show the average frequency of each bias in the three-bias mutational spectrum in 30 deme competition experiments over time. Treatment
minimum and maximum are shown with dotted lines about the mean. Each
experiment used 50 demes of 400 organisms with tournament selection every
2000 updates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

Deme competitions having diﬀerent mutation methods. The solid
lines above show the average frequency of mutation biases in 50 demes from
30 replicates. Dotted lines show the minimum and maximum of instruction set
frequencies from the 30 treatments. Two treatments are shown above diﬀering
only in the way mutation bias can change after each round of competition.
Structured mutations limit mutations to immediate neighbors in the six-bias
spectrum. Unstructured mutations allow any bias to mutate to any other in
only one step. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78

The evolution of a mutation bias in a population without demes.
The number of replicates refers to the number of the 300 replicates where
one mutation bias is expressed more than by half of the population. All
populations began with organisms all having the UNB bias. . . . . . . . . . .

80

Average ﬁtness distribution in single bias experiments. The 2×POS
and UNB treatments had statistically identical ﬁnal population average ﬁtnesses (p = 0.075, 2-tailed Mann-Whitney U-Test) . . . . . . . . . . . . . . .

81

Average distribution of mutation eﬀects around random viable
genotypes. Each line in the graph above shows the average probability
of a type of mutation around random viable genotypes from 100 replicates
sampled every 5000 updates. The type of mutation is identiﬁed in the legend.
Colored lines show the diﬀerences in distribution of mutation eﬀect under POS
(yellow), UNB (blue) and NEG (red). . . . . . . . . . . . . . . . . . . . . . . .

82

xiv

6.1

The evolution of mutation biases over diﬀerent mutation rates. Each
plot shows the number of replicates (out of 300) where a single mutation bias
dominates in the population. 27 biases were allowed: UNB and a bias where
a single instruction had an inﬂow rate 10 higher than the others. The legend
shows the biases that a relatively high number of replicates preferred. The
title for each plot shows the scaling of the rate of substitution from the default
in Appendix B.1. Insertion and deletions were not scaled. . . . . . . . . . .

xv

89

CHAPTER 1
An Introduction to Mutation Biases
Mutation is one of the primary drivers of genetic change. Along with recombination and
gene transfer, it creates genetic variation that selection can act upon. As the variation in
genomes aﬀects how species adapt to their environment, an understanding of the eﬀects of
mutation is crucial in understanding how organisms evolve.

1.1

What is a mutation bias?

I deﬁne a mutation bias to be a distribution of inﬂow probabilities for each possible genetic
state (a nucleotide, amino acid, or Avidian instruction) per mutation event. In this work, I
focus on two mutation events, insertions and substitutions. During each of these events, a
speciﬁc site in the genome (a new site for an insertion or an existing site for a substitution)
adopts a particular state with a ﬁxed, unconditional probability. The set of probabilities for
all possible states is a mutation bias.
This is a simple model for mutation rates with a few important features that I want
to highlight. First, for substitution events, I assume that the probability for each new
state is independent of the original state. Second, I do not include any mechanism to
repair mutations. Third, in my substitution model, it is possible for the resulting state of
a substituted site to be the same as before the mutation event. Finally, I have deliberately
separated mutation rate from mutation bias. The rate that mutations occur is independent
of the probability distribution for the new state. In nature, mutation bias, mutation rate,
and how individual nucleotides mutate to one another are inherently tied together. However,

1

this simple model allows me to isolate and clearly illustrate the eﬀects of mutation bias.

1.2

Is mutation bias an adaptation for evolvability?

Because mutation can produce selectable variation, mutation bias may be a selectable trait
that confers evolvability, the ability to leverage or mitigate the eﬀects of genetic change.
This dissertation examines whether mutation bias meets the criteria to be an adaptation for
evolvability.
In order for mutation bias to serve as an adaptation for evolvability, it must be heritable,
variable, and selectable. In this dissertation, I make mutation bias a fully heritable trait in
my organisms. This is partially supported in the natural world. For example, mutation bias
(along with rate) is partially heritable by virtue of the DNA replication and repair machinery
encoded in any organism’s genome. Of course, mutation bias is aﬀected by other elements
such as the inherent mutability of the genetic substrate and the particular environment the
organism exists in. In this work, I make mutation bias variable by creating a limited number
of diﬀerent mutation biases an organism can have.
This leaves selectability. Determining the selectability of mutation bias is the primary
focus of this dissertation. It is not entirely clear that mutation bias can be selectable. Certainly, a particular bias might create beneﬁcial mutants that will allow the bias to hitchhike
to ﬁxation in a population; however, the beneﬁt conferred by a mutation bias (e.g. the set
of genetic changes) might be so uncoupled from its consequence (the discovery of a novel,
adaptive trait that selection can act directly upon) as to have the fate of the mutation bias
left to chance. This observation implies that mutation bias is something that can only inﬂuence long-term evolution and is not something that competition at the individual level
would be able to distinguish.

2

Selectionist

Neutralist

Amino acid composition is driven by GC content [1, 37, 43].

GC content correlates positively with “ambivalent” amino acids [15].

Protein-coding regions are positively correlated with GC content [27].

Third codon sites are most correlated with genomic GC [27].

GC content might help with DNA thermostability in hostile environments [3].

Only structural RNA GC content is correlated
with temperature [17].

Strong mutation bias can lead to the selection
of non-optimal novelty [45].

Mutation is a weak pressure in mutationselection balance [37, 45].

GC:AT content diﬀerences might be due to a GC:AT content diﬀerences are the result of
competition for resources [33].
neutral processes [44].
Table 1.1. Selectionist and neutralist hypotheses for GC:AT biases. Broadly, there
are two diﬀerent ideas about the importance of composition biases: selectionist and neutralist. Selectionists argue that composition biases of genomes serve an adaptive purpose.
Neutralists believe that composition diﬀerences are the consequence of selectively-neutral
processes.

1.3

Previous work on mutation bias

Previous work on mutation bias falls into three primary categories: the observation of compositional biases in organisms, the causes of compositional biases in organisms, and the
consequences of compositional biases in organisms. The majority of work focuses on the
observation and causes of compositional biases in bacterial chromosomes. The work on consequences of compositional bias covers a broader range of species. Table 1.1 highlights some
potential hypotheses of variable GC:AT biases.
Genetic diﬀerences of GC:AT content in bacteria were observed as early as the late
1950s. While looking for correlations between DNA and RNA in bacteria, Belozersky and
Spirinfound found there to be a variety of GC:AT ratios from the 19 bacterial species they
examined, ranging from ratios of 0.45 ± 0.02 to 2.73 ± 0.02 [2]. Other ratios, purine to
pyrimidine (AG:CT) and GT:AC showed no major deviation from 1.0 for all examined

3

species, owing to Watson-Crick pairings.
To explain this diﬀerence in GC:AT content, two researchers independently theorized that
the composition bias is the result of a varying mutation bias operating under equilibrium
(selectively-neutral) conditions [13, 39]. There is evidence to support this hypothesis as
GC:AT biases are especially noticeable in relatively neutral parts of the genome (e.g. spacers
and third-position sites in codons relative to chromosomal regions producing structural RNA
[27]). Consequently, mutation bias is potentially important for neutral evolution [40].
There are many causes of mutation bias in nature, due to both inherent DNA instability
and the capability of replication and repair enzymes. One of the most cited reasons for a
GC:AT bias is the inherent instability of cytosine, which creates an asymmetric pressure
away from GC to AT pairs. In its methylated form, cytosine mutates via deamination to
thiamine, creating a transition mutation. When it is not methylated, it deaminates into
uracil, a correctable state provided appropriate repair enzymes are available. As such, DNA
has a natural propensity to mutate toward a higher AT content.
However, repair mechanisms are not always available nor is there a unidirectional preference for higher AT content, as is the case with the mutT E. coli strain. mutT mutants
were created through X-ray induced mutation and discovered to have a three-fold higher
mutation rate than the wildtype [41]. The higher mutation rate produced an increase in the
number of mutations from AT→GC, increasing the genomic concentration of GC [6]. The
mutT enzyme, knocked out in mutT strains, provides protection from mutation by degrading a potential mutagen, 8-oxodGTP, an oxidized form of the nucleotide guanine [24]. In
the absence of the mutT enzyme, as caused for example by an insertion element-induced
knockout in the original mutT strain [4], 8-oxodoGTP can pair with either cytosine or adenine, potentially leading to a transversion during subsequent replication if not detected and
repaired by additional enzymes [10].
There are other potential causes of mutation bias. Because mutation is more likely in
single-stranded than double stranded DNA (at least for cytosine and adenine) [12, 23, 19],

4

the location of a nucleotide relative to the origin and terminus of replication [26, 25], the
strand the nucleotide occupies [26, 22], and the frequency it is transcribed [11] are all factors
in determining both the rate and direction of mutation.
I now consider prior work that studies the consequences of GC:AT biases. Several papers
have examined how GC:AT content aﬀects protein encoding. Even before the discovery of
codon mapping, researchers observed a correlation between genome GC content and protein
amino acid content [38]. Using the often degenerate third position of a codon as a metric
for directional mutation pressure between GC and AT nucleotide content, many authors
have found that a strong positive correlation between genomes with high third position GC
content and the amino acids glycine, alanine, arginine, and sometimes proline (GAR[P]) and
negative correlation with phenylalanine, tyrosine, isoleucine, lysine, and sometimes methionine (FY[M]INK) [38, 18, 15, 35, 1]. Providing more direct evidence for a causal role for
mutation, research has found a strong substitution asymmetry favoring GARP to FYMINK
in GC-rich and GC-poor homologs between two divergent species [43]. The extent to which
changes in amino acids are driven by mutation bias under neutral evolution [35, 43, 15] or
selection for protein function [1] is not completely known.
There have been suggestions that GC content is directly selected and not just the byproduct of mutation bias. One possible reason for GC content being directly selected is that GC
rich regions of chromosomes tend to be more thermally stable than AT rich regions. This is
because a GC pair has three hydrogen bonds where as AT only has two [42]. This hypothesis
is supported by the observation that “warm-blooded” vertebrates tend to have more GC-rich
regions (isochores) than “cold-blooded” vertebrates [3]. There is also a link between optimal
growth temperatures for eubacteria and archaea with the GC content of their structural
RNAs (but not the GC content of their genomes) [17]. Alternately, there is a hypothesis for
direct selection of higher AT content genomes to reduce the energy needed to replicate [33].
Finally, there has been little direct evidence from previous work that mutation bias can
cause change in evolutionary outcomes. There is no work from natural systems because of

5

the diﬃculty in manipulating mutation bias in natural systems. The only previous work I
am aware of are two relatively simple computational model studies. In the ﬁrst study, with
an extremely simple model, the authors show that extraordinarily biased mutation rates
can lead to non-optimal selective outcomes in small populations [45]. Several years later,
one of the authors further explored this topic using an NK model [37]1 . He showed that a
model with an alphabet of four “nucleotide” states and a translation step to map codons
into “amino acids” could lead to an evolved bias in amino acid composition. However, it
is important to note that the only meaning for nucleotides and amino acids is captured by
the codon encoding and associated random ﬁtness values. In particular, the result seems to
follow directly from the codon encoding used in the study.

1.4

Can mutation biases confer evolvability?

In order for mutation bias to have an evolutionary aﬀect, it must be shown that applying
a mutation bias can change the outcome of evolution in obligate populations. For it to be
evolvable, it must both be something that selection can distinguish and be itself heritable
and mutable.
As discussed above, there is evidence to suggest that mutation bias in nature ﬁts these
criteria. Mutation bias has been implicated in altering protein composition. It has also been
shown to be modulated (along with mutation rate) by the presence of diﬀerent replication
and repair enzymes and cytosine methylation. Consequently, mutation bias in nature can be
derived in part from the product of genes which are themselves evolving. What is missing
from the studies discussed above is direct evidence that mutation bias, in a non-trivial
system, can meet these three criteria.
In this body of work, I directly test whether or not mutation bias can be a selectable trait
for evolvability. To do so, I show that applying a mutation bias can lead to diﬀerent rates
1 In

an NK model, ﬁtness is determined from the combined contribution of N sites with
each site having K interactions with other sites [20].
6

and scope of environmental adaptation. I also show that the eﬀects of diﬀerent mutation
bias can be distinguished by selection. Finally, I show that mutation bias, given a mutable,
heritable representation, can be consistently selected by individuals in a population.

7

CHAPTER 2
Avida: A Digital Life Model
Studying evolution under experimental conditions is a challenge. The timescale over which
evolution occurs is typically orders of magnitude more than the length of a graduate program. Consider an extreme example: suppose one wants to examine how a herd of elephants
evolves some novel adaptation to an environmental change. Elephants are not capable of reproduction until they reach about thirteen years of age, and their gestation time is 22 months.
Considering it generally takes many generations for a phenotype to ﬁx in a population, using
elephants to study novel trait evolution is clearly infeasible. To test any evolvability claim
would require ﬁnding (or producing) a reliable control herd that lives without the environmental change doubling these problems, albeit in parallel; even then the statistical power
from such an experiment would be quite low.
It is for these reason researchers choose to study evolution in laboratory model systems with much shorter gestation times: fruit ﬂies, microorganisms, and the like. However
these systems are also fraught with their own idiosyncratic problems. Organic systems require careful maintenance of their support equipment, routine checks for contamination, and
multiple physical resources to test experimental hypotheses. Added all up, a single set of
evolution experiments could easily create many years worth of work in up-keep alone, to say
nothing of the time and resources it takes to collect and analyze data. The dividends of such
experiments may well be worth the costs; but broad examinations of evolutionary theories
over multiple dimensions become cumbersome. Digital life helps mitigate these problems by
providing a more tractable and less resource-intensive platform to explore a wide variety of
evolutionary hypotheses.
8

Digital life is largely deﬁned by the self-replicating computer program. Such programs
contain machine code capable of instructing the hardware they are instantiated upon to replicate. They may also be evolved to solve problems by introducing mutations and providing
ﬁtness beneﬁts for demonstrating good solutions. A number of diﬀerent software packages
enable such programs to “live” inside a computer. Perhaps the most famous early digital life
package is Tierra [32]. Organisms in Tierra are machine code programs that share a common
memory space “soup”. Tierra itself acts like an operating system, allocating CPU time for
each organism to replicate and “reaping” old organisms to keep space available for oﬀspring.
Digital organisms in the simplest Tierra environment evolved to optimize their replication
algorithm and to exploit other organisms to reproduce faster.
For my experiments, I chose to use the digital evolution platform Avida [29]. Avida
follows in the footsteps of Tierra. Unlike Tierra’s “soup”, Avida enforces a strict separation
of each organism’s memory space. This helps keep asexual lineages identiﬁable and fosters
an easier understanding of the causes of adaptive change. This chapter will be devoted
to a description of the terms used throughout this work, Avida, and the methods used to
implement the experiments in the following chapters.

2.1

Avida

Avida is a software package that allows researchers to explore evolution through experimentation using digital organisms. Digital organisms in Avida experience competition for limited
resources, inheritance, and genetic mutation; therefore they are capable of evolving adaptations to their environment. Avida allows the researcher to tightly control environmental
conditions and easily observe resulting population responses, allowing for hypotheses that
are diﬃcult to study in natural systems to be readily explored.
An Avida experiment can be thought of as a digital analogue of a microbial experiment.
An Avidian is a digital organism. It is comprised of two parts: a sequence of virtual CPU

9

instructions (its genome) and a virtual CPU (its biological equipment). Everything outside of
an organism is its environment. The organism’s environment provides an essential metabolic
resource called SIPs (Single Instruction Processing units [21]), which give the organisms
the ability to process their genome. How many SIPs an organism receives depends upon
how it interacts with the environment to produce products or behaviors established by the
researcher. The composite of these products and behaviors deﬁnes an organism’s phenotype.
The genome is the heritable substrate in Avida. It is comprised of 26 diﬀerent virtual
CPU instructions. Like a bacterial chromosome, it is circular, so that the ﬁrst instruction
in the genome follows the last. These instructions are capable of changing the internal
state of the virtual CPU and are Turing-complete. Roughly, these instructions are split
into four diﬀerent classes: no-operation/behavior modiﬁcation, genome-processing control,
reproduction, and numerical operation. Appendix A provides a detailed description of the
function of each of these twenty-six instructions.
The concepts of gene and locus in Avida are less clear than in microorganisms. To
avoid ambiguity, I will use the word site when discussing a particular location in an Avidian
genome. The length of a genome is simply be the number of instructions it contains.

2.1.1

Avidians: genomes and life-cycles

Figure 2.1 depicts an Avidian genome and how it is processed in one generation. The virtual
CPU (not shown) that processes the genome contains three diﬀerent registers, two stacks
(currently capped at ten elements), four specialty pointers that identify diﬀerent locations
in the genome, and a special purpose register that traces the most recent sequence of nop
instructions read during replication.
Execution of an organism begins with the virtual CPU being reset so that all four specialpurpose heads (the instruction pointer, the read, write, and ﬂow heads) point to the ﬁrst
site in the genome, labeled with a star in Figure 2.1. All registers are set to the value
zero and the stacks are empty. When the organism receives a SIP, a quantum of metabolic

10

energy in Avida, it processes the instruction at the site pointed to by the instruction pointer.
Depending on the identity of the instruction, mathematical operations may be carried out,
the environment may provide input or receive output, or the state of the virtual CPU’s
stacks, registers, or heads may be altered. Unless the instruction explicitly alters the state
of the instruction pointer, the instruction pointer moves to the next site after processing.
When the instruction pointer reaches the end of the organism’s genome, it is moved to the
start. This makes an Avidian genome circular.
The organism depicted in Figure 2.1 is the ancestor used to seed many of the experiments
in this work. It consists of two functional components: an initialization module at the start
of the genome that prepares the organism for replication; and a copy-loop at the end of the
genome that copies the individual instructions in the genome to the oﬀspring’s memory. A
long “backbone” of the virtual CPU instruction nop-C occupies the space in the genome
between these two sections. The nop-C backbone provides blank space for adaptations to
evolve.
The h-alloc instruction at the start of the organism’s initialization module causes the
virtual CPU to append nop-A instructions to an organism’s genome, tripling the genome’s
length. The ﬁrst part of the genome also uncouples the read and write-head, the former still
pointing to the ﬁrst instruction in the genome and the latter moved to the ﬁrst site to receive
an instruction copied from the parent genome. The action is accomplished by the h-search
instruction using nop templating, wherein a speciﬁc pattern of nops, complements of the
nops located after the h-search instruction, are located within the genome. The h-search
instruction places the ﬂow-head (the ﬁnal of the four genome pointers) after that pattern.
The mov-head instruction then places the write-head at the location of the ﬂow-head. This
prepares the genome for copying, since the read-head is at the start of the genome and the
write-head is now at the start of the newly allocated space for the oﬀspring.
In the default organism in Figure 2.1, all copying from the parent genome to what will
become the oﬀspring occurs in the copy-loop at the end of the parent genome. The copy-loop

11

contains the h-copy instruction, which copies the instruction at the site pointed to by the
read-head to the site pointed to by the write-head. As nop instructions are copied, their
identities are noted and stored in a special purpose label register. This register is used by
the instruction if-label to change the behavior of the instruction pointer to conditionally
process pieces of code. When a non-nop instruction is copied, the label register is cleared.
The copy-loop of the genome depicted in Figure 2.1 terminates when the instructions
at the end of the genome are copied because the h-divide instruction gets processed when
the complement of the nops located after the if-label instruction in the copy-loop gets
copied to the oﬀspring’s genome. Although h-divide can be processed at any time, it will
not be successful unless speciﬁc conditions, set in the experiment’s conﬁguration, are met.
These conditions include the number of instructions processed and the number of instructions
copied. Processing h-divide before these conditions are met consumes SIPs but performs
no work.
Once h-divide is successfully processed, the oﬀspring’s memory is cleaved from the
parent’s genome by using the position of the read and write-heads to deﬁne the beginning
and end of the oﬀspring genome. Any excess instructions allocated by h-alloc are removed.
Avida then provides the oﬀspring genome its own piece of virtual hardware and places the
organism into the population. Since the oﬀspring has not processed its genome, it initially
receives the same number of SIPs as its parent.

2.1.2

The Avida population, environment, and organism ﬁtness

The world that the Avidians occupy may be thought of as a virtual Petri dish. Typically
this world contains a matrix of cells that only a single Avidian may inhabit at a time. These
cells are linked together to form a torus – a borderless two-dimensional shape. This world
can be further subdivided into isolated subunits called demes. Chapter 5 will make use of
demes to select mutation biases.
A population is the collection of organisms occupying the world at a particular time.

12

C

no

p−

no

p−
C

p−

C

C

no

nop
−

nop−C

nop−C

nop−C

C
p−
no
C
p−
no
−C
nop
nop−C

−C

p
no

C

−
op

−C

no
p

n

C
p−
ad
no
he
v−
mo
−A
nop
C
nop−
h−search

−C

no
p

C

p−

no

nop−
C
nop
−C
nop−C

nop−C

h−alloc

nop−C

nop−B

nop−

nop−

C

A

nop

mo

−C

p
no

no

p
no

l
be

la

if−

h

−C

arc

py

co
h−

se
h−

nop

nop−C

nop−C

nop−C

nop−C
nop
−C
no
p−
C
n
op
−C
n
op
−C

v−h
ead
h−
div
ide
no
p−
no
A
p−
C

−C

C
p−

−C

Figure 2.1. The genome of a default Avidian. Execution of instructions begins at the
pentagram and proceeds counter-clockwise. Forward movement of the instruction pointer is
shown in blue; backward movement is shown in red. Sites comprising the nop-C backbone
are in gray. For interpretation of the references to color in this and all other ﬁgures, the
reader is referred to the electronic version of this dissertation.

13

As organisms reproduce, their oﬀspring are placed in the virtual Petri dish, many times
displacing and killing an existing organism. The speciﬁc placement of an organism upon
its birth depends on settings established by the researcher. Typically, oﬀspring are either
placed randomly in the world to produce unstructured populations or in one of the cells
immediately adjacent to the parent (without concern for the properties of the organism the
oﬀspring may be replacing) producing structured populations.
Organisms that reproduce faster will occupy an ever increasing amount of the digital
Petri dish, and eventually drive all other clades extinct unless frequency dependent selection
is possible, such as when there are multiple limited resources. For this work, it is the
competition for space that drives selection.
The duration of an Avida experiment as well as the timing of researcher-speciﬁed events
is often measured in a unit called an update. Updates may be thought as the time it takes
a population to exhaust a ﬁxed supply of SIPs. Typically, when an organism receives a SIP,
it is able to process the next instruction in its genome on its virtual CPU. The number of
SIPs available in any update is dependent on the population size. For experiments in this
work, the total number of SIPs available per update is 30 times the number of organisms in
the population. How the total number of SIPs in a given update is allocated to individual
organisms creates relative processing speed diﬀerences within the population.
An organism-speciﬁc value called merit determines how many SIPs the organism is given
in per update. Going back to the bacterial experiment analogy, merit may be thought of
as the “metabolic” rate of the organism. The higher its value compared to its peers, the
“faster” an organism processes its genome. Merit is initially set to be proportional to the
minimum of either the number of instructions the organism processes in order to divide or
the number of instructions it copied into the genome of its last oﬀspring. In practice, this
prevents organisms from being penalized for having longer genomes. Additional merit may
be gained by environmental adaptation.

14

Merit is thus deﬁned as:

T

M = M0

Bt

(2.1)

where M0 is proportional to number of SIPs processed prior to replication or oﬀspring length,
T is the set of observed adaptations that are rewarded with an associated multiplicative
increase of magnitude Bt .
The environment in Avida is everything “outside” of an organism. In its simplest form,
the environment supplies organisms with SIPs and requested pseudo-random bit strings.
This simple environment also examines the bit strings that an organism produces when it
processes an instruction that outputs a bit-string. Since the environment keeps track of both
the inputs an organism receives and the output it sends, it is possible to treat the organism as
a black box that maps inputs into outputs. By adjusting merit based on observed mappings,
organisms receive a diﬀerent number of SIPs, eﬀectively changing the relative speed at which
they operate.
Researcher-deﬁned mappings are called tasks. Typically tasks are either simple mathematic or Boolean logic operations, but they can also be complex behaviors or interactions.
The set of tasks and their associated merit adjustments deﬁne the reward structure of the environment. The most common reward structure used in an Avida experiment is the Logic-9,
shown in Table 3.1. In the Logic-9, performing any of nine Boolean logic tasks provide merit
rewards. The size of the reward roughly is based on the complexity of the individual tasks,
as deﬁned by the number of NAND operations required to perform each operation. Merit
rewards are applied multiplicatively to the merit of an organism. There is a maximum of
one reward per task per organism and no limit on the number of organisms that can be
rewarded for performing the task. Consequently, organisms which perform a large number
of complex tasks are selectively advantageous in the Logic-9 environment.
The absolute ﬁtness (ω) of an organism is the ratio of its merit to its replication eﬃciency:
M0 T Bt
M
=
ω=
τ
τ

15

(2.2)

where M is the merit of the organism as deﬁned in Equation 2.1, and τ is the number of
SIPs needed for replication. Unlike a genetic algorithm, which typically use explicit ﬁtness
functions to determine which genomes get propagated to the next generation ﬁtness in Avida
is implicit, with the environment providing metabolic rewards to organisms for performing
tasks. In Avida, high absolute ﬁtness does not guarantee survival; Avida is ﬁtness-agnostic
when it comes to replacing organisms with newly created oﬀspring. Consequently, organisms
with high absolute ﬁtness may be replaced by less ﬁt organisms.

2.1.3

Instructions, mutations, and mutation biases

Mutations occur during replication in the form of substitutions, insertions, and deletions.
The rates of these mutations are established by the researcher at the start of the experiment
and may be modiﬁed mid-experiment.
Unlike the four nucleobases in DNA or the standard 20 amino acids in proteins, Avida
typically uses a 26-letter genetic alphabet with the symbols a-z mapped to each instruction.
Further diﬀerent from natural systems, there is no translation step between genome and
function in Avida; instruction identity is atomic, although the behavior of an instruction
may be modiﬁed by other instructions (particularly no-operation or nops) anywhere in the
genome. For example, the presence of a nop-A immediately following an add instruction will
change which virtual register receives the summation. Appendix A deﬁnes the behavior of
each instruction as well as how its behavior is modiﬁed by the presence of nop instructions
at various places in the genome.
A collection of virtual CPU instructions and any metabolic or mutagenic properties associated with each instruction deﬁnes an instruction set. For the purposes of the experiments
in this work, all mutation biases are represented by predeﬁned instruction sets. I use the
term “mutation bias” to refer to a single instruction set with a distinct set of mutagenic
properties for each instruction. A mutation bias skews the probability of substitution to or
insertion of each instruction from parent to oﬀspring.

16

Although mutations may occur to an oﬀspring’s genome either during replication or after
dividing from the parent, the experiments in this work apply substitutions during instruction
copying and insertion and deletions (indels) occurring during division.
When a substitution or insertion occurs, a new instruction is drawn at random from the
instruction set. By default, every instruction has the same chance being selected. However,
the mutation probability for each individual instruction may be altered by changing its
redundancy in the instruction set. An instruction’s redundancy is simply its abundance in
the instruction set. The higher an instruction’s relative redundancy (abundance), the more
likely it is to be drawn from a random sample of the collection.
Another diﬀerence between Avida and natural systems is that there is the possibility of a
substitution occurring and not altering the oﬀspring’s genome. Since mutation outcomes are
based on relative abundance of instructions in the instruction set, there is a possibility that
a mutation occurs but produces no change in the genome. This decouples the researcherspeciﬁed mutation rate and the actual mutation rate. Consequently, the mutability of a
particular site depends on the instruction at that site and its redundancy. For a particular
site with instruction i, its rate of mutation is (1 − pi )µ, where pi is the relative probability of
picking the instruction and µ is the substitution rate. The diﬀerence between the speciﬁed
and actual mutation rate will become important when I discuss the reason for the selection
of a mutation bias in Chapters 4 and 5.
The manner in which instruction sets with diﬀerent redundancies (mutation biases) are
inherited and mutate diﬀer between experiments. In Chapter 3, a single mutation bias
will be applied to populations as a whole to ﬁnd the diﬀerences in evolutionary behavior
of obligate populations under diﬀerent mutation biases. In Chapter 4, multiple mutation
biases are present in the population and are inherited perfectly from parent to oﬀspring.
Both inheritance of multiple mutation biases and the mutation between biases is allowed in
the experiments in Chapter 5 by specifying an additional mutation parameter, µb , which is
the probability that the bias will be altered during transmission from parent to oﬀspring.

17

2.2

An Avida experiment

Each Avida experiment is an instance of evolution [31]. During the course of an experiment,
a researcher can capture a variety of information. Some examples include the average ﬁtness
of the population, the kinds of adaptations present, and the evolutionary history of each
organism in the population. Figure 2.2 contains plotted data from one of the experiments
in Chapter 3. This experiment will serve as a case-study of a typical Avida experiment.
Each Avida experiment is an independent instance of digital organism evolution. In order
to test the eﬀects of diﬀerent treatments, experiments are often repeated multiple times
with identical conﬁgurations. A single integer value, called a seed, diﬀerentiates replicates
by initializing a random number generator to produce diﬀerent values when stochasticity is
required. For example, the placement of an organism in the population or which sites in
the genome get mutated depend on the values produced by the random number generator.
Since all of the stochasticity in each experiment depends only upon a single random number
seed, an experiment may be repeated multiple times with the same outcome.
As all organisms in the initial population are of the same ﬁtness, Avida gives each organism the same probability of receiving a SIP. As the clones process their code, they will
begin to copy their genome. It takes the default ancestor 189 SIPs to create a copy of itself
(τ in Equation 2.2). As described above, this process involves four steps: (1) allocation of
oﬀspring memory, (2) conﬁguration of the virtual CPU to begin copying, (3) copying each
instruction from parent to oﬀspring, and (4) termination of the copy process when the instruction h-divide is processed. During the copying of an instruction, it may be mutated
prior to being written to the oﬀspring’s genome. During division, additional instructions may
be inserted or deleted from the oﬀspring genome. These substitutions and indels provide
heritable variation for selection to act upon. Following replication and division, the parent
and oﬀspring CPUs are reset to their initial state with merit updated based on the tasks the
parent has completed.

18

At the end of the ﬁrst few updates of an Avida experiment, some organisms will have
gained more SIPs than others due to chance. This set of organisms will have a greater chance
of propagating to the next generation. As the experiment proceeds, mutations accumulate
in the genome and may inﬂuence either the eﬃciency of replication or the merit (τ and M
in Equation 2.2). If these organisms are not overwritten, they will sweep the population by
replacing all organisms with their relatively more ﬁt descendants.
Avida experiments proceed until a researcher-speciﬁed condition is met. Typically this
is a limit on the update time or average generation count of the population. In Chapter
4, experiments are set to terminate when one of two subpopulations drives the other to
extinction. By the end of an Avida experiment, the handwritten ancestor will have adapted
to the environment. These adaptations may not be optimal or exploit the environment
completely; the maximum population ﬁtness at the end of each experiment will vary for the
same experimental setup.
When examining the historic path of a population, the primary line of descent (PLoD) is
often used. This line of descent begins with the default ancestor and contains each ancestral
genotype produced throughout time until the ﬁnal dominant genotype in the population at
the end of the experiment is reached. Each step along this line of descent is at a diﬀerent
genetic depth: the number of distinct genotypes beginning with the handwritten ancestor at
depth 0. The PLoD is stored during the course of the experiment and may be analyzed afterward. Figure 2.2-A shows the relationship of the PLoD to the rest of the Avida population
over the course of an experiment.
Each genotype in the PLoD may be examined at the end of an experiment for historic behavior; they may also be re-examined in a virtual test environment. Many times the behavior
of a genotype may be more complicated than its history suggests. For example, phenotypic
stochasticity, the random ability for a phenotypes to emerge, is possible. Phenotypic stochasticity can alter an organism’s ﬁtness because of genome-environment interactions altering
gestation time or task demonstration. To test for phenotypic stochasticity, I loaded genomes

19

Phylogenic Depth

A

Fitness [log]

B

250
200
150
100
50
0
20

All Tasks Evolved

15

1.0
0.8
0.6
0.4
0.2
0.0

10
5

Stochastic Phenotype

0
−5

0

20

EQU Evolved

40
60
Update [×103 ]

80

100

Figure 2.2. Evolutionary trajectory of an Avida experiment. A. A ﬂame graph
showing the abundance of organisms at diﬀerent phylogenetic depths over time. Abundances
increase from black through red to yellow. The trajectory of the PLoD is plotted as a cyan
color line. B. The ﬁtness trajectory of the PLoD over time. The color of the markers indicate
the stochasticity of phenotypes as measured in the test environment.
on the PLoD into a virtual test environment and fully-processed them 1000 times. Phenotypes are marked unique if they have a diﬀerent set tasks, a diﬀerent number of times tasks
performed, or if gestation time is diﬀerent among all tests. I classify genotypes as being
stochastic if they posses more than one phenotype after analysis; otherwise I declare them
to be static. Figure 2.2-B shows the ﬁtness behavior of our case-study experiment with
the color of colored markers indicating phenotypically stochastic genotypes and annotations
showing which tasks are being performed.

20

2.3

Experiment-speciﬁc features

Additional features that will be used in the experiments in this work will be introduced when
they are used. These include the ability to switch mutation biases for the entire population
in Chapter 3, the ability to have multiple mutation biases in a population in Chapter 4, and
the ability for individual organisms to possess and mutate between diﬀerent mutation biases
using both multiple demes and single population setups.

21

CHAPTER 3
The Adaptive Consequences of
Mutation Bias
Adaptive evolution requires mutation, inheritance, and selection. Altering the outcome of
any of these three processes has the potential to change the evolutionary trajectory of a
population in a non-trivial manner. Consequently, biasing the ability of a population to
sample its genetic landscape has the potential to alter evolutionary adaptation. In order for
a mutation bias to evolve as an adaptation, a bias must (1) alter evolutionary adaptation in
a beneﬁcial manner, (2) be visible to selection, and (3) be subject to heritable variation. In
this chapter, I explore the ﬁrst of these three requirements.
To begin, I created a pair of potentially advantageous and disadvantageous mutation
biases using information from evolving populations. I then examined the ability of these
mutation biases to alter ﬁtnesses, evolve complex tasks, and transform genetic compositions
of obligate populations. Taken as a whole, these experiments demonstrate that there exist
mutation biases that are able to beneﬁcially alter the evolutionary trajectory of populations
of digital organisms.

3.1

Creating a favorable mutation bias

Given that most changes in a genome are deleterious, deriving a mutation bias that will
allow populations to adapt to their environment better than chance requires information
about the environment and its eﬀects on the population’s genetic composition. There is no

22

a priori expectation that a random mutation bias will serve any adaptive eﬀect. As such, I
used information about successful mutations to identify a beneﬁcial mutation bias.
In order to ﬁnd a potentially beneﬁcial bias, I began by employing the methodology
used to create the Dayhoﬀ PAM matrix (an amino acid substitution matrix) using the
virtual instructions in Avida. I then removed some of the restrictions of the PAM-matrix
methodology and derived a single vector of mutation inﬂow rates probabilities. From this
vector, I created the two mutation biases used in this chapter: the positive (POS) and negative
(NEG) biases.

3.1.1

Dayhoﬀ PAM-like matrix

The inspiration for using a mutation bias to improve evolution came from earlier work to
create a Dayhoﬀ PAM-like matrix for Avida [7]. The PAM-matrix is hand-created amino
acid substitution matrix for protein residues a particular PAM distance apart. PAM distance
is deﬁned by the number of “accepted” amino acid substitutions per 100 residues between
two proteins1 . Consequently a PAM-N matrix deﬁnes the likelihood of some amino acid
i being substituted by amino acid j in proteins a PAM distance N apart. Because the
history any two residues are not rooted in the creation of the PAM matrix, the PAM-N
matrix is bidirectionally tabulated. That is, the count of substitutions from i → j = j → i.
Traditionally, the PAM-250 is used in maximum likelihood estimations; though to some
extent newer bioinformatic applications substitute the PAM matrix with another type of
transition matrix, the BLOSUM-62 [16].
One of the nice summary statistics from the Dayhoﬀ PAM matrix is its asymptotic
“steady state” at large PAM distances. By applying the PAM matrix many times (or taking
its ﬁrst eigenvector), the distribution of ﬁnal states of transition becomes uncoupled from
initial conditions. This vector is the theoretical distribution of amino acid states between
1 “Accepted”

is not a well-deﬁned term. Dayhoﬀ and Schwartz deﬁne it to be when a
mutation becomes the “new predominant form” for a species.

23

well-separated residues. I exploited this property to create the mutation biases I will use in
later experiments.
Using Avidian genomes instead of protein sequences, I repeated Dayhoﬀ’s method to
create a transition matrix, albeit with slight modiﬁcations. To begin, I evolved a set of
20 replicates populations under the Logic-9 reward structure. I list those few non-default
conﬁguration settings in Appendix B.2, though it doesn’t vary much from the default Avida
setup. To get an equivalent to a PAM-1 matrix, I collected whole populations and their
evolutionary history from each replicate every 100 updates. At the end of the experiment, I
combined these populations and their evolutionary history into a single genetic tree, which is
a sample of the entire evolutionary history of the population. Depending on how I tabulated
the substitutions, I was able to get diﬀerent types of transition matrices.
Unlike Dayhoﬀ’s amino acid substitutions, the evolutionary history of each genotype in
Avida is perfectly encoded. Consequently, two assumptions could be relaxed in creating
an Avidian PAM-like matrix: bidirectionally (so i → j = j → i) and the assumption of a
PAM-distance (since the distance between any two genotypes need not be inferred). These
simplifying assumptions made the tabulation of transition matrices easier and provided a
clearer means of interpreting the resulting matrix. Instead of the resulting matrix representing distances 1 PAM apart, the individual transition probabilities the possibility of a
non-lethal mutation from instruction i to instruction j within a single generation.
From the historical information contained in the population samples, I created two different matrices M bi and M uni , where I used bidirectional and unidirectional tabulations,
respectively. For either matrix Mi,j is the probability of an instruction i mutating to instruction j during replication. I created the bidirectional M bi by equating transitions between
instructions i and j. The bidirectional matrix is not a symmetrical matrix (Mi,j = Mj,i )
because each row i is normalized by the total number of i → j transitions observed. I created
a second matrix M uni by keeping the tabulations unidirectional.
Both methods have some merit: bidirectional assumes some degree of neutrality for

24

substitutions (as assumed in the PAM matrix [7]) and unidirectional captures the exact
evolutionary trajectory of the population. I chose to use the bidirectional matrix as a basis
for the remainder of my work. The chief reason for this was incidental: the “steady state”
value of M bi deviated from a uniform distribution more so than M uni . As I will show later,
this decision did allow me to produce a Logic-9 friendly mutation bias, albeit using a more
simpliﬁed version of the bias than the original M bi would produce.
Figure 3.1 shows M bi and its near “steady-state” condition. As mentioned before, one of
the advantages of the “steady state” is that the original identity of an instruction no longer
plays a determining factor in the outcome of a substitution. That is, any instruction i has
an equal probability of mutating to a particular instruction j. Put another way, an inﬁnitlysized population of genotypes under a random walk can expect to have a composition ˆ equal
b
to one row of the matrix shown in 3.1-B after a suﬃcient amount of time has elapsed.
Although in the short term, mutations between states in the genome may be dependent
on the initial identity of each site, the long-term consequences of a mutation bias should
drive populations to a similar genetic composition outcome, barring strong selection. Consequently, a major assumption of my work is that a mutation bias can be represented by a
single vector s where each element is the relative abundance of one genetic state as compared
ˆ
to another. Selection, of course, disrupts this assumption because the context of one genetic
state over another has the potential to be adaptively meaningful; but the overall direction
of genetic change is adequately captured by s.
ˆ

3.1.2

Further simpliﬁcations of biases

Although the mutation bias generated from M bi above is well-speciﬁed, some of the parameters used to generate it were chosen more arbitrarily. For instance, the sampling of
populations every 100-updates might give a good approximation for the complete evolutionary history of the population but was chosen more for observational completeness of the
transition matrix rather than capturing evolutionarily meaningful artifacts. Further, I had

25

B

2000
Mbi

abcde f gh i j k lmnopqr s t uvwxyz
To

abcde f gh i j k lmnopqr s t uvwxyz
To

−4.8 −4.0 −3.2 −2.4 −1.6 −0.8 0.0
Probability [log10 ]

From
zyxwvu t s r qponml k j i hg f edcba

From
abcdefgh i j k lmnopqrs tuvwxyz

A

0.8

Figure 3.1. Transition matrices. Letters along the axes correspond to virtual-CPU instructions in Appendix A. A. A Markov transition matrix generated from point and insertion
mutations accumulated during the course of evolution in the Logic-9 reward structure. B.
The near-saturation state of this matrix.
some question as to whether each sample replicate should be equally weighted when tabulating the values for any resulting transition matrix. After all, some replicates will have
populations more adapted to the environment than others due to chance alone. Finally, there
was the distribution of the bias: how meaningful are the many diﬀerent relative probabilities?
In order to simplify s and remove variation in s due to arbitrary decisions to the concerns
ˆ
ˆ
above, I decided to use only three diﬀerent instruction probabilities: low, medium, and high.
These three probabilities were loosely ﬁt to the original eigenvector (ˆ of M bi as follows:
b)
medium is 3 1 more likely than low; and high is 5 times more likely than low.
3
Once the relative ratios were established, the question became how to apply them across
the 26 instructions of the default Avida instruction set. As shown in Figure 3.2 there are

26

clearly some instructions that are more represented in s than others, especially those dealing
ˆ
with logical task IO {nand, io}

NOP modiﬁcation {nop-A, nop-C} , or replication

{h-copy} . Since other work has shown there to be an antagonistic relationship between
task acquisition (and therefore higher ﬁtness) and replication eﬃciency [34], I decided to

0.14
0.12
0.10
0.08
0.06
0.04
0.02
0.00

nop-A
nop-B
nop-C
if-n-equ
if-less
pop
push
swap-stk
swap
shift-r
shift-l
inc
dec
add
sub
nand
IO
h-alloc
h-divide
h-copy
h-search
mov-head
jmp-head
get-head
if-label
set-ﬂow

Mutation Probability

place {h-copy} in the low category.

Instruction
UNB
POSbi−matrix

POS
NEG

NEGbi−matrix

Figure 3.2. A comparison of the saturation values of the transition matrix and
corresponding simpliﬁed values used in the INST-3 mutation bias spectrum.

3.1.3

The INST-3 spectrum

For the remainder of this work, I will refer to the potentially advantageous mutation bias as
POS; NEG will be an “anti-bias” made by swapping instructions with high and low probability
in POS. UNB will be a bias where each instruction is equally probable. Figure 3.2 compares
the original Dayhoﬀ-like versions of these biases to their simpliﬁed derivatives.
27

In order to simplify terminology later on as I add more mutation biases, I refer to the
set of mutation biases identiﬁed as UNB, POS, and NEG in Figure 3.2 as the INST-3 mutation
bias spectrum. Although transitions between the diﬀerent biases are prohibited in the work
presented in this chapter (unless explicitly stated), it will be helpful to think of the mutation
biases as being states in an evolvable system. This will become more important for the
evolution of mutation biases in Chapter 5.

3.2

Mutation biases can change the evolutionary trajectory of obligate populations.

All experiments in this chapter will be in one of the two environment reward structures
listed in Table 3.1. The Logic-9 reward structure is well studied in Avida. It rewards
ﬁtness based upon the complexity of binary logic tasks on received bit-strings. The most
complicated task in the Logic-9 is EQU. Previous work shows that EQU requires simpler
rewarded tasks to evolve [21]. EQU also tends to evolve largely through expatiation: EQU
co-opts sites in the genome from other tasks [28].
As a test of the ability of a mutation bias to inﬂuence the eﬀects of adaption, I repeat the
experiments of Lenski et al. [21] to determine whether or not a presumed beneﬁcial mutation
bias can modulate the rate and number of replications acquiring the complex task EQU, its
eﬀect on ﬁtness, and its ability to evolve EQU in an environment that does not reward for
simpler tasks.
My experiments in this chapter examine three diﬀerent questions: (1) can mutation
bias alter the outcome of evolution if it is applied at the start of an experiment (Section
3.2.1)?; (2) can a change in mutation bias alter the outcome of evolution in already adapted
populations (Section 3.2.2)?; and (3) can mutation bias alone evolve the complex task EQU
(Sections 3.2.3)? I will also examine how bias changes the genetic composition of populations
(Section 3.3).

28

NOT
Logic-9
EQU-only

NAND

AND

Task
ORN OR ANDN

21
0

21
0

22
0

22
0

23
0

23
0

NOR

XOR

EQU

24
0

24
0

25
225

Table 3.1. Environment reward structures used in this chapter. Rewards are applied
multiplicatively when an organism divides and is contingent on successful demonstration of
the displayed Boolean logic operations on bit-strings provided by the environment.

3.2.1

The eﬀects of mutation bias on task adaptation

A natural place to begin exploring the eﬀects of mutation bias on evolution is to examine
the inﬂuence of biases on a set of replicate treatments, all beginning with a common set of
initial conditions. I used diﬀerences in the speed of adaptation (task acquisition or ﬁtness
gain per update), frequency of complex task evolution, and ﬁnal average population ﬁtness
as measures of environmental adaptation.
The ﬁrst set of experiments to test the eﬀect of mutation bias on adaptation begins with
three treatments: POS, UNB, and NEG-only variants. Each treatment had 300 replicates with
evolution beginning with a fully-seeded population of the default length-50 ancestor genome
(see Figure 2.1) under the Logic-9 reward structure. Each replicate ran for 105 updates.
At the end of each experiment, I identiﬁed the PLoD (primary line of descent) for each
replicate, and evaluated its genotypes for ﬁtness, task performance, and stochasticity. I
tabulated a population as performing a task if any genotype along the PLoD deterministically
demonstrated the task. I used the behavior of genotypes along the PLoD as a proxy for the
historical behavior of the population since reproduction is asexual and metabolic rewards
for tasks are inexhaustible. This combination of factors makes it unlikely for more than
one deeply-rooted clade to persist for long periods of time. Consequently, the PLoD should
reﬂect the predominant historical state of the population over time. I used the number of
steps from the common ancestor to the ﬁrst genotype performing each task as a measure of
task acquisition speed. I also collected the average ﬁnal ﬁtness of each population and the

29

∗∗

∗∗ ∗∗ ∗∗ ∗∗
∗∗

∗∗ ∗
∗∗ ∗∗

EQU-Only Environment
300 ∗∗ ∗∗
∗∗ ** p < 0.005
200
* p < 0.05
100
∗∗ ∗∗
∗∗
0 ∗∗ ∗∗ ∗∗
NOT
NAND
AND
ORN
OR
ANDN
NOR
XOR
EQU

300
200
100
0

Logic-9 Environment

NOT
NAND
AND
ORN
OR
ANDN
NOR
XOR
EQU

Replicate Count

A

Task

Task

B
Depth

800
600
400
200
0

NEG
UNB
POS
Logic-9 Environment

NEG
UNB
POS
EQU-Only Environment

Figure 3.3. The evolution of tasks under diﬀerent mutation biases and environment reward structures. A. The number of replicates acquiring each task under mutation
biases: yellow, POS; blue, UNB; red, NEG. B. The distribution of the number of genetic steps
from the ancestor genotype to the ﬁrst acquisition of EQU along the PLoD. Colored boxes
show the the inner quartiles; the median is shown by a gray line. The upper and lower range
of the distribution is shown by dotted lines.
genetic composition of the population over time.
Since I based the POS upon successful mutations in the Logic-9 reward structure, I
hypothesized that the POS treatment will adapt better to the environment (both in terms
of adaptive speed and overall ability), and end with ﬁnal populations that have a higher
average ﬁnal ﬁtness. Likewise, the NEG treatment should be less adapted to the environment
than both UNB and, especially, POS.
Figures 3.3 and 3.4 show the results of these three treatments. The results are as expected:
the POS replicates showed signiﬁcantly higher ﬁnal ﬁtnesses than the UNB replicates (Figure
3.4, median=14.93 [log2 ] versus 14.35 [log2 ], p = 0.002, Mann-Whitney U-Test). In terms of

30

tasks, the POS replicates demonstrated complex tasks in signiﬁcantly more replicates than
UNB replicates. Speciﬁcally, the tasks NOR, XOR, and EQU had signiﬁcantly more replicates
demonstrating them along the PLoD (p < 0.05, 1-tailed Fisher’s Exact Test, Bonferroni
corrected). The speed of task acquisition also signiﬁcantly improved for all tasks (p < 0.05,
Mann-Whitney U-Test Bonferroni corrected) except xor, which failed to fall within the
Bonferroni corrected conﬁdence interval (p = 0.010, uncorrected Mann-Whitney U-Test). A
good example of this change in acquisition speed is for the most complex tasks in the Logic-9
reward structure, EQU. EQU acquisition depth of populations under POS decreased relative to
UNB populations, with a median EQU acquisition depth of 160 genomes in UNB populations as
compared to 90 genomes in POS replicates (p < 0.001, uncorrected Mann-Whitney U-Test).
Also as expected, the replicates under the NEG bias did not fair as well as the UNB or POS
replicates. Final average population ﬁtness was signiﬁcantly lower than UNB (median=12.94
[log2 ], p < 0.001, Mann-Whitney U-Test). Likewise, fewer replicates obtained the three most
complicated tasks (p

0.001, Bonferroni corrected) under the Logic-9 reward structure.

Overall, performance on all adaptive metrics was lowest in the NEG replicate populations
and highest in the POS populations. These results demonstrate mutation bias is suﬃcient to
change the evolutionary trajectory of populations, both helping and hindering adaptation.
However, the extent to which the two biases explored above can inﬂuence adaptation has
not been fully demonstrated. The experiments above all began with the same, hand-written
ancestor; whether adapted populations can utilize a mutation bias to adapt more so than
mutationally unbiased peers has not been shown. Further, how well the Logic-9 reward
structure is captured by the POS bias is also not known.

3.2.2

Mutation bias can alter evolutionary trajectory of adapted
populations

In order to test whether or not mutation bias can inﬂuence already adapted populations,
I repeated the experiments above but added ﬁve more treatments. All populations began
31

Average Final Population Fitness [Log]

20
15

∗∗

∗∗

∗∗

∗

∗∗

10
5
0
−5

* p < 0.05
** p < 0.005
POS

UNB

NEG

5k
10k
Treatment

20k

40k

80k

Figure 3.4. The distribution of ﬁnal population average ﬁtnesses under diﬀerent
treatments in the Logic-9 environment reward structure. Asterix markers show
distributions signiﬁcantly diﬀerent from the UNB treatment using a 2-tailed Mann-Whitney
U-Test. POS, NEG, and UNB are treatments where populations are forced to use one mutation
bias; the remaining treatments switch biases from UNB to POS en masse at the times indicated.

as before with the same default hand-written ancestor and conﬁguration. Each population
began under UNB conditions. Each treatment switched from all organisms being unbiased to
using the POS mutational bias at either 5, 10, 20, 40, and 80 ×103 updates. Also as before,
each treatment was repeated 300 times.
The ﬁtness comparisons of these treatments are shown in Figure 3.4. Populations that
switched to POS at 5, 20, and 40 ×103 had average ﬁnal population ﬁtnesses higher than
UNB populations (p < 0.05, Mann-Whitney U-Test, Bonferroni corrected). Likewise, those
same treatments showed signiﬁcant improvement in EQU acquisition, displayed in Figure 3.5.
Speciﬁcally, those treatments showed individual improvements in the number of replicates
that evolved EQU after the switch from UNB to POS (p < 0.05, 1-tailed Fisher’s Exact Test,
32

uncorrected) relative to replicates continuing in UNB to the end of the experiment.
The two anomalous populations at 10 and 80 × 103 updates did not see improved ﬁtness
or EQU acquisition. The latter can be explained by a lack of time to evolve EQU2 . I believe the
diﬀerence at 10 × 103 is an anomaly or potentially the result of a non-uniform probability of
getting EQU with some transition around 10 × 103 as points immediately before and after it
show improved ability to acquire EQU.
Although the results from this set of experiments are not as strong as previous comparisons between treatments that were either always under UNB or POS, there is evidence that
the eﬀect still exists. In the next chapter I will explore these ideas more when I compete
mutation biases against each other using genotypes evolved under diﬀerent biases. I do,
however, ﬁnd these are results enough to support the claim that environmentally-adapted
genotypes can adapt to the Logic-9 reward structure better under the POS bias than under
unbiased conditions.

3.2.3

Mutation bias can allow for the evolution of complex tasks
de novo

The POS bias was generated using information from successful substitutions in the Logic-9
reward structure; consequently, it contains some information about it. Replaying these
mutations in the form of a bias as shown above demonstrates an ability to move populations
to better adapt to the Logic-9 reward structure. One plausible reason for this behavior is
that POS mutational bias creates a pressure to emulate the genetic-composition of simple
tasks. If this is the case, then these simple tasks should appear in greater propensity under
POS than under UNB even in the absence of selective pressure. In other words, chance alone
could allow for simple tasks to occur. Fixation would not occur without selection (except
perhaps through unlikely drift). However, if this mutational pressure is strong enough,
2 Using

a sliding window of 20 × 103 updates and examining UNB-only replicates, there is
diminishing ability of replicates to obtain EQU over the course of the runs. Data not shown.

33

Fraction of Replicates Evolving EQU

∗

0.4

∗

∗

0.3
0.2
0.1
∗ p < 0.05
0.0
0

20

40
60
Update [x103 ]

80

100

Figure 3.5.
The acquisition frequency of EQU. Colored horizontal lines show the
fraction of replicates that evolved EQU in populations that experienced only one mutation
bias (yellow=POS, blue=UNB, red=NEG). Dashed colored lines show the fraction of replicates
that have evolved EQU over time. Green horizontal bars show the fraction of replicates
that have demonstrated EQU at each of the ﬁve updates during which a switch from POS to
UNB occurred. Vertical green bars show the additional fraction of treatment replicates that
acquired EQU after the swap from UNB to the POS. Treatments that swapped from UNB to POS
where signiﬁcantly more replicates acquired EQU after the swap than the UNB-only treatment
are indicated with an asterisk.
there is a possibility for complex tasks to evolve “spontaneously” through a manipulation of
mutation probabilities alone. Adding strong selection for complex tasks then allows for the
possibility of ﬁxation and maintenance in the population.
In order to test the possibility that mutation bias alone can allow for the spontaneous
generation of complex tasks, I repeated the ﬁrst set of experiments in this chapter in the
EQU-only reward structure. As the name suggests, this reward structure only provides merit
increases for the task EQU. In Lenski et al. [21], this reward structure was used as a control to
test whether or not simpler tasks were required to act as building blocks for the evolution of

34

the task EQU. The authors of the study found that simpler rewarded tasks allow for, and are
required for, the evolution of EQU. Here, I repeat their experiment with minor modiﬁcations
(as before, see Appendix B.1), to test whether or not a mutation bias is capable of evolving
EQU in a reward structure absent these necessary building blocks.
Under each mutation bias in INST-3, I evolved 300 replicates for 105 updates under the
EQU-only reward structure, beginning with fully seeded populations of the default length50 handwritten ancestor. As before, I examined the PLoD for task acquisition. Although
the simpler 8 tasks of the Logic-9 were not rewarded, chance does allow for spontaneous
generation of these tasks (see Figure 3.3).
EQU evolved in 18 out of the 300 replicates under the POS bias. EQU was not demonstrated
by any replicate under either the UNB (repeating the results of Lenski et al.) or NEG biases.
Replicates under the POS bias also showed spontaneous evolution of signiﬁcantly more simple
tasks (see Figure 3.3) than the other two biases, despite the fact that they were not rewarded.
These results indicate that the POS bias is capable of emulating some of the selective behavior
of the Logic-9 reward structure, allowing for otherwise unlikely tasks to evolve.
One interesting observation is that, despite the fact that these populations were only
rewarded for EQU, simpler building blocks may have contributed to the evolution of EQU.
Speciﬁcally 13 of the 18 replicates showed evidence of phenotypic stochasticity for EQU immediately prior to EQU being correctly implemented. Stochasticity, as discussed in Chapter
2, is measured by repeatedly testing genomes with diﬀerent sets of pseudo-random numbers
as inputs. An example of an input-dependent version of EQU performed by one of the POS
replicates is this implementation:

EQU ≈ 1 + I1 + I2

(3.1)

where, I1 and I2 are two inputs given to the organism via an IO instruction execution.
It so happens that this has an approximately 10−3 probability of correctly calculating EQU
because of the length of the bit-strings randomly generated by the environment. Speciﬁcally,

35

each organism receives one of three diﬀerent bit-strings whenever it executes an IO. Each
bit-string received is 32-bits in length, with the upper 8-bits being deterministic to assure
that all bit-wise combinations are present for any pair of the three inputs. The lower 24-bits
of each bit-string are randomly generated.
Genotypes that implemented the simple function in Equation 3.1 exploited the fact that
there is a ( 3 )24 (≈ 10−3 ) chance that at least one of the ﬁrst 24-bits in each pair of inputs
4
contains a one. For each of the ﬁrst 24-bits, adding 1 will do one of three things: (1) in the
case 0+0+1, 1 will be the result; (2) 1+0+1 = 0+1+1 = 0 carry 1; or (3) 1+1+1 = 1 carry
1. In the last two cases, the resulting value is identical to that of EQU. Only in the ﬁrst case
would the function return an incorrect value. Consequently, as long as there is not a position
in the ﬁrst 24 bits of the two input bit-strings that contains a zero, then the genotype will
be successful at demonstrating EQU. (The upper 8-bits are set by Avida; only the highest
bit contains zero in both bit-strings, not aﬀecting the resulting calculation.) Although the
probability is low, such combinations do occur, and selection is strong enough under the
EQU-only reward structure to cause the implementation to persist.
Overall, 42 of 300 replicates under the POS bias demonstrated EQU statically or stochastically (24 only stochastically) along the PLoD compared to two replicates under UNB that
demonstrated EQU only stochastically. Although phenotypic stochasticity appears to be important for the evolution of EQU in the EQU-only owing to its presence in the majority (13
of 18) of replicates immediately before they achieved EQU statically, the exact role that phenotypic stochasticity plays in evolution has not been completely explored and may prove a
fruitful avenue of investigation, especially with regard to diﬃcult to evolve tasks or when
the relative cost of developing a task is high.

36

3.3

Other eﬀects of mutation bias

One of the key assumptions about my implementation of mutation bias is that the bias
reﬂects a type of “compositional optimum” for evolved genomes. I do not claim that the POS
is the most optimum, but I believe it likely better than UNB.
In Dorn et al. [9], the authors present a hypothesis that a “monomer abundance distribution biosignature” (MADB) exists to distinguish biotic and abiotic conditions. In addition
to using amino acid and carboxylic acid concentrations from both biotic and abiotic samples, the authors used Avida to detect the presence of a MADB biosignature. In this case,
they examined the eﬀect of selection on two diﬀerent implementations of a handwritten
ancestor evolving under UNB conditions over seven diﬀerent mutation rates. The expected
distribution of instructions under abiotic conditions would be, on average, equal for each
instruction. The authors ﬁnd, however, that irrespective of ancestor and (except at lethal
levels) mutation rates, a common biosignature emerges for all treatments. The authors concede that there is some variation between the distributions caused by the ancestors because
of historical contingency dealing with replication method (the two ancestors had extremely
diﬀerent means of replicating themselves), but for the most part instructions that were over
or under-represented by one ancestor were also favored or disfavored by the other.
As a consequence of their work, Dorn et al. provide a convincing argument that evolution with unbiased mutations (as the authors used) will result in a common compositional
outcome regardless of ancestor or mutation rate. Additional work by Dorn [8] also provides
evidence that the mutation bias does not contribute much to the ﬁnal compositional signature. This leaves the environment and its selective pressures as the drivers of genome
composition.
The overall consequence of selection being the deciding factor in composition is that it
implies some kind of environment-speciﬁc compositional optimality. The POS bias seeks to
emulate this composition. In order to see how genetic compositions of POS and UNB popu-

37

lations replicates change over time, I measure the average Kullback-Leibler (KL)-divergence
of the replicate populations from sections 3.2.1 and 3.2.2.
KL-divergence is deﬁned as:
DKL (P Q) =

P (i)log
i

P (i)
Q(i)

(3.2)

where P is the distribution of instructions at a particular update for a single replicate’s
entire population and Q is the expected distribution of instructions of the POS or UNB. For
P (i)

cases where P (i) = 0, I assigned P (i)log Q(i) to be 0.
All values here are reported in bits, which means the KL-divergence of the two distributions can be thought of as the average number of extra bits needed to convey a message
composed from states using a distribution of P when optimally encoded for the distribution Q. For our purposes, this value can be thought of as the average number of bits of
information genomes under selection diﬀer from the mutation bias. Figure 3.6 shows the
KL-divergence from populations in sections 3.2.1 and 3.2.2.
In general, the average composition of all populations are closer to POS than UNB over
time. All treatments had an average KL-distance of less than 1.5 bits under POS. In contrast,
all treatments were at least 1.9 and as high as 2.2 bits diﬀerent from NEG. Interestingly,
switching from UNB to POS can visibly change the composition of the population. After
these treatments became POS biased, their average composition began to deviate from their
UNB-only counterpart, asymptotically approaching the average composition of POS relative to
UNB. Despite this observation, there appears to be a gradual accumulation of artifacts in all
populations, as the average composition distance of all replicates has a slight upward trend
away from POS over time.

3.4

Summary

In this chapter, I created a mutation bias (POS) and demonstrated it can (1) improve adaptation under the Logic-9 reward structure; (2) allow for already adapted populations to better
38

Average KL Distance [bits]

Against POS

2.0

Against UNB
3.2

1.9

3.0

1.8

2.8

1.7
1.6

2.6

1.5

2.4

1.4

2.2

1.3

2.0

1.2

0

20

40
60
Update [x103 ]

POS

80

100

UNB⇒POS

1.8

0

20

UNB

40
60
Update [x103 ]

80

100

NEG

Figure 3.6. Population-wide genetic composition changes over time relative to POS and UNB mutation biases. The
colored lines show diﬀerent obligate treatments: blue=UNB only; yellow=POS only; red=NEG only; green=swap from UNB to POS.
Green triangle markers show the point at which the mutation bias switched for each bias-swap treatment.

39

adapt to their environment than under UNB; (3) emulate some of the genome-composition
pressure under the Logic-9 reward structure to spontaneously produce both simple and
complex tasks. I also showed that an “anti-bias” created by inverting the redundancies of
POS, called NEG, can retard adaptation in the Logic-9 reward structure. Further, I found
that mutation bias can aﬀect population-level genetic composition but that selection does
drive divergence from expected compositions.
Overall, the results from this study meet the ﬁrst of the three components needed for
the evolution of a beneﬁcial mutation bias: the potential to improve adaptation in a given
environment. In the next chapter, I will study if selection can distinguish between two
mutation biases. I will also explore how genotypes evolved under one mutation bias are
aﬀected by their history with regard to the selective advantage of a mutation bias.

40

CHAPTER 4
Selecting a Mutation Bias
I demonstrated the ability of mutation bias to aﬀect the outcome of evolution but can evolution select for an optimal mutation bias? Many processes that confer long-term evolvability
are at odds with short-term selective pressures experienced by individuals. Alternatively, the
eﬀects of mutation bias might not even be visible to selection, aﬀecting only the long-term
adaptive behavior of the population.
Mutation bias is not alone in having a potential disparity between short and long-term
selective behavior. In terms of the disparate behavior between short and long-term selective
diﬀerences, perhaps one of the most examined evolvability-conferring processes is the evolution of mutation rates. There is a tradeoﬀ between short and long-term outcomes (reviewed
by [36]). In the short-term there is an increase in the number of deleterious mutations being
accumulated; over time with a suﬃciently smooth ﬁtness landscape ([5]) or a high number
of accessible beneﬁcial mutations (for example [14]), high-mutation mutants can outcompete
their wildtype peers. The key to whether or not a high-mutation strain goes to ﬁxation
depends on its short-term advantage. If novel beneﬁcial adaptations are a number of mutational steps away, a higher mutation rate may not be selectively favorable. In particular,
if the selective advantage is not high enough at the individual rather than per capita level,
high mutation populations with small initial abundance may be lost to drift.
Mutation biases may have a similar diﬃculty. Even though there is a tendency for
populations to adapt better as a whole under the POS than the UNB bias, the short-term
eﬀects of the POS bias might not be beneﬁcial. The short-term consequence of mutation
biases described in the previous chapter are not known. In the preceding experiments, I
41

applied mutation biases on a population as a whole. As a result, the selective eﬀect of one
bias relative to another in the short-term cannot be gauged.
Fortunately, there is reason to suspect that the POS bias from the previous chapter is
at least slightly beneﬁcial relative to the UNB bias in the short-term. This is based on two
observations. The ﬁrst is from the the KL-distances in Section 3.3 with averages shown
in Figure 3.6. Comparing the the KL-distance using POS as a basis (Q in Equation 3.2)
against UNB, the POS bias is closer to the composition of all experimental averages over all
sampled times than the unbiased distribution. As such, the POS bias is consistently closer
to the actual composition of organisms in the Logic-9 reward structure than UNB. Next is
the observation made in Chapter 2 that researcher-speciﬁed and actual mutation rates vary
because of the way mutation is implemented in Avida: sites might mutate but not change
identity. If a mutation bias closely matches the genetic composition of a population, as in
the case with POS relative to UNB, than the probability that an instruction will mutate to
itself is maximized. Consequently, overall mutational load decreases as more synonymous
mutations occur.
Despite these observations, the advantage of a beneﬁcial bias such as POS might not be
visible to selection. Small decreases in mutational load might not be large enough (especially
in small populations with high levels of drift) to have any noticeable selective beneﬁt in the
short-term. Further, the long-term beneﬁts of a mutation bias might be so decoupled from
the cause – a better mutation bias relative to peers– as to be a trait that is diﬃcult to
hitchhike upon, leaving its fate to chance.
In this chapter, I will explore whether the mutation biases from the previous chapter are
visible to selection by competing mutation biases against one another.

42

4.1

Mutation bias may be visible to selection

In order to compete diﬀerent mutation biases in head to head competitions, I needed to
modify Avida to handle multiple instruction sets within a single experiment and monitor
which instruction sets are in use by organisms in the population.
I began mutation bias competitions with the population being fully-seeded using either
the default length-50 nop-C ancestor (used to begin experiments in the preceding chapter)
or the ﬁnal dominant organism from 30 of the 900 experiments in Section 3.2.1, with 10
genotypes from each mutation bias.
I measured the competitive advantage of each mutation bias against the UNB bias by
competing two subpopulations against each other. I seeded the test subpopulation to be a
fraction, πt , of the population. It used one of the three mutation biases used in Chapter
3: the POS, UNB, or NEG. This subpopulation competed against the remaining 1 − πt of
the population that I assigned to be mutationally unbiased (UNB). Mutation biases did not
change over the course of the experiments and were inherited from parent to oﬀspring. The
experiments proceeded until the oﬀspring of one of the subpopulations drove the other to
extinction.
I repeated each competition a number of times and tabulated the frequency competitions
drove UNB to extinction, denoted Ωt . By looking at how Ωt diﬀered between treatments
relative to their initial abundance, I was able to determine how selectable mutation biases
were relative to UNB and how diﬀerent parameters aﬀect outcome. Treatments that drove
UNB to extinction better than chance “won” competitions and were selectively advantageous.
Those treatments that were driven to extinction by a UNB subpopulation worse than chance
“lost”. Treatments where outcome was indistinguishable from chance were “tied”, where
neither bias had an advantage over the other.
Figure 4.1 displays the full range of πt and Ωt are along the x and y-axes, respectively.
The neutral expectation, where πt = Ωt , is displayed with caricatured error bars. Outcomes

43

with Ωt above the neutral expectation show better-than-chance outcome relative to its competitor, indicating its mutation bias is selectively-advantageous compared to its an unbiased
competitor. Outcomes below the neutral expectation indicate relatively negative selection.
Every set of treatments includes a control where UNB is competed against itself. Any signiﬁcant variation from the neutral expectation in these controls would indicate something
is amiss with the implementation of the experiment. I found no signiﬁcant deviation in the
control experiments outside of chance.
For the remainder of this chapter, I will use the experimental design above to examine
whether or not mutation bias is opaque to selection relative to another bias using both the
default ancestor and organisms evolved under the three mutation biases from the previous
chapter. I will also examine what the eﬀects of population size are on outcome (Section 4.1.2);
the eﬀects of population structure on outcome (Section 4.1.3); and if there are any diﬀerences
in the success of mutation biases between evolved and unevolved organisms (Section 4.2).
Finally, I will begin to explore why mutation biases are selected (Section 4.3), a topic that
will be continued in Chapter 5.

4.1.1

Baseline competition results

In this section I describe baseline competition results. This baseline will be used to contrast
how changes in population size and structure aﬀect the selective advantage of mutation
biases. For the baseline parameters, I used an unstructured (mass action) population size
with a maximum size of of 3600 organisms. Later I will increase the population size to
10,000 and introduce structure in the population by restricting oﬀspring placement. Other
experimental parameters were identical to those of experiments performed in Section 3.2.1.
In order to see if the two non-uniform biases in the previous chapter (POS and NEG) are
subject to selection, I competed them against mutationally-unbiased (UNB) organisms. Each
competition began with a fully-seeded population of the default nop-C ancestor. I assigned a
fraction of the population, πt , to be either POS, NEG, or UNB (the latter serving as a control).

44

Win Frequency (Ωt )

1.0
0.8

Positive Selection
“Wins”

o
err

0.6
0.4

or

NE

U

A
TR

err

0.2

L

Negative Selection
“Loses”

0.2
0.0
0.0

r

0.4
0.6
Initial Frequency (πt )

0.8

1.0

Figure 4.1. Baseline competition results. In the absence of selective pressure, competition outcome will be based solely upon the initial frequency that a particular bias has in
the population. Results that fall above the diagonal line show evidence of positive selection (“wins”) relative to a peer subpopulation; outcomes below the line show evidence for a
selective disadvantage (“losses”) relative to a peer subpopulation.

45

1.0
0.8

Ωt

0.6
0.4
0.2
0.0
0.0

0.2

0.4
POS

πt
UNB

0.6

0.8

1.0

NEG

Figure 4.2. Competition against UNB in an unstructured population. Initial competitor abundances (πt ) are shown against competitive success (Ωt ). Yellow, blue, and red
lines indicate competitions between UNB and POS, UNB, and NEG, respectively. Treatments
signiﬁcantly diﬀerent than chance (p < 0.05, 2-tailed Binomial Test) are shown by triangle markers; competitions not diﬀerent than chance are shown by crosses. Dashed lines
connecting treatments are shown to contrast outcome against the neutral expectation.
I assigned the remaining (1 − πt ) of the population to be mutationally unbiased (UNB). For
this set of experiments, I tested πt at 0.05, 0.10, 0.20, 0.40, 0.50, 0.60, 0.80, and 0.95.
The location of an organism in its toroidal world determined whether it was assigned
to have either the test bias or be part of the UNB competitor. Both subpopulations were
grouped together. I repeated each competition 200 times, with experiments ending when
the oﬀspring of only one of the the two competitors remain in the population.
In general, POS won competitions under all initial abundances (πt ) and NEG tied with
UNB (Figure 4.2). Of the assayed values of πt , all POS had signiﬁcantly more populations
outcompeting their UNB peers than chance (p < 0.05, 2-tailed Binomial Test, Bonferroni

46

corrected). All NEG and UNB versus UNB competitions had outcomes not signiﬁcantly diﬀerent
than chance for all values of πt . These results show that the experimental design is valid (as
UNB versus UNB tied) and, more importantly, selection cannot distinguish between NEG and
UNB.
The observation that POS won against UNB with initial population sizes as small as 180 of
3600 is encouraging, as anytime a new mutation bias-producing phenotype arises, it will be
extraordinarily rare and subject to the eﬀects of drift in ﬁnite populations. In the following
chapter I explore the ability of mutation bias to arise at low frequency and come to dominate
the population.
The fact that NEG is indistinguishable from UNB despite their divergent long-term behavior
is surprising. There are at least a couple of reasons why this might be so: UNB and NEG might
have similar inﬂow rates and magnitudes of beneﬁcial mutations under these experimental
conditions; it could also be that the rates of beneﬁcial mutations diﬀer, but are both so low
that selection cannot distinguish between them at the population size being evaluated.

4.1.2

The eﬀect of population size on the relative selectability of
mutation bias

An increase in the population size relative to the baseline competitions should decrease the
eﬀects of genetic drift and increase the absolute number of genotypes evaluated, leading to
the discovery of more beneﬁcial mutations. Further, increased population sizes also allow
for a ﬁner distinction between genotypes with close ﬁtness values. As mentioned above, if
NEG and UNB have diﬀerent rates or distributions of beneﬁcial mutations, but both are really
low, the diﬀerence would be indistinguishable at small population sizes. So, if competition
outcomes diﬀer between diﬀerently-sized populations, it would provide evidence that inﬂow
rates or distributions of beneﬁcial mutations diﬀer between NEG and UNB populations.
The dashed-lines in Figure 4.3 shows POS and NEG competitions against UNB under unstructured (mass action) conditions. The darker lines come from treatments with a pop47

ulation size of 10,000; the lighter lines are simply the outcome of the experiments in the
previous section. Signiﬁcant diﬀerences in outcome between 10,000 and 3600 population
sizes are shown by triangle markers (p < 0.05, 1-tailed Fisher’s Exact Test); crosses show
diﬀerences where population size had no signiﬁcant diﬀerence on competition outcome.
Increasing the population size did not allow selection to distinguish NEG from UNB. For all
values of πt , NEG and UNB tied, making the results no diﬀerent from the smaller population
baseline. These results again suggest that NEG and UNB biases are similar in competitive
ability.
The larger population sizes did allow POS to win more often for intermediate values of
πt (=0.20, 0.40, 0.60) relative to the baseline. For ranges of πt closer to either extreme, POS
organisms did not win signiﬁcantly more often. The lack of improvement at small values of
πt suggests that the eﬀects of drift were negligible on the experiments from the preceding
section. If drift were a signiﬁcant factor in outcome, higher initial abundances in the larger
population size should allow for signiﬁcant increase in success (Ωt ).
The lack of signiﬁcant diﬀerences for high values of πt under POS could be due to the
eﬀects of saturation, especially with the large values of πt where Ωt exceeds 0.90 for both
population sizes when πt ≥ 0.80. These treatments had little room for improvement, so
signiﬁcant diﬀerences were diﬃcult to obtain. For example, for the POS treatment with
πt = 0.80 at a population size of 3600, Ωt was 0.925 (185/200 treatments). In order for
there to have been a signiﬁcant improvement, Ωt would have to have reached 0.970 (194/200
treatments), so almost complete success of POS over UNB. Mid-range values of πt , which
competed POS against UNB on a more even footing (since neither POS or UNB had an advantage
due to initial abundance), showed signiﬁcant diﬀerence as one would expect.

48

1.0

0.8

Ωt

0.6

0.4

0.2

0.0
0.0

0.2

0.4

πt

0.6

0.8

1.0

Figure 4.3. Mutation bias competitions with diﬀerent population sizes. Initial competition seed frequency (πt ) is
plotted against the fraction of competitors that drove UNB competitors to extinction (Ωt ). POS competitions are in yellow; NEG
are in red. Lighter colored lines competed in a population of size 3600 whereas darker colored lines competed in a population of
size 10, 000. Unstructured (mass action) and structured (local replacement) populations are distinguished by dashed and solid
lines, respectively. Competition results that signiﬁcantly diﬀer from chance (p < 0.05, 2-tailed Fisher’s Exact Test) between
population sizes for the same replication method are shown by a triangle; insigniﬁcant results are shown by a circle.
49

4.1.3

Population structure is an important factor in the selection
of mutation biases.

In this section, I vary the placement of oﬀspring to provide structure to populations. In
the baseline competitions above, oﬀspring were placed randomly in the population creating
a structureless world. In the experiments below, I require oﬀsprings to be placed in the
local neighborhood of cells around their parent. This change creates a structured population
as colonies can only expand at their edges. If bias requires mutations to interact, then
structured populations will give competing populations time to accumulate them.
If a rare or highly beneﬁcial mutation arises in an oﬀspring in a population without
structure, it will spread at an exponential rate. Consequently, it is diﬃcult for multiple
deeply-divergent clades to co-exist for relatively long periods of time in unstructured populations when sparse or uncommon highly-beneﬁcial mutations predominate and sweep to
ﬁxation at exponential rates. This lack of structure makes the genotypes in the population
relatively homogenous as the recent common ancestor of the population isn’t very distant
from extant genotypes.
Under local replacement oﬀspring are placed in the cells adjacent to their parents, creating
a structured population. This type of population structure reduces the rate at which a
beneﬁcial mutation sweeps the population as a sweeping clade can grow only at the boundary
between it and its peers. This change in replication method should allow for more mutations
to accumulate in each competing clade, creating the possibility for mutations to interact
more so than under random oﬀspring placement. Consequently, if local placement improves
outcome, then the increase of success for POS over UNB or UNB over NEG might be the result
of an increase in epistasis between mutations. If there is no change, then it is possible that
there is simply a set of independent beneﬁcial mutations that cause POS to win over UNB and
NEG to be selectively identical to POS.
Figure 4.4 compares the outcomes of competition in 3600-sized populations under both

50

structured (dashed lines) and unstructured (solid lines) populations. I repeated each competition treatment 200 times and used the default nop-c ancestor under the same experimental
conditions as in the previous section. With the exception of the treatment where πt = 0.95
(due to saturation, both structured and unstructured treatments had Ωt = 1.0), structured
population signiﬁcantly improved the competition outcome in favor of POS relative to UNB
(p < 0.05, 1-tailed Fisher’s Exact Test, Bonferroni corrected).
NEG treatments, on the other hand, performed signiﬁcantly worse in structured rather
than unstructured populations relative to UNB. With the exception of the case where πt =
0.95, all other treatments show signiﬁcantly lower Ωt (p < 0.05, 1-tailed Fisher’s Exact Test,
uncorrected) relative to their population-wide placement counterparts. NEG now performed
signiﬁcantly worse than chance for the ﬁrst time over all but the smallest initial abundance
assessed. Like POS, I believe it is likely that UNB also had a relative advantage to its NEG
competitor because of better increased ability to accumulate multiple mutations to create a
selectively-beneﬁcial eﬀect in a structured population.
These results suggest that population structure plays an important role in how selectable
a mutation bias is by virtue of allowing mutations to accumulate. Well-mixed populations
experience faster selective sweeps when a beneﬁcial mutation arises; structured populations
slow the progress of the sweep. By allowing mutations to accumulate in a structured population, the eﬀects of mutation biases are more pronounced and, therefore, more distinguishable.
Relatively speaking, the eﬀects of roughly tripling the population size from 3600 to 10,000
organisms has less of an inﬂuence on Ωt than changing the structure of the population. Figure
4.3 shows the diﬀerence in competitive outcome for all four replication method × population
size treatments for POS and NEG versus UNB competitions. Neighborhood replication improves
competitive outcome for POS by making it almost a certainty that POS will outcompete UNB
for initial abundances greater than 0.40. Switching to a larger population size improves
outcome signiﬁcantly for treatments with lower values of πt (p

0.05, 1-tailed Fisher’s

Exact Test, Bonferroni corrected). At the lowest initial abundance examined (πt = 0.05),

51

1.0
0.8

Ωt

0.6
0.4
0.2
0.0
0.0

0.2

UNB Unstructured
UNB Structured

0.4

πt

0.6

POS Unstructured
POS Structured

0.8

1.0

NEG Unstructured
NEG Structured

Figure 4.4. Competitions with diﬀerent population structure. Each line above shows
the outcome a series of competition experiments over initial abundance (πt ) of mutation
biases with yellow, blue, and red coloring showing competition between POS, UNB, and NEG
biases against UNB, respectively. Experiments with outcomes signiﬁcantly diﬀerent between
structured (local replacement) and unstructured (mass action) populations (p < 0.05, 2tailed Fisher’s Exact Test) are shown by square markers; insigniﬁcant results are shown by
crosses.
there is improvement to be gained by increasing the population size when using a structured
populations but not when using unstructured populations. This diﬀerence suggests that
structured populations are capable of amplifying the eﬀects of a particular mutation bias
even at low initial abundances, an eﬀect not shown by simply increasing the population size
alone.

52

4.2

Does adaptation inﬂuence the selection of a mutation bias?

The length-50 nop-C-backbone ancestor genotype used to seed all of the previous experiments allows for selection to distinguish between mutation biases, especially in structured
populations that use a local oﬀspring placement policy. However, the default ancestor’s
nop-c backbone has a lot like a “blank tape” for mutations to accumulate upon without
signiﬁcantly hurting ﬁtness of the organism. Evolved genotypes, in contrast, may have their
ﬁtnesses more aﬀected by mutation than this unevolved genotype. Consequently, mutation
bias may not be as subject to selection with evolved genotypes as additional restraints such
as increased epistasis are present in evolved organisms relative to the default ancestor.
It is important that mutation biases be distinguishable in well-adapted genotypes. Natural systems are inherently well-adapted to their environment, so a mutation bias must be
selectable in combination with evolved genotypes for it to be evolutionarily meaningful in
nature.
In this section, I will compete 30 of the ﬁnal dominant genotypes from experiments
in Section 3.2.1 with 10 from each of the mutation biases used in that experiment. The
genotypes selected all were from runs that obtained EQU along the PLoD. I examined whether
(1) mutation biases were still visible to selection if evolved ancestors were used to seed
competitions; (2) if there were any changes in outcome relative to competitions with the
ancestor genotype; and (3) if the mutational history of the evolved genotypes inﬂuenced
competition outcome.

4.2.1

Mutation bias is still selectable with an evolved genotype.

Figure 4.5 shows competitive outcome of a single evolved genotype taken from the end of one
of the replicates with an unbiased mutational background to the default ancestor baseline

53

1.0
0.8
Ωt

0.6
0.4
p < 0.05
× p = N.S.

0.2
0.0
0.0

0.2

0.4

πt

NOP-C Ancestor POS
NOP-C Ancestor NEG

0.6

0.8

1.0

UNB Evolved POS
UNB Evolved NEG

Figure 4.5. Unevolved and evolved genotype bias competition results. Colored lines show the results of competition
of POS, NEG (yellow and red, respectively) against UNB. Darker colored lines show competitions using a genotype evolved under
UNB. Lighter colored lines show results from competitions using the default ancestor. Solid lines show competitions that were
structured; dashed lines show competitions which were unstructured. Triangle markers show competitions where population
structure signiﬁcantly altered outcome (p < 0.05, 2-tailed Fisher’s Exact Test); square markers show competitions where
population structure did not change outcome.
54

competitions from Section 3.2.1. As with previous competitions, I competed POS, NEG, and
UNB subpopulations of this genotype against UNB over a range of initial abundances in both
structured (local replacement) and unstructured (mass action) populations.
In general, the POS signiﬁcantly outperformed UNB in both structured and unstructured
populations, with the exception of the largest initial abundance of POS (πt = 0.95) in structured population. The unstructured treatments performed signiﬁcantly better than chance
for all values of πt examined (p < 0.05, 2-tailed Binomial Test, Bonferroni corrected). However, outcomes from the structured “neighborhood” population are less clear. Only the
smallest initial abundances (πt < 0.60) were still signiﬁcant (p < 0.05) after correction for
multiple comparisons.
NEG competitions against UNB were even more diﬃcult to compare under both structured
and unstructured populations. Unstructured treatments were not signiﬁcantly diﬀerent from
chance at πt = 0.95 and 0.80 but either marginally or signiﬁcantly diﬀerent from a neutral
outcome at other values of πt . It is a similar case for NEG competitions in structured populations where outcomes were not diﬀerent than chance for πt = 0.90, 0.80, 0.50, and 0.05 but
either marginally or signiﬁcantly diﬀerent from chance for other values of πt . Clearly, the
strength of selection against NEG-biased genotypes is at best marginal against UNB at small
initial abundances with this particular evolved genotype.
Comparing the evolved and unevolved genotypes, there was little diﬀerence in outcomes
in unstructured populations for both POS and NEG competitions against UNB. There were a
couple treatments that show marginal diﬀerences between evolved and unevolved genotypes
in the POS competitions (at πt = 0.60 and 0.40) and the NEG competitions (at πt = 0.60 and
0.20) but any signiﬁcance disappears after a Bonferroni correction for multiple comparisons.
Perhaps the most striking diﬀerence between competitions between evolved and unevolved genotypes takes place in structured populations. Earlier, I showed that population
structure created a large diﬀerence in competitive outcome using the unevolved ancestor,
likely due to an increase in mutation interactions. With this evolved genotype, POS does

55

not win signiﬁcantly more often in structured or unstructured populations except at the
smallest initial subpopulation size (πt = 0.05). Similarly, NEG performed no diﬀerently in
structured versus unstructured populations, tying with UNB. This would seem to indicate
that a structured population (and resulting mutation accumulation) is not suﬃcient to allow
these two biases to signiﬁcantly alter competitive outcome relative to unstructured populations, alluding to possible diﬀerences in the local landscape between evolved and unevolved
genotypes.

4.2.2

Mutation bias is selectable using additional evolved genotypes.

To get a more general understanding of the diﬀerence between evolved and unevolved genotype competitions, I competed each of the 30 ﬁnal dominant genotypes using the same
conﬁguration as previous experiments. However, instead of assessing outcome over a range
of πt , I evenly split all experiments between the test bias and UNB. As before, experiments ran
until one bias drove the other to extinction. I performed all experiments in populations with
a capacity of 3600 organisms beginning fully seeded with the test genotype. I tested both
structured (local replacement) and unstructured (mass action) populations. I replicated each
competition 100 times.
Figure 4.6 shows the outcomes of these competitions relative to a neutral expectation
and the unevolved nop-c ancestor competitions. In general, the outcomes were similar to the
ancestor: POS outcompeted UNB signiﬁcantly more often than chance in both structured and
unstructured populations. Of the 30 genotypes tested, 27 outcompeted UNB using POS more
often than chance (p < 0.05, 1-tailed Binomial Test, Bonferroni corrected) in both structured
and unstructured populations. However, the non-competitive genotypes were not the same
between the structured and unstructured competitions as only one evolved genotype was not
competitive under both conditions.
The pattern for NEG competition was not as clear. Of the 30 genotypes tested, 17 of them
56

Evolved in
POS

Evolved in
UNB

Evolved in
NEG

A BCDE FGH I J

A BCDE FGH I J
Evolved Genome

A BCDE FGH I J

1.0

ΩM
t

0.8
0.6
0.4
0.2
0.0

Figure 4.6. Competition results using evolved genotypes as compared to neutral outcome. 30 ﬁnal dominant
genotypes were taken from experiments in Section 3.2.1, with 10 from each mutation bias background. Yellow, blue, and red
markers show the outcome of 100 competitions against UNB for POS, UNB, and NEG, respectively. Each treatment began with
the population being evenly divided between the test bias and UNB. Signiﬁcant wins or losses are shown by diamond markers
(p < 0.05, 2-tailed Binomial Test); ties are shown by a plus marker.
57

signiﬁcantly diﬀered from chance outcomes in unstructured populations (p < 0.05, 2-tailed
Binomial Test, Bonferroni corrected). Of those that were not signiﬁcant under a multiple
comparison correction, 8 were never signiﬁcant and the other 5 were signiﬁcant prior to the
correction, with 3 almost meeting the cutoﬀ criteria. Outcome in structured populations was
similar but slightly improved: only 8 of the 30 genotypes did not outcompete UNB signiﬁcantly
better than chance, with 2 being close to the cutoﬀ criteria after correction.
One of the key diﬀerences between structured and unstructured populations when competing nop-c genotypes using diﬀerent biases was the improved outcome of structured populations relative to unstructured ones. This diﬀerence is not present for all of the evolved
genotypes and is shown in Figure 4.7. Indeed, with the POS competitions, only 1 of the 30
evolved genotypes showed signiﬁcant diﬀerences between structured and unstructured populations, after correcting for multiple comparisons (p < 0.05, 2-tailed Fisher’s Exact Test,
Bonferroni corrected). Without this correction, a total of 5 of the 30 genotypes showed outcomes statistically diﬀerent between structured and unstructured populations. The strength
of the diﬀerence in outcomes between evolved and the unevolved genotype is quite telling.
The nop-c ancestor competitions improved signiﬁcantly from 75% wins (151/200) to almost 100% (199/200) when structured populations were used. The single evolved genotype
signiﬁcantly improved from 87% (87/100) to 99% (99/100). These results clearly indicate
that for POS competitions against UNB, population structure does not play as great of a
role in determining selective outcome using evolved genotypes as it does with the unevolved
genotype.
Comparing NEG competitions against UNB in both structured and unstructured populations results in a similar diﬀerence. None of the 30 genotype competitions are signiﬁcantly
diﬀerent between structured and unstructured populations after Bonferroni correction. Compared to the nop-C unevolved ancestor, which showed a 67% (108 to 80/200) reduction in
the ability of NEG to compete against UNB, the worst loss for evolved genotypes was only 9%
(11 to 9/100).

58

Overall, the diﬀerence in outcomes between evolved and unevolved genotypes with respect to population structure may explain why a particular bias outcompetes another. If
mutation accumulation is important, then one would expect a diﬀerence between structured
and unstructured populations. Evolved genotypes simply do not have the “blank tape” to
accumulate mutations that the nop-c ancestor possesses. Epistasis between sites and adaptations might simply disrupt the process of mutation accumulation necessary for a bias to
get a boost from slower sweep times.

4.3

Why are mutation biases selected?

It may be taken for granted that the potential beneﬁt of a mutation bias is the product of
an increased probability or larger selective eﬀect for beneﬁcial mutations. However, modulation of beneﬁcial mutations are not the only route for a mutation bias to be selectively
advantageous.
For a mutation bias to be positively selected, it must (relative to a competitor) lower the
lethal and deleterious loads by increasing either the probability that a mutation is neutral or
beneﬁcial or by decreasing the negative eﬀect of deleterious mutations. This reduction allows
for the possibility that an increase in the probability of neutral mutations is suﬃcient to allow
for selection of mutation bias. In this section, I examine whether or not mutation bias can
be selected in environments where positive mutations are disallowed. If mutation bias can
still be selected, then beneﬁcial mutations are not the only route by which a mutation bias
can come to dominate a population.
Avida allows the researcher to “turn-oﬀ” beneﬁcial mutations by examining the behavior
of a mutant and sterilizing any oﬀspring that shows improvement over its parent. This has a
practical eﬀect of increasing the lethal load experienced by a population, as oﬀspring would
be unable to replicate if they have beneﬁcial mutations. In order for such populations to
thrive, the number of beneﬁcial mutations accessible to the population must be driven down

59

Evolved in
POS

Evolved in
NEG

Evolved in
UNB

1.0

ΩM
t

0.8
0.6
0.4
0.2

ΩN
t

ΩN
t

1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0

0.0

ΩN
t

Figure 4.7. Competition results of evolved genotypes under diﬀerent population structures. Each plot shows the
outcomes of competitions for a genotypes evolved in a particular mutation bias. The color of the markers in each plot identify
the bias being competed against UNB: yellow, POS; blue, UNB; red, NEG. Genotypes where population structure mattered are
shown with a diamond marker (p < 0.05, 2-tailed Fisher’s Exact Test); unevolved genotypes are shown with a circle and are
signiﬁcant for diﬀerences in outcome between population structures for POS and NEG competitions.
60

relative to neutral and deleterious mutations.
Evolved genotypes should have relatively few beneﬁcial mutations compared to the unevolved ancestor. They also are more representative of the behavior of extant, well-adapted
natural systems. As these genotypes are the product of hundreds of generations of evolution,
they are well-adapted to the environment. Consequently, converting beneﬁcial mutations accessible to these evolved genotypes into eﬀectively lethal changes did not hurt the population
too much. This allowed me to see if mutation biases can be selected based exclusively upon
their eﬀect on a change in neutral and deleterious mutational loads.
The use of evolved genotypes also allowed for another avenue of questioning. Genotypes
that evolved under a particular mutation bias might be adapted to that bias in addition to
their environment. If this dynamic is occurring, then genotypes competing with their native
bias should perform better than genotypes competing with a non-native bias.

4.3.1

Mutation bias can be selected in the absence of beneﬁcial
mutation.

As before, I competed the 30 evolved genotypes from Section 3.2.1 in one of the three mutation biases against UNB at an initial frequency of πt = 0.50. I performed each competition
with beneﬁcial mutations on and oﬀ, with 250 replicates for each treatment. Figure 4.3.1
shows the results of these competitions with respect to a neutral outcome and compares the
diﬀerence between treatments where beneﬁcials are or are not allowed for the same genotype.
In the absence of beneﬁcial mutations, only one genotype was not able to compete against
UNB under a POS bias in a manner signiﬁcantly diﬀerent than chance (p < 0.05, 2-tailed Binomial Test, Bonferroni corrected); only seven genotypes, all evolved in the NEG bias, competed
as well as chance when competing in the NEG versus UNB competition. This result compares
quite favorably with a repeat of competitions with beneﬁcial mutations where one genotype
of the 30 evolved genotypes did not perform diﬀerently from chance in POS competitions
and seven genotypes performed about as well as chance competing in NEG. These results
61

Evolved in
POS

Evolved in
NEG

Evolved in
UNB

1.0

ΩB−
t

0.8
0.6
0.4
0.2

ΩB+
t

ΩB+
t

1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0

0.0
ΩB+
t

Figure 4.8. Mutation bias competitions of evolved ancestors in the presence and absence of beneﬁcial mutations.
Each plot distinguishes competitions for genotypes evolved in a particular mutation bias background. The color of the markers
indicate the bias competed against UNB: yellow, POS; blue, UNB; red, NEG. Horizontal axes give the frequency of successful
competitions against UNB in environments with beneﬁcial mutations present; vertical axes show results from environments
where beneﬁcial mutants are sterilized. Points falling within the vertical and horizontal bars about the middle of the plot
are not signiﬁcantly diﬀerent than a chance outcome for competitions with beneﬁcial and no beneﬁcial mutations, respectively
(p < 0.05, 2-tailed Binomial Test, N =100). Diamond markers indicate where there is a signiﬁcant diﬀerence between outcomes
when beneﬁcial mutations are or are not present for a single genotype (p < 0.05, 2-tailed Fisher’s Exact Test, uncorrected.).

62

strongly indicate that there is not much diﬀerence in the number of genotypes that perform
diﬀerently than chance when beneﬁcial mutations are disallowed in evolved genotype competitions. Therefore selection can distinguish mutation biases without beneﬁcial mutations.
There is some suggestion that the lack of beneﬁcial mutations does not disrupt selection
from distinguishing between biases when comparing individual genotypes between treatments where beneﬁcial mutations are either allowed or sterilized. In POS competitions, 14 of
the 30 genotypes showed signiﬁcant diﬀerences in outcomes between competitions with and
without beneﬁcial mutations (p < 0.05, 2-tailed Fisher’s Exact Test, Bonferroni corrected).
Of those 14, 6 showed signiﬁcantly improved outcomes when beneﬁcial mutations are sterilized (p < 0.05, 1-tailed Fisher’s Exact Test, Bonferroni corrected). NEG competitions fared
similarly. 11 of the 30 genotypes showed diﬀerences between competitions with and without
beneﬁcial mutations, and 8 of those 11 showed signiﬁcantly improved outcomes when beneﬁcial mutations are sterilized (p < 0.05, 1-tailed Fisher’s Exact Test, Bonferroni corrected),
especially in genotypes evolved in the NEG bias, which account for 5 of those 8.
The results above not only indicate that selection is able to distinguish between mutation
bias in competitions of evolved genotypes in the majority of cases, but also that competition
outcomes can be improved if beneﬁcial mutations are not present. There are two possible
reasons this might be the case: there could be an increase in the availability of neutral
mutations or the eﬀects and abundance of deleterious mutations could be lower. In any case,
this shows that it is not necessary for mutation biases to hitchhike on beneﬁcial mutations
to allow selection to choose between them.

4.3.2

Mutation bias selection can be historically-contingent.

Although one mutation bias might be selected over another due to a change in the prevalence
and distribution of ﬁtness eﬀect for deleterious mutations, a change in the probability of
neutral mutations might be suﬃcient, especially given the implementation of mutations in
Avida. As mentioned previously, the declared and true mutation rate in Avida are distinct.

63

During a mutation event, it is possible for a site to be substituted with the instruction
presently at that site. Consequently, high frequency instructions in the genome that have a
high probability of being mutated to would cause the rate of synonymous substitutions to
increase, lowering the eﬀective mutation rate.
One way to observe this behavior is to see whether or not genotypes evolved in and
competed with the same mutation bias outperform peers that were evolved under another
bias in an environment absent of beneﬁcial mutations. Figure 4.9 shows the distribution of
outcomes for competitions, separating out genotypes that evolved under the same conditions
as the competition bias from those that did not. When beneﬁcial mutations are not present,
there is a signiﬁcant diﬀerence in the distribution of outcomes between native and non-native
competitors for both POS (p < 0.001, 1-tailed Mann-Whitney U-Test) or NEG competitions
(p < 0.001). Competitions with beneﬁcial mutations available did not show any signiﬁcant
diﬀerence in outcomes of POS competitions (p = 0.052) and NEG competitions (p = 0.223)
between native and non-native genotypes.
These results suggest that genotypes that evolved in a particular mutation bias compete
better in that bias when beneﬁcial mutations are not available. Competition results are
almost indistinguishable when beneﬁcial mutations are available. Additionally, these results
suggest that a neutrality (in the form of a lower eﬀective mutation rate) may play an important role in mutation bias selection when beneﬁcial mutations are not present, as genotypes
that are closer to the bias they compete within may perform better.
One way to examine whether or not neutrality via synonymous substitution is a factor
in determining outcome is to compare the KL distance of evolved genotypes against the bias
they compete in. If the case that genomes are closer in identity to the bias they compete in
inﬂuences outcome, there should be a correlation between KL distance and outcome. Figure
4.10 compares outcomes to KL distance (deﬁned in Equation 3.2).
Only NEG competitions in an environment absent of beneﬁcial mutations show a correlation that would support the hypothesis that genotypes closer in identity to their competition

64

Ωt

POS
1.0
0.8
0.6
0.4
0.2
0.0

Ωt

1.0
0.8
0.6
0.4
0.2
0.0

p = 0.052
POS

Other

POS
1.0
0.8
0.6
0.4
0.2
0.0

With Beneﬁcial Mutations

p = 0.223
NEG

No Beneﬁcial Mutations
1.0
0.8
0.6
0.4
0.2
0.0

p < 0.001
POS
Other
Genotype Background

NEG

Other

NEG

p < 0.001
NEG
Other
Genotype Background

Figure 4.9. Comparison of competition winners against mutation bias background of evolved seed genotypes. pvalues shown are from 1-tailed Mann-Whitney U-Tests of same-as-competition background genotypes competition wins compared
to wins of evolved genotypes from other mutation bias backgrounds.

65

bias outperform those that do not. In this case, there is a signiﬁcant negative correlation (r = −0.789, p < 0.001) between KL distance and competition outcome. A similar,
though weaker trend is present when beneﬁcial mutations are present in POS competitions
(r = −0.511, p = −0.004), but the presence of beneﬁcial mutations does not test neutrality
alone. There are no signiﬁcant correlations between outcomes and KL-distance for experiments where beneﬁcial mutations are not present and POS is being competed against UNB
(r = −0.199, p = 0.291) or where beneﬁcial mutations are present and NEG is being competed
against UNB (r = 0.163, p = 0.390).
The results above show that genotypes competing in a NEG environment have a strong
correlation with how close the genotypes are to the bias with which they are competing. For
all other cases, there is either no correlation or the eﬀects of beneﬁcial mutations cannot
be ruled out. One possible explanation for the strong signal with NEG competitions and
correlation is how divergent NEG is from the selective pressure of the Logic-9 environment.
Genotypes have a tendency to be closer in identity to POS than NEG (compare the range of
KL-values in Figure 4.10). It may just be the case that the closeness of all genotypes to POS
makes it impossible for selection to distinguish among small diﬀerences between genotype
composition, meaning that all genotypes from all backgrounds are virtually identical with
regard to the eﬀects of synonymous mutation.

4.4

Summary

In this section, I examined whether or not mutation biases are visible to selection. I began
by testing if selection can distinguish between mutation biases when competed against one
another using the default nop-C ancestor and a variety of initial conﬁgurations. Of the two
non-uniform biases introduced in the previous chapter, POS and NEG, POS is almost always
selectively distinguishable from UNB. The structure of the population, whether there is local or
global placement of oﬀspring, plays an important role in altering outcome. Local replacement

66

With Beneﬁcial Mutations
POS

KL Distance

5

NEG
r=-0.511
p=0.004

4
3

r=-0.163
p=0.390

2
1
0

No Beneﬁcial Mutations
POS

KL Distance

5

NEG
r=-0.199
p=0.291

4
3

r=-0.789
p=0.000

2
1
0
0.0

0.2

0.4

0.6

0.8

1.0

0.0

Ωt

0.2

0.4

0.6

0.8

1.0

Ωt

Figure 4.10. Correlation of KL-Distance of evolved seed genotypes to competition outcomes. Each plot shows
competition results of POS or NEG against UNB. Beneﬁcial mutations were either allowed or disallowed for each set of competitions.
The color of the markers indicate which background the genotypes evolved under (yellow, POS; blue, UNB; red, NEG). KL-distance
is based on the composition of the genotypes relative to the bias in which they competed, measured in bits. Correlation
coeﬃcients (r) and signiﬁcance measures (p) are shown with each ﬁgure along with a least-squares ﬁt line to the points.
67

allows for a stronger distinction of both POS and NEG relative to UNB. This diﬀerence is likely
due to an increase in the interaction of mutations made possible by slowing selective sweeps.
Population size also plays a role in the strength of distinguishing between biases; however,
it is not as strong as population structure for the values tested.
Because the unevolved ancestor had a lot of room for mutations to accumulate, it is
possible that the distinction of mutation biases is only an artifact of its lack of adaptation.
I examined whether or not genotypes evolved under the three diﬀerent mutation biases (10
from each) could also have selection distinguish mutation biases. I found that mutation
biases can be distinguished by selection using evolved genotypes, but that the diﬀerence
that population structure makes is not consistent, suggesting that mutation interaction is
not as important with evolved genotypes as the unevolved ancestor.
In order to examine whether a decrease in deleterious mutations absent of beneﬁcial
mutations is suﬃcient for one mutation bias to be selected over another, I repeated the
competition experiments using the 30 evolved genotypes. I found that there is virtually
no diﬀerence in the number of genotypes that compete diﬀerently from random chance in
experiments with and without beneﬁcial mutations. Further, I found that there were some
genotypes that competed better in competitions without beneﬁcial mutations than with
them.
This strange outcome led me to examine whether or not there is a correlation in outcome
of competition and the mutation bias in which the genotype evolved. If such a correlation
existed, it would explain why some genotypes performed better in competitions without
beneﬁcial mutations and indicate that there is a historically-contingent eﬀect of mutation
bias. I found that genotypes compete better when they use their native bias than when they
do not. I also found that, at least for the NEG bias, there is a correlation between genotype
composition and competition bias when beneﬁcial mutations are not present. This observation implicates an increase in synonymous mutation as the cause of successful outcomes
in NEG competitions. No such signiﬁcant correlation was observed with POS competitions

68

without beneﬁcial mutations. One reason this may be the case is that genotypes tend to be
more similar to POS than to NEG making small diﬀerences in composition have no eﬀect on
outcome.
Although selection can distinguish between mutation biases, especially when the biases
are seeded at a relatively high abundance in the population, it is not certain that they can
evolve. In the next chapter, I will examine whether or not a mutation bias can mutate into
a population and be selected.

69

CHAPTER 5
Evolving Mutation Bias
In this chapter, I explore whether mutation biases can evolve. Previous chapters have shown
that mutation bias can alter the outcome of competition and be a selectable trait. This
chapter examines whether populations can evolve a mutation bias if isolated subpopulations
and individuals are given the ability to mutate between biases.
This chapter is split into four parts: a discussion of diﬃculties and experimental modiﬁcations needed to investigate the evolution of mutation biases (Section 5.1); an overview
of evolving mutation bias in segregated subpopulations called “demes” (Section 5.2); a discussion of experiments to evolve mutation biases without demes (Section 5.3); and ﬁnally
a presentation of biased genetic landscapes, which helps to answer why one bias is selected
over another (Section 5.4).

5.1

How to represent a mutation bias

I say that a mutation bias evolved if populations can maintain that bias at a frequency
signiﬁcantly greater than chance. In order for mutation bias to evolve it must be heritable,
selectable, and subject to variation through mutation. In the previous chapters I have
provided the ﬁrst two requirements to organisms with regard to mutation bias but not the
third.
For mutation biases to vary, there must be some genetic construct that maps its state
to a set of mutation probabilities. This exercise is an instance of trying to solve the “representation problem”, which is at the heart of evolutionary problem solving. Ideally, a good

70

representation for a mutation bias (or any phenotypic trait) would allow for smooth phenotypic transitions, allow genomes to sample genotype space over the course of evolution, and
allow selection to ﬁnd the optimal phenotype. Before I can proceed with testing whether or
not a mutation bias can evolve, I must ﬁrst come up with some way to represent the mutation
bias that adequately meets the preceding criteria and would also yield a clear signal that
genotypes in a particular environment preferentially evolve one mutation bias over another.
The simplest way to get a clear indication that selection prefers individuals to have one
bias over another is to reduce the number of possible states that the representation of a
mutation bias can have. This is not an easy task. Consider a representation that allows each
of the 26-instructions to take one of two values: low and high. For the sake of argument,
let an instruction labeled as low have an inﬂow 10-fold higher than low. This representation
allows for just over 76 million possibilities. For any given experiment, a population would be
able to examine only the smallest fraction of this space. This is no diﬀerent from any other
evolutionary-problem solving eﬀort: optimality is not guaranteed because a small fraction of
the overall genotype space is ever examined by the population. However, the exercise here
is not to ﬁnd the optimal bias but to see whether or not individuals can evolve a bias with
particular properties that are selectively advantageous.
It turns out that obtaining a signal in this example is diﬃcult. In one attempt (data not
shown), I found that the ﬁnal mutation biases from populations evolved with just such a
two state-setup for each instruction were entropically indistinguishable from random noise.
In other words, there was no signal at all resulting from evolving a mutation bias in this
manner. There are at least a few reasons why this setup didn’t work. First, there was
no possible selective advantage using the setup for the bias. I ﬁnd this unlikely. Second,
selection couldn’t ﬁnd a beneﬁcial bias because of the averaging eﬀect of the 26 diﬀerent
parameters. If instructions are split evenly between high and low probabilities, then the
relative diﬀerence between probabilities is decreased. This averaging eﬀect might make it
diﬃcult for selection to single out a set of instructions to be highly represented. Finally, the

71

rate of change for the mutation bias might have been too high.
To simplify matters, I chose to limit the set of possible biases to three or six diﬀerent
options. If the majority of individuals across populations used of one or a set of these biases
signiﬁcantly more frequently than the others, then I said the populations have evolved their
mutation bias.
A “mutational spectrum” describes which mutation biases are available to an organism.
In this chapter, mutational spectra come in two varieties: a three-bias spectrum and a
six-bias spectrum. The three bias spectrum is comprised of the three biases used in the
preceding chapters: POS, UNB, and NEG. The six-bias spectrum is derived from these three
biases. I created the three additional biases by expanding the relative abundance of each
instruction in POS or NEG relative UNB by a particular factor. For example, 2×POS has the
relative diﬀerence between each instruction in POS increased by a factor of 2 relative to UNB;
1 ×POS
2

1
has half the diﬀerence in abundance between POS and UNB; and 2 ×NEG has half the

diﬀerence between NEG and UNB. The six-bias spectrum transitions from NEG through 2×POS
smoothly and is shown in Figure 5.1.
Changes to mutation biases may be applied either in a structured or unstructured manner. When structured, mutation bias can only change to the two nearest biases in their
spectrum. Biases at the extremes of either spectrum are able to mutate directly to each
other. Unstructured changes allow any mutation bias to mutate to any other in one step.

5.2

Mutation biases can evolve using demes.

My chief concern before starting this project was whether or not rare mutation biases would
be lost by drift before their eﬀects could be adequately evaluated by selection. In the
competitions in Chapter 4, the rarest initial abundance of a mutation bias was 5%: 180
out of 3600 individuals. At this size, there was little eﬀect of drift on competition outcome
(there was no major diﬀerence when increasing population size) and only a slight advantage

72

0.25
NEG
Inﬂow Probability

0.15

POS

1 ×NEG
2

0.20

UNB
1 ×POS
2

2×POS

0.10

0.00

nand
IO
nop-C
nop-A
nop-B
if-n-equ
if-less
pop
push
swap-stk
swap
shift-r
shift-l
inc
dec
add
sub
h-alloc
h-divide
h-copy
h-search
mov-head
jmp-head
get-head
if-label
set-ﬂow

0.05

CPU Instruction

Figure 5.1. The six-bias mutation spectrum. All biases are derived by modifying the
relative distance between instructions in POS or NEG relative to UNB by a particular factor,
identiﬁed in the legend.
for POS winning more often than chance against UNB. It is not clear from these results that
rare mutation biases would have much of a chance to thrive, especially since mutation bias
does not confer an immediate ﬁtness advantage.
To determine if selection can identify a mutation bias as being advantageous relative to
another when allowed to change, I explored the evolution of mutation biases using demes
rather than individuals as the carrier of mutation bias.

5.2.1

What are demes?

Demes are segregated subpopulations that co-exist but do not interact unless action is taken
by the experimenter. For the experiments in this chapter, there was no migration of individuals between demes.

73

One of the uses of demes is to examine group selection. Demes can be made to compete
against one another based on how well the individuals in each deme perform a particular
group-level behavior. For this set of experiments which demes survive and replicate were
based on the average ﬁtness of each deme at the end of a round of competition. At that
time, demes underwent tournament selection where each deme was seeded using the deme
with the highest average ﬁtness compared to three other demes chosen at random from the
population. The only information transmitted between competition rounds were the demes’
mutation bias. Each round began anew with all demes being fully-seeded with the default
ancestor.
One of the initial diﬃculties with setting up deme experiments was deciding on a set of
deme parameters. The number of demes, the size of each deme, and the length of competition
were all additional considerations not present in an Avida experiment without demes. In
order to quickly assay the outcome over a set of deme parameters, I collected average ﬁnal
population ﬁtnesses over a range of population sizes. By examining variation in ﬁnal average
population ﬁtness among experiments of diﬀerent population sizes and diﬀerent mutation
biases, I found which experimental conditions were likely to allow for mutation biases to
evolve in demes competitions.
Figure 5.2 summarizes the results of a set of calibration experiments I used to determine
the size of each deme and the length of each round of competition. Populations of 200, 400,
800, and 1600 evolved for a total of 16,000 updates (the entire time range is not shown)
under the same conditions demes would experience during each round of competition. Each
population evolved using one of the three mutation biases in the three-bias spectrum. By
examining when the average population ﬁtness values diﬀered between bias treatments for
a particular population size, I could ﬁnd when deme competitions would be likely to show
competitive diﬀerences.
As a result of these calibration experiments, I selected a deme size of 400 with a total
of 50 demes in each experiment. I held tournament selection between demes every 2000

74

1-tailed U-Test p-Value

UNB & POS

1.0
0.8
0.6
0.4
0.2
0.0

1.0
0.8
0.6
0.4
0.2
0.0

N=200
N=400
N=800
N=1600

UNB & NEG

0

500

1000

1500
2000
3]
Update [×10

2500

3000

Figure 5.2. Calibration experiments to ﬁnd a good pair of deme size and competition length. Populations of four diﬀerent sizes evolved under each bias in the three-bias
mutational spectrum. How signiﬁcantly diﬀerent the average population ﬁtnesses are between each bias-treatment using a 1-tailed U-Test is shown along the vertical axis for each
population size (N). Comparisons between POS and NEG treatments are not shown.
updates, a time identiﬁed by the calibration experiments to be where there was a signiﬁcant
diﬀerence between populations under the three biases. (Although assessed, Figure 5.2 does
not show the signiﬁcance of ﬁtnesses between POS and NEG over time.)

5.2.2

Mutation bias can evolve with demes.

Mutation bias was able to evolve in demes under a variety of initial conditions, mutation
methods, and with diﬀerent mutational spectrums.
Figure 5.3 shows the average frequency demes possess each bias in thee three-bias spectrum. Experiments began with either all demes being assigned to be UNB or were given a
random mutation bias. Each of the two setups was repeated 30 times and with each bias

75

Average Deme Frequency

Random Initial Conditions

1.0
0.8
0.6
0.4
0.2
0.0

1.0
0.8
0.6
0.4
0.2
0.0

POS
UNB
NEG

UNB Initial Conditions

0

5

10
15
Competition

20

25

Figure 5.3. Deme competitions beginning with diﬀerent initial conditions. The
ﬁgures above show the average frequency of each bias in the three-bias mutational spectrum
in 30 deme competition experiments over time. Treatment minimum and maximum are
shown with dotted lines about the mean. Each experiment used 50 demes of 400 organisms
with tournament selection every 2000 updates.
having an inﬂow rate of one for each round of competition to prevent competitive exclusion.
When experiments began with demes being randomly assigned one of the three biases, POS
demes consistently came to dominate experiments within ﬁve rounds of competition, with
UNB and NEG populations quickly being driven to their minimum allowed frequency. When
experiments began with all demes being UNB, it took a little more time for selection to choose
POS, but by around 10 competitions into the experiment UNB, demes were driven out of the
population. NEG never made a noticeable advancement its frequency.
Using the six-bias spectrum, deme competition revealed that 2×POS dominated experiments but POS was not excluded from the populations. Figure 5.4 shows how the distribution
of demes with particular mutation bias changed over the course of competition using struc-

76

tured and unstructured mutations. Each of these two treatments had bias change at a rate
of 0.05 per deme, per competition and no guarantee that all biases would be present for each
round of competition.
Deme competition experiments that used structured mutation biases forced demes to
1
transition from UNB to 2×POS via 2 ×POS and POS. Approximately 5 rounds of tournament

selection into the experiment, UNB had, on average, the same frequency as 1 ×POS. A few
2
1
rounds later, 2 ×POS had reached its all time maximum average abundance in experiments;

from then on, it lost ground to POS and, eventually 2×POS. Interestingly, 2×POS is not shown
by these competition experiments to competitively exclude POS. Since POS is a bias created
by successful mutations, I expected 2×POS to only exaggerate the eﬀect. However, by the
end of the experiments, POS had an average frequency of about 0.80 in experiments; 2×POS
occupied an average a little less than 0.20. This would seem to indicate that, although POS
is an overall better bias in these competitions, there is a small but reasonable chance that
2×POS will outperform POS.
Allowing demes to mutate between biases in the six-bias spectrum directly, a couple of
distinct periods are noticeable. While the average presence of UNB in experiments was driven
down, 1 ×POS, POS, and 2×POS are all increasing in abundance at about the same rate.
2
Approximately 5 rounds of competition into the experiments, the rate of 1 ×POS increase
2
slowed relative to the other two POS-based biases. It began to decline as POS and 2×POS
increased their average abundance. Just after 5 rounds of competition, POS increased at a
rate faster than 2×POS eventually having an average of 0.70 frequency. 2×POS reached an
average frequency of 0.40 and declined to about 0.20 as POS continued to increase its presence
in experiments.
The transition point at 5 rounds of competition is interesting since it shows that mutation
biases of diﬀerent eﬀect can all increase simultaneously by competing against less successful
biases; it was only when they reached a particularly high presence in the populations that
they began to frequently compete against each other in tournament selection. These results

77

Average Deme Frequency

Structured Mutations

1.0
0.8
0.6
0.4
0.2
0.0

1.0
0.8
0.6
0.4
0.2
0.0

2×POS
POS
1 ×POS
2
UNB

Unstructured Mutations

1 ×NEG
2
NEG
0

5

10
15
Competition

20

25

Figure 5.4. Deme competitions having diﬀerent mutation methods. The solid lines
above show the average frequency of mutation biases in 50 demes from 30 replicates. Dotted
lines show the minimum and maximum of instruction set frequencies from the 30 treatments.
Two treatments are shown above diﬀering only in the way mutation bias can change after
each round of competition. Structured mutations limit mutations to immediate neighbors
in the six-bias spectrum. Unstructured mutations allow any bias to mutate to any other in
only one step.
suggest that a variety of relatively-beneﬁcial mutation biases can co-exist, provided there is
a competitor competitively-worse than them.

5.3

Mutation biases can evolve without demes.

The success of the POS mutation bias in deme competitions shows the potential for a mutation
bias to evolve; however, the outcome was expected due to the initial parameter assays. To
truly test whether or not populations can evolve one of the mutation biases, I allowed
individuals in a single population to evolve their mutation bias.

78

Figure 5.5 shows the results of allowing 300 replicate populations to evolve a mutation
bias over 105 updates using the six-bias mutational spectrum. All populations began, fully
seeded with the default nop-C ancestor and had the UNB bias. Mutation biases changed at
a rate of 10−3 per generation. Biases were freely allowed to mutate over the entire six-bias
spectrum. Other conﬁguration settings were identical to those used in the majority of this
work and listed in Appendix B.1.
Very quickly, populations had a strong preference for evolving to use 2×POS. By 3100
updates into the experiments, UNB lost its dominant state among all replicates, being replaced
1
by 2×POS. By that time, there was also an increase at a smaller rate for both 2 ×POS and POS.

By the end of the experiment, 2×POS was the dominant mutation bias in 83% of populations.
POS was the next most abundant dominant bias, dominating in less than 10% of populations.
The major diﬀerence in outcome between this experiment and the deme experiments
above is the identity of the victor. In the deme experiments, POS strongly dominated experiment outcome. Here, 2×POS is clearly the dominant form in the vast majority of replicates.
To see if there was any diﬀerence in evolutionary outcome using 2×POS relative to POS
and UNB I repeated the experiment in Section 3.2.1 using 2×POS as the only bias the replicate
populations were able to use. The distribution of ﬁnal average ﬁtnesses are shown in Figure
5.6. I found no signiﬁcant diﬀerence (p = 0.075, 2-tailed Mann-Whitney U-Test) in the ﬁnal
ﬁtness between 2×POS and UNB; and a signiﬁcant diﬀerence between POS and 2×POS.
Combined with the previous experiment, these results indicate that evolution can evolve
a mutation bias; however, the evolve mutation bias might not be optimal for long-term
success.

5.4

Why are mutation biases selected?

In the previous chapter, I showed that mutation biases can be selected even without the
presence of beneﬁcial mutations. I speculated that an overall reduction in the deleterious

79

300
Number of Replicates

2× POS
250

POS

200

1 ×POS
2

150

UNB

100

1 ×NEG
2

50
0

NEG
0

20

40
60
Time [Update ×103 ]

80

100

Figure 5.5. The evolution of a mutation bias in a population without demes. The
number of replicates refers to the number of the 300 replicates where one mutation bias is
expressed more than by half of the population. All populations began with organisms all
having the UNB bias.
mutational load, which encompasses both an increase in neutral and beneﬁcial mutations
might be the cause of one bias outcompeting another. In this section, I expand upon my
previous work by examining the local ﬁtness landscapes of random viable genotypes over the
course of a typical Avida experiment in this work.
From each of 100 replicate populations under conditions identical to the UNB treatment
in Section 3.2.1, I chose a random viable genotype every 5000 updates. For each genotype,
I then collected ﬁtness information about its 1-substitution away neighbors. To get the
1-substitution neighbors, I mutated every site in the sample genome to each of the 25 instructions. I assigned a ﬁtness to each mutant using the average ﬁtness from 10 trials to
account for phenotypic stochasticity. By comparing the relative ﬁtness of each mutant to
its original, I was able to ﬁnd the probability that a substitution would be either beneﬁcial,
80

Average Final Fitness [Log]

20

A

B

C

D

15
10
5
0
−5

B

A

C

2×POS

D

POS

Treatment

UNB

NEG

Figure 5.6. Average ﬁtness distribution in single bias experiments. The 2×POS
and UNB treatments had statistically identical ﬁnal population average ﬁtnesses (p = 0.075,
2-tailed Mann-Whitney U-Test)
neutral, deleterious, or lethal. To account for ﬁnite population size eﬀects, I assigned genotypes with a relative ﬁtness of (1.0 ± 3600−1 ) to be neutral. To test for diﬀerences in the
landscape due to mutation bias, I created ﬁtness vectors where the relative abundance of
each mutant was derived from its probability of arising under POS, UNB, and NEG biases.
Figure 5.7 shows how the average distribution of beneﬁcial, neutral, deleterious, and
lethal mutations vary in the local landscape of the random viable genotypes from 100 replicate populations under three mutation biases when synonymous mutations are allowed. In
general, POS shows relatively higher probability of achieving a neutral mutation relative to
the two other biases, and a correspondingly lower average probability of deleterious and
lethal mutations.
In order to see if there is any quantitative diﬀerence between POS and UNB ﬁtnesses, I

81

Categorical
Mutation Probability

0.8

0.6
beneﬁcial
neutral
deleterious
lethal

0.4

0.2

0.0

0

20

40
60
Update [×103 ]

80

100

Figure 5.7. Average distribution of mutation eﬀects around random viable genotypes. Each line in the graph above shows the average probability of a type of mutation
around random viable genotypes from 100 replicates sampled every 5000 updates. The type
of mutation is identiﬁed in the legend. Colored lines show the diﬀerences in distribution of
mutation eﬀect under POS (yellow), UNB (blue) and NEG (red).
compared the distribution of ﬁtness vectors under each bias, both allowing and excluding
the possibility of synonymous mutations for each sample landscape. Not accounting for
multiple comparison corrections, only a couple samples had signiﬁcantly diﬀerent ﬁtness
vectors between POS and UNB (p < 0.05, 1-tailed U-Test) when synonymous substitutions
were not included in the ﬁtness vectors. Such results were not indicative of anything short
of identical ﬁtnesses of local neighbors regardless which of the two biases are used. Allowing
vectors with synonymous substitution, there were many more instances where POS-biased
ﬁtness vectors have a signiﬁcantly higher range of ﬁtness values than UNB-biased counterparts;
however, signiﬁcance vanishes after correcting for multiple comparisons. For each of the
20 sample time points, at least one and as many as eight of the 100 replicates have POS-

82

ﬁtness vectors with distributions shifted signiﬁcantly to the right of UNB-ﬁtnesses (p < 0.05,
uncorrected 1-tailed U-Test). However, in both cases there was no signiﬁcant indication of
major diﬀerences between the distribution of 1-mutant ﬁtnesses when correcting for multiple
comparisons sans a single comparison made with synonymous mutations allowed at a one
time point.
There is only a small and very weak diﬀerence in the local ﬁtness landscapes of random
viable genotypes between POS and UNB biases. How can evolution pick between biases with
such a small local ﬁtness?
One possibility for the small diﬀerences in local landscapes is that they could be the
result of the sampling procedure. Since most mutations are at least deleterious (as shown
in Figure 5.7), any random sample in the population is likely to not be the most ﬁt. At any
given time, all things being equal, any organism has only a N −1 (N being population size)
chance of its oﬀspring outcompeting all other organisms. This value decreases when ﬁtness
diﬀerences are taken into consideration. So, the samples taken from this set of experiments
could just be from those common genotypes with lineages that preferentially become extinct
over time.
Indeed, only organisms along the PLoD up to the most recent common ancestor at the end
of an experiment were truly successful. Perhaps a rare event, such as a favorable local ﬁtness
landscape, a positive epistatic pairing, or a more ﬁt competitor being randomly replaced
in the population allows for success. In those cases, small, but constant trait-based biases
might be ampliﬁed to the point where selection can distinguish them. Since mutation bias
consistently decreases deleterious loads, its long-term inﬂuence might be great.
Perhaps a more interesting experiment would be to compare the frequency of signiﬁcant
diﬀerences of ﬁtness distributions along the PLoD under diﬀerent mutation biases relative to
those of random samples. Even if there are slightly more diﬀerences that survive the scrutiny
of strict statistical testing, there would be evidence to strengthen the argument that small,
chance increases in beneﬁcial outcome are the driving force for the evolution of mutation

83

biases as well as singling out those organisms whose oﬀspring will have a disproportionate
chance to dominate.
Another possible reason why biases might be selected despite their statistically-identical
local ﬁtness landscapes is that the aggregate behavior of a bias might be a driving force for
selectability over time. In other words, biases might not need to have a large local eﬀect to be
selectable; a small but consistent advantage might be suﬃcient for a bias to be preferentially
selected.

5.5

Summary

In this chapter, I examined the ability for a mutation bias to evolve. With consideration
of the large possibility state for mutation biases, I chose to use small three and six-bias
mutational spectrums. I allowed both demes and individuals to evolve to use either the
three or six biases. At the end of deme experiments, regardless of whether mutation was
structured or unstructured, demes evolved to use POS preferentially over the other biases.
When individuals were allowed to evolve a mutation bias, 2×POS rose to dominance in the
in six-bias treatments, despite the fact it does not signiﬁcantly improve adaptation relative
to UNB in the long-term.
Looking for why one bias might be chosen over another, I sampled random viable genotypes periodically over the course of 100 replicate experiments. I then found the local ﬁtness
landscape around these genotypes and classiﬁed mutants as being either beneﬁcial, neutral,
deleterious or lethal relative to the sample. I also assigned ﬁtnesses to each mutant. Although there appeared to be small qualitative diﬀerences between the landscapes biased by
POS and UNB I found little statistical diﬀerence between the distribution of relative ﬁtnesses
under diﬀerent biases for these landscaped samples. This lack of diﬀerence led me to consider
the possibility that rare increases in the supply of non-deleterious mutations or small but
consistent beneﬁts might be the cause for a mutation bias to be selected.

84

CHAPTER 6
Discussion and Further Avenues to
Explore
In the preceding chapters, I have shown that mutation bias can signiﬁcantly change the
outcome of evolution; can be visible to selection; and can evolve in a limited trait-space. One
element, why a particular bias is chosen by evolution over another, I have only speculated
about. I now discuss four possible ways to extend this work.

6.1

The role of synonymous mutations

One possible reason for the selection of a mutation bias such as POS may be the small increase
in robustness caused by synonymous mutations during substitution events. The POS bias
increases the probability of synonymous mutations relative to the UNB biased based on my
ﬁndings in Chapter 3 that the POS bias more closely matches the composition of genomes
than the UNB bias does. My ﬁndings in Chapter 5 provide some evidence that synonymous
mutations may be a reason why the POS bias allows organisms to produce better oﬀspring
than the UNB bias. Synonymous mutation also may explain my Chapter 4 ﬁndings where I
show that the POS bias can outcompete the UNB bias even when beneﬁcial mutations are not
allowed.
In future work, I plan to determine more precisely the role of synonymous mutations
in the selection of mutation bias. I plan to do this by making synonymous mutations a
researcher-controlled option that can be turned oﬀ. If a researcher does not allow synonymous

85

mutations, the system will force a site to change to a new instruction when the site is
selected for a substitution mutation. This implies the researcher-speciﬁed mutation rate will
be identical to the eﬀective mutation rate, something that is not quite true in the current
implementation of Avida.
I plan to use this feature as follows. First, I will conduct more competition experiments
from Chapter 4 where I disallow synonymous mutations and where I disallow both synonymous and beneﬁcial mutations. With the ﬁrst experiment, I can test whether beneﬁcial
mutations and other non-synonymous neutral mutations are suﬃcient to allow one bias such
as POS to outcompete another bias such as UNB. With the second experiment, I can test
whether non-synonymous neutral mutations are suﬃcient to allow one mutation bias such
as POS to outcompete another mutation bias such as UNB.

6.2

The role of the environment

I performed all of the experiments in this work using a common set of experimental conditions and some variant of the Logic-9 reward structure. The Logic-9 reward structure is
well-studied, making it an excellent test case; however, it is not known if these results are
generalizable to other reward structures or environments.
In future work, I plan to repeat the preceding experiments using the path ﬁnding environment from Avida, where an organism is rewarded for its ability to follow a trail of
resources. The path ﬁnding reward structure is fundamentally diﬀerent than the Logic-9
reward structure in three ways. First, the critical instructions needed for performing a path
ﬁnding behavior, which include sensing markers, turning, and moving, are signiﬁcantly different than the instructions used to perform a logic operation such as NAND or IO. Second,
because the rewarded behaviors are signiﬁcantly diﬀerent, the evolution of good solutions
may be quite diﬀerent in the path ﬁnding reward structure than the Logic-9 reward structure. One piece of evidence that supports this diﬀerence is that only 6% of path ﬁnding

86

replicates typically evolve to high ﬁtness where as 35% of Logic-9 replicates typically evolve
high ﬁtness populations.

6.3

The role of mutation bias in warping ﬁtness landscapes

I’ve only examined the eﬀect of mutation bias on the neighbors closest to viable genotypes
selected at random. I found that there is no signiﬁcant diﬀerence in the distribution of
ﬁtnesses of these mutants when weighted by biases, but an overall small qualitative diﬀerence
in the distribution of beneﬁcial, neutral, and deleterious mutations. Even with these small
changes mutation bias may warp the ﬁtness landscape to allow diﬀerent adaptations to
emerge.
One way to test if biases produce diﬀerent adaptations is to examine organisms evolved.
Looking at which instructions are used to implement adaptations might provide information
about the structure of the adaptation. If diﬀerent biases produce diﬀerently structured
adaptations, then there is evidence that warping the ﬁtness landscape using a bias leads to
diﬀerent regions of the ﬁtness landscape. Such an understanding is important because it
provides an additional means of varying selective search by pitting selection and mutation
against one another as drivers of evolution.

6.4

Allowing the evolution of arbitrary mutation biases

In this work, I created a small number of “complete” mutation biases that I let organisms
use. Some reasons for this were practical: I wanted to have clear signals when selection
chose a mutation bias, and I wanted to have a well deﬁned set of states to analyze. However,
these biases only explore a fraction of possible biases and were created from knowledge about
evolution in the Logic-9 reward structure. Allowing mutation biases to evolve with fewer

87

constraints would strengthen this work. Further, additional parameters such as mutation
rate could be varied to see if they aﬀect the evolution of mutation bias.
One attempt to evolve mutation bias with additional degrees of freedom is shown in
Figure 6.1. Replicates in these experiments were allowed to use any of 27 mutation biases:
one of the biases was UNB; the other 26 increased the probability of mutating to a single
instruction by a factor of ten.
I repeated each experiment 300 times over four diﬀerent scalings of the default substitution rate to see if there were any changes in bias evolution. In general, h-copy was greatly
preferred by populations, with the uniform bias’s dominance decaying quickly, losing its top
standing across all replicates by about 20 × 103 updates in all but the lowest mutation rate
treatment. Under the mutation rate used in the majority of this work, a high h-copy bias
came to dominance in 234 of the 300 replicates (78%). At both ends of the mutation rate
assay, the preference for high h-copy weakened. At a substitution rate of 10−3 of normal,
h-copy was in the majority of only 39 replicates. At a ten-fold higher substitution rate than
usual, h-copy was only dominant in only 36 of 300 populations. IO had the most replicates
evolving it at the end of that treatment with 46 replicates predominantly using it.
It would make sense that the mutation bias would be inﬂuenced by mutation rate. It
is known that mutation rates higher than usual allow populations to better adapted to
the Logic-9 reward structure [5]. I expect populations might be able to leverage a taskproducing instruction such as IO to a greater degree at these high mutation rates for either
purposes of robustness due to a greater need for synonymous mutation or task-production.
Finally, having biases evolve to a greater degree on their own might provide additional
information about environments, leading to the possibility of greater self-adaption of genomes
to the environment.

88

x10−3

Number of Replicates

300

x10−2
Uniform
nop-A
nop-B
nop-C
pop
push
swap-stk
nand
IO
h-alloc
h-divide
h-copy
h-search
if-label
set-ﬂow

250
200
150
100
50
0
Normal

Number of Replicates

300

x10

250
200
150
100
50
0

0

20

40
60
80
3]
Update [x10

100

0

20

40
60
80
3]
Update [x10

100

Figure 6.1. The evolution of mutation biases over diﬀerent mutation rates. Each plot shows the number of replicates
(out of 300) where a single mutation bias dominates in the population. 27 biases were allowed: UNB and a bias where a single
instruction had an inﬂow rate 10 higher than the others. The legend shows the biases that a relatively high number of replicates
preferred. The title for each plot shows the scaling of the rate of substitution from the default in Appendix B.1. Insertion and
deletions were not scaled.
89

APPENDICES

APPENDIX A
Avida Virtual CPU Instructions
The virtual CPU instructions listed below were used in all Avida experiments in this work.
Instruction descriptions were adapted from the documentation from Avida v2.6 [30]. Each
instruction in an Avidian genome is represented by an alphabetic symbol.
By default, many of the instructions use the BX register and its compliment the CX register
for inputs. This behavior may be modiﬁed by a nop, causing the instruction to examine a
diﬀerent register pair (listed below). The notation ?BX? will be used to denote the conditional
target pair of registers for relevant instructions below.
Instructions which move heads may have their behavior modiﬁed by nops as follows:
nop-A refers to the instruction pointer, nop-B to the read head, and nop-C to the write
head. The conditional target heads will be labeled as ?IP? below.

91

Table A.1. Description of default Avida virtual CPU instructions.
Symbol

Name

a

nop-A

b

nop-B

c

nop-C

d
e

Description

The instructions nop-A (a), nop-B (b), and nop-C (c)
are no-operation instructions and will not do anything
when executed. They can, however, modify the behavior
of the preceding instruction or act a label that denotes
a location in the genome.
nops are often paired with their compliment when
specifying the behavior of the preceding instruction.
nop-A is complimented with nop-B; nop-B with nop-C;
and nop-C with nop-A.

if-n-equ and if-less, along with if-label execute the
if-n-equ next instruction (possibly following a modifying nop) if
the contents of register ?BX? is not equal to or less than
if-less ?CX?, respectively. Any nop following the instruction will
specify the register compliment pair to be used in the
comparison.

f

pop

g

push

push and pop will places from the value ?BX? register
into the active stack or moves the value from the top of
the active stack to the ?BX? register.

92

Table A.1 cont’d
Symbol

Name

Description

h

swap-stk

i

swap

j

shift-r

k

shift-l

l

inc

m

dec

n

add

o

sub

p

nand

q

IO

This instruction simultaneously transmits the contents of
register BX and receives a value from the environment
to place into BX.

r

h-alloc

This instruction allocates additional space to store the
oﬀspring genome at the end of the parent’s genome. The
new sites are initialized to nop-A. The size of the new
allocation can be set in the conﬁguration ﬁle.

s

This instruction divides its oﬀspring and (by default) resets the parent. The memory from the start of the organh-divide ism to the read head constitutes the parent; the memory
from the read head to the write head constitutes the oﬀspring; excess sites are lost.

Toggles the active stack.

Swaps the contents of register ?BX? with its compliment.

These instructions modify the value of register ?BX?.
shift-r and shift-l perform a bitwise shift of the contents of register ?BX? either right or left, respectively,
padding with zeros. inc and dec raise or lower the value
of register ?BX? by 1. add sums register ?BX? and ?CX?;
sub subtracts ?CX? from ?BX?. NAND performs a bitwise
not-and on the contents of register ?BX? and ?CX?.

93

Table A.1 cont’d
Symbol

Name

Description

t

h-copy

This instruction copies the instruction located at the read
head to the site located at the right head.

u

v
w
x

This instruction will place the ﬂow head at the ﬁrst following occurrence of a set of nops matching the compliment of the nops following it. If no nops follow h-search,
h-search then the ﬂow head is placed immediately after it. Register BX and CX will receive the distance from the current
position of the instruction pointer to the compliment and
the size of the label, respectively. If no following nops are
present, the values of register BX and CX are set to 0.

mov-head These instructions move ?IP?. mov-head jumps ?IP? to
the location of the ﬂow head. jmp-head moves ?IP? the
jmp-head number of positions forward in the organism based on
get-head the value of register CX. get-head will copy the position
of ?IP? into the CX register.

y

if-label will read the nop label following it and tests
if-label whether or not the compliment of that label has been
recently copied. If so, the following instruction gets executed; otherwise it gets skipped.

z

set-flow This instruction moves the ﬂow head to the position denoted in the ?CX? register.

94

APPENDIX B
Experiment Settings

B.1

Common Settings

Many of the experiments in this work were performed using a common set of experimental
settings. Below is a truncated list of these settings.

Table B.1. Common experimental settings used in this work.
Setting

WORLD GEOMETRY

Value

Description

Torus

The shape of the Avida world. A Torus has
no boundaries. This setting does not make
any diﬀerence in the behavior of the Avida
population when in Mass Action (global)
placement; however, it does aﬀect the behavior of Neighborhood (local) oﬀspring
placement.

95

Table B.1 cont’d
Setting

HARDWARE TYPE

Value

Description

Original CPUs

All experiments in this work uses the original heads-based CPU. This virtual CPU
contains three numerical registers, a special purpose register to store the last set of
nops read, two stacks, and four pointers
(instruction pointer and the read, write,
and ﬂow heads).

Depending on the experiment, this may be
one of two values. In Mass Action, oﬀspring are placed randomly in the population. In neighborhood, oﬀspring replace
an organism in the cells surrounding the
parent.

Mass Action
BIRTH METHOD

or
Random in neighborhood

PREFER EMPTY

Yes

Preferentially select empty cells when using oﬀspring placement.

ALLOW PARENT

Yes

Allow the parent to be replaced by the oﬀspring.

DEATH METHOD

Exec = N*LIM+d

AGE LIMIT

N=20

AGE DEVIATION

d=0

Organisms will die when the number of instruction executed equals the length of its
genomes * AGE LIMIT + AGE DEVIATION.

96

Table B.1 cont’d
Setting

Value

Description

DIVIDE METHOD

Reset Parent

The parent’s registers and heads will be
reset after the division of the oﬀspring.

CHILD SIZE RANGE

MIN COPIED LINES

This setting sets the maximum diﬀerence
in length between the parent and oﬀspring.
A value of 2.0 requires the oﬀspring to be
at least half as long as the parent and at
most twice as long. This value also determines the number of instructions added to
the end of the genome following the ﬁrst
execution of the h-alloc instruction.

2.0

This sets the minimum fraction of the
number of sites in the parent genome that
must be copied before division is allowed.
h-divide instructions executed before this
criteria is met are ignored.

0.9

MIN EXE LINES

0.05

REQUIRE ALLOCATE

This sets the minimum fraction of instructions that must be executed by the organism before divide. h-divide instructions
executed before this criteria is met are ignored.

Yes

This setting requires that h-alloc be executed before a divide is allowed.

97

Table B.1 cont’d
Setting

Value

FAIL IMPLICIT

Yes

POINT MUT PROB

0.0

There are no “cosmic-ray” mutations applied per update.

COPY MUT PROB

0.0025

This is the probability of a substitution (including synonymous) occurring during the
copying of an instruction.

INS MUT PROB

0.0

DEL MUT PROB

0.0

DIV MUT PROB

0.0

DIVIDE MUT PROB
DIVIDE INS PROB
DIVIDE DEL PROB

Description

This setting prohibits oﬀspring that are
not identical to their parent in the absence of explicit mutations, such as the
ones listed below.

These settings are for insertion (INS), deletion (DEL), or point (DIV) mutations applied per-site on divide.

0.0
These settings are for mutations applied
on divide over the entire genome for
point (MUT), insertion (INS) and deletion
(DEL) events.

0.05
0.05
0.0

98

Table B.1 cont’d
Setting

Value

AVE TIME SLICE

These settings aﬀect how merit is mapped
into SIPs. The ﬁrst setting determines how
many SIPs are to be made available to the
population, in this case 30 × N , where N
is the population size. The proportional
slicing method distributes merit randomly
based on the relative merit of each individual (e.g. it is not deterministic). The base
merit method sets the initial merit (before task bonuses are applied) to be proportional to the minimum of the number
of lines executed or copied by the parent.
The default bonus is the initial merit before any tasks are applied.

30

SLICING METHOD

Description

Probabilistic

BASE MERIT METHOD ∝ min{exec, copied}
DEFAULT BONUS

1.0

99

B.2

Calibration Settings

The initial runs used to generate the steady state matrix diﬀered from the common settings.
Below are the diﬀerences between the common settings and the calibration settings.

Table B.2. Deviant calibration experiment settings.
Setting

Value

Description

DEATH METHOD

Never die

In the calibration runs, organisms never
died of old age.

0.50

Fewer sites needed to be copied in the calibration runs before divide is allowed.

COPY MUT PROB

0.0075

The substitution rate was three times
higher than the common settings.

FAIL IMPLICIT

Oﬀ

Organisms are allowed to produce diﬀerent
organisms in the absence of mutation.

MIN COPIED LINES

100

BIBLIOGRAPHY

BIBLIOGRAPHY

[1] Banerjee, T., Gupta, S. K., and Ghosh, T. C. Role of mutational bias and
natural selection on genome-wide nucleotide bias in prokaryotic organisms. Biosystems
81, 1 (Jul 2005), 11–8.
[2] Belozersky, A., and Spirin, S. A correlation between the compositions of deoxiribonucleic and ribonucleic acids. Nature 183, 4628 (1958), 111–112.
[3] Bernardi, G. Isochores and the evolutionary genomics of vertebrates. Gene 241, 1 (1
2000), 3–17.
[4] Bhatnagar, S. K., Bullions, L. C., Lew, G., and Bessman, M. J. Characterization of the defect in the Escherichia coli mutT1 mutator gene. The Journal of
Bacteriology 172, 5 (5 1990), 2802–2803.
´
[5] Clune, J., Misevic, D., Ofria, C., Lenski, R. E., Elena, S. F., and Sanjuan,
R. Natural selection fails to optimize mutation rates for long-term adaptation on rugged
ﬁtness landscapes. PLoS Computational Biology 4, 9 (09 2008), e1000187–.
[6] Cox, E. C., and Yanofsky, C. Altered base ratios in DNA of an Escherichia coli
mutator strain. Proceedings Of The National Academy Of Sciences Of The United States
Of America 58, 5 (1967), 1895.
[7] Dayhoff, M., Schwartz, R., and Orcutt, B. C. A model of evolutionary change
in proteins, supplement 3. In Atlas of Protein Sequence and Structure, M. Dayhoﬀ, Ed.
National Biomedical Research Foundation, Washington, DC, 1978, pp. 345–352.
[8] Dorn, E. Universal Biosignatures for the Detection of Life. Phd, California Institute
of Technology, May 2005.
[9] Dorn, E., Nealson, K., and Adami, C. Monomer abundance distribution patterns as a universal biosignature: Examples from terrestrial and digital life. Journal of
Molecular Evolution (2011-01-21), 1–13.
[10] Fowler, R., and Schaaper, R. The role of the mutT gene of Escherichia coli in
maintaining replication ﬁdelity. FEMS Microbiology Reviews 21, 1 (AUG 1997), 43–54.
[11] Francino, M. P., and Ochman, H. Strand asymmetries in DNA evolution. Trends
in Genetics 13, 6 (Jun 1997), 240–245.
[12] Frederico, L. A., Kunkel, T. A., and Shaw, B. R. cytosine deamination in
mismatched base-pairs. Biochemistry 32, 26 (Jul 1993), 6523–6530.
[13] Freese, E. On evolution of base composition of DNA. Journal of Theoretical Biology
3, 1 (1962), 82–101.

101

[14] Gentile, C. F., Yu, S.-C., Serrano, S. A., Gerrish, P. J., and Sniegowski,
P. D. Competition between high- and higher-mutating strains of Escherichia coli.
Biology Letters (2011).
[15] Gu, X., Hewett-Emmett, D., and Li, W. H. Directional mutational pressure
aﬀects the amino acid composition and hydrophobicity of proteins in bacteria. Genetica
102, 3 (1998), 383–391.
[16] Henikoff, S., and Henikoff, J. G. Amino acid substitution matrices from protein
blocks. Proceedings of the National Academy of Sciences 89, 22 (11 1992), 10915–10919.
[17] Hurst, L. D., and Merchant, A. R. High guanine-cytosine content is not an adaptation to high temperature: a comparative analysis amongst prokaryotes. Proceedings
Of The National Academy of Sciences of the United States of America 268, 1466 (Mar
2001), 493–497.
[18] Jukes, T. H., and Bhushan, V. Silent nucleotide substitutions and G+C content
of some mitochondrial and bacterial genes. Journal of Molecular Evolution 24, 1 (198612-01), 39–44.
[19] Karran, P., and Lindahl, T. Hypoxanthine in deoxyribonucleic acid: generation
by heat-induced hydrolysis of adenine residues and release in free form by a deoxyribonucleic acid glycosylase from calf thymus. Biochemistry 19, 26 (12 1980), 6005–6011.
[20] Kauffman, S. A. Metabolic stability and epigenesis in randomly constructed genetic
nets. Journal of Theoretical Biology 22, 3 (3 1969), 437–467.
[21] Lenski, R., Ofria, C., Pennock, R., and Adami, C. The evolutionary origin of
complex features. Nature 423 (2003), 139–144.
[22] Lind, P. A., and Andersson, D. I. Whole-genome mutational biases in bacteria.
Proceedings Of The National Academy of Sciences of the United States of America 105,
46 (Nov 2008), 17878–17883.
[23] Lindahl, T., and Nyberg, B. Heat-induced deamination of cytosine residues in
deoxyribonucleic acid. Biochemistry 13, 16 (1974), 3405–3410.
[24] Maki, H., and Sekiguchi, M. Mutt protein speciﬁcally hydrolyses a potent mutagenic substrate for dna synthesis. Nature 355, 6357 (January 1992), 273–275.
[25] McLean, M. J., Wolfe, K. H., and Devine, K. M. Base composition skews,
replication orientation, and gene orientation in 12 prokaryote genomes. Journal of
Molecular Evolution 47, 6 (Dec 1998), 691–696.
[26] Mrazek, J., and Karlin, S. Strand compositional asymmetry in bacterial and large
viral genomes. Proceedings Of The National Academy of Sciences of the United States
of America 95, 7 (Mar 1998), 3720–3725.

102

[27] MUTO, A., and OSAWA, S. The guanine and cytosine content of genomic DNA
and bacterial evolution. Proceedings Of The National Academy of Sciences of the United
States of America 84, 1 (JAN 1987), 166–169.
[28] Ofria, C., Huang, W., and Torng, E. On the gradual evolution of complexity
and the sudden emergence of complex features. Artiﬁical Life 14, 3 (2008), 255–263.
Artiﬁcial Life.
[29] Ofria, C., and Wilke, C. Avida: A software platform for research in computational
evolutionary biology. Journal of Artiﬁcial Life 10 (2004), 191–229.
[30] Ofria, et al. The avida digital life platform. Version 2.6, http://avida.devosoft.org.
[31] Pennock, R. Models, simulations, instantiations and evidence: The case of digital
evolution. Journal of Experimental and Theoretical Artiﬁcial Intelligence 19, 1 (2007),
29–42.
[32] Ray, T. S. Evolution, complexity, entropy and artiﬁcial reality. Physica D: Nonlinear
Phenomena 75, 1-3 (1994), 239 – 263.
[33] Rocha, E. P. C., and Danchin, A. Base composition bias might result from competition for metabolic resources. Trends in Genetics 18, 6 (Jun 2002), 291–294.
[34] Rupp, M., Torng, E., and Ofria, C. The evolution of novel body types under
diﬀering selective pressurs in digital organisms. In Proceedings of the Tenth International
Conference on Artiﬁcial Life (Bloomington, IN, 2006), pp. 268–274.
[35] Singer, G. A. C., and Hickey, D. A. Nucleotide bias causes a genomewide bias in
the amino acid composition of proteins. Molecular Biology and Evolution 17, 11 (Nov
2000), 1581–1588.
[36] Sniegowski, P. D., Gerrish, P. J., Johnson, T., and Shaver, A. The evolution
of mutation rates: separating causes from consequences. BioEssays 22, 12 (Dec 2000),
1057–1066.
[37] Stoltzfus, A. Mutation-biased adaptation in a protein NK model. Molecular Biology
and Evolution 23, 10 (2006), 1852–1862.
[38] Sueoka, N. Correlation between base composition of deoxyribonucleic acid and amino
acid composition of protein. Proceedings of the National Academy of Sciences 47, 8 (08
1961), 1141–1149.
[39] Sueoka, N. On the genetic basis of variation and heterogeneity of DNA base composition. Proceedings Of The National Academy of Sciences of the United States of America
48, 4 (1962), 582–592.
[40] Sueoka, N. Directional mutation pressure and neutral molecular evolution. Proceedings Of The National Academy of Sciences of the United States of America 85 (1988),
2653–2657.
103

[41] Treffers, H. P., Spinelli, V., and Belser, N. O. A factor (or mutator gene)
inﬂuencing mutation rates in Escherichia coli. Proceedings Of The National Academy of
Sciences of the United States of America 40, 11 (11 1954), 1064–1071.
[42] Wada, A., and Suyama, A. Local stability of DNA and RNA secondary structure
and its relation to biological functions. Progress in Biophysics and Molecular Biology
47, 2 (1986), 113–157.
[43] Wang, H. C., Singer, G. A. C., and Hickey, D. A. Mutational bias aﬀects
protein evolution in ﬂowering plants. Molecular Biology and Evolution 21, 1 (2004),
90–96.
[44] Wernegreen, J. J., and Funk, D. J. Mutation exposed: A neutral explanation for
extreme base composition of an endosymbiont genome. Journal of Molecular Evolution
59, 6 (Dec 2004), 849–858.
[45] Yampolsky, L., and Stoltzfus, A. Bias in the introduction of variation as an
orienting factor in evolution. Evolution & Development 3, 2 (2001), 73–83.

104