EVOLUTION AND EVOLVABILITY IN CHANGING ENVIRONMENTS
By
Rosangela Canino-Koning

A DISSERTATION
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
Computer Science – Doctor of Philosophy
2017

ABSTRACT
EVOLUTION AND EVOLVABILITY IN CHANGING ENVIRONMENTS
By
Rosangela Canino-Koning
The specific meaning of the term “evolvability” is heavily debated, but most definitions can
be summarized as: the potential of populations and genomes to produce adaptive variation
and complex structures in response to mutation and selection. Changing environments are
thought to play a significant role in shaping and promoting evolvability through alternating
selective pressures.
In this dissertation, I will discuss my recent research on the interplay between changing
environments, evolvability, genetic architecture, and the evolution of horizontal gene transfer
(HGT), an information-rich mutagenic function that is ubiquitous in nature. Before delving
into my own research, however, I begin in the first chapter by providing a survey of current
literature on each of these topics, with emphases on how they are believed to arise, how they
affect subsequent evolution, and how they relate to each other.
Genetic architecture and population dynamics clearly have a complex interplay in ongoing evolutionary dynamics. Evolutionary history, population diversity, modularity, and task
size all play a role in determining the location and characteristics of populations in genotype
space, and alter the genotype to phenotype map that permits neutral genetic variation. All of
these features contribute to evolvability. In Chapter 2, I demonstrate how changing environments provided a sufficient selective pressure to produce quasi-modular genetic architectures
that allow for rapid adaptation to the meta-environment of environmental change.
Horizontal gene transfer is a highly regulated, ubiquitous, and ancient mechanism for
exchanging genetic material between unrelated organisms. In the third chapter, I explore
conditions which may have led to the evolution of horizontal gene transfer through transformation, and identify mechanisms that might support its continued performance.

In Chapter 4, I compare the fitness and phenotypic effects of the HGT process against
other types of increasingly less information rich mutational operators. I demonstrate that
not only is HGT selected for in harsh changing environments, but that other mutagenic
instructions that contain less information, or provide lesser fitness benefits are not similarly
selected for.
In the fifth chapter, I explore the long-term evolutionary potential of populations evolved
in changing environments by evolving two different populations, one evolved in a minimal
changing environment, and the other in a rich changing environment, and exposing them to
a brand new environment. I demonstrate that while populations adapted to harsh changing
environments are indeed able to adapt quickly to previously seen environmental changes, that
these populations do not fare as well in brand new environments. Rather, benign changing
environments perform best in measures of task discovery and exploration.
In the final chapter, I conclude with a synthesis of my results, along with implications
for the field, as well as identification of some new directions for pursuing my research into
changing environments.

Copyright by
ROSANGELA CANINO-KONING
2017

This thesis is dedicated to Kendall Koning.
I would never have gotten this far without you.

v

ACKNOWLEDGMENTS

I would like to thank all the members of the Devolab, past and present, for their unflagging
engagement, criticism, and encouragement over the years. I couldn’t have asked for a better
lab.
A special thanks to Art Covert, my lab bestie for many years. Your encouragement,
friendship, and advice on how to approach my work was invaluable. Also, special thanks
to Matt Rupp, Luis Zaman, and Josh Nahum. All of you asked important questions at
various points that strongly shaped my work. This stuff would have been much less useful
and interesting without your input.
A very special thank you to Mike Wiser, my friend and faithful frequent collaborator. A
solid half of my research is based on our collaboration, and I have no idea how any of these
papers could have gotten out the door without your help. You’re not around just for the
stats!
To my former co-advisor Titus Brown, thanks for kicking me out of your lab, you jerk. ;)
Trying to finish with two completely different lines of research would have been virtually
impossible, and I appreciate your wisdom in forcing me to make a decision. Seriously,
though, thank you for your advice and friendship.
Finally, thank you to my advisor Charles Ofria. I had never considered pursuing evolution
as a research topic until I randomly met you during my first visit to MSU. I’m glad I did.
For one, my research topic would have been way more boring, and second, the environment
you foster in your lab is incredibly nurturing and supportive. I’m sure there are a lot of
great advisors out there, but you’re the best I know.

vi

TABLE OF CONTENTS

LIST OF TABLES

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

x

LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xi

KEY TO ABBREVIATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
CHAPTER 1 INTRODUCTION - CHANGE, ADAPTATION AND THE EVOLUTION OF EVOLVABILITY . . . . . . . . . . . . . . . . . . . . .
1.1 Evolvability and Evolutionary Potential - Why Study It . . . . . . . . . . . .
1.2 What is Evolvability (and why is it so hard to pin down) . . . . . . . . . . .
1.3 Changing Environments and Evolvability . . . . . . . . . . . . . . . . . . . .
1.4 Historical Conceptions of Evolvability . . . . . . . . . . . . . . . . . . . . . .
1.4.1 Modern Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.2 Evolvability as a Distinct Concept . . . . . . . . . . . . . . . . . . . .
1.4.3 Theoretical Frameworks for the Evolution of Evolvability . . . . . . .
1.5 So, what do I mean by Evolvability? . . . . . . . . . . . . . . . . . . . . . .
1.5.1 What is Modularity? . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.1.1 Measuring Modularity . . . . . . . . . . . . . . . . . . . . .
1.5.2 What is Robustness? . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.2.1 Measuring Robustness to Mutation . . . . . . . . . . . . . .
1.5.3 Predicting Short-Term Evolvability with Landscape Metrics . . . . .
1.5.4 Expected Value of Fitness Landscapes . . . . . . . . . . . . . . . . .
1.6 Digital Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.1 Avida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7 Statistical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
2
3
4
4
6
8
9
9
10
11
12
14
16
17
18
20

CHAPTER 2 CHANGING ENVIRONMENTS PROMOTE RAPID ADAPTATION
IN DIGITAL ORGANISMS . . . . . . . . . . . . . . . . . . . . . .
2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Evolvability and Genetic Architecture . . . . . . . . . . . . . . . . . .
2.1.1.1 Mutational Landscapes . . . . . . . . . . . . . . . . . . . .
2.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1.1 Cyclic and Stochastic Changing Environments . . . . . . . .
2.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Cyclic Changing Environments . . . . . . . . . . . . . . . . . . . . .
2.3.1.1 Performance of EQU . . . . . . . . . . . . . . . . . . . . . .
2.3.1.2 Evolutionary History and Population Structure . . . . . . .
2.3.1.3 Genetic Architecture . . . . . . . . . . . . . . . . . . . . . .
2.3.1.4 Nearby Mutational Landscape . . . . . . . . . . . . . . . . .
2.3.2 Stochastic Changing Environments . . . . . . . . . . . . . . . . . . .

21
21
22
23
24
24
24
26
27
27
28
30
34
38

vii

2.4

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

CHAPTER 3 CHANGING ENVIRONMENTS AND THE EVOLUTION OF HORIZONTAL GENE TRANSFER . . . . . . . . . . . . . . . . . . . . .
3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Origins of Horizontal Gene Transfer in nature . . . . . . . . . . . . .
3.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 HGT in Avida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1.1 Environmental Conditions . . . . . . . . . . . . . . . . . . .
3.2.2 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Changing environments elevate HGT use . . . . . . . . . . . . . . . .
3.3.2 HGT derives most benefit from on-cycle fragments, but not all . . . .
3.3.2.1 Fitness Effects . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2.2 Beneficial Phenotype Switching . . . . . . . . . . . . . . . .
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CHAPTER 4 HORIZONTAL GENE TRANSFER VS OTHER TYPES OF MUTATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1.1 Alternative Mutagenic Instructions . . . . . . . . . . . . . .
4.2.1.2 Comparing HGT to Other Mutation Types . . . . . . . . .
4.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Other mutation types are not elevated in response to HGT . . . . . .
4.3.2 Mutation fitness effect correlate with mutagenic instruction use . . .
4.3.3 HGT mutations increase evolved probability of beneficial phenotype
switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CHAPTER 5 CHANGING ENVIRONMENTS AND LONG TERM EVOLVABILITY
5.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1.1 Environmental Treatments . . . . . . . . . . . . . . . . . . .
5.2.1.2 Set 1 - Minimal Cyclic Changing Environments . . . . . . .
5.2.1.3 Set 2 - Rich Cyclic Changing Environment . . . . . . . . . .
5.2.2 Measuring Task Discovery and Task Performance . . . . . . . . . . .
5.2.2.1 Task Discovery . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2.2 Task Performance . . . . . . . . . . . . . . . . . . . . . . .
5.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Task Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1.1 Benign changing environments outperform harsh environments in task discovery . . . . . . . . . . . . . . . . . . . .

viii

43

46
46
46
47
48
49
51
51
51
54
54
57
59

61
61
62
62
63
64
65
66
68
69
70
72
72
73
73
74
77
77
78
79
81
81
81
81

5.3.1.2

5.4

Harsh changing environments drive populations across the
mutational landscape . . . . . . . . . . . . . . . . . . . . .
5.3.2 Task Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.2.1 Benign changing environments outperform harsh environments in task performance . . . . . . . . . . . . . . . . . .
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.

86
88

.
.

88
90

CHAPTER 6 CONCLUSION AND FUTURE DIRECTIONS . . . . . . . . . . . .
6.1 Limitations of Cyclic Changing Environments . . . . . . . . . . . . . . . . .
6.2 Future Directions - Horizontal Gene Transfer and Long Term Evolvability . .

92
93
94

APPENDICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
APPENDIX A
EXPERIMENTALLY DERIVING PARAMETERS FOR CHANGING ENVIRONMENT CYCLE LENGTHS . . . . . . . . . . 97
APPENDIX B
EXPERIMENTALLY DERIVING PARAMETERS FOR HGT
RECOMBINATION PROBABILITY AND BONUS LEVELS 100
APPENDIX C
CHANGING ENVIRONMENTS ELEVATE ALL INSTRUCTION USE DUE TO REPEATED BOTTLENECKS . . . . . 104
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

ix

LIST OF TABLES

Table 2.1: Experimental Treatments - Cyclic and Stochastic Changing Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

Table 2.2: OLS Regression Results - Mean Fraction of Mutants Regained
EQU vs Number of Functional and Vestigial Sites . . . . . . . . .

40

Table 3.1: Logic-9 Rewarded Task Groupings . . . . . . . . . . . . . . . . . . .

50

Table 3.2: Experimental Treatments - Evolution of HGT . . . . . . . . . . . .

52

Table 3.3: Experimental Treatments - Effects of HGT . . . . . . . . . . . . . .

53

Table 4.1: Experimental Treatments - Mutation Types . . . . . . . . . . . . .

65

Table 5.1: Experimental Treatments - Minimal Cyclic Changing Environment 78
Table 5.2: Rich Changing Environments - Basic Task-set Rewarded Task
Groupings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

Table 5.3: Experimental Treatments - Rich Cyclic Changing Environment .

80

x

LIST OF FIGURES

Figure 1.1: An example virtual CPU from Avida, with a circular genome
(blue), three registers (purple), input and output handlers (tan), and an
instruction pointer (yellow) indicating the next instruction to be executed. 18
Figure 2.1: Number of organisms performing EQU task. We measured the
execution of the EQU task in all treatments. By the end of the run, we
observed fixation in the control treatment. In the benign treatment, we
observed increasing periodic dips in execution that coincide with phases
of non-reward as the experiments progressed. In the harsh treatment,
we observed adaptation, resulting in abrupt disappearance of EQU in
the punishment phase, followed by rapid recovery of EQU performance
during the reward phase. . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Figure 2.2: Phylogenetic depth over time of a sample population evolved in each
of the three treatments of the cyclic changing environments. Phylogenetic depth is the number of mutational steps from the original ancestor,
and is a rough analog for generations. White horizontal lines mark the
depth of the most recent common ancestor, and discontinuities in this
line indicate that the most recent common ancestor has changed, and
thus that a sweep occurred, or that a competing clade went extinct. The
control treatments had a mean of 18 sweeps (STD=9.05), the benign
treatments had a mean of 21 (STD=19.05), and the harsh treatments
had a mean of 88 sweeps (STD=23.37). Note the difference in scales between y-axes: the control-evolved population has a maximum depth of
400 mutational steps from ancestor, while the harsh-evolved has upward
of 1100. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

Figure 2.3: Per-site entropy over time of a representative sample population.
Each vertical slice represents the per-site entropy of the population at
each update by genetic locus. Hotter colors (red/orange/yellow) indicate greater diversity at this locus, while cooler colors (blues) indicate
the a locus is more consistent across the population. . . . . . . . . . . .

30

Figure 2.4: Population entropy over time of the representative sample population in Figure 2.3. Mean population entropy indicates the relative
diversity of the population at any given time, while the per-site entropy
(see Fig 2.3) shows where in the genomes the population diversity is
located. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

xi

Figure 2.5: Genetic architecture of XOR and EQU over time in static environment for the final dominant genotype in a randomly selected
replicate. Proceeding from the left of each figure, each vertical slice
represents an organism along the line-of-descent to the final dominant.
Positions along the Y-axis represent each genome locus; loci in an organism are colored based on the tasks that they code for. Sites in red
are active sites that code for the XOR task only, sites in blue are active
sites for the EQU task only, and purple sites code for both XOR and
EQU. Knockouts to the sites in black are lethal to the organism. Sites in
the lighter colors (tan, light blue, lavender) represent vestigial sites for
XOR only, EQU only, or both tasks, respectively. As we proceed from
left to right, we can see the evolutionary history of the final dominant
genotype. XOR and EQU overlap almost completely throughout the run. .

31

Figure 2.6: Genetic architecture of XOR and EQU over time in benign
environment for the final dominant genotype in a randomly selected
replicate. Proceeding from the left of each figure, each vertical slice
represents an organism along the line-of-descent to the final dominant,
and as in Figure 2.5, colors represent tasks performed by each genome
locus. In this genome, XOR and EQU evolve to overlap much less than
in the control. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

Figure 2.7: Genetic architecture of XOR and EQU over time in harsh environment for the final dominant genotype in a randomly selected
replicate. Proceeding from the left of each figure, each vertical slice
represents an organism along the line-of-descent to the final dominant,
and as in Figures 2.5 and 2.6, colors represent tasks performed by each
genome locus. In this genome, XOR and EQU evolve to overlap even less
than in the control and benign treatments, with the EQU-only task sites
becoming increasingly scattered throughout the genome. . . . . . . . . .

32

Figure 2.8: Number of functional and vestigial sites by treatment. Both
the benign and harsh changing environments had significantly more sites
devoted to performing only the EQU function (Wilcoxon Rank Sum Test:
Z = -5.57 and -6.96, respectively, p << 0.001). The harsh environment
has a significantly larger number of vestigial sites for the fluctuating
(EQU) task compared to the benign treatment or control (Wilcoxon
Rank-Sum Z = -6.57 and -8.33, p << 0.0001). . . . . . . . . . . . . . .

33

xii

Figure 2.9: A survey of the single-step mutational neighborhood around
organisms that performed the fluctuating task. Note that in both the
benign and harsh treatments, there were significantly more mutants
that lost the EQU task as compared to the control (Wilcoxon Rank
Sum Test: Z = -5.46 and -7.80 respectively, p << 0.0001). This result
indicates that it was easier for the organisms in both treatments to turn
off the EQU task in response to one mutation. . . . . . . . . . . . . . .

34

Figure 2.10: Correlation between task length and mutational task loss in the
1-step neighborhood across all treatments. Note the strong correlation
between the length of the EQU task and the fraction of mutants that lost
EQU (Spearman’s Rho: rs = 8.72, p << 0.001). Further, consider the
weaker correlation between XOR task length, and fraction of mutants
that lost XOR. This suggests that EQU is even less robust to mutation
compared to XOR than can be accounted for by task length alone. . . .

36

Figure 2.11: A survey of the two-step mutational neighborhood of the organisms that lost EQU function in the one-step survey. We found that
in both the harsh and benign treatments, there were significantly more
organisms that regained function in response to mutation than the control. (Wilcoxon Rank Sum Test: Z = -47.9 and -57.82 respectively, p
<< 0.0001). This result indicates that it was easier for the organisms
in both fluctuating environments to regain the task in response to one
additional, non-reversion mutation. . . . . . . . . . . . . . . . . . . . .

37

Figure 2.12: Genomic and phenotypic diffusion rates, showing the probabilities of producing offspring that are genotypically (Dg ) or phenotypically (Dp ) distinct from the parent, while not reducing fitness. Note
that while overall neutral exploration capacity remains relatively stable
between treatments (Kruskal Wallis: H(2) = 1.44, p = 0.49), phenotypic
exploration capacity is increased in both treatments, but especially in
the Harsh treatment. (Wilcoxon Rank Sum Test: Z = -8.02, -8.39,
respectively, p << 0.001). This result is consistent with changing environments promoting the phenotypic evolvability of populations. . . . . .

38

Figure 2.13: Multiple linear regression predicting mean fraction of secondstep mutants from the number of functional and vestigial sites in the
original organism. See Table 2.2. . . . . . . . . . . . . . . . . . . . . . .

39

xiii

Figure 2.14: Genomic and phenotypic diffusion rates in stochastic changing
environments, showing the probabilities of producing offspring that are
genotypically and phenotypically different from the parent, while remaining fitness neutral or better. As in the cyclic environment, Dg remains stable for the Benign treatment, but drops slightly in the Harsh as
compared to the control, though this drop isn’t statistically significant
(Kruskal Wallis H(2) = 1.11, p = 0.57). Harsh Dp however, is significantly lower than seen in the cyclic environment treatment (Wilcoxon
Rank-Sum Test: Z = -6.19, p << 0.0001). This result shows that harsh
stochastic environments may not be as effective as cyclic environments
at increasing the probability that organisms will produce phenotypically
different, yet neutral offspring. . . . . . . . . . . . . . . . . . . . . . . .

41

Figure 2.15: A survey of the single-step mutational neighborhood in the
stochastic changing environment around organisms that performed the
fluctuating task. Again, in the static and harsh treatments, values are
comparable to the cyclic changing environment . However, in the benign treatment, the mean for the loss of the fluctuating task (EQU)
was slightly higher in the stochastic treatment (Mdn = 0.2) than the
cyclic (Mdn = 0.17), though the effect is barely statistically significant
(Wilcoxon Rank-Sum Test: Z = -2.4, p = 0.015). This result is consistent with stochastic environmental change being equivalently effective
at moving organisms to areas of the fitness landscape where they can
more easily switch task expression. . . . . . . . . . . . . . . . . . . . . .

42

Figure 2.16: A survey of the two-step mutational neighborhood in the stochastic changing environment of the organisms that lost EQU function in the
one-step survey. We found that the fraction of organisms regaining the
fluctuating task (EQU) from a single additional mutation in the harsh
treatment (Mdn = 0.013) were reduced compared to the cyclic harsh
treatment (Mdn = 0.01) (Wilcoxon Rank-Sum Test: Z = 12.75, p <<
0.0001) The opposite, however, was true of the Benign treatments. As
in Fig 2.15, we find that stochastic outperforms cyclic (Wilcoxon RankSum Test: Z = -18.43, p << 0.0001) This result confirms that the harsh
stochastic environment is probably less effective than the cyclic harsh at
promoting evolvability, but that the opposite may be true for a benign
environment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

xiv

Figure 2.17: Number of functional and vestigial sites by treatment in a
stochastic changing environment. The vestigial site counts for EQUonly performing organisms remain comparable to the cyclic environment
(Wilcoxon Rank-Sum Z = 0.46, 1.45, and -1.10, p = 0.6, 0.14, and 0.2).
The functional sites were also comparable, however, there was a slight,
but statistically significant decrease in the number of XOR & EQU
overlapping sites in the stochastic vs cyclic environments (Wilcoxon
Rank-Sum Test: Z = -3.05, p<0.01). . . . . . . . . . . . . . . . . . . . .

44

Figure 3.1: The HGT process. Organisms can execute instructions that trigger uptake from the environment. When uptake occurs, there is an
experimenter-defined chance that either it will yield a boost to speed of
execution or, alternatively, that the fragment will be integrated into the
genome. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

Figure 3.2: Number of HGT fragment uptakes in static and changing environments, without a grazing bonus, with a grazing bonus, and a no HGT
control, where the HGT-Uptake instruction is inert. HGT uptake increased in response to a changing environment, and also in response to
a grazing bonus. The grazing environment and a changing environment
combined resulted in an even larger increase of fragment uptakes than
either the changing environment, or the bonus alone (Wilcoxon Rank
Sum Test: Z = -4.93 and -7.47 respectively, p << 0.0001). . . . . . . . .

54

Figure 3.3: Origin and fitness effect distributions of HGT fragments, sampled midway through the experiment at 100,000 updates, and aggregated across all replicates. We applied each fragment in each cell’s
reservoir, one at a time, to the organism in the cell, then recorded the
fitness effect. The x-axis is the birth update of fragment’s original donor
organism. The y-axis is a fragment’s fitness effect. The color of each
point represents the number of fragments that originate in that birth
update a given fitness value. Hotter values indicate more fragments
from that time origin at that fitness effect. Most fragments with a positive fitness effect (the upper half of the figure) appear in bands that
correspond with the matching phase of an earlier cycle. . . . . . . . . .

55

xv

Figure 3.4: Mean and median fitness effects of fragments in reservoirs, with
95% confidence intervals. Fragments in reservoirs are replaced by fragments based on the origin of donor organism. For the On-Phase treatment, We only permitted fragments in reservoirs that originated in a
matching phase of the current cycle. For the Off-Phase treatment, we
only permitted fragments from non-matching phases. Plus two controls:
first, where no filtration takes place, and ”Both” where fragments are
injected from a mixed set of origins. The Off-Phase treatment had a
significantly lower fitness effect than either of the controls (Wilcoxon
Rank-Sum Test: Z = 143 and 31 respectively, p << 0.001), while the
On-Phase treatment had a significantly better fitness effect (Wilcoxon
Rank-Sum Test: Z = 105 and 3 respectively, p < 0.002). . . . . . . . . .

56

Figure 3.5: Fraction of all fragments that produced a beneficial phenotype
changes, with 95% confidence intervals. The ”On-Phase” treatment
had significantly more fragments that convey a beneficial phenotype
change than either of the controls (Wilcoxon Rank Sum Test: Z = -6.42
and -6.12 respectively, p << 0.001), while the ”Off-Phase” had significantly fewer (Wilcoxon Rank-Sum Test: Z = 7.11 and 7.35 respectively,
p << 0.001). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

Figure 3.6: Number of uptaken fragments in the filtered reservoir treatments.
The ”On-Phase” treatment has a significantly larger number of HGT
fragment uptakes, as compared to control, ”both”, and ”off-phase”
treatments (Wilcoxon Rank-Sum Test: Z = -3.9**, -3.2*, and -6.5**,
respectively, p < 0.002* and p << 0.001**) This shows that HGT is
significantly more beneficial when fragments match the current phase
of the cycle. Thus, this suggests that the primary benefit from HGT is
not mutational disruption, but the information that fragments convey
about the current environment. . . . . . . . . . . . . . . . . . . . . . . .

58

Figure 4.1: Executions of mutagenic instructions. In static environments, use
of all mutagenic instructions was strongly suppressed (Wilcoxon Rank
Sum Test: Z = -22.65, p<<0.001). In changing environment treatments, the HGT and HGT-Shuffled instructions were used at elevated
rates, compared to the other mutagenic instructions, including the Die
control (Wilcoxon Rank Sum Test: Z = 10.66, p<<0.001). The HGT
instruction (Mdn = 87389.71, CI 95% [82982.98, 96000.3]) is used more
than the HGT-Shuffle instruction (Mdn = 52220.3, CI 95% [45094.92,
57465.52]), which is used more than HGT-Random (Mdn = 25442.98,
CI 95% [22099.45, 30490.08]), indicating that the information content
of the mutation matters. . . . . . . . . . . . . . . . . . . . . . . . . . .

66

xvi

Figure 4.2: Mutagenic instruction use vs fitness effect of mutation. The
use of the mutagenic instruction correlates with the fitness effect of that
instruction (Spearman’s Rho: rs = 0.41, p << 0.001). Because mutagenic instructions are integrated into the genomes, those instructions
that produce a beneficial fitness effect are more likely to be selected for.

68

Figure 4.3: Fraction of beneficial phenotype-switching mutations vs mutagenic instruction use. We observe a strong correlation between the
fraction of mutations that produce beneficial phenotype switches, and
the use of the mutagenic instruction (Spearman’s Rho: rs = 0.59, p =
<< 0.001). This correlation is much stronger than the correlation between fitness effect and mutagenic instruction use. As such, this result
suggests that it is not only the absolute fitness effect that is selected
for, but the evolvability benefit. . . . . . . . . . . . . . . . . . . . . . .

69

Figure 5.1: Number of new expanded task set tasks discovered in postreward in the minimal environments. The left plot shows a timeseries of the number of non-ephemeral tasks discovered by populations
by each treatment. The right plot shows the number of tasks discovered
at the end of the experiments. While the individual values overlap their
neighbors, the top and bottom-most treatments (Benign and Harsh) are
significantly different from each other (Wilcoxon Rank Sum Test: Z =
2.75, p < 0.01). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

Figure 5.2: Number of new expanded task set tasks discovered post-reward
in rich environments. The left plot shows a time-series of the number of non-ephemeral tasks discovered by populations in each treatment.
The right plot shows the number of tasks discovered by the end of the
experiments. Overall, the number of expanded task set tasks discovered in the rich environments (Mdn = 24.0, CI 95% [23.0, 25.0]) is
significantly lower than those found in the minimal environments (Mdn
= 36.0, CI 95% [35.0, 36.0]) (Wilcoxon Rank Sum Test: Z = -16.15, p
<< 0.001). However, the same pattern holds, where the benign changing environment treatment discovers significantly more tasks than the
harsh changing environment (Wilcoxon Rank Sum Test: Z = 5.96, p
<< 0.001). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

xvii

Figure 5.3: Number of new expanded task set tasks discovered in minimal
environments, over the whole experiment. The left plot shows a
time-series of all new tasks discovered over the course of the entire run,
including non-rewarded expanded task set tasks. The right-hand
plot shows the final count at the end of the run. Before we introduce
rewards for performing expanded task set tasks, the harsh changing
environment discovers far more new tasks (Mdn = 28.0, CI 95% [27.0,
30.0]) than either of the other treatments (Mdn = 22.0, CI 95% [22.0,
23.0]) (Wilcoxon Rank Sum Test: Z = 8.61, p << 0.001). This occurs
despite no reward being given for performing the expanded task set
tasks in the first part of the experiment. . . . . . . . . . . . . . . . . . .

86

Figure 5.4: Number of new expanded task set tasks discovered in rich
environments, over the whole experiment. The left plot shows a
time-series of all new tasks discovered over the course of the entire run,
included non-rewarded expanded task set tasks. The right-hand plot
shows the final count of tasks discovered by the end of the run. Again,
both sets of changing environments (BenignCE and HarshCE) randomly
discover more expanded task set tasks than the control treatment
before rewards for those tasks are offered (Wilcoxon Rank Sum Test: Z
= -4.32 and -3.73 respectively, p < 0.001). This result suggests that the
alternation of the direction of selection drives populations to explore
new regions of the fitness landscape more effectively than directional
selection alone. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

Figure 5.5: Number of distinct tasks performed in minimal environments.
The left plot shows a time-series of the number of distinct tasks performed by the treatment populations over time. The right-had plot
shows the number of tasks performed at the end of the experiments.
The harsh changing environment treatment performs substantially and
significantly fewer tasks than any of the benign or control treatments
(Wilcoxon Rank Sum Test: Z = -11.22 and -11.15 respectively, p <<
0.001). The benign treatments perform best, but the differences are not
statistically significant from the control (Kruskal Wallis: H(2) = 2.76,
p = 0.25). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

xviii

Figure 5.6: Number of distinct tasks performed in rich environments. The
left plot shows a time-series of the number of distinct tasks performed
by the treatment populations over time. The right-had plot shows the
number of tasks performed at the end of the experiments. Similar to the
minimal environment, the harsh changing environment treatment performs substantially and significantly fewer tasks than any of the benign
or control treatments (Wilcoxon Rank Sum Test: Z = -4.32 and -3.73
respectively, p << 0.001). Similarly to task discovery, the rich environment performs fewer tasks overall (Mdn = 11.0, CI 95% [10.0, 12.0]),
compared to the minimal environment(Mdn = 17.0, CI 95% [17.0, 18.0])
(Wilcoxon Rank Sum Test: Z = -9.25, p << 0.001). Interestingly, the
Harsh Quiescent treatment performs the most tasks, though this effect is only slightly significantly different from the benign treatments
(Wilcoxon Rank Sum Test: Control Z = 4.33, HarshCE Z = -9.3, p <
0.001; BenignCE Z = 2.25, Benign Quiesce Z = 1.96, p < 0.05). . . . .

89

Figure 6.1: Task discovery, with and without HGT grazing bonus. Populations evolving with a grazing bonus had a strong negative correlation
between task discovery and HGT use (Spearman’s Rho: rs = -0.71, p
<< 0.001). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

Figure A.1: Survey of task execution for a series of cycle-lengths. The top plots
count the number of executions of the EQU instruction in the control
treatment. Each organism only receives a bonus for executing EQU once.
The seed population performed EQU, and it is never lost. The middle
and lower plots show EQU execution in benign and harsh changing environments, respectively. Each line describes a different cycle-length
treatment. The longer cycle lengths correspond with longer times to
lose and regain EQU. Only treatments with cycles longer than 1000
updates achieve fixation, at a maximum value of 3600 EQU executions. .

98

Figure A.2: Survey of task time to EQU fixation for harsh changing environments for a series of cycle-lengths. Only those treatments where
EQU fixation occurs (cycle lengths greater than 1000 updates), were
surveyed. The longer the cycle time, the longer it takes for fixation to
occur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

Figure B.1: Survey of HGT use for a series of recombination probabilities in a
static environment. The left-hand figure shows a time-series of fragment
uptakes, with and without bonus values. The right-hand plot shows the
final uptake counts at the end of the runs. Those values at a recombination probability of less than 0.1 are not meaningfully depressed as
compared to the bonus values. Values greater than 0.1 showed more
suppression, and ultimately reached mutational melt-downs with few
surviving populations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
xix

Figure B.2: Survey of HGT use for a series of bonus values in a static environment. The left plot shows a time-series of HGT fragment uptakes,
while the right-hand plot shows final uptake values at the end of the experimental runs. With recombination probability at 0.1, bonus values
of zero depress HGT use. A bonus of 0.1 increases uptake dramatically,
indicating a very high use. Bonuses at 0.5 and greater show diminishing
returns in increasing HGT use. . . . . . . . . . . . . . . . . . . . . . . . 101
Figure B.3: Survey of HGT use, across a series of comparable bonus values
in a static environment, with a recombination probability of 0.1. This
figure shows a sweep of bonus values, demonstrating a largely linear progression of increasing HGT use as bonus values increase, thus balancing
negative effects caused by recombination in a static environment. . . . . 102
Figure C.1: Die instruction executions across a series of artificial bottlenecks.
We observe that the Die instruction is elevated in a harsh changing
environment as compared to a static environment. We apply a pair of
bottlenecking procedures. In the ”Serial Transfer” treatments, we kill
the population, but select increasingly fewer organisms to seed from.
As the number of seed organisms become fewer, the expression of the
Die instruction increases. This is consistent with founder effects being
likely the cause of increasing expression of strongly deleterious traits in
harsh changing environments. . . . . . . . . . . . . . . . . . . . . . . . . 104

xx

KEY TO ABBREVIATIONS

CE

Changing Environment

CVA

Additive Genetic Coefficient of Genetic Variation

Dg

Genomic Diffusion Rate

Dp

Phenotypic Diffusion Rate

KW

Kruskal Wallis

h2

Narrow-sense Heritability

H2

Broad-sense Heritability

HGT

Horizontal Gene Transfer

mS

Spatial Modularity

ME

Mutational Event

MRI

Mutation Rate Increase

rP

Phenotypic Robustness

rG

Genotypic Robustness

MWW

Mann Whitney Wilcoxon

xxi

CHAPTER 1
INTRODUCTION - CHANGE, ADAPTATION AND THE EVOLUTION OF
EVOLVABILITY

1.1

Evolvability and Evolutionary Potential - Why Study It

The evolutionary potential of a genome is a controversial and nuanced topic, ultimately
measurable only in retrospect once the evolutionary success of its descendants is known.
Questions relating to evolutionary potential, however, are some of the biggest in Evolutionary Biology: What selective pressures drive organisms to become more evolvable? What
aspects of genetic architecture influence evolutionary potential? How do we go about predicting longer-term evolutionary success? And how do features of the environment, such as
complexity, change, and periodicity drive and constrain movement across mutational landscapes?
The evolution of sex, multi-cellularity, and other major transitions are characterized by
significant changes in genetic architecture that coincide with the transitions [1]. The adaptive radiations that accompanied Metazoan evolution were also accompanied by changes in
genetic architecture that were carried along as species diversified and colonized new ecological niches [2]. The vast diversity of species and their complex ecological interplay depends
fundamentally on the ability of populations to not only adapt to their environment, but also
create new niches and rapidly explore and exploit their environment as it changes around
them. Evolvability has many subtle forms that are produced in different types of changing
environment.
Within evolutionary computation, evolvability is also fundamental. The “representation
problem”, which influences every aspect of evolutionary search, can be characterized as a
problem of how to design the underlying genetic encoding such that genomes can not only
express complex solutions, but can also be mutated in meaningful ways [3]. In particular,

1

good designs for genetic representations often involve increasing the probability that a recombination between potential solutions can produce a result that is not only viable, but
more fit than either parent. The entire goal of the representation problem is to improve
evolvability so that better solutions can be found. By definition, systems that exhibit good
characteristics in evolvability produce good solutions more quickly, while avoiding premature
convergence [4] so adaptive evolution continues to as high a level as possible. Beyond the
representation problem, many of the barriers to complexity are actually barriers to evolvability.

1.2

What is Evolvability (and why is it so hard to pin down)

In its most abstract sense, evolvability appears to be a simple concept: the ability of
genetic systems to produce adaptive variation. However, the devil is in the details. How,
exactly do genetic systems generate adaptive variation? How do we measure this potential?
Should all forms of variation count as evolvability? At what time-scales does evolvability
act? And finally, how did it evolve in the first place? That is, are evolvable features under
some form of direct selection, or are they by-products of other processes?
Evolvability, in its details, must mean different things at different evolutionary scopes
and time-scales. Depending on your perspective, evolvability can describe the response
to selection at the population level [5, 6], the ability of populations to adapt to changing
conditions [7], larger phenomena such as variability generation [8], exploration of neutral
spaces and robustness [9, 10], generation of novel features [11, 12], or even the potential to
generate the larger clade-level innovations [2] and major transitions [1]. Beyond that, there
is a lot of confusion and controversy about the definitions and components of evolvability
even within any one of these scopes [13].
Finally, it is unclear whether evolvability is acted upon by direct selection, or whether it
is a byproduct of other traits that are selected upon, or some combination of the two. At the
individual level, its possible that some traits that support evolvability, such as robustness of

2

developmental or cell processes [2] could have been selected for directly in response to adverse
environmental conditions. However, at the population level, traits like neutral variation
generation are more likely to have hitchhiked on the genomes of the adaptive variants that
they produced. Finally, at the clade level, genetic structures that produced populations
of adaptive variants with robust and flexible genetic architectures would have been more
successful at adaptive radiations [3], and thus go on to found whole branches of life with
those traits [2].
Of course, we must be careful when invoking selection at higher levels than the individual.
While there is some evidence to support clade-level selection in the evolution of evolvability [14], caution should be applied when attributing evolutionary outcomes to higher levels of
selection when random chance or lower levels of selection are adequately explanatory. Specifically, we need to be careful to avoid falling into the trap of adaptationism [15] by assuming
that evolvability is an end in itself. Selection can only act on organisms and populations
as they exist, against the current environment, and it is an error to assume that patterns
identified in hind-sight are predictive of future evolution.

1.3

Changing Environments and Evolvability

Sustained directional selection adjusts the composition of phenotypes and genotypes in
a population [16], typically moving that population across the mutational landscape to local
regions of higher fitness. When populations find a fitness peak, they tend to cluster there,
and exploration of regions further away slows dramatically.
In changing environments, however, the direction of selection is not fixed and peaks are
not stable. Instead, as the environment changes, populations are driven to explore new
regions of the mutational landscape [17, 18]. As they proceed, populations accumulate and
carry with them the genetic material acquired in prior explorations and adaptations, and
use this history as raw material for new adaptation [19]. Indeed, earlier work has shown
that changing environments promote evolvability in many contexts, without compromising

3

robustness [20, 21]. Strength of selection is also an important component of this exploration,
since the harshness of the environment drives the speed with which organisms adapt to new
conditions [22].
Evolution has many subtle forms that are produced due to evolution in different types
of changing environments. In this dissertation, we show how changing environments not
only drive exploration of the mutational landscape, but also select for populations whose
genetic architectures are qualitatively different than those from populations evolved in static
environmental conditions under purely directional selection. We argue that alternating the
direction of selection acts as an engine for evolvability, promoting the acquisition of new
traits, increasing the rate of exploration of the mutational landscape, and promotes the use
and maintenance of certain kinds of evolvability-promoting mutations.

1.4

Historical Conceptions of Evolvability

Evolvability is described at many different scopes and levels in the literature, each with
varying amounts of detail and predictive power. As such, it may be best to avoid attempting
to unify the concept, and rather acknowledge that evolvability is not a singular idea, but
rather an overlapping and interrelated set of concepts relating to adaptation and evolutionary
potential. In order to synthesize the large field of evolvability and understand how the
distinct scopes and ideas connect together, a historical narrative is clearly useful.

1.4.1

Modern Synthesis

The evolution of evolvability as a formalized theory originated with Dawkins [3] and
Alberch [11], though the underlying concept (as the response to selection, measured by heritability) existed much earlier, in the work of Fisher [5] and Wright [16]. Fishers fundamental
theorem of the response of a population to selection identified narrow-sense heritability (h2 )
as a measure for how evolvable populations were. Evolvability as heritability (h2 ) is a measure of the portion of the phenotypic variation in a population that can be accounted for by

4

additive genetic effects. h2 therefore is the component that directly relates to a populations
response to selection [6].

h2 =

V arA
V arP

(1.1)

In contrast to narrow-sense heritability (h2 ), broad-sense heritability (H 2 ) refers to the
entire genetic contribution to a populations variance, including dominance and epistasis.
Because of these other contributors, it is unsuitable for isolating the response to selection.
As a measure of evolvability, narrow-sense heritability (h2 ) was also used as a term in the
breeders equation, in order to estimate the response of a population to artificial selection.

R = h2 S

(1.2)

Heritability, however, is not an ideal predictor for the response to selection because it
fails to integrate factors such as the population distribution of variability in a trait [6].
Heritability, being scaled by total population variation in a trait, would predict the same
response to selection regardless of whether the standard deviation of variance of that trait
was large or small, or where the mean of that trait lay.
Houle advocated for an alternative genetic variability measure that suffered from fewer
of these problems: the Additive Genetic Coefficient of Genetic Variation (CVA ).
s

CVA = 100

VA
X̄

(1.3)

Using CVA as the measure of genetic variability is superior to narrow-sense heritability
because it scales additive genetic variance by the trait mean, rather than by total population
variation. Thus, the additive variation component isnt overwhelmed by large population
trait variance [23]. Since life-history (fitness-related) traits tend to have large population
variances, h2 predicts that life-history traits have low heritability and thus low response to
selection [24]. CVA , however, being scaled by trait mean, predicts much higher response to
selection for life-history traits [25, 6].
5

CVA still suffers from significant drawbacks as predictors for adaptation and evolvability
in a larger sense [25]. Both h2 and CVA measures predict the response to selection based on
the expressed trait variation in a population, under the current environmental conditions.
They say nothing of the potential for cryptic variation that may be revealed in different
genetic background, nor do they address differences in genetic architecture that may promote
faster adaptation. Ultimately, CVA is best when examining the short-term response to
selection in artificially-selected populations, in static environments, with low mutational
load [6].
Clearly, such short-term, population-based measures are unsuitable for measuring larger
patterns of the evolution of evolvability, especially over the long term.

1.4.2

Evolvability as a Distinct Concept

Dawkins, in his foundational paper on evolvability and evolutionary constraint [3], re-framed
the problem of evolvability in the context of computational evolution and development.
Dawkins described a generative genetic system based on a few alleles, and rules that governed development based on the traits encoded in the alleles. Each allele would govern the
execution of a generative rule, and the rules would interact with each other as they produced
the phenotype. As he added new kinds of rules (constraints) into the generative process, he
showed that the system produced more and more complexity.
Dawkins used this example to draw parallels to biological generative developmental systems and how evolutionary constraints in development allow for more complex and robust
phenotypes. Dawkins identified a few key themes that underlay the more powerful features
of developmental systems. These systems would be organized in such a way as to facilitate
cumulative effects. That is, innovations in constraints can build upon each other and are
cumulative in evolutionarily interesting ways[3].
Dawkins hypothesized that these kinds of generative developmental systems, or embryologies were the basis for evolvability, and that they must have evolved as a result of their

6

intrinsic power to produce adaptive variation. Dawkins further suggested that the genetic
systems that persisted were those that facilitated adaptive radiations into new or otherwise
empty ecological niches.
Alberch followed up Dawkins ideas with a more thorough accounting of how, exactly,
these kinds of evolvable traits translate into an analyzable phenotype space [11]. Alberch
dismantled the concept of a simplistic, hierarchical genotype-to-phenotype mapping function
and emphasized that developmental and cell metabolic systems are strongly dynamical,
nonlinear systems, for which genes are just one part of the regulatory cycle. Because of the
dynamic nature of cell processes, it was clear that the gene-centric, population genetics view
was inadequate to fully describe the complexity of the processes involved, and how they
translated complex parameters into phenotypes. To that end, a new framework for analysis
was required.
Alberch introduced the concept of “parameter spaces” to describe the variation in genotypic parameters that results in distinct phenotypes, while addressing the lack of one-to-one
correlation between alleles (parameters) and phenotype. Parameter spaces are multidimensional spaces, divided by parameter thresholds (bifurcation boundaries) that form borders
between phenotypes. The domains bounded by these thresholds include all of the parameter
combinations that produce a given phenotype. Larger domains can be described as more
stable than smaller domains, because there are larger ranges of neutral variation available
before organisms tip into a different phenotype. Populations with distinct phenotypes and
varying parameters can thus be visualized as blobs occupying areas in parameter space.
Alberch contended that the “evolvability potential” of a dynamical system is encapsulated by the properties of the parameter space. Specifically, the topology of the bifurcation
boundaries govern the ease with which the systems can produce both neutral and adaptive
variation. Alberch asserted that the generative systems must have undergone selection that
favors those systems that provide a good balance between exploration and stability, but
provided no mechanism for that selection.

7

Dawkins and Alberch laid out a compelling case for the role generative developmental
systems in facilitating evolvability, but their theoretical frameworks were far from complete.

1.4.3

Theoretical Frameworks for the Evolution of Evolvability

The Wagner and Altenberg paper on the evolution of evolvability significantly expanded the
theoretical framework behind the evolution of the genotype-phenotype map [8]. The authors
draw on knowledge from computational evolution to inform their perspective on evolvability,
since the problem of evolvability is central to the representation problem in evolutionary
computer science.
Initially, Wagner and Altenberg emphasized a distinction between variation and variability. Variation is the realized diversity in a population, which is a concept that lies firmly
within population genetics and the gene-centric modern synthesis. Variability, on the other
hand, is a concept that they introduced to describe the ability to generate new phenotypes
in response to mutation or environmental change. Variability is a metric associated with a
local neighborhood in a genotype to phenotype map, and depends on features of that map,
including pleiotropy and modularity, and robustness and flexibility of biological processes.
Wagner and Altenberg’s paper led to a vast proliferation of new work exploring the evolution of evolvability. Of particular note is the Kirschner and Gerhart 1998 paper [2], which
explored metazoan evolution for examples of traits that, in combination, acted to increase
evolvability. The authors found numerous examples of new, evolvable features coinciding
with adaptive radiations. The authors also develop a case for a combination of direct selection upon the individual for evolvability-enhancing features, and those traits persisting as
by-products as a result of adaptive radiations, setting the stage for the evolution of more
and more complex evolvable features.

8

1.5

So, what do I mean by Evolvability?

As I described above, evolvability is a series of distinct, but overlapping concepts that are
generally concerned with adaptation, variation, and/or novelty generation. For the purposes
of this dissertation, I am using the Wagner/Altenberg conception of evolvability, which
focuses on variability (i.e., the generation of adaptive variation in response to mutation).
Variability depends primarily on the organization and interrelation of the components of the
genome; that is, the genetic architecture, and the resulting genotype-to-phenotype map.
The major features that influence this metric for evolvability appear to be modularity
of functional components and phenotypic robustness to mutation and environmental perturbation. While there are other architectural features that are also likely to contribute to
evolvability, they will not be the focus of this dissertation.

1.5.1

What is Modularity?

Modularity is the degree to which traits are both self-contained and decoupled from each
other. Modular organization can appear at different scales, from the reduction of overlap
between unrelated gene regions (spatial modularity [26]), to the decoupling the mutational
effects on distinct traits (functional modularity [8]), to the composition of groups of related
trait complexes (variational modularity [27, 28]).
Features such as evolvability and robustness are thought to rely heavily on modularity [8]. For example, traits with high functional modularity will have low pleiotropy and
therefore should be able to evolve independently—a critical feature if individual traits need
to quickly respond to changes in selection. Additionally, modular traits may be more easily
re-purposed or co-opted by other traits to add new function [28]. Conversely, spatially modular genomic regions, because they are more self-contained, tend to better resist disruption
from recombination, thus increasing robustness [26].
The relationship between modularity and pleiotropy is complex. At small scales, spatial

9

modularity acts to directly reduce pleiotropy by reducing the number of traits affected by
a single locus [26]. However, at higher scales, modularity may rely on pleiotropic links
within groups of related trait complexes to enable those groups to evolve and optimize in
concert [27].
Despite the benefits described above, modularity, like many other variational trait complexes, may not be an unmitigated boon for evolvability. High levels of functional modularity
may reduce the overall evolvability of a genotype by reducing the incidence of mutations of
large effect and reducing the size of mutational targets [29]. Reducing the incidence of large
changes reduces the likelihood of the development of entirely new traits as a result of relatively few mutations. Thus, the evolvability benefit of modularity may be mediated by the
scale and degree to which it occurs.

1.5.1.1

Measuring Modularity

At the phenotypic level, modularity is assessed based on the functional independence of
traits and trait complexes. Spatial modularity is correlated with functional modularity,
though it is possible to have spatially modular genomes that are not functionally modular
and vice-versa [30, 31].
For the purposes of this research, I will focus on spatial modularity. Spatial modularity
may be measured by calculating the proportion of traits that are affected by a given site in
the genome, normalized by the number of sites that code for a trait [26]. Trivially, this can
be measured by performing knock-out experiments to identify the sites that contribute to
particular function.
To measure Spatial Modularity, mS :
1. count the total number of traits expressed in a genome: T
2. identify the number of sites that code for any trait: set K
3. count the number of items in set K: k
10

4. count the number of traits coded for by each site within set K: tk ;
5. calculate the inverse of the average number of traits coded for per site to
reflect the level of spatial modularity (mS ) of coding regions of a genome
mS =

1.5.2

1
1 Pk tk
k i=1 T

(1.4)

What is Robustness?

Much like evolvability, robustness is a set of overlapping concepts concerned with the ability
of a genotype to maintain a given phenotype despite an unexpected disruption [10, 32].
Most commonly, robustness is studied in regard to either perturbations in the environment
or else mutational disruptions. In the first case, the evolution of robustness to environmental
disturbances depends heavily on the flexibility and decoupling of gene regulatory or signaling
pathways [2]. For example, a gene-regulatory or signaling pathway that is loosely coupled
may make use of signaling from multiple incoming paths, rather than depending on a single,
rigid precursor. This type of arrangement is more likely to continue to function even if some
part of the signaling path is disrupted. An example of this kind of robust arrangement is
nerve conduction in vertebrates where axons connect several cells, thus routing signals in
parallel, and avoiding single points of failure [2].
For the purposes of my research, I will focus on the second case: mutational robustness.
Distinct from robustness to environmental perturbation, robustness against mutation depends largely on degeneracy, redundancy, and regulatory decoupling [10]. Degeneracy refers
to a many-to-one relationship between an encoding and a product, such that several codes
can produce a single output. Thus, there is a chance that mutations in the code will not
alter the product. One example of this feature is codon degeneracy in biological organisms,
where, depending on the hydropathy of the amino-acid, single, or even double mutations in
some positions of the encoding do not affect the binding of the encoded amino-acid [33].

11

Similarly, redundancy refers to the duplication of function in multiple places in the
genome, such that mutations altering function in one copy of a gene do not alter function in the other copy. Redundancy may also refer to redundancy of function within genes,
such that if a mutation occurs in one portion of a gene, other neighboring portions of the
protein will compensate, and the protein will retain its structure and function.[34]
Finally, regulatory decoupling allows for more than one kind regulatory precursor to
provide inputs for a process [34]. Thus, if mutation were to damage one set of precursors,
others can take their place and preserve function. An example of this kind of architecture is in
the production of the acetate precursor for the Krebs cycle, which produces ATP in all aerobic
organisms [35]. Acetate can be derived from either carbohydrates, lipids, or proteins, thus if
any of those pathways are damaged by mutation, or limited by environmental perturbation,
acetate can still be produced from other sources, and ATP production can continue.
It is worth noting that many of the architectural features that confer robustness to
processes and genomes are based on arrangements of modular structures [36, 37]. In this
way, much of robustness is facilitated by the evolution of modularity.

1.5.2.1

Measuring Robustness to Mutation

Robustness to mutation can be assessed in multiple ways, either from the perspective of a
specific phenotype, a specific genotype, or combinations of the two. From the perspective
of an individual genotype, you can assess its robustness by calculating the proportion of
mutations that produce a phenotype that is different from the one expressed by the target
genotype [38]. In most cases it is easiest to focus on single-step mutations (to cover the 1neighborhood in the fitness landscape), but sampling from the full distribution of mutation
combinations that occur naturally will produce a more exact results.
To measure Genotypic Robustness, rG , of a genotype G:
1. count the number of loci in the genome: n

12

2. count the number of possible alleles at a given site: D
3. enumerate all possible single-step mutants that may arise from the given
genotype (or sample from a more realistic distribution): n(D − 1);
4. count those mutants that prove to be neutral phenotypic variants: RG ;
5. calculate the proportion of neutral phenotypic variants to reflect the probability of a neutral variant being produced by this genotype in response to
mutation.
rG =

RG
n(D − 1)

(1.5)

Genotypic robustness is trivially negatively correlated with genotypic evolvability, because each neutral variant in the 1-neighborhood of a genotype is, by definition, not of a
different phenotype. However, the inverse is not necessarily the case, because each nonneutral neighbor phenotype may not be unique. Therefore, a non-robust genotype may not
necessarily have high evolvability if its neighborhood is dominated by a single or few distinct
phenotypes [38].
From the perspective of the phenotype, robustness may be assessed by to taking the
average genotypic robustness across the phenotype.
To measure Phenotypic robustness, rP :
1. count the number of distinct neutral genetic variants that produce a given
phenotypic trait in a population, (SetK : k);
2. calculate the proportion of neutral variants produced by single-step mutations rG , averaged over all of the neutral genetic variants to reflect the
probability of a neutral genotype currently in the population producing another neutral genotype in response to mutation.
rP =

k
1X
r
k i=1 G

13

(1.6)

Unlike genotypic robustness, higher phenotypic robustness has been shown to correlate
with phenotypic evolvability in cases where the possible number of neutral variants in a
phenotype (the frequency of the phenotype) is high [38]. With increasing numbers of neutral
variants, the number of potential unique phenotypes in the 1-neighborhood of the phenotype
increases.
These measures of robustness are each limited in that they do not address realized population composition, the shape of the mutational landscape, nor the expected frequency of
the target phenotype. In particular, the correlation of phenotypic robustness with evolvability depends on the expected phenotypic frequency [38]. Thus, if the frequency is unknown,
phenotypic robustness may not predict evolvability.
Further, different populations may have vastly different numbers of realized neutral variants for a given phenotype. Factors such as gene-flow, bottle-necking, linkage dis-equilibrium,
founder effects, and sexual selection may strongly affect overall diversity in populations, including the neutral diversity for a particular phenotypic trait that we are concerned with [11].
For this reason, while population level metrics may cause a phenotype to appear to be
non-robust, this apparent value may be the result of the amount and type of realized diversity
present in a given population, rather than the robustness of that phenotype as predicted by
its potential neutral network [11].

1.5.3

Predicting Short-Term Evolvability with Landscape Metrics

As indicated above, the features that confer robustness may also promote evolvability by
allowing for greater neutral genetic diversity within a given phenotype. The larger the
number of distinct genotypes with the same phenotype in a connected region of the fitness
landscape, the more exploration of the genotype space that can be done without decreasing
organismal fitness. As a population diffuses through such a neutral region, more potential
phenotypes become available in few mutational steps [9].
Historically, predicting this robust-yet-evolvable quality has been challenging. Previously-

14

used measures for robustness that focus on counting the proportion of unique genotypes that
compose a phenotype (Phenotypic Robustness [38]) are limited in their ability to predict the
evolvability of a population, especially where phenotypic frequency is unknown.
In contrast, we will use Genomic Diffusion Rate, which is the probability that an offspring
will be different from its parent, while expressing a neutral or positive fitness effect. This
metric may be used to characterize overall population evolvability as it approximates the
overall rate in which entirely new genotypes are encountered [39].
To calculate the Genomic Diffusion Rate (Dg ) in the local neighborhood of a genotype,
first calculate its Fidelity (F ), or the probability of an offspring sharing this genotype with
its parent. Given a uniform mutation rate, Fidelity can be calculated by measuring the
probability that a single locus is not mutated (1 − µ) and raising it to the power of the
genome length (l). Next, measure the proportion of one-step mutants that are neutral or
beneficial when compared to the parent (pν ) as well as those that are detrimental or lethal
(pd ), which must sum to one (pν + pd = 1). The Neutral Fidelity (Fν ) of a genotype is thus
the probability that no harmful mutations occur, assuming no epistasis. Finally, subtracting
Fidelity from Neutral Fidelity will yield the overall probability of producing an offspring
with a different genotype, yet neutral or better fitness (Dg ).

F = (1 − µ)l

(1.7)

Fν = (1 − µpd )l

(1.8)

Dg = Fν − F

(1.9)

Measures of neutral exploration, however, only show part of the picture. While some
form of neutrality is necessary for exploring a fitness landscape, new phenotypes must be
discovered to achieve higher local evolvability. In order to assess evolvability more specifically,
we introduce a related measure, the Phenotypic Diffusion Rate (Dp ), which represents the
15

probability that an offspring will be fitness-neutral (or better), but also express a different
phenotype than its parent. To do so, we must first measure the proportion of one-step
mutants that are phenotypically neutral as compared to their parent (ppν ) and follow a similar
procedure as above, first calculating the probability that a phenotype-changing mutation will
occur (µpheno ), then the phenotypic-level Fidelity (Fpν ).

µpheno = µ(1 − ppν )

(1.10)

Fpν = (1 − µpheno )l

(1.11)

Dp = Fν − Fpν

(1.12)

The difference between the overall neutral fidelity and the phenotype-preserving neutral
fidelity (Fν − Fpν ) yields the phenotypic diffusion rate.

1.5.4

Expected Value of Fitness Landscapes

In the context of changing environments, the expected fitness value (E(w)), and thus the
neutrality, of a mutant in the mutational landscape will vary depending on the environmental
context. So, in one environment, a mutant may be highly fit, but the same allele may
be highly deleterious in a different environment. In order to address this variation, all
metrics must be normalized by the probability that a particular environment will occur (Pi ).
That is, the nearby mutational landscape must be evaluated in each possible environment,
yielding a traditional fitness landscape. Then, the set of fitnesses of each mutant (wi ) in each
environment must be aggregated according to the probability of that environment occurring.

E(w) =

e
X
i=1

16

wi P i

(1.13)

1.6

Digital Evolution

Digital Evolution uses self-replicating computer programs as model organisms to study
evolutionary dynamics [40]. Unlike theoretical simulations, digital organisms have a fully
functional genome that direct them to self-replicate, mutate, and compete with their peers
for resources and space in which to reproduce. Because digital organisms undergo genetic
mutations (i.e., variation) that are passed on to their offspring (inheritance), and their survival is based on the actions they take (differential selection), they undergo evolution by
natural selection [41].
Digital organisms do not suffer from many of the drawbacks of experimentation on natural
organisms. Three of the advantages of digital organisms are particularly relevant for our
studies. First, the rates of reproduction in digital systems are much faster than in even the
most rapidly-reproducing physical organisms; we can process generations of organisms in
seconds, rather than the hours required for the fastest biological organisms under sustained
conditions [42, 43], or the weeks to years needed for more complex multicellular organisms [44,
45].
Second, using digital organisms allows us to tightly control and verify experimental conditions. For example, in physical organisms, factors such as mutation rate can generally be
measured only after the fact, or coarsely altered through mutagens. In digital organisms,
however, we can not only control mutation rates with fine-grained precision, but also types
and probabilities of different types mutations (e.g., substitutions vs. insertions vs. deletions). Furthermore, we are also able to track and replay the evolutionary history of every
organism at any point in time to verify that unusual or unexpected results do not represent
measurement error. This ability to exactly replicate evolutionary results at an individual
organism level is firmly out of reach for experiments with physical organisms.
Finally, we can precisely and perfectly map the mutational landscape around the genome
of a digital organism, and identify the role of every site in its genome [39]; such exhaustive
techniques are not feasible in even the simplest physical organisms. All of these factors make
17

digital organisms ideal for studying the effects of changing environments on the mutational
landscape.
It is also worth noting that certain kinds of experimental evolution experiments are simply
intractable in biological systems. For example, experiments comparing the fitness effects and
outcomes of different kinds of mutations would be extremely difficult, time-consuming, and
data-poor at a population-level scale. In contrast, these kinds of experiments can be easily
performed using digital evolution models.

1.6.1

Avida

Throughout the rest of this dissertation, I use the Avida digital evolution platform to explore
the effects of changing environments on the evolvability of populations of digital organisms,
both in the short and long-term. Avida is a software platform for performing evolution
experiments with digital organisms in a virtual world.

Figure 1.1: An example virtual CPU from Avida, with a circular genome (blue),
three registers (purple), input and output handlers (tan), and an instruction pointer
(yellow) indicating the next instruction to be executed.

18

An Avida organism is composed of a circular genome of assembly-like computer instructions that are executed in a virtual CPU (Fig 1.1). Populations of these organisms are placed
in a toroidal world in individual cells where they are allowed to execute, reproduce, compete
for space, mutate, and evolve.
Organisms in Avida are self-replicating, and experience mutation. The genomes of the
initial default organisms contain all of the instructions necessary for reproduction. However, the instructions are not copied into an offspring with perfect fidelity. By default, the
reproductive copy instruction is faulty, meaning that it will probabilistically introduce errors (mutations) into the offspring genomes. These offspring organisms execute their own
genomes even when different from their parent, and in turn pass on their inherited mutations,
along with new mutations, to their own offspring (i.e., variation in the systems is heritable).
Avida worlds can be space- or resource-constrained. Avida allows the experimenter to
configure many aspects of the environment, thus subjecting the organisms to various kinds
of selective pressures. In many cases, these environments will include resources that can be
metabolized by performing specific functions or activities, resulting in a boost to execution
speed that gives the organisms a competitive advantage. However, even without explicit
external pressures, organisms still experience an implicit pressure to execute more quickly
and efficiently. The organisms that run fastest are typically able to also reproduce fastest,
and thus out-compete their peers for space.
Avida is available for download without cost from http://avida.devosoft.org/,
and specific versions along with data-files to reproduce the experiments described in this dissertation may be found at https://github.com/voidptr/avida, https://github.
com/voidptr/dissertation, and https://github.com/voidptr/dissertation_
data.

19

1.7

Statistical Methods

Most of the statistical techniques used in this dissertation are non-parametric, and focused
on differentiating between sample distributions. In general, we applied Wilcoxon Rank-Sum
tests [46] to distinguish between pairs of distributions, as well as Kruskal-Wallis [47] for
identifying whether we could reject the null hypothesis of sameness between several different
distributions. We assume all distributions are independent, and that compared distributions
have similar shapes. In all situations where there were multiple comparisons of a given
distributions, we applied Bonferonni corrections [48] before assessing statistical significance.
In certain cases, we report mean and median values of distributions. In these cases, we
also report the standard deviation or 95% confidence intervals.
In specific cases, we also apply Spearman’s rank-order correlation coefficient ρ (or rs ) [49]
to measure correlations between data sets. In all cases, data points are matched from within
a replicate.

20

CHAPTER 2
CHANGING ENVIRONMENTS PROMOTE RAPID ADAPTATION IN
DIGITAL ORGANISMS

2.1

Background

The interaction between an environment and possible genomes can be mathematically
expressed by a fitness landscape. Fitness landscapes are a mathematical tool to map genetic
sequences to reproductive fitness. Many studies have examined the important role that
different types of fitness landscapes play on evolutionary dynamics and outcomes, both in
biological populations [50, 51, 52, 53] and in evolutionary computation settings [54, 55, 56].
However, real-world fitness landscapes are far more complex and varied than the limited
or idealized models that are used in most of these studies. Neighboring regions of real
landscapes can have starkly different properties from each other based on the effects of
and interactions among mutations; as such, a local region of a fitness landscape around a
genotype is commonly referred to as its mutational landscape.
Examples of the type of properties that we are interested in include robustness, epistasis,
and modularity, all of which are measurements of how information is organized inside of a
genome and commonly categorized as components of an organism’s “genetic architecture”.
Isolated pockets in a landscape can often be characteristically different from the landscape as
a whole due to the amount and organization of genetic information. In fact, in most natural
fitness landscapes, the vast majority of neighborhoods consist entirely of non-replicating
genomes with zero fitness (and thus no genetic information), making life itself appear to be
a rare exception [57].
Evolution on these convoluted landscapes is clearly limited to those regions that have
non-zero fitness, with a selective pressure for fitness to increase. Beyond that, however,
populations can evolve toward neighborhoods with specific local properties based on the

21

evolutionary forces acting upon the populations. For example, high mutation rates drive
populations toward neighborhoods with a higher fraction of neutral mutations in an effect
dubbed survival of the flattest [21]. Similarly, sexual populations tend toward regions of the
fitness landscape with more modularity [26] and more negative epistasis [58] than otherwise
equivalent asexual populations.
Understanding these dynamics is of broad interest. It is important to evolutionary computation, given the strong influence of local landscape properties on the quality of the final
solutions that an evolving population is able to obtain. Its relevance to evolutionary biology
is equally obvious – the local landscape that a population occupies will influence the selective
forces at play in the population, creating a feedback cycle between these two important evolutionary factors [59, 60, 61, 62]. Disentangling such interactions is likely to provide further
insights into fundamental evolutionary dynamics. Computational artificial life systems have
the advantage of being able to bridge these two realms: they have unconstrained evolutionary dynamics similar to natural systems, while maintaining the ability to rapidly perform
experiments and collect any data we need about populations or their local landscapes.

2.1.1

Evolvability and Genetic Architecture

As described in Chapter 1, evolvability refers to a series of distinct but overlapping concepts
that are generally concerned with adaptation, variation, and/or novelty generation [13]. Depending on your perspective, evolvability can describe the response to selection at the population level [5, 6], the ability of populations to adapt to changing conditions [7], larger
phenomena such as variability generation [8], exploration of neutral spaces and robustness [9, 10], generation of novel features [11, 12], or even the potential to generate clade-level
innovations [2] and major transitions [1]. For the purposes this chapter, we will focus on
evolvability as the capacity for mutations to generate adaptive variation in a genome.
In the short-term, this kind of evolvability determines a population’s response to selection, and depends primarily on the organization and interrelation of information in the

22

genome; that is, the genetic architecture, and the resulting genotype-to-phenotype map [8].
An example of evolvable architecture can be found in some bacterial genomes that contain
highly mutable genome regions, called contingency loci. Small sets of insertions or deletions to these regions create transcription frameshifts that alter the expression of nearby
coding regions, thus allowing populations to easily switch phenotypes via minor mutations.
Contingency loci are most often seen in the genomes of pathogens, which are subject to frequent environmental shifts caused by the host immune system [63]. Thus, these populations
are able to produce large amounts of heritable variation despite their reduction in diversity
resulting from population bottlenecks.

2.1.1.1

Mutational Landscapes

Properties of genetic architectures such as evolvability and robustness are determined by
the shape of the resulting mutational landscape (local fitness landscape around a genotype,
accessible in a single mutation) [38]. Robust genetic architectures that can tolerate more
mutations without altering their phenotype reside in mutational landscapes that connect to
more neutral mutants. Similarly, architectures where mutations are more likely to cause phenotype switching without substantial reductions in fitness, reside in more evolvable regions
of genotype-space.
It is worth noting that not all regions of the mutational landscape may be equally accessible. Some genome regions may be more resistant to mutation than others. For example, in
Escherichia coli, the methyl-directed mismatch repair (MMR) pathway has been shown to
preferentially repair coding regions over non-coding regions [64]. Alternately, some kinds of
mutations may be more likely to occur than others. A mutation accumulation (MA) study
of Salmonella typhimurium found a strong bias toward GC-to-TA transversions rather than
GC-to-AT transitions [65]. These kinds of effects thereby skew the probabilities of some
kinds mutations occurring that might lead into certain neighborhoods of the mutational
landscape. These kinds of differential probabilities may therefore moderate a population’s

23

diffusion through the mutational landscape.
Further, response to selection is likely to be weaker in regions of the landscape where there
are fewer available mutations that provide potentially adaptive traits, whereas response to
selection will be stronger in regions where there are many adaptive variants available within a
few mutational steps [11, 66]. This differential response to selection may therefore constrain
the ability of populations to diffuse across a fitness landscape.
In order to assess the potential of different regions of the fitness landscape to promote or
hinder evolvability, we will use both the Genomic Diffusion Rate (Dg ) (Eq 1.9) and the
Phenotypic Diffusion Rate (Dp ) (Eq 1.12), as normalized across changing environments
(Eq 1.13).

2.2

Methods

2.2.1

Experimental Design

In order to examine the dynamics and mechanisms of evolving populations in changing environments, we performed two sets of experiments. We subjected populations of evolving
digital organisms to a set of cyclic changing environments, and a set stochastic changing environments. The cyclic environments were designed to simulate predictable cycles of change,
such as day/night or seasonal cycles, whereas the stochastic environments represent less predictable oscillations in environmental states, such as random weather patterns, or climactic
changes. These experiments allow organisms to adapt to a predictable set of environments,
and explores short-term evolvability dynamics. See Table 2.1

2.2.1.1

Cyclic and Stochastic Changing Environments

For the cyclic environment, we subjected a total of 150 replicate populations of digital
organisms to two different treatments of two-phase cyclically changing environments, plus a
static control. The environment cycles between 500 updates of reward, and 500 updates of
punishment; as such each full cycle is 1000 updates, or roughly 30 generations. We chose
24

Table 2.1: Experimental Treatments - Cyclic and Stochastic Changing
Environments
Treatment
Control

Changing
Environment
None
(static)

CCE
Benign

Cyclic

CCE
Harsh

Cyclic

SCE
Benign

Stochastic

SCE
Harsh

Stochastic

Rewarded Tasks
XOR
EQU
constant
constant
3
2
25
benign
constant
fluctuating
23
0 or 25
harsh
constant
fluctuating
23
−25 or 25
benign
constant
fluctuating
23
0 or 25
harsh
constant
fluctuating
23
−25 or 25

Four types of changing environment, plus a static control. In the first two treatments, the
environment switches in a predictable cycle, whereas in the second two, the environment
switches at random intervals.

this cycle length after surveying a series of possible values in order to determine an optimal
length of time. That is, long enough to allow adaptation to occur and spread through
the population, but short enough to reduce the effects of drift destroying vestigial genetic
information. For more details about this survey, please refer to Appendix A.
In the static control, there is no cycle. Rather, the rewards remain constant. The first
phase of the experiment extends for 200 cycles, or 200,000 updates, approximately 6,000
generations.
The stochastic changing environment experiment is similar to the cyclic environment, except that rather than the environment toggling every 500 updates, the environmental switch
happens randomly, with a 0.002 probability of changing on every update. This averages, in
the long term, to approximately one switch every 500 updates, but in the short term, the
environmental switches are unpredictable.

25

We set up the system to detect organisms that performed XOR or EQU, two challenging
bitwise logical tasks. In the static control, XOR is rewarded with a CPU speed (and thus
fitness) multiple of 8, while EQU is rewarded with a CPU speed multiple of 32. In the harsh
treatment, as the cycle progresses, the XOR reward remains constant, while the EQU reward
cycles between a 32-fold bonus and a correspondingly harsh 32-fold penalty (i.e., CPU speed
is divided by 32 when EQU is performed in the off cycle). The benign treatment is nearly
identical to the harsh treatment, except that the reward merely goes away in the off-cycle
as opposed to incurring a severe penalty.
In both environments, we identify EQU as the Fluctuating Task. XOR, because it is
rewarded continuously, is the Backbone Task, and is used as a background for comparing the
separation or intertwining of functional genetic components in the evolution of EQU. Further,
the 4-fold difference in reward level between XOR and EQU encourages the evolution and
maintenance of EQU when possible.
For all of the experiments described in this section, we held the individual genomes at
a fixed length of 1211 instructions, but tested the new genomes for mutations after each
successful replication event at a substitution probability of 0.00075 per site. We configured
the Avida world to have local interactions on a toroidal grid that is 60-by-60 cells (3600 cells
in total), and we seeded the initial populations with an ancestor that was previously evolved
to perform XOR and EQU under a static reward. The genetic architecture for performing
XOR and EQU is tightly intertwined in this ancestral organism, as it was evolved with no
selective pressure for modularity.

2.3

Results and Discussion

Our experiments demonstrate that digital organisms that were evolved in changing environments differ substantially from those that evolved in static environments in a number
1 As

part of our initial controls, we hand-wrote an organism with separated sections that
performed XOR and EQU. This hand-written organism had 121 instructions and as such we
used this genome length as a constraint for the evolve organisms as well.

26

of ways. These differences include the number of mutations that fix in the lineage from
the ancestor (the “phylogenetic depth”), key metrics of their genetic architecture, and the
presence of reservoirs of pseudogenes that change the nearby mutational landscape. These
features represent adaptation to the larger regime of repeated environmental switching. We
also show that while populations evolved in cyclic environments are slightly better adapted to
change than those that evolved in stochastic environments, in most measures of adaptation
and short-term evolvability, these differences are generally not significant. This result indicates that while regular periodicity may offer a slight advantage for adaptation, stochastic
environments perform similarly in most respects.

2.3.1

Cyclic Changing Environments

We will begin by examining the characteristics of populations evolved in cyclic changing
environments.

2.3.1.1

Performance of EQU

Each population was seeded with organisms that performed both the EQU fluctuating task,
and the XOR backbone task. We measured the execution of the EQU task, and observed that
in the static control treatment, EQU is fixed in the population and remains so throughout the
run. In contrast, we observed a periodic dip in the execution of EQU in the benign changing
environment during the non-rewarded phase of the cycle, followed by a rapid recovery when
rewards are reinstated. Finally, in the harsh treatment, we observed abrupt disappearance
of EQU performance, followed by rapid recoveries, coinciding with phases of reward and
punishment. As expected, these results suggest that the populations are responding to the
selective pressures to perform EQU when it is rewarded, and to lose functionality when it is
not rewarded or when it is punished.

27

Figure 2.1: Number of organisms performing EQU task. We measured the execution
of the EQU task in all treatments. By the end of the run, we observed fixation in the control
treatment. In the benign treatment, we observed increasing periodic dips in execution that
coincide with phases of non-reward as the experiments progressed. In the harsh treatment,
we observed adaptation, resulting in abrupt disappearance of EQU in the punishment
phase, followed by rapid recovery of EQU performance during the reward phase.

2.3.1.2

Evolutionary History and Population Structure

We then surveyed the evolutionary history and population structure of the evolving populations. Evolution in the harsh cyclic changing environment resulted in many more mutations
fixing, and thus populations with substantially higher phylogenetic depth as compared to
those evolved in static or benign environments. At each environmental shift, adaptive mutations rapidly swept and fixed in the populations. (Fig 2.2)
The populations that evolved in the control and benign environments displayed more
genetic diversity as compared to those evolved in the harsh cyclic environment, which underwent a bottleneck at each cycle shift (see Fig 2.4). Because a selective sweep reduces
current diversity within a population, the smaller number of sweeps in the benign and control treatments led populations in them to have higher standing diversity for most of their
evolutionary history than those populations from the harsh changing environment. Despite
this higher standing diversity in the benign and control treatments, regions of low diversity
are still evident in the genomes of these populations, implying purifying selection on the
traits encoded at these sites (see Fig 2.3).

28

Figure 2.2: Phylogenetic depth over time of a sample population evolved in each of the
three treatments of the cyclic changing environments. Phylogenetic depth is the number of
mutational steps from the original ancestor, and is a rough analog for generations. White
horizontal lines mark the depth of the most recent common ancestor, and discontinuities in
this line indicate that the most recent common ancestor has changed, and thus that a
sweep occurred, or that a competing clade went extinct. The control treatments had a
mean of 18 sweeps (STD=9.05), the benign treatments had a mean of 21 (STD=19.05),
and the harsh treatments had a mean of 88 sweeps (STD=23.37). Note the difference in
scales between y-axes: the control-evolved population has a maximum depth of 400
mutational steps from ancestor, while the harsh-evolved has upward of 1100.

29

Figure 2.3: Per-site entropy over time of a representative sample population. Each
vertical slice represents the per-site entropy of the population at each update by genetic
locus. Hotter colors (red/orange/yellow) indicate greater diversity at this locus, while
cooler colors (blues) indicate the a locus is more consistent across the population.

2.3.1.3

Genetic Architecture

The alternating selection in both benign and harsh changing environments results in qualitatively different architectural styles as compared with those genomes evolved in the static
environment. The task arrangements evolved under both experimental treatments are much
more scattered throughout the genome than in the control, which is tightly compacted.
Specifically, the bulk of the sites responsible for performing the fluctuating task (EQU) did
not overlap with the backbone task (XOR), except for a small core region, which represents
portions of the tasks that are shared between XOR and EQU. That is, in the changing environment treatments, we see many more sites that only code for a single task, whereas in

30

Figure 2.4: Population entropy over time of the representative sample population in
Figure 2.3. Mean population entropy indicates the relative diversity of the population at
any given time, while the per-site entropy (see Fig 2.3) shows where in the genomes the
population diversity is located.

the static treatment, the majority of functional tasks sites code for both XOR and EQU. (See
Figs 2.5, 2.6, and 2.7)

Figure 2.5: Genetic architecture of XOR and EQU over time in static
environment for the final dominant genotype in a randomly selected replicate.
Proceeding from the left of each figure, each vertical slice represents an organism along the
line-of-descent to the final dominant. Positions along the Y-axis represent each genome
locus; loci in an organism are colored based on the tasks that they code for. Sites in red
are active sites that code for the XOR task only, sites in blue are active sites for the EQU
task only, and purple sites code for both XOR and EQU. Knockouts to the sites in black
are lethal to the organism. Sites in the lighter colors (tan, light blue, lavender) represent
vestigial sites for XOR only, EQU only, or both tasks, respectively. As we proceed from left
to right, we can see the evolutionary history of the final dominant genotype. XOR and EQU
overlap almost completely throughout the run.

31

Figure 2.6: Genetic architecture of XOR and EQU over time in benign
environment for the final dominant genotype in a randomly selected replicate.
Proceeding from the left of each figure, each vertical slice represents an organism along the
line-of-descent to the final dominant, and as in Figure 2.5, colors represent tasks performed
by each genome locus. In this genome, XOR and EQU evolve to overlap much less than in
the control.

Figure 2.7: Genetic architecture of XOR and EQU over time in harsh
environment for the final dominant genotype in a randomly selected replicate.
Proceeding from the left of each figure, each vertical slice represents an organism along the
line-of-descent to the final dominant, and as in Figures 2.5 and 2.6, colors represent tasks
performed by each genome locus. In this genome, XOR and EQU evolve to overlap even less
than in the control and benign treatments, with the EQU-only task sites becoming
increasingly scattered throughout the genome.

In terms of site placement over time, functional task site locations in the control treatment
did not change substantially over the course of the experiment. In the benign treatment,
many more regions that performed the fluctuating task (XOR) were scattered throughout
32

the genome, but site positions remained relatively fixed throughout the run after an initial
adaptive phase. In the harsh treatment, however, not only are the active sites scattered, but
the positions of active sites change and proliferate wildly over time.
In addition to the variation in site placement, populations in the benign and harsh changing environment treatments had significantly more functional sites devoted to performing just
the EQU task (Wilcoxon Rank Sum Test: Z = -5.57 and -6.96, respectively, p << 0.001).
Interestingly, populations evolved in both the benign and harsh treatments also show development of a large reservoir of formerly functional, now vestigial, sites; that is, sites that
remain unchanged from when they were previously active in performing a task, but were
disabled by a mutation elsewhere and are thus now neutral. These vestigial pseudogene-like
sites may be important for allowing the organisms to quickly re-adapt as the fluctuations in
the environment restore the previously-rewarded functions. (Fig 2.8)

Figure 2.8: Number of functional and vestigial sites by treatment. Both the benign
and harsh changing environments had significantly more sites devoted to performing only
the EQU function (Wilcoxon Rank Sum Test: Z = -5.57 and -6.96, respectively, p <<
0.001). The harsh environment has a significantly larger number of vestigial sites for the
fluctuating (EQU) task compared to the benign treatment or control (Wilcoxon Rank-Sum
Z = -6.57 and -8.33, p << 0.0001).

33

2.3.1.4

Nearby Mutational Landscape

In order to identify the role that these longer task footprints and pseudogene-like structures
play, we performed a survey of the single-step mutational neighborhood surrounding the
most abundant genotype present at the end of the experiment for each replicate population.
Each neighborhood contained 3,025 distinct mutants (121 loci with 25 possible mutations
per locus) in each of the 50 replicates per treatment, for a total of nearly 450,000 mutants
surveyed. We measured the fraction of mutants that lost each of the rewarded tasks. (Fig 2.9.

Figure 2.9: A survey of the single-step mutational neighborhood around organisms
that performed the fluctuating task. Note that in both the benign and harsh treatments,
there were significantly more mutants that lost the EQU task as compared to the control
(Wilcoxon Rank Sum Test: Z = -5.46 and -7.80 respectively, p << 0.0001). This result
indicates that it was easier for the organisms in both treatments to turn off the EQU task
in response to one mutation.

We found that in both the benign and harsh treatments, there were many more mutations
that resulted in loss of the fluctuating task as compared to the control (Wilcoxon Rank Sum
Test: Z = -5.46 and -7.80 respectively, p << 0.0001). An increase in task loss in the harsh
treatment is to be expected, but why would the benign treatment lose EQU nearly as easily as
the harsh treatment? One possibility is selective pressure to lose the task. There is no explicit
34

pressure for task loss, merely an absence of reward. Even so, there is certainly an implicit
penalty for performing a complex task for which there is no reward. Another possibility
is drift. Indeed, in Figure 2.1, we observe a steady downward trend in execution of EQU
when rewards are withdrawn. Then, as the reward returns, new mutations are applied that
reactivate the task, and overall performance recovers quickly. This pattern of loss and regain
would, over time tend, to increase the length of the task. Indeed, as noted in Figure 2.7,
there is a rapid increase in task length as EQU is cyclically lost and regained.
However, is increased task length enough to account for increased task vulnerability
to mutation? In order to begin to address this question, we calculated the correlation
between task length and the fraction of mutants that lost each of the tasks. We discovered
a strong correlation between the number of functional sites and the number of task-losing
mutants for the EQU task, both alone, and overlapping with XOR (Spearman’s Rho: rs =
8.72 and 6.45, respectively, p = << 0.001) (Fig 2.10). We also found a weaker, but still
significant correlation between the number of XOR-only functional sites and loss of the XOR
task (Spearman’s Rho: rs = 3.85, p << 0.001). This result confirms our intuition that the
longer the task, the more targets there are for mutation to disable the task.
Further, the lower correlation between length and task loss for the XOR suggests that it
is not only task length, but some other architectural feature that makes the XOR task more
robust to mutation, and the EQU task more fragile. Even so, the question of what kinds of
architectural features account for this differential robustness remains open.
We then measured the proportion of second step mutants that regained EQU after having
lost it in the single-step survey. We found that changing environments shifted shifted the
populations’ position in the mutational landscape, such that when a task that was lost due
to mutation, that task could be regained via one or two additional mutations elsewhere.
That is, once a mutation caused the loss of a task, a different mutation could reactivate the
task. (Fig 2.11).
We speculate that this effect is due to the availability of reservoirs of formerly vestigial

35

Figure 2.10: Correlation between task length and mutational task loss in the
1-step neighborhood across all treatments. Note the strong correlation between the length
of the EQU task and the fraction of mutants that lost EQU (Spearman’s Rho: rs = 8.72, p
<< 0.001). Further, consider the weaker correlation between XOR task length, and fraction
of mutants that lost XOR. This suggests that EQU is even less robust to mutation compared
to XOR than can be accounted for by task length alone.

sites. How such reservoirs might perform these functions remains an open question. New
mutations may either re-enable the old functional sites, or recruit vestigial functionality to
perform the task elsewhere. Potentially, these vestigial sites are not altogether dormant at
all. They might individually appear vestigial in the context of a single knockout survey, but
they might also be related to other sites in a network of backup functionality that becomes
activated in response to mutation. More research is needed to explore what role these feature
play.
As an overall measure of neutral exploration, we also measured the proportion of nondeleterious mutants in the nearby fitness landscape - the Genomic Diffusion Rate. We
found that this proportion remained approximately the same between all treatments (Kruskal
Wallis: H(2) = 1.44, p = 0.49). However, we found that the Phenotypic Diffusion Rate, the
proportion of these mutants with different (and potentially adaptive) phenotypes, increased
in the changing environment treatments as compared to the controls (Wilcoxon Rank Sum
Test: Z = -8.02, -8.39, respectively, p << 0.001). In this way, the organisms from the
changing environment treatments have an advantage over organisms from the control runs
36

Figure 2.11: A survey of the two-step mutational neighborhood of the organisms
that lost EQU function in the one-step survey. We found that in both the harsh and benign
treatments, there were significantly more organisms that regained function in response to
mutation than the control. (Wilcoxon Rank Sum Test: Z = -47.9 and -57.82 respectively, p
<< 0.0001). This result indicates that it was easier for the organisms in both fluctuating
environments to regain the task in response to one additional, non-reversion mutation.

in the short-term evolvability of the fluctuating task. This result is consistent with real
adaptation, not only to resources in their local environment, but a direct adaptation to the
environmental change. (Fig 2.12)
What might account for this adaptation? Similar to the relationship between the number
of functional sites of a task, and the number of single-step mutants that lost that task (See
Fig 2.10), we hypothesize that the reacquisition of tasks in the 2nd-step survey may be
mediated by the amount of useful task material present in the genome. We performed a
multiple linear regression, predicting the mean fraction of mutants that regained EQU, by
the number of functional and vestigial sites contained in the original genome (See Table 2.2
and Fig 2.13).
We can predict approximately 47% of the variation in mean number of second step
mutants that regained EQU based on the number of functional and vestigial sites. Most

37

Figure 2.12: Genomic and phenotypic diffusion rates, showing the probabilities of
producing offspring that are genotypically (Dg ) or phenotypically (Dp ) distinct from the
parent, while not reducing fitness. Note that while overall neutral exploration capacity
remains relatively stable between treatments (Kruskal Wallis: H(2) = 1.44, p = 0.49),
phenotypic exploration capacity is increased in both treatments, but especially in the
Harsh treatment. (Wilcoxon Rank Sum Test: Z = -8.02, -8.39, respectively, p << 0.001).
This result is consistent with changing environments promoting the phenotypic evolvability
of populations.

of the variation is predicted by the number of functional sites, though vestigial sites do
contribute a small amount. This result is consistent with the role of task length, and thus
the number of informational sites, being important for regaining task function. We could
not, however, account for all variation, indicating that there are other factors, possibly in
robustness or modular architecture of tasks, that are important to this kind evolvability.

2.3.2

Stochastic Changing Environments

Contrary to our expectations, stochastic changing environments were, overall, no more effective at promoting evolvability than cyclically changing environments. Harsh environments
performed slightly worse, whereas benign environments were slightly better, though neither
result was consistently statistically significant. There was a slight but significant reduction

38

Figure 2.13: Multiple linear regression predicting mean fraction of second-step
mutants from the number of functional and vestigial sites in the original organism. See
Table 2.2.
in the Phenotypic Diffusion Rate (Dp ) between the cyclic and stochastic harsh changing
environments; Dp settled on a lower median (Mdn = 0.0) in the stochastic harsh treatment
as compared to the cyclic harsh (Mdn = 0.0058) (Wilcoxon Rank-Sum Test: Z = -6.19, p
<< 0.0001), indicating a lower probability of the population producing offspring that would
switch phenotypes neutrally. In the Benign treatments, however, Stochastic environments
fared slightly better than cyclic, though this result was only barely statistically significant
(Wilcoxon Rank-Sum Test: Z = 2.2, p<0.03). (Fig 2.14)
Despite the reduced Dp in the harsh treatment, both the overall fraction of 1-step mutants that lost EQU, and the fraction of 2nd-step regaining of EQU, were only very slightly
reduced in comparison to the cyclic treatments, and this effect was not statistically significant(Fig 2.15, 2.16). This result suggests that stochastic harsh environments are certainly

39

Table 2.2: OLS Regression Results - Mean Fraction of Mutants Regained EQU
vs Number of Functional and Vestigial Sites
Dep. Variable:
Mean Fraction
Model:
OLS
Method:
Least Squares
No. Observations:
141
Df Residuals:
138
Df Model:
2

Intercept
Func Sites
Vest Sites

R-squared:
Adj. R-squared:
F-statistic:
Prob (F-statistic):
Log-Likelihood:
AIC:
BIC:

coef

std err

t

0.0003
0.0016
0.0005

0.001
0.000
0.000

0.243
8.115
3.180

Omnibus:
Prob(Omnibus):
Skew:
Kurtosis:

79.316
0.000
1.970
10.675

P>|t| [0.025
0.808
0.000
0.002

-0.002
0.001
0.000

Durbin-Watson:
Jarque-Bera (JB):
Prob(JB):
Cond. No.

0.472
0.464
61.65
7.39e-20
467.28
-928.6
-919.7

0.975]
0.003
0.002
0.001
1.928
437.211
1.15e-95
15.0

Multiple linear regression, predicting Mean fraction of second-step mutants that regained
EQU, based on the number of Functional and Vestigial sites in the original genome.

no more effective at promoting evolution toward areas of the mutational landscape where
such mutations were common, and may, in fact perform worse.
In contrast, we observed a very slight, but statistically significant increase in the fraction
of 1-step mutants that lost EQU in the stochastic treatment versus the cyclic (Wilcoxon
Rank-Sum Test: Z = -2.4, p = 0.015). This effect was matched by a slight increase in
the fraction of 2-step mutants that regained EQU in the benign stochastic treatment vs
cyclic (Wilcoxon Rank-Sum Test: Z = -18.42, p << 0.0001). This result suggests that in
stochastic changing environments, benign environments might possibly perform better than
harsh environments for promoting evolvability. However, because the effect sizes were so
small, we cannot conclusively find that stochastic environments perform any differently from
cyclic at promoting evolvability.
Few differences between the cyclic and stochastic treatments also appeared in the number
of functional and vestigial sites. Both the numbers of functional and vestigial sites in the

40

Figure 2.14: Genomic and phenotypic diffusion rates in stochastic changing
environments, showing the probabilities of producing offspring that are genotypically and
phenotypically different from the parent, while remaining fitness neutral or better. As in
the cyclic environment, Dg remains stable for the Benign treatment, but drops slightly in
the Harsh as compared to the control, though this drop isn’t statistically significant
(Kruskal Wallis H(2) = 1.11, p = 0.57). Harsh Dp however, is significantly lower than seen
in the cyclic environment treatment (Wilcoxon Rank-Sum Test: Z = -6.19, p << 0.0001).
This result shows that harsh stochastic environments may not be as effective as cyclic
environments at increasing the probability that organisms will produce phenotypically
different, yet neutral offspring.

stochastic environment were similar to those in the cyclic environment. In the stochastic
harsh treatment, there was a small, but significant reduction in the number of XOR+EQU
overlapping functional sites (Mdn = 14) as compared to the cyclic treatment (Mdn = 16) .
(Fig 2.17)
Together, from these measures, we conclude that stochastic environments exert similar
evolutionary pressure to move toward regions of the mutational landscape that are more
congenial to neutral phenotypic exploration and evolvability. However, the combination of
the slight improvements in benign stochastic environments, matched by slight decreases in
effectiveness in harsh stochastic environments, suggests that the periodicity of the cyclic
environment provides a slight advantage to adapting to harsh environments. In the benign

41

Figure 2.15: A survey of the single-step mutational neighborhood in the stochastic
changing environment around organisms that performed the fluctuating task. Again, in the
static and harsh treatments, values are comparable to the cyclic changing environment .
However, in the benign treatment, the mean for the loss of the fluctuating task (EQU) was
slightly higher in the stochastic treatment (Mdn = 0.2) than the cyclic (Mdn = 0.17),
though the effect is barely statistically significant (Wilcoxon Rank-Sum Test: Z = -2.4, p =
0.015). This result is consistent with stochastic environmental change being equivalently
effective at moving organisms to areas of the fitness landscape where they can more easily
switch task expression.

environments, however, the stochastic nature may be less of a disadvantage. We hypothesize that this dynamic may be due to the randomly-occurring environmental changes either
occurring too rapidly for a response to selection, or too slowly, such that drift may cause the
information contained in vestigial sites to mutate away. While the environment, on average,
experiences as many changes as in the cyclic experiment, the distribution of the length of
those environment periods may be very different. We conclude that our stochastic changing environment is not more effective than a cyclic changing environment, and under harsh
conditions, may actually be slightly worse for promoting the evolution of evolvability.

42

Figure 2.16: A survey of the two-step mutational neighborhood in the stochastic
changing environment of the organisms that lost EQU function in the one-step survey. We
found that the fraction of organisms regaining the fluctuating task (EQU) from a single
additional mutation in the harsh treatment (Mdn = 0.013) were reduced compared to the
cyclic harsh treatment (Mdn = 0.01) (Wilcoxon Rank-Sum Test: Z = 12.75, p << 0.0001)
The opposite, however, was true of the Benign treatments. As in Fig 2.15, we find that
stochastic outperforms cyclic (Wilcoxon Rank-Sum Test: Z = -18.43, p << 0.0001) This
result confirms that the harsh stochastic environment is probably less effective than the
cyclic harsh at promoting evolvability, but that the opposite may be true for a benign
environment.

2.4

Conclusion

In cyclic changing environments, the direction of selection shifts frequently, and periodically drives populations to not only explore new regions of the genetic landscape, but also
to carry with them vestigial genetic information about previous environmental conditions.
Thus, the resulting populations are not only adapted to the current environment, but also to
the meta-environment of cyclic change. Because of their evolutionary history, the genomes
contain vestigial fragments of genetic material that were adapted to prior environments. As
this exploration proceeds, mutations accumulate in the population, each creating a link to
a new region of the mutational landscape. As these links accumulate, they form a reservoir

43

Figure 2.17: Number of functional and vestigial sites by treatment in a stochastic
changing environment. The vestigial site counts for EQU-only performing organisms remain
comparable to the cyclic environment (Wilcoxon Rank-Sum Z = 0.46, 1.45, and -1.10, p =
0.6, 0.14, and 0.2). The functional sites were also comparable, however, there was a slight,
but statistically significant decrease in the number of XOR & EQU overlapping sites in the
stochastic vs cyclic environments (Wilcoxon Rank-Sum Test: Z = -3.05, p<0.01).

of mobility for the population to quickly shift to new phenotypes as dictated by current
selective conditions. In this way, the accumulation of vestigial or pseudogene-like regions
acts as an indirect adaptation to the larger pattern of changing selective forces.
By contrast, in static (non-changing) environments, the majority of neutral mutations
do not connect to as many phenotypically-interesting regions of genotype-space. There are
far fewer pseudogene-like regions available that could regain functionality should conditions
change. Thus, populations evolved in static environments are less evolvable in the short-term.
These results suggest, therefore, that architectural features that help with evolvability
are more likely the result of repeated hitchhiking on adaptive mutants. In particular, we
observed that much of the task-loss associated with the harsh changing environment could be
attributed to increasing task length which is a result of the continuous addition of new mutations activating and deactivating the task. Despite this correlation, however, we observed

44

a potential difference in robustness between the XOR and EQU tasks, which suggest that a
kind of anti-robustness may also be selected for as a result of the changing environments.
Surprisingly, stochastically changing environments are not more effective at exploration
than cyclic changing environments, even if, on average, the amount of time spent in each
environment was equal. We hypothesize that this result is because of more opportunity for
drift to destroy the information contained in vestigial regions, as well as potentially fewer
opportunities for populations to respond to selection.

45

CHAPTER 3
CHANGING ENVIRONMENTS AND THE EVOLUTION OF HORIZONTAL
GENE TRANSFER

3.1

Background

Horizontal Gene Transfer (HGT) is a broad term for the non-reproductive transfer of
genetic material between organisms. Organisms may uptake genes directly from the environment (transformation via natural competence [67]), or else receive them via bacterial
conjugation [68] or viral infection (transduction [69, 70]). In the case of transformation, the
fragments may either be decomposed inside the recipient cell for their nutrients, or recombined into their genomes.
HGT has had a profound impact on the evolutionary history of both prokaryotes and
eukaryotes, with one study showing approximately 81% of genes in the sample “being involved in HGT at some point in their history” [71]. For example, HGT appears to be the
primary mechanism by which antibiotic resistance is conferred [72, 73] since most antibiotics
are sourced from the environment, and the organisms that develop them are themselves resistant to the compounds. However, the origins and evolution of HGT mechanisms remain
unclear.

3.1.1

Origins of Horizontal Gene Transfer in nature

In prokaryotes, ”transformation” is an HGT mechanism by which organisms spontaneously
uptake the DNA of dead organisms in the environment. Competent organisms benefit in
several ways. 1) DNA is composed of a 5-carbon sugar, a phosphate, and nitrogenous bases,
materials that are useful for DNA synthesis and repair. 2) The organisms may also benefit
from taking up gene fragments that confer new adaptive functionality into the genome [74].
However, it is unclear whether the origins of transformation functions were developed solely in

46

order to obtain nutrients (the Grazing Hypothesis), or if the acquisition of new functionality
was selected for as well. While grazing for gene fragments as nutrients certainly conveys
an advantage, the possibility of integrating these gene fragments is likely to be deleterious
to organisms more often than it is beneficial [75]. For example, since the DNA would be
originating from dead organisms, DNA fragments may be of low quality, and recombine
deleterious mutations, or even remove competence altogether [75]. Alternately, errors in
homologous recombination may apply fragments to random locations in the genome.
Although advances in molecular biology are allowing researchers to investigate the mechanisms of HGT and even reconstruct specific inferred cases of HGT (as reviewed in Bock
2015 [76]), the processes themselves are ancient and nearly ubiquitous [77]. This very ancientness makes studying the early evolution of HGT in physical organisms exceedingly
challenging, as we lack easily tractable systems that differ only in whether or not HGT
exists within them. Therefore, empirical studies in natural systems remain exceedingly rare.
In order to test the Grazing Hypothesis of the origin of HGT, and to address the question of whether there are circumstances where gene fragment integration may be beneficial,
we subjected populations of evolving digital organisms to a harsh changing environment,
where there is a strong selective pressure to quickly switch phenotype. We supplied organisms with an instruction that performs Horizontal Gene Transfer (HGT-Uptake). That is,
the instruction triggers uptake of a genetic fragment from the environment, and there is a
probability that, rather than metabolizing the fragment for a bonus to execution speed, the
fragment will instead be homologously recombined into the organism’s genome. We show
that in harsh changing environments, without any kind of bonus, organisms increase use of
HGT as compared to execution in a static environment.

3.2

Methods

In this chapter, we use Avida to test hypotheses about the origins of Horizontal Gene
Transfer.

47

3.2.1

HGT in Avida

In Avida, HGT is triggered by the HGT-Uptake instruction that, when executed, attempts
to uptake a genome fragment from the individual cell reservoirs in the environment. As
organisms die in Avida runs with HGT enabled, we collect fragments of their genomes in
reservoirs. These fragments will deteriorate over time, with older genomes disappearing from
the reservoir as new ones enter. Fragments for uptake will be randomly selected from the
reservoir.
We have implemented a configurable probability that, when a fragment is taken up, it is
not metabolized; instead, homologous recombination may occur (Figure 3.1). We performed
experiments to derive bonus levels, fragment sizes, and recombination probabilities to arrive
at a maximum use level for the HGT instruction. See Appendix B for more details.
For all experiments described in this chapter, we used a 10% recombination probability.
Please refer to Appendix B for more information about the selection of this probability value.
We also required three instructions as the minimal homologous match length on either side
of the fragment. Three instructions on either side of the fragment (263 unique sequences)
approximates the number of unique values keyed by 7 nucleotides (47 unique sequences).
For the purposes of homologous recombination in plasmid cloning in E. coli, 20bp is enough
to assume identity [78].
Homologous recombination requires a pair of valid matching sites in the genome, which
are selected as follows: We search for a set of sites that match the first three instructions
of the uptaken fragment, starting at the beginning of the genome. We search the whole
genome, until we find a matching site for the front three instructions of the fragment. Then,
we begin searching for a match for the back three instructions of the fragment, starting at
the edge of the front match. If a valid back-end match site is not found, we scan forward,
looking for the next front-end match and repeat the process until all possible match sites on
the genome are exhausted.
If no match is found, recombination fails. If recombination succeeds, it replaces the

48

content of the organism’s genome between the selected beginning and end match sites with
the content of the fragment. This may result in the genome growing or shrinking, depending
on the distance between the matches, and the length of the fragment.

Figure 3.1: The HGT process. Organisms can execute instructions that trigger uptake
from the environment. When uptake occurs, there is an experimenter-defined chance that
either it will yield a boost to speed of execution or, alternatively, that the fragment will be
integrated into the genome.

3.2.1.1

Environmental Conditions

All experiments in this chapter compared outcomes between static environments, and harsh
changing environments. In a similar manner to the experiments listed in the previous chapter
(Chapter 2, Table 2.1), task rewards in the harsh changing environment switched from a

49

Table 3.1: Logic-9 Rewarded Task Groupings

Group 1

Group 2

Tasks

Reward
Phase 1

Reward
Phase 2

NOT
AND
OR
NOR
EQU
NAND
ORN
ANDN
XOR

21
22
23
24
25
−21
−22
−23
−24

−21
−22
−23
−24
−25
21
22
23
24

Logic-9 tasks were divided into to groups, with one task from each pair of tasks of
equivalent complexity assigned to a group. The EQU task, which has no complexity
equivalent, was arbitrarily assigned to the first group. During the first half of a cycle, we
rewarded the first group of tasks and punished the second group (see Reward Phase 1).
During the second half of the cycle, reversed the pattern, and rewarded the second group,
and punished the first group (Reward Phase 2).

positive to a negative reward. For the HGT experiments, we did not establish a backbone
task that was always rewarded. Rather, we divided the Logic-9 environment into two halves,
and alternated positive and negative rewards for each task in each set. There are four
pairs of tasks of equivalent complexity, and we randomly allocated one from each pair to
an experimental group. We also assigned EQU, which is the most complex task, and has
no equivalent, to a random group. Thus, for the first phase of the cycle, we punished the
NOT, AND, OR, NOR, and EQU instructions at −21 , −22 , −23 , −24 , and −25 respectively,
while rewarding NAND, ORN, ANDN, and XOR at 21 , 22 , 23 , and 24 . In the second phase of
the cycle, these rewards flipped, such that we rewarded NOT, AND, OR, NOR, and EQU, and
punished NAND, ORN, ANDN, and XOR (See Table 3.1).
Each complete cycle lasted 1000 updates, and the whole experimental run extended for
200,000 updates. The static environment rewarded executions of all the Logic-9 tasks at
their default levels, with no reward switching.

50

3.2.2

Experimental Design

For the treatments corresponding to the first set of hypotheses on the origins of horizontal
gene transfer, we subjected four populations of evolving digital organisms with HGT to
harsh changing environments (Table 3.2), plus a pair of non-HGT control. The treatments
correspond to the combination of two factors: static vs changing environment, and grazing
bonus vs no bonus.
For the second set of hypotheses, where we identify the mechanisms that promote the
use of HGT, we manipulated the content of the reservoirs to contain fragments drawn from
specific phases in the cyclically changing environment, such that fragments either matched or
did not match the environment (Table 3.3). We then measured HGT use, as well as average
fitness effects of the HGT mutations, and the fraction of mutations that led to beneficial
phenotype switches.

3.3

Results and Discussion

Our results, discussed in detail below, show that both an uptake bonus and changing
environment promote the use of HGT, and that the increases in uptake are largely additive.
Further, we found that while on average, HGT mutations are neutral, that the majority of
the benefits conveyed by HGT in changing environments come from fragments originating
in periods of the cycle where the environment matched the current environment. This result
is consistent with the information content of the fragment being valuable. Finally, we find
that providing only fragments from the matching cycle elevates uptake rates significantly.

3.3.1

Changing environments elevate HGT use

We measured HGT fragment uptake in four conditions (see Table 3.2), plus of pair of nonHGT controls. Without a bonus, in a static environment, fragment uptake was depressed
to a low level as compared to the rate of the non-HGT control, where the HGT-Uptake
instruction does nothing (Wilcoxon Rank-Sum Test: Z = 9.74, p << 0.0001). This result is
51

Table 3.2: Experimental Treatments - Evolution of HGT

Treatment
Static Control
(no HGT)
CE Control
(no HGT)
HGT
B0.0
(Natural Competence
No Bonus)
HGT
B0.0
CE
(Natural Competence
No Bonus)

Changing
Env.
Type

HGT
Action

Bonus

Static

None

n/a

Harsh Cyclic

None

n/a

Static

10%
Recombination
Probability

n/a

Harsh
Cyclic

10%
Recombination
Probability

n/a

HGT
B0.8
(Natural Competence
with Bonus)

Static

HGT
B0.8
CE
(Natural Competence
with Bonus)

Harsh
Cyclic

10%
Recombination
Probability
otherwise
Bonus
Allocation
10%
Recombination
Probability
otherwise
Bonus
Allocation

20.8 per
Uptake

20.8 per
Uptake

Four treatments corresponding to the combination of two factors: Static vs Changing
Environment, and Grazing Bonus vs No Grazing Bonus, plus a non-HGT control, where
the HGT instruction is inert.

52

Table 3.3: Experimental Treatments - Effects of HGT
Treatment

Fragment
Source

HGT
Both
OnPhase
OffPhase

organism death
sampled from organisms from both phases
sampled from organisms from the matching phase
sampled from organisms from the non-matching phase

Four treatments corresponding to the sources of fragments. The first treatment used the
default fragment source (dead organisms from the environment). The second treatment
sampled a population for organisms corresponding to both phases, and injected those into
the reservoirs. The third and fourth treatments sampled the population, but only injected
fragments from the matching and non-matching phases, respectively.

consistent with HGT in a static environment being largely deleterious (Figure 3.2). However,
in a no-bonus harsh changing environment, fragment uptake was elevated compared to the
static environment (Wilcoxon Rank Sum-Test: Z = -8.44, p << 0.0001). This shows that
in the context of a harsh changing environment, the integration of new genetic material is
more beneficial than in the static environment. We also found that, regardless of whether the
environment is static or changing, when a bonus to fragment uptake was provided (analogous
to the nutritive benefit granted by natural competence in biological organisms), fragment
uptake also increased (Wilcoxon Rank Sum Test: Z = -8.44, and -7.47, p << 0.0001).
In order to investigate the relationship between the effects granted by a nutritive bonus
and the benefit of fragment recombination in a changing environment, we selected a bonus
level that increased fragment uptake in a static environment to a level comparable to the
increase seen in changing environments without a bonus (for more details of this bonus
selection, please see Appendix B). We then combined these factors, giving a bonus plus a
changing environment. We saw that the resulting uptake level increased largely additively.
This result suggests that the benefits granted by a grazing bonus are generally independent
of the benefits conveyed by integrating new genetic material.
Thus, not only is HGT evolution possible absent a bonus, the benefit stacks with that of

53

Figure 3.2: Number of HGT fragment uptakes in static and changing environments,
without a grazing bonus, with a grazing bonus, and a no HGT control, where the
HGT-Uptake instruction is inert. HGT uptake increased in response to a changing
environment, and also in response to a grazing bonus. The grazing environment and a
changing environment combined resulted in an even larger increase of fragment uptakes
than either the changing environment, or the bonus alone (Wilcoxon Rank Sum Test: Z =
-4.93 and -7.47 respectively, p << 0.0001).

a grazing bonus, proving a more likely scenario by which HGT might evolve.

3.3.2
3.3.2.1

HGT derives most benefit from on-cycle fragments, but not all
Fitness Effects

In order to understand the basis of the beneficial nature of HGT in changing environments,
we measured the fitness effect of individual fragments on individual organisms within a
population. We calculated the average fitness effects of fragments of the non-replaced HGT

54

control treatment at the end of the last environmental cycle, and generated a distribution
of fragments, and sorted the fragments by age and fitness-effect (Figures 3.3). We observe
a clear pattern of more beneficial fitness effects from fragments of organisms originating in
the matching cycle phase.

Figure 3.3: Origin and fitness effect distributions of HGT fragments, sampled
midway through the experiment at 100,000 updates, and aggregated across all replicates.
We applied each fragment in each cell’s reservoir, one at a time, to the organism in the cell,
then recorded the fitness effect. The x-axis is the birth update of fragment’s original donor
organism. The y-axis is a fragment’s fitness effect. The color of each point represents the
number of fragments that originate in that birth update a given fitness value. Hotter
values indicate more fragments from that time origin at that fitness effect. Most fragments
with a positive fitness effect (the upper half of the figure) appear in bands that correspond
with the matching phase of an earlier cycle.

To quantify this observation, we performed experiments where we replaced the fragments
in the reservoir with fragments originating in the matching phase, the off-phase, and mixture
of both phases as a control. We measured the mean and median fitness effects of fragments
in these treatments (Figure 3.4). We found that HGT mutations were, on average, neutral,
or nearly neutral in all the treatments. Both the non-replaced control (Mdn = 0.0, 95%
55

CI [0, 0]) and the replaced-”both” treatment (Mdn = -0.008, 95% CI [-0.009, -0.008]) were
neutral or nearly neutral. The median fitness effect in the ”on-phase” treatment was mildly
deleterious (Mdn = -0.054, 95% CI [-0.055, -0.052]), while the mean was more strongly
beneficial (M = 1.19, SD = 19.7). In contrast, in the ”off-phase” treatment, the median
fitness effect was, again, mildly deleterious (Mdn = -0.0005, 95% CI [-0.0006, -0.0004]), but
with a much more deleterious mean (M = -23.06, SD = 101.8). This suggests that while, on
average, HGT mutations remain nearly neutral, a few fragments from the matching phase
were strongly beneficial, while the opposite was the case for the non-matching phase.

Figure 3.4: Mean and median fitness effects of fragments in reservoirs, with 95%
confidence intervals. Fragments in reservoirs are replaced by fragments based on the origin
of donor organism. For the On-Phase treatment, We only permitted fragments in reservoirs
that originated in a matching phase of the current cycle. For the Off-Phase treatment, we
only permitted fragments from non-matching phases. Plus two controls: first, where no
filtration takes place, and ”Both” where fragments are injected from a mixed set of origins.
The Off-Phase treatment had a significantly lower fitness effect than either of the controls
(Wilcoxon Rank-Sum Test: Z = 143 and 31 respectively, p << 0.001), while the On-Phase
treatment had a significantly better fitness effect (Wilcoxon Rank-Sum Test: Z = 105 and
3 respectively, p < 0.002).

56

3.3.2.2

Beneficial Phenotype Switching

In our environments, mutations that convey phenotypic change should have the largest
impact. Specifically, the largest fitness benefits should occur when a mutation leads to the
acquisition of a new rewarded task, or the loss of a punished task.

Figure 3.5: Fraction of all fragments that produced a beneficial phenotype
changes, with 95% confidence intervals. The ”On-Phase” treatment had significantly more
fragments that convey a beneficial phenotype change than either of the controls (Wilcoxon
Rank Sum Test: Z = -6.42 and -6.12 respectively, p << 0.001), while the ”Off-Phase” had
significantly fewer (Wilcoxon Rank-Sum Test: Z = 7.11 and 7.35 respectively, p << 0.001).

We quantified the phenotypic effect of each fragment by counting the number of times
that fragments produced a beneficial phenotype change, vs all HGT mutations (Figure 3.5).
We saw that a significantly larger proportion of fragments in the ”on-phase” treatment produced beneficial phenotype changes (Mdn = 0.09, 95% CI [0.07, 0.11]), as compared to fewer
in the normal HGT control (Mdn = 0.03, 95% CI [0.03, 0.04]) and ”both” treatments (Mdn
= 0.04, 95% CI [0.035, 0.05]) (Wilcoxon Rank Sum Test: Z = -6.42 and -6.12 respectively,
p << 0.001). In contrast, we observed virtually no beneficial phenotype changes originating
in fragments from the ”off-phase” treatment (Mdn = 0.009, 95% CI [0.006, 0.01]). This
57

result was significantly worse than both the control and the ”both” treatments, which produced non-zero beneficial phenotype switches (Wilcoxon Rank-Sum Test: Z = 7.11 and 7.35
respectively, p << 0.001)
These results suggest that most direct benefit of using HGT derives from taking up
fragments that match the cycle phase of the environment of the affected organism, and thus
likely contains information that relates to that environment. Further, if fragments from the

Figure 3.6: Number of uptaken fragments in the filtered reservoir treatments. The
”On-Phase” treatment has a significantly larger number of HGT fragment uptakes, as
compared to control, ”both”, and ”off-phase” treatments (Wilcoxon Rank-Sum Test: Z =
-3.9**, -3.2*, and -6.5**, respectively, p < 0.002* and p << 0.001**) This shows that HGT
is significantly more beneficial when fragments match the current phase of the cycle. Thus,
this suggests that the primary benefit from HGT is not mutational disruption, but the
information that fragments convey about the current environment.

matching phase are indeed beneficial, we would expect to see an increase in HGT use in those
treatments, as compared to those where the fitness effects are mixed or deleterious. And
indeed (Figure 3.6), we observed just such an increase. Thus we can conclude that HGT
in our changing environments is most beneficial when the fragments in the environment
contain information that would be beneficial in that environment. However, even when no
58

such information was available, HGT use was not significantly depressed as compared to the
control treatment. This suggests that despite the lack of exclusively matched environmental
information, that fragments could still provide some benefit.

3.4

Conclusion

Our experiments confirm our expectations about the evolution of horizontal gene transfer,
and match what we would expect to see in nature. First, we find that grazing bonuses, such
as those conveyed by the uptake of nutrient-rich DNA fragments in natural systems, cause
an elevation of use of the horizontal gene transfer instruction, regardless of the potential risk
of recombining uptaken gene fragments.
Further, when there is direct selection for phenotypic change - such as in a changing
environment - we observe an increase in the use of the HGT instruction, even when no
grazing bonus is offered. This is consistent with the possibility of recombination itself being
selected for. Beyond this, we find that it is not only the fact of the recombination that
is beneficial, but the information contained in the fragment. We found that most of the
benefit conveyed by HGT derived from fragments that match the current environment, but
also that when we filter so that only those fragments are available, that use of the HGT
instruction increases even further. Even so, HGT use is still modestly elevated even when no
new information is provided by fragments. This suggests that it is not just novel information
that conveys a benefit. Rather, it is possible that HGT might be useful for other functions,
such as error correction.
In natural systems, evidence for phenotype change via HGT is apparent in the evolution
of antibiotic resistance in bacteria, where resistance is acquired largely by the spread of
resistance genes via horizontal gene transfer. Therefore, our results provide a key insight
into how horizontal gene transfer mechanisms could be selected for, and evolve in natural
systems.
It is worth noting that most prior studies of HGT have been observational studies that

59

look at existing traits and phylogenies and attempt to make inferences about the evolution
of those traits on that basis. Performing experimental evolution studies of the evolution
of HGT in organic systems is currently intractable. Digital evolution, on the other hand,
allows us to explore and test many hypotheses about the evolution of HGT, such as the
explicit benefits and consequences of different types of mutations. It gives us an opportunity
to compare granular fragment grazing bonuses and quantify their effects on evolutionary
outcomes. These experiments are ones that we would not be able to perform any other way.

60

CHAPTER 4
HORIZONTAL GENE TRANSFER VS OTHER TYPES OF MUTATION

4.1

Background

In both natural and artificial systems, populations evolve mechanisms to reduce or eliminate mutations [79], despite evidence that higher mutation rates are optimal for adaptive
evolution [80]. In artificial systems, prior research has failed to show a substantial increase in
endogenously-controlled mutation rates, even when such an increase would be beneficial for
long-term adaptive evolution, such as in a changing environment [80]. However, Horizontal
Gene Transfer through transformation seems to be an exception to this rule.
In nature, transformation is a highly regulated and refined mechanism for taking up DNA
fragments from the environment [81, 82, 83]. Clearly, evolution is acting to maintain and
preserve these functions, despite the risk of harmful recombinations. In the previous chapter,
we showed that HGT is under positive selection in harsh changing environments. Despite the
fact that the fitness effects of recombination tend to be neutral to slightly deleterious, HGT
use is up-regulated. What makes HGT different from other types of mutations? Is it the
beneficial fitness effects of HGT mutations? The information content of fragments relating
to a new environment? The probability of phenotypic changes? Furthermore, we need to
ask what makes HGT special as compared to other types of mutations in these respects.
And can any of the differences the we uncover account for the increased selection pressure
for HGT as compared to other mutation types?
We hypothesize that those instructions that convey the largest amount of information,
the best fitness outcomes, and the best likelihood of beneficial phenotype change will be used
more than those that convey less information or lead to worse fitness outcomes.
In order to address these question, we created instructions that create different kinds of
mutational effects with similar per-instruction impact to HGT. Each new instruction controls

61

for one specific aspect of HGT to determine how important it is as compared to others. We
performed experiments with these new mutagenic instructions under the identical conditions
as our evaluation of HGT, in static vs. changing environments. We found that not only are
these new instructions triggered at significantly lowered rates as compared to HGT, but that
the rate at which they are used correlates significantly with the amount of useful information
expected to be conveyed by the mutation.

4.2

Methods

In this chapter, we use Avida to compare mutational effects of HGT to other types of
mutations. As in the previous chapter, HGT is triggered by the HGT-Uptake instruction,
and fragments are collected from reservoirs in the environment.
All experiments in this chapter compare outcomes between static environments and harsh
changing environments. Similarly to the experiments in the previous chapter, task rewards
in the harsh changing environment switch from a positive to a negative reward between
the divided set of tasks in the Logic-9 environment. Please refer to Table 3.2 for additional
details. Each complete cycle lasts 1000 updates, and the whole experimental run continues for
200,000 updates. Also as in the previous chapter, the static environment rewards executions
of all the Logic-9 tasks at their default levels, with no reward switching.

4.2.1

Experimental Design

We conducted a total of 14 treatments in order to isolate the advantages of HGT-Uptake
and to identify the underlying reasons why this instruction is under positive selection. Each
treatment differed by either environmental condition (static vs. changing) or the available
mutagenic instruction.

62

4.2.1.1

Alternative Mutagenic Instructions

In order to perform experiments comparing HGT to other types of mutagenic instructions, we
modified the functioning of the HGT instruction to perform a new set of mutagenic functions
which should have the same raw, per-instruction effect as the normal HGT instruction. All
mutagenic instructions have the same 10% probability of triggering their mutagenic effect.
All instructions also have the same viable recombination site requirements as the default
HGT instruction (as detailed in Chapter 3, Methods), in order to be able to compare use
rates across treatments.
The specific set of possible instructions are:
• HGT (Intact Fragment): The default HGT operation, as detailed in Chapter 3,
Methods. We uptake a fragment from the environment. We apply a 10% probability that the fragment is recombined into the organism’s executing genome. A valid
recombination site is required for recombination to occur.
• HGT Shuffle: We uptake a fragment from the environment, and a valid recombination
site is found, as above. Prior to recombination, however, we shuffle the fragment. The
identical set of instructions are inserted, but the order of each instruction randomized.
We then insert the fragment at the selected site.
• HGT Random: We uptake a fragment from the environment, and find a valid recombination site, as above. Prior to recombination, however, we replace the entire
fragment with an equal number of randomly selected instructions, and insert this new
sequence at the selected site.
• Mutation Event - Sampled: We uptake a fragment from the environment, and find
a valid recombination site, as above. Rather than recombine, however, we apply a
number of point mutations in random locations throughout the genome. The number of applied mutations matches the number of instructions in the fragment. The

63

mutations applied are sampled, with replacement, from the selected fragment. This
mutagenic instruction is analogous to the the HGT Shuffle mutagen, except that
instead of having a shuffled fragment applied in a single location, the instructions from
the fragment are sampled and applied randomly throughout the genome.
• Mutation Event - Random: We uptake a fragment from the environment, and find
a valid recombination site, as above. Rather than recombine, we apply a number of
random point mutations, matching the number of instructions in the fragment. This
mutagenic instruction is analogous to the HGT Random mutagen, except that, again,
its effects are applied randomly throughout the genome instead of at a single location.
• Mutation Rate Increase: We uptake a fragment from the environment, and find
a valid recombination site, as above. Rather than recombine, we increase the pointmutation rate for the organism, such that it will experience an expected additional
number of point mutations matching the number of instructions in the uptaken fragment.
• Die: We uptake a fragment from the environment, and find a valid recombination site,
as above. Rather than recombine the fragment in, the organism instead dies. As with
each of the other cases, the finding of a recombination site is simply to control for
the frequency of success to ensure that this effect is trigged with the same probability
as recombination. The Die instruction is a control, to identify a minimal level of use
where populations would suppress the use of the instruction as much as possible.

4.2.1.2

Comparing HGT to Other Mutation Types

For the experiments comparing the mutational effects of different types of mutations, we
provided populations of evolving digital organisms with instructions that endogenously trigger different kinds of mutation events (see above), then subjected them to both static and
harsh changing environments (Table 4.1).
64

Table 4.1: Experimental Treatments - Mutation Types
Treatment

Environment

HGT
HGT CE
HGT-Shuffle
HGT-Shuffle CE
HGT-Random
HGT-Random CE
ME-Sampled
ME-Sampled CE
ME-Random
ME-Random CE
MRI
MRI CE
Die
Die CE

Static
Changing
Static
Changing
Static
Changing
Static
Changing
Static
Changing
Static
Changing
Static
Changing

Mutagenic Instructions
HGT
HGT-Shuffle
HGT-Random
ME-Sampled
(Mutation Event - Sampled)
ME-Random
(Mutation Event - Random)
MRI
(Mutation Rate Increase)
Die

Two types of environment (static vs changing environment), for each mutagen. No bonus
was given for performing any of the mutagenic instructions.

The goal of each treatment is to compare the use rates of each of the different mutagenic
instruction across several factors. We can examine the effects of localization (concentrating
mutations in a single area) by comparing the HGT-Random vs the ME-Random treatments.
We can measure the effect of time-concentration (all mutations happening at once vs spread
out over time) by comparing the ME-Random and MRI treatments. We can examine the
effect of information content by comparing the HGT, HGT-Shuffle, and ME-Sampled
treatments. We can identify a basement-level for mutagenic instruction use by comparing
against the use of the entirely deleterious Die instruction. Finally, we can compare all these
factors with their environment by comparing the static vs changing environment treatments.

4.3

Results and Discussion

Our experimental results (detailed below) show that only mutagenic instructions containing useful information are elevated in response to changing environments. Intact-fragment
HGT is used most, with shuffled-fragment (HGT-Shuffle) used less, and the other, non-

65

information-bearing mutagenic instruction types used at the lowest levels. Further, we find
a positive correlation between expected fitness and mutagenic instruction use. That is, mutagenic instructions that have higher expected fitness effects are used more. Finally, we see
a strong positive correlation between the fraction of mutations from a mutagenic instruction
that provide a beneficial phenotype-altering change, and the resulting use of that instruction.

4.3.1

Other mutation types are not elevated in response to HGT

Figure 4.1: Executions of mutagenic instructions. In static environments, use of all
mutagenic instructions was strongly suppressed (Wilcoxon Rank Sum Test: Z = -22.65,
p<<0.001). In changing environment treatments, the HGT and HGT-Shuffled
instructions were used at elevated rates, compared to the other mutagenic instructions,
including the Die control (Wilcoxon Rank Sum Test: Z = 10.66, p<<0.001). The HGT
instruction (Mdn = 87389.71, CI 95% [82982.98, 96000.3]) is used more than the
HGT-Shuffle instruction (Mdn = 52220.3, CI 95% [45094.92, 57465.52]), which is used
more than HGT-Random (Mdn = 25442.98, CI 95% [22099.45, 30490.08]), indicating that
the information content of the mutation matters.

In order to compare the use of HGT against other kinds of mutations, we compared rates

66

of non-bonus HGT fragment uptake against a series of other mutation types, in both static
and changing environments (Fig 4.1). As expected, in the static environment, endogenouslycontrolled performance of all types of mutations (including HGT) is strongly suppressed
(Wilcoxon Rank Sum Test: Z = -22.65, p << 0.001). However, in harsh changing environments, use of HGT dominates the other mutation types (Wilcoxon Rank Sum Test: Z =
10.66, p << 0.001). Of particular interest is ranking of the use of the HGT-like instructions
by order of information content.
The baseline intact-HGT instruction is used most (Mdn = 87389.71, CI 95% [82982.98,
96000.3]), followed by the HGT-Shuffle instruction(Mdn = 52220.3, CI 95% [45094.92,
57465.52]), and finally followed by HGT-Random(Mdn = 25442.98, CI 95% [22099.45, 30490.08]),
where no information remains. The latter (Mdn = 25,442.98, CI 95% [22099.45, 30490.08])
performs comparably to the remaining mutation event types: ME-Sampled (Mdn = 25,798.03,
CI 95% [24335.01, 30824.09]), and ME-Random (Mdn = 28,369.85, CI 95% [22829.31,
33745.83]) (Kruskal-Wallis H 2 = 1.91, p = 0.3). The MRI and Die instructions are used
at even lower levels (Mdn = 22493.75, CI 95% [19330.91, 24818.06] and 21021.12, CI 95%
[17722.93, 23308.02]), respectively). This result is consistent with our hypothesis that the
information content of the fragment is an important predictor of the use of HGT.
Also of note is that the primary difference between the ME-Sampled and HGT-Shuffle
treatments is the localization of the mutation effect (the HGT-Shuffle fragment insertion
is applied to a single location, whereas with ME-Sampled, the instructions are scattered
randomly throughout the genome), however their use rates are significantly and substantially different (Wilcoxon Rank Sum Test: Z = 7.19, p << 0.001). This result suggests
that localization of the HGT mutation plays an important role, over and above any useful
enrichment of instructions originating in a living organism.
We speculate that this effect may also synergize with the level of modularity of a genome.
If a genome is even slightly modular, there are gradients of relatedness between loci that
decrease with physical distance. A single mutation is enough to disrupt a function. Thus, if

67

all mutations are concentrated in one region, they would be more likely to affect fewer total
functions. Thus, concentrating mutations to a single area may limit the reach of the damage,
so to speak, as opposed to hitting many different locations at once. We would expect this
effect to increase as modularity of a genome increases.

4.3.2

Mutation fitness effect correlate with mutagenic instruction use

Figure 4.2: Mutagenic instruction use vs fitness effect of mutation. The use of the
mutagenic instruction correlates with the fitness effect of that instruction (Spearman’s Rho:
rs = 0.41, p << 0.001). Because mutagenic instructions are integrated into the genomes,
those instructions that produce a beneficial fitness effect are more likely to be selected for.

Prior research has failed to show a substantial increase in endogenously-controlled mutation rates, when such an increase would be beneficial for long-term evolution, such as in
a changing environment [80]. Why should HGT mutations be different? In order to address
this question, we measured the average fitness effect of each mutation, and compared it to
that mutation’s usage rate in changing environments. We observed a positive correlation between the average fitness effect, and the use of the mutagenic instruction (Spearman’s Rho:
rs = 0.41, p << 0.001). We observed many more positive or neutral fitness effects from the
68

HGT instruction (Mdn = 0.08, CI 95% [-0.12, 0.37]) than the other mutagenic instruction
types, which exhibited primarily neutral or negative mutation effects (Mdn = -0.62, CI 95%
[-0.79, -0.52]) (Wilcoxon Rank Sum Test: Z = 7.09, p << 0.001). This result is consistent
with mutagenic instruction use being under direct selection (Fig 4.2).

4.3.3

HGT mutations increase evolved probability of beneficial phenotype switching

Figure 4.3: Fraction of beneficial phenotype-switching mutations vs mutagenic
instruction use. We observe a strong correlation between the fraction of mutations that
produce beneficial phenotype switches, and the use of the mutagenic instruction
(Spearman’s Rho: rs = 0.59, p = << 0.001). This correlation is much stronger than the
correlation between fitness effect and mutagenic instruction use. As such, this result
suggests that it is not only the absolute fitness effect that is selected for, but the
evolvability benefit.

We measured the proportion of mutations that produce beneficial phenotype changes
(Fig 4.3). In the context of a changing environment, a mutation that switches an organism’s
phenotype to match the environment should be strongly selected for. Indeed, we found that
this proportion was significantly and substantially higher for HGT mutations (Mdn = 0.041,
CI 95% [0.0291, 0.0463]) than other mutation types (Mdn = 0.004, CI 95% [0.0036, 0.0053])
69

(Wilcoxon Rank Sum Test: Z = 8.56, p << 0.001), and that there was strong correlation
between the proportion of beneficial phenotype-switching mutations and use of mutagenic
instructions (Spearman’s Rho: rs = 0.59, p = << 0.001). This correlation is much stronger
than the correlation with fitness effect, suggesting that the magnitude of the fitness effect is
less important to selection than the sign of the effect.

4.4

Conclusion

Our experiments expand on our understanding of the evolution of horizontal gene transfer,
and how it relates to other types of mutations in the context of changing environments. As
expected, we find that the fitness effects of different types of mutations vary significantly,
and that these effects predict the levels of use of that mutagenic instruction.
In particular, we observed a substantial increase in the use of the HGT instruction in
response to a changing environment. What could account for this increase? If this increase
were driven purely by an increase in the effective mutation rate, we would expect to see
a similar increase in all instructions that increase this mutation rate. Instead, we do not
observe such an increase in the use of the MRI instruction, which explicitly increases the
mutation rate in just such a way. Instead, the use of this instruction was not noticeably
different from the level of the Die instruction control.
Another possibility that might account for increase in the use of the HGT instruction
would be the benefit of limiting mutations to a single contiguous region. In this case, we
would expect to see an increase in the rate of the HGT-Random instruction over the level of
the Die control. We do observe just such an increase, but while it is statistically significant,
it is not substantial compared to the elevation we observe of the HGT instruction.
One other possibility is that there is a benefit to biasing mutation toward known-useful
instructions, such as those collected from living organisms. In this case, we would expect to
see a similar increase in use of the HGT-Shuffle instruction. We do observe a substantial
increase of this instruction over HGT-Random, however, the increase of HGT is much higher.

70

This is consistent with some benefit occurring from a biased instruction content, but does
not account for the entirety of the effect.
Thus, the most likely possibility is that it is specifically the information content of the
fragment that accounts for the extra increase of HGT over HGT-Shuffle. We found a strong
correlation between the fraction of mutations that produce a beneficial phenotype change,
and the use of that mutagenic instruction. Thus, in the context of a changing environment, where there are strong selective pressures to change your phenotype, the information
corresponding to the target environment would be very valuable.
This result is consistent with prior research that shows that populations will tend to
depress the use of non-information-rich mutagens, even though, in the long-term, higher mutation rates are likely to be optimal [80]. This result is further evidence that selection tends
to act in the short term. Thus, even though certain kinds of mutations and architectural
features may promote long-term evolvability, these features are hitchhiking on short-term
adaptive benefits. Thus, our research shows that even though evolvability may evolve, it is
not necessarily selected due to its long-term consequences.
As with the experiments described in the previous chapter, performing equivalent tests of
horizontal gene transfer in an organic system would be extremely difficult, time consuming,
and data poor. Even using the latest techniques in molecular biology, experiments comparing
the effects of different kinds of mutations, measuring their use, and isolating their fitness
effects are impossible at population-level scales [84]. Digital evolution allows us to perform
the kinds of experiments that otherwise could not be done in natural systems.

71

CHAPTER 5
CHANGING ENVIRONMENTS AND LONG TERM EVOLVABILITY

5.1

Background

For longer evolutionary timescales, beyond the limited scope of direct response to selection against an environment, evolvability is concerned with variability generation and
exploration of neutral spaces. Populations that exhibit this kind of evolvability would possess genomes with genetic architectures that more easily traverse the mutational landscape
along neutral roads and thereby discover new fitness peaks while avoiding needing to cross
fitness valleys. This kind of evolvability would allow populations to more easily colonize new
ecological niches and form new clades [2, 12].
Despite some common features, the relationship between short-term and long-term evolvability is not obvious. Architectural features and evolutionary pressures that convey shortterm evolvability may not be the same as those that confer longer-term evolvability [13]. For
example, features such as anti-robustness that promote rapid adaptation to a harsh fluctuating environment might reduce fitness in constant or benign fluctuating environments as
compared to that of wild-type invaders. Alternately, the adaptation to harsh fluctuating
environments and the resulting bottlenecks would potentially reduce diversity to the point
where large amounts of neutral novelty generation could not occur.
Finally, there is some evidence that the types of selection regimes typically used in experiments with changing environments and evolvability might preferentially favor individual
evolvability (the probability of an individual’s offspring accessing novel phenotypes) over
population-level evolvability (the probability of the population at large accessing novel phenotypes) [85, 86]. Adaptive selection, that is, selection toward a particular goal, has been
shown to depress population diversity even while it increases individual evolvability in changing environment regimes. In contrast, divergent selection, such as frequency-dependent selec-

72

tion, increases standing diversity, and thus evolvability at the population level [85]. Therefore, it is not clear that the kinds of selective pressures that promote short-term adaptation
in changing environments would, in turn, promote exploration and exploitation of novel
environments.
In this chapter, we examine how two different kinds of changing environments affect
long-term evolutionary potential. We introduce change-evolved populations from prior experiments, to an entirely new environment, where we can assess long-term variability generation in the form of new task discovery and exploration.

5.2

Methods

For the experiments described in this chapter, we evolve populations in both minimal
and rich environments. Minimal environments have few rewarded tasks, and genomes are
fixed length and limited in size. Rich environments allow rewards for many tasks, and
genome lengths are allowed to vary. For our experiments with minimal environments, we
used populations originally evolved in Chapter 2 to survey the long-term evolutionary potential of populations originating in environments with a single fluctuating task. For the rich
environment experiments, we evolved a new set of populations that originate in a more complex changing environment, with alternating sets of fluctuating tasks, and variable length
genomes.

5.2.1

Experimental Design

The goal of our experiments is to evolve populations where short-term evolutionary pressures
dominate, and then subject them to an entirely new environment, where we can measure
their long-term evolutionary potential. In order to examine the long-term dynamics and
mechanisms of evolving populations in changing environments, we performed two sets of
experiments, one set with populations evolving in a minimal environment, and the other in
a rich environment.

73

Each set is composed of five environmental treatments per set, for a total of 10 treatments.
Each treatment was divided into two stages, with the first stage focusing on short-term
adaptation to a changing environment, and the second stage on long-term evolvability via
adaptation to an expanded set of tasks.
For both set of experiments, we took populations evolved in conditions where short-term
evolvability pressures dominated, and introduced them to a completely new environment,
with an expanded set of rewarded bitwise tasks to perform: Logic-77. For the purposes of
this chapter, we refer to those tasks which were selected for in stage 1 as the basic task
set. The Logic-77 task set is a super-set of the basic task set, and includes all bitwise tasks
for which there are up to 3 inputs, including those that were initially rewarded in stage 1.
We refer to the additional tasks from Logic-77 - those which are not part of the basic tasks
set, and that we reward only in stage 2 - as the expanded task set. The total Logic-77
task set is a combination of both the basic and expanded task sets.
The first set of experiments examines the evolutionary dynamics of populations in a
minimal changing environments, with a single fluctuating task. These experiments are a
continuation of the experiments described in Chapter 2. For the second set of experiments,
we evolved populations in a rich changing environment where rather than evolving to turn a
single task on and off, we evolved populations that switch back and forth between performing two halves of the Logic-9 environment. The environment and genetic structure of the
second set of experiments derives from the experiments described in Chapter 3. However,
these populations were evolved without a working HGT instruction. The first stage of each
experiment is as described above, while the second stage takes the evolved populations and
adds the expanded task set.

5.2.1.1

Environmental Treatments

As outlined above, for each of our experiment sets, we prepared four different types of changing environment treatments, plus a static control. In the second stage of each treatment, we

74

examine how populations adapt to a brand new environment. The active changing environment treatments will still juggle the alternating direction of selective pressures associated
with cycling rewards and punishments. The quiescent treatments, in contrast, remove the
reward alternation in the second stage Thus, these treatments provide only directional selection for adaptation to the new environment. This allows us to isolate the effect of alternating
directions of selection on adaptation to a new environment.
• Static (Control): This treatment is a baseline for comparing adaptation to the expanded task set. For the first 200k updates (stage 1), we reward populations for
performing either XOR and EQU for the minimal environment (Table 5.1), or the
whole Logic-9 task set (Table 5.3). For the second 200k updates (stage 2), we add
constant rewards for the expanded task set. Each new task is rewarded at a 1.2-fold
bonus to task execution.
• Benign Changing Environment: This treatment shows the effects of a continuing
benign changing environment on adaptation to the expanded task set. For the first
200k updates (stage 1), we alternate rewarding and not rewarding populations for
performing either the EQU task (the minimal environment - Table 5.1), or we alternate
rewarding each half of the Logic-9 task set (Tables 5.3 and 3.1). For the second stage of
the experiment, starting at 200k updates, we add constant rewards for each of the new
tasks in the expanded task set, at a 1.2-fold bonus to task execution. The environmental
fluctuation from the first stage continues through the end of the experiment.
• Benign Quiescent Changing Environment: In contrast to the benign changing
environment treatment, this treatment tests the abilities of populations initially evolved
in a benign changing environment to adapt to the expanded task set, but without active
environmental fluctuation during the adaptation. For the first 200k updates (stage 1),
we alternate rewarding and not rewarding populations, as in the Benign Changing
Environment above. For the second stage of the experiment, starting at 200k updates,

75

we add constant rewards for each of the new tasks in the expanded task set, at a 1.2fold bonus to task execution. The environmental fluctuation from the first phase stops
at 200k updates, and we instead reward the tasks of the first phase (the basic task-set)
as we did in the static treatment (all constant reward).
• Harsh Changing Environment: This treatment shows the effects of a continuing
harsh changing environment on adaptation to the expanded task set. For the first 200k
updates (stage 1), we alternate rewarding and punishing populations for performing
either the EQU task (the minimal environment) (Table 5.1), or we alternate rewarding
and punishing each half of the Logic-9 task set (Tables 5.3 and 3.1). For the second
stage of the experiment, starting at 200k updates, we add constant rewards for each
of the new tasks of the expanded task set, at a 1.2-fold bonus to task execution.
The environmental fluctuation from the first phase continues through the end of the
experiment.
• Harsh Quiescent Changing Environment: In contrast to the harsh changing environment treatment, this treatment tests the abilities of populations initially evolved
in a harsh changing environment to adapt to the expanded task set, but without active
environmental fluctuation during the adaptation. For the first 200k updates (stage 1),
we alternate rewarding and punishing populations, as in the Harsh Changing Environment above. For the second stage of the experiment, starting at 200k updates, we
add constant rewards for each of the new tasks in the expanded task set, at a 1.2-fold
bonus to task execution. The environmental fluctuation from the first stage stops at
200k updates, and we instead reward the basic tasks of the first phase as we did in the
static treatment (all constant reward).

76

5.2.1.2

Set 1 - Minimal Cyclic Changing Environments

As described above, the first set of experiments consisted of four treatments, plus a control,
and each treatment was divided into two stages. In the first stage, for a duration of 200,000
updates (analogous to our earlier experiments, detailed in Chapter 2), we rewarded a pair of
two-input bitwise logical tasks: XOR and EQU. We rewarded XOR at a constant rate, with an
8-fold bonus to execution, and we alternated rewarding and punishing (or non-rewarding)
the EQU task with a reward that switches between 32-fold bonus to execution and either
0 reward for the benign treatments, or a -32-fold punishment in the harsh treatment. For
the second stage, lasting an additional 200,000 updates, we added a constant reward for
executing the expanded task set. Each task in the expanded task set was rewarded with a
constant 1.2-fold bonus to execution (20.3 ). This reward structure provided a mild selective
pressure to evolve these task. However, the benefits to performing them do not overwhelm
the existing selective pressure to continue performing the basic tasks rewarded by the original
changing or static environment.
As in Chapter 2, we held the individual genomes at a fixed length of 121 instructions,
and applied mutations after each successful replication event at a substitution probability
of 0.00075 per site. This limitation in genome length, plus the limited set of tasks initially
rewarded results in a less rich environment for evolution to occur. We configured the Avida
world to have local interactions on a toroidal grid that is 60-by-60 cells (3600 cells in total).

5.2.1.3

Set 2 - Rich Cyclic Changing Environment

The second set of experiments looked at the evolution of populations of organisms with
variable-length genomes, evolved in a richer cyclic changing environment. As in the minimal
environment experiment set, we performed four experimental treatments, plus a static control
(Table 5.3). For the first stage of the experiments, we divided the basic Logic-9 tasks into two
groups (Table 5.2) and alternated reward and punishment (or non-reward) between them.
For the control treatment, we rewarded all of the Logic-9 basic task set. For the second
77

Table 5.1: Experimental Treatments - Minimal Cyclic Changing Environment
Treatment

Changing
Env.
Type

Rewarded Tasks
Stage 1
(0-200,000 Updates)

XOR

EQU

constant
25
benign
fluctuating
0 or 25
benign
fluctuating
0 or 25
harsh
fluctuating
−25 or 25
harsh
fluctuating
−25 or 25

Control

None
(static)

constant
23

Benign

Cyclic

constant
23

Benign
Quiescent

Cyclic

constant
23

Harsh

Cyclic

constant
23

Harsh
Quiescent

Cyclic

constant
23

Stage 2
(200,000-400,000 Updates)
Expanded
Task-set
(Logic-77
XOR
EQU
minus
XOR & EQU)
constant
constant
constant
3
5
2
2
20.3
benign
constant
constant
fluctuating
23
20.3
0 or 25
constant
23

constant
25

constant
20.3

constant
23

harsh
fluctuating
−25 or 25

constant
20.3

constant
23

constant
25

constant
20.3

Four types of cyclic changing environment, plus a static control. Each treatment is split
into two stages. The first stage is a normal changing environment like those found in
Chapter 2, Table 2.1. The second stage introduces an additional set of tasks (the expanded
task set) that are rewarded at a lower rate.

stage, we introduced rewards for performing the new expanded task set tasks, either with
continuing alternating selection (CE), or switching to constant reward (Quiescent).

5.2.2

Measuring Task Discovery and Task Performance

Task discovery and task performance are important measures not only for the adaptation
of digital organisms to their local environment, but they also indicate the extent to which
populations are more or less evolvable. Populations that are more evolvable should be able
to acquire new tasks at a faster rate than less evolvable populations. If the evolvability of our
78

Table 5.2: Rich Changing Environments - Basic Task-set Rewarded Task
Groupings
Basic
Task-set
(Logic-9)

Group A

Group B

Tasks

Reward
Phase 1

Reward
Phase 2

NOT
AND
OR
NOR
EQU
NAND
ORN
ANDN
XOR

21
22
23
24
25
−21
−22
−23
−24

−21
−22
−23
−24
−25
21
22
23
24

The basic task-set (Logic-9) tasks are divided into to two groups, with one task from each
pair of tasks of equivalent complexity assigned to each group. The EQU task, which has no
complexity equivalent, is assigned to the first group. During the first phase of a cycle, we
reward the first group of tasks and punish the second group (see Reward Phase 1). During
the second phase of the cycle, we reward the second group, and punish the first group
(Reward Phase 2).

populations is affected by evolution in a changing environment, then this effect should result
in differential rates of task discovery and performance. Task discovery and performance
together describe the exploration and exploitation of the environment by a population.

5.2.2.1

Task Discovery

Task discovery represents the level of exploration of the fitness landscape. We measured task
discovery by counting the number of unique non-ephemeral tasks that have been discovered
by a population. Each task may be performed only once per organism, yielding a maximum
task count of 3600 at any given time. We define a non-ephemeral task as one that is performed
by at least than 0.1% of the population. Therefore, in order for a new task to be marked as
discovered, it must be performed by at least 4 individuals at the time of sampling.
Once a task is discovered, it may not be undiscovered; task discovery counts will always

79

Table 5.3: Experimental Treatments - Rich Cyclic Changing Environment
Treatment

Changing
Env.
Type

Rewarded Tasks
Stage 1
(0-200,000 Updates)
Basic Task-set
(Logic-9)
Groups
A&B

Control

None
(static)

Benign

Cyclic

Benign
Quiescent

Cyclic
to Static

Harsh

Cyclic

Harsh
Quiescent

Cyclic
to Static

constant
21−5
benign
fluctuating
A: 21−5 or 0
B: 21−4 or 0
benign
fluctuating
A: 21−5 or 0
B: 21−4 or 0
harsh
fluctuating
A: 21−5 or −21−5
B: 21−4 or −21−4
harsh
fluctuating
A: 21−5 or −21−5
B: 21−4 or −21−4

Stage 2
(200,000-400,000 Updates)
Expanded
Basic Task-set
Task-set
(Logic-9)
(Logic-77
Groups
minus
A&B
Logic-9)
constant
constant
21−5
20.3
benign
fluctuating
constant
A: 21−5 or 0
20.3
B: 21−4 or 0
constant
21−5

constant
20.3

harsh
fluctuating
A: 21−5 or −21−5
B: 21−4 or −21−4

constant
20.3

constant
21−5

constant
20.3

Four types of cyclic changing environment, plus a static control. Each treatment is split
into two stages. The first stage is a normal changing environment like those found in
Table 2.1. The second stage introduces an additional set of tasks (the expanded task
set) that are rewarded at a lower rate.

80

increase monotonically. We measure overall task discovery by beginning to collect unique
tasks starting at the beginning of the run. For the overall measurement, we count all possible
tasks - the entire Logic-77 task set - even though not all tasks are rewarded in the first stage
of the experiment. We also measure post-reward task discovery, where we begin counting
new tasks from the beginning of the second stage of the experiment, once we have begun
rewarding execution of the expanded task set. Task discovery can range anywhere from a
minimum of zero tasks discovered, to a maximum of 77.

5.2.2.2

Task Performance

In addition to counting the number of unique task discovered, we also measure task performance. We measure task performance by counting the total number of unique, nonephemeral tasks that a population is performing at each sampling point. This measure
represents the level of exploitation of the fitness landscape. This measure can range from
0 to a maximum of 77 task being performed by the population. This value will always be
either equal to, or smaller than the number of tasks discovered, since a population can’t
perform a task it hasn’t discovered yet.

5.3

Results and Discussion

5.3.1

Task Discovery

Task discovery is an important measure of long-term evolvability in that it quantifies the
ability of populations to explore and adapt to entirely new environments. We measured task
discovery in each of the changing environment treatments.

5.3.1.1

Benign changing environments outperform harsh environments in task
discovery

We found that once we began rewarding the expanded task set, populations evolving in harsh
changing environments discovered many fewer tasks that those evolving in benign changing
81

environments. This effect is consistent across both the minimal (Wilcoxon Rank Sum Test:
Z = 2.75, p < 0.01) and the rich environment sets (Wilcoxon Rank Sum Test: Z = 5.96, p
<< 0.001) (Figs 5.1, 5.2). We hypothesize that this effect is due to the relative differences
in the strength of selection between the harsh changing environment and the directional
selection toward the expanded task set.

Figure 5.1: Number of new expanded task set tasks discovered in post-reward in
the minimal environments. The left plot shows a time-series of the number of
non-ephemeral tasks discovered by populations by each treatment. The right plot shows
the number of tasks discovered at the end of the experiments. While the individual values
overlap their neighbors, the top and bottom-most treatments (Benign and Harsh) are
significantly different from each other (Wilcoxon Rank Sum Test: Z = 2.75, p < 0.01).

In the harsh changing environments, the selective pressure to gain or lose the fluctuating
tasks represents up to a 2 ∗ 25 -fold bonus over the course of a single cycle, whereas the
expanded task set can individually only offer a 1.2-fold bonus to execution speed. Thus,
those organisms that promptly gain or lose a fluctuating task are more likely to survive,
regardless of whether or not they have gained one of the new expanded task set tasks.

82

Figure 5.2: Number of new expanded task set tasks discovered post-reward in
rich environments. The left plot shows a time-series of the number of non-ephemeral
tasks discovered by populations in each treatment. The right plot shows the number of
tasks discovered by the end of the experiments. Overall, the number of expanded task
set tasks discovered in the rich environments (Mdn = 24.0, CI 95% [23.0, 25.0]) is
significantly lower than those found in the minimal environments (Mdn = 36.0, CI 95%
[35.0, 36.0]) (Wilcoxon Rank Sum Test: Z = -16.15, p << 0.001). However, the same
pattern holds, where the benign changing environment treatment discovers significantly
more tasks than the harsh changing environment (Wilcoxon Rank Sum Test: Z = 5.96, p
<< 0.001).

Thus pressures to gain and lose the fluctuating tasks are much stronger than the pressure to
acquire new expanded task set tasks, thereby depressing the rate at which they are found.
In contrast, the benign environment experiences a weaker strength of selection for EQU
task gain and loss, in the form of a maximum 25 -fold bonus directional selection pressure to
gain the tasks, and no direct pressure to lose the task. Thus, when compared to the harsh
treatments, the fraction of the total selective pressure for gaining new expanded tasks is
greater in the benign treatment. This increased pressure, plus the benefit of an increased
exploration rate conveyed by the benign changing environment, result in a higher overall

83

task discovery rates.
Interestingly, in the harsh quiescent treatment (HarshQuiescent) beginning in stage 2, we
saw that task exploration recovered and achieved a comparable level to the control (Wilcoxon
Rank Sum Test: Z = -0.91, p = 0.37). What could account for this recovery?
One possibility is that the introduction of the new tasks provided sufficient selective
pressure to cause the increase in the discovery rate. In this case, we would expect to see a
similar increase in task exploration in the harsh changing environment treatment (HarshCE).
Another possibility is that the alternating environment in the first part of the experiment
created a diversity disadvantage in populations in those treatments. If this were the case,
we would expect HarshQuiescent’s task discovery to initially grow more slowly than the
control, which would have suffered from no such disadvantage. Then, as diversity recovered,
we would expect to see task discovery grow at comparable rates.
Finally, there is the possibility is that the alternating selection regime was directly responsible for depressing task exploration. In this case, once we stopped alternating task
rewards, we would expect to see a significant difference in task discovery rates between the
HarshQuiescent and HarshCE treatments.
Indeed, we found that the the HarshQuiescent treatment has a much higher task discovery rate than the HarshCE treatment. This is inconsistent with the hypothesis that the
task rewards alone account for the recovery of the HarshQuiescent. Instead, this result is
consistent with the possibility of a direct negative effect from the continuing alternating
selection. We also found that there was a lag in task discovery compared to the control.
This suggests that there was, at least initially, some population-level disadvantage occurring
in the HarshQuiescent populations. We also observed that after the initially slow recovery
phase, the quiescent treatment rapidly increased its task discovery rate, and exceeded that
of the control. This is consistent with a recovery of diversity, plus, potentially some lingering
architectural advantage for finding new tasks.
Also of interest is the difference in task discovery rates between the benign environment

84

populations BenignCE and BenignQuiescent. Once the expanded task rewards are introduced, the BenignCE populations continue to be subject to a benign changing environment,
whereas the BenignQuiescent populations are only subject to directional selection toward the
evolution of the original and expanded tasks. In both environment types, the task discovery
rate for the BenignCE populations (Minimal: Mdn = 37.0, CI 95% [36.0, 38.0]; Rich: Mdn
= 29.0, CI 95% [26.0, 31.0]) are slightly higher than for BenignQuiescent (Minimal: Mdn
= 36.0, CI 95% [34.0, 38.0]; Rich: Mdn = 24.0, CI 95% [22.0, 27.0]), but the effect is not
statistically significant in the minimal environment (Rich: Wilcoxon Rank Sum Test: Z =
3.15, p < 0.01; Minimal: Wilcoxon Rank Sum Test: Z = 1.39, p = 0.16). Both, however, still
perform better than the control treatment (Minimal: Mdn = 34.5, CI 95% [32.0, 38.0]; Rich:
Mdn = 22.0, CI 95% [21.0, 25.0]), though this effect is only statistically significant between
the BenignCE and Control treatments in the rich environment (Wilcoxon Rank Sum Test:
Z = -4.33, p < 0.001). What could account for this reversal of the pattern observed between
HarshCE and HarshQuiescent?
One possibility is that some population-level diversity advantage is being conveyed by
the activity of the benign changing environment. In this case, we would expect the BenignQuiescent task discovery rates to initially closely track that of the BenignCE treatments,
and then as diversity equalized, to drop down to rates comparable to the control.
Another possibility is that the benign changing environment is directly promoting task
exploration. In this case, we would expect to see a significant difference in task discovery
rates between the BenignCE and BenignQuiescent treatments.
We observe that following the introduction of the expanded task set tasks, the BenignQuiescent treatment task rates quickly depart from the BenignCE task discovery rates.
This result is inconsistent with the hypothesis of a population diversity advantage. If anything, task discovery levels lag behind the control treatment. Thus, we find that it is most
likely that the benign changing environment is directly promoting task discovery, though the
mechanism of this promotion remains unclear.

85

5.3.1.2

Harsh changing environments drive populations across the mutational
landscape

Figure 5.3: Number of new expanded task set tasks discovered in minimal
environments, over the whole experiment. The left plot shows a time-series of all
new tasks discovered over the course of the entire run, including non-rewarded expanded
task set tasks. The right-hand plot shows the final count at the end of the run. Before we
introduce rewards for performing expanded task set tasks, the harsh changing
environment discovers far more new tasks (Mdn = 28.0, CI 95% [27.0, 30.0]) than either of
the other treatments (Mdn = 22.0, CI 95% [22.0, 23.0]) (Wilcoxon Rank Sum Test: Z =
8.61, p << 0.001). This occurs despite no reward being given for performing the
expanded task set tasks in the first part of the experiment.

In the first part of the experiments, despite the expanded task set tasks not being rewarded, both changing-environment treatments (BenignCE and HarshCE) discovered more
new tasks than the control (Minimal: Wilcoxon Rank Sum Test: Z = -5.75 and -11.15 respectively, p << 0.001; Rich: Wilcoxon Rank Sum Test: Z = -4.32 and -3.73 respectively,
p < 0.001). In the minimal environment, the harsh treatment in particular discovered substantially and significantly more expanded task set tasks than either the benign treatment
(Wilcoxon Rank Sum Test: Z = -8.0, p << 0.001) or the control, despite these tasks not
86

Figure 5.4: Number of new expanded task set tasks discovered in rich
environments, over the whole experiment. The left plot shows a time-series of all
new tasks discovered over the course of the entire run, included non-rewarded expanded
task set tasks. The right-hand plot shows the final count of tasks discovered by the end of
the run. Again, both sets of changing environments (BenignCE and HarshCE) randomly
discover more expanded task set tasks than the control treatment before rewards for
those tasks are offered (Wilcoxon Rank Sum Test: Z = -4.32 and -3.73 respectively, p <
0.001). This result suggests that the alternation of the direction of selection drives
populations to explore new regions of the fitness landscape more effectively than directional
selection alone.
being rewarded (Fig 5.3. We speculate that this effect may be due to the large phylogenetic
depth of the harsh-evolved populations, where the repeated bottlenecks drive the populations
along a kind of forced march across the mutational landscape. However, as the experiment
proceeds, and expanded task set task rewards are introduced, this effect disappears, and
task discovery rates converge (Kruskal Wallis: H(2) = 6.97, p = 0.03).

87

5.3.2

Task Performance

In additiona to task discovery, task performance is another an important measure of longterm evolvability, in that it quantifies exploitation and fixation of traits that are beneficial
in new environments. We measured task performance in each of the changing environment
treatments.

5.3.2.1

Benign changing environments outperform harsh environments in task
performance

Figure 5.5: Number of distinct tasks performed in minimal environments. The
left plot shows a time-series of the number of distinct tasks performed by the treatment
populations over time. The right-had plot shows the number of tasks performed at the end
of the experiments. The harsh changing environment treatment performs substantially and
significantly fewer tasks than any of the benign or control treatments (Wilcoxon Rank Sum
Test: Z = -11.22 and -11.15 respectively, p << 0.001). The benign treatments perform
best, but the differences are not statistically significant from the control (Kruskal Wallis:
H(2) = 2.76, p = 0.25).

Similar to task discovery, populations evolving in harsh changing environments performed

88

Figure 5.6: Number of distinct tasks performed in rich environments. The left plot
shows a time-series of the number of distinct tasks performed by the treatment populations
over time. The right-had plot shows the number of tasks performed at the end of the
experiments. Similar to the minimal environment, the harsh changing environment
treatment performs substantially and significantly fewer tasks than any of the benign or
control treatments (Wilcoxon Rank Sum Test: Z = -4.32 and -3.73 respectively, p <<
0.001). Similarly to task discovery, the rich environment performs fewer tasks overall (Mdn
= 11.0, CI 95% [10.0, 12.0]), compared to the minimal environment(Mdn = 17.0, CI 95%
[17.0, 18.0]) (Wilcoxon Rank Sum Test: Z = -9.25, p << 0.001). Interestingly, the Harsh
Quiescent treatment performs the most tasks, though this effect is only slightly significantly
different from the benign treatments (Wilcoxon Rank Sum Test: Control Z = 4.33,
HarshCE Z = -9.3, p < 0.001; BenignCE Z = 2.25, Benign Quiesce Z = 1.96, p < 0.05).

far fewer distinct tasks than either the control, or either benign populations (Wilcoxon
Rank Sum Test: Minimal: Z = -11.22 and -11.15 respectively; Rich: Z = -4.32 and -3.73
respectively, p << 0.001) (Fig 5.5 and 5.6). While both the BenignCE and BenignQuiescent
populations seemed to outperform the control, this effect was only statistically significant
in the rich environment (Wilcoxon Rank Sum Test: Z = 2.42 and 2.37 respectively, p <
0.05). In the minimal environment, the differences were not statistically significant (Kruskal
Wallis: H(2) = 2.76, p = 0.25).

89

Interestingly, in the rich environments, the HarshQuiescent treatments seemed to outperform all other environment types in task performance, though the differences between
HarshQuiescent and both benign treatments are only barely statistically significant (Wilcoxon
Rank Sum Test: Control Z = 4.33, HarshCE Z = -9.3, p < 0.001; BenignCE Z = 2.25, Benign Quiesce Z = 1.96, p < 0.05). We speculate that this effect may be due to a lingering
architectural effect of evolving in harsh changing environments. For example, because task
length increases in changing environments, these tasks are more likely to experience mutations that could change their phenotype in a variety of ways. Thus, once the pressure to limit
diversity is released, the population would be much more likely to produce a large amount
of population variation in a short time. Thus, we would expect to see a significant increase
in measures of task performance, but might also expect to see a relatively lower number of
task being performed by the entire population. Further research is needed to identify the
mechanisms responsible for this effect.

5.4

Conclusion

The relationship between short and long term evolvability is non-obvious. Architectural
features and selective pressures that promote repeated re-adaptation to a known set of environments may not be beneficial for the acquisition of entirely new adaptive traits. For
example, harsh changing environments act to depress both fitness and population diversity,
which might make these populations less effective at adaptation when introduced into a new
environment.
Indeed, our experiments show that harsh changing environments, with their strong selective pressures, suppress the ability of populations to acquire new, weakly-selected traits.
However, benign changing environments, with their milder set of selective pressures, are
able to leverage their accumulated heritage of dormant vestigial sites to rapidly respond to
selection, and acquire new tasks at a faster rate than either harsh or non-change-evolved
populations. However, despite the direct negative effects of harsh changing environments,

90

populations initially evolved in these environments are able to rapidly acquire new tasks if
alternating selection is removed. This result suggests that there are important architectural
features conveyed by these environments that are beneficial for new task acquisition.
Our results are consistent across both the minimal and rich environment types. This suggests that regardless of environmental and genomic complexity, changing environments are
important drivers of adaptation and long-term evolvability, either directly by driving populations to move across the fitness landscape, or indirectly, by conveying lingering architectural
advantages.

91

CHAPTER 6
CONCLUSION AND FUTURE DIRECTIONS

In this dissertation, we explore the evolutionary dynamics of changing environments, along
with their impact on both short and long-term evolvability. We find that changing environments promote short-term adaptation by driving populations to regions of genotype space
where more adaptive mutants are available within one or two mutational steps.
Harsh changing environments create selective pressures to switch phenotypes, rather
than selecting only for increasing fitness. These kinds of selective pressures are well suited
to promoting the evolution of information-rich mutation types like horizontal gene transfer
via transformation. HGT in particular is an excellent adaptation to harsh changing environments, where there is a strong selective pressure for phenotype switching. Indeed, we observe
that HGT is much more strongly selected for than other types of mutation operators with
similar associated mutation rates. The fragments from the environment serve as reservoirs
for dormant functionality, just as vestigial regions within genomes do, thus providing more
opportunities for mutations to produce switches between phenotypes.
In the context of long-term evolutionary potential, the benefits of changing environments
are less clear. Benign changing environments appear to perform at least, if not more efficiently, than purely directional selection at acquiring traits in a novel environment. While
benign changing environments appear to convey some architectural advantages in terms of
task discovery and performance, the effects are slight. This result may be due to the types of
selection at play in our changing environments. The selective pressures in our changing environments are largely adaptive selective pressures, rather than divergent selective pressures.
Divergent selection pressures, such as negative frequency dependence, have been shown to
outperform adaptive selection pressures in measures of population-level evolvability [85]. Our
results are consistent with these findings, and suggest that changing environments alone are
insufficient for promoting long-term population-level evolvability.
92

6.1

Limitations of Cyclic Changing Environments

Changing environments produce a set of selective pressures that speed up exploration of
genotype space, while also building reservoirs of partial functionality that may be co-opted in
the evolution of more complex structures. These features make changing environments useful
for both their exploratory power in natural evolution, and as practical tools in the Artificial
Life toolkit. Ultimately, however, as alluded to above, cyclic changing environments only
re-tread existing phenotypic ground, and though genotypic exploration can be faster than
under purely directional or stabilizing selection, the space explored remains constrained by
the type of phenotypes that are selected. Despite this constraint, however, we see that,
particularly under harsh conditions, a lot of novel genotypic ground may be explored, even
without direct selection for novelty.
Even so, there must exist methods of exploring genotype space that do not suffer from
these limitations at all. For example, perhaps repeated bottlenecking of populations could
promote faster traversal of the fitness landscape in quasi-random directions. More ambitiously, perhaps these kinds of environments could be coupled with dynamically increasing
open-ended complexity goals, or divergent selection mechanisms such as negative frequency
dependence to promote the maintenance of diversity in evolving populations.
Understanding the mechanisms by which select environmental conditions alter fitness
landscapes is vital to understanding the forces that promote evolvability and increase complexity. In particular, understanding the role of vestigial sites may help us untangle how
robustness can promote evolvability. Are these vestigial sites merely inactive remnants,
reservoirs of function, or are they part of a complex compensatory framework supporting
and buffering the expression of the phenotype? Or all of these things? Changing environments provide one view into these dynamics, but we must explore further to find other
mechanisms for exploring and exploiting genotype space.

93

6.2

Future Directions - Horizontal Gene Transfer and Long Term
Evolvability

Our work in understanding how changing environments interact with evolvability and
different kinds of mutations is obviously by no means complete. In particular, questions of
how mutational operators like horizontal gene transfer or sexual reproduction interact with
long-term evolutionary potential remain open.
In addition to our experiments characterizing the long-term evolutionary potential of
populations evolved in minimal and rich changing environments, we also subjected HGTevolved populations to the same expanded task set environments as described in Chapter 5.
Intriguingly, we found a strong negative correlation between the use of a grazing HGT bonus

Figure 6.1: Task discovery, with and without HGT grazing bonus. Populations
evolving with a grazing bonus had a strong negative correlation between task discovery and
HGT use (Spearman’s Rho: rs = -0.71, p << 0.001).

and rates of task discovery (Spearman’s Rho: rs = -0.71, p << 0.001). In contrast, we
found a much weaker and less robust correlation when no grazing bonus was given for HGT
(Spearman’s Rho: rs = -0.12, p < 0.01) (Fig 6.1). This result is surprising because we

94

would expect that an information rich mutation operator would promote the discovery of
new tasks by combining existing functionality in novel ways. However, in the case of the
grazing bonus, while HGT does use generally increases, we also observed that this increase
was negatively associated with discovery of new tasks. Why should mutation by HGT reduce
task discovery? There are several factors that may account for this counterintuitive result.
First, evolving HGT with a grazing bonus may lead to fundamentally different genetic
architectures than those found in treatments where HGT use gives no direct reward. Because
the HGT instruction is relatively simple to acquire and confers a substantial execution bonus,
those genetic architectures that use it might have evolved features that are more robust
against HGT-caused mutations, while still being able to reap the benefits of the grazing
bonus. This very robustness might then make these architectures slower to adapt to new
environments.
Another possibility is that this correlation is related to treatment use patterns, where
treatments under harsh alternating selection not only use HGT more, but also exhibit lower
amounts of task discovery. In fact, this is the pattern that appears in the non-bonus HGT
treatments. However, in the grazing bonus treatments, we observed an overall increase in
the use of HGT across all treatment types, with no associated increase in task discovery.
This relationship would therefore suggest that HGT does not itself have a significant effect
on task discovery at all, and that instead this correlation is related purely to the fact that
HGT levels increase due to a bonus, and thus have no strong effect on task discovery one way
or another. If so, then this might also provide evidence for the possibility of architectural
adaptation to HGT with a grazing bonus.
This result underlines how much we have yet to learn about how changing environments
interact with different kinds of mutations that affect genetic architectures in different ways.
Evolvability remains a complex and rich topic of study, and there is still much to learn.

95

APPENDICES

96

APPENDIX A
EXPERIMENTALLY DERIVING PARAMETERS FOR CHANGING
ENVIRONMENT CYCLE LENGTHS

Cyclic changing environments have predictable cycles and thus have consistent periods of
time that allow adaptation and fixation of traits. Too short a cycle, and traits are not able
to fix. Too long a cycle and traits that are no longer selected for in one phase, but are useful
in the other, become increasingly vulnerable to loss through genetic drift.
In order to identify an optical cycle time to support our experiments, we surveyed a series
of cycle lengths, and measured task performance rates in both benign and harsh changing
environments (Fig A.1).
We found that, of our surveyed values, a cycle time of 1000 updates (roughly 30 generations) both provided adequate time for traits to evolve and fix (and thus be performed by the
entire population), but also not enough time for drift to destroy alternate-phase traits, thus
minimizing the time required to re-evolve the task. Cycle times that were too short never
acquired and fixed adaptive traits in the entire population, while as cycles got longer, the
fluctuating tasks would take much longer to re-evolve, indicating that the populations had
drifted away from the regions of the mutational landscape that contained them (Fig A.2).

97

Figure A.1: Survey of task execution for a series of cycle-lengths. The top plots count
the number of executions of the EQU instruction in the control treatment. Each organism
only receives a bonus for executing EQU once. The seed population performed EQU, and it
is never lost. The middle and lower plots show EQU execution in benign and harsh
changing environments, respectively. Each line describes a different cycle-length treatment.
The longer cycle lengths correspond with longer times to lose and regain EQU. Only
treatments with cycles longer than 1000 updates achieve fixation, at a maximum value of
3600 EQU executions.

98

Figure A.2: Survey of task time to EQU fixation for harsh changing environments
for a series of cycle-lengths. Only those treatments where EQU fixation occurs (cycle
lengths greater than 1000 updates), were surveyed. The longer the cycle time, the longer it
takes for fixation to occur.

99

APPENDIX B
EXPERIMENTALLY DERIVING PARAMETERS FOR HGT
RECOMBINATION PROBABILITY AND BONUS LEVELS

B.1

Recombination Probability Sweep

Figure B.1: Survey of HGT use for a series of recombination probabilities in a
static environment. The left-hand figure shows a time-series of fragment uptakes, with and
without bonus values. The right-hand plot shows the final uptake counts at the end of the
runs. Those values at a recombination probability of less than 0.1 are not meaningfully
depressed as compared to the bonus values. Values greater than 0.1 showed more
suppression, and ultimately reached mutational melt-downs with few surviving populations.

In nature, the probability of horizontal gene transfer occurring varies wildly by species,
environmental conditions, and mechanism of action. In order to identify an optimal probability of HGT uptake resulting in recombination, we performed a series of experiments

100

comparing different probabilities, coupled with a pair of basic grazing bonuses. Our initial
grazing bonuses were based on the reward given for a similarly complex task - NAND - which
only requires a single instruction, plus an IO instruction, to implement. NAND is typically
rewarded with a bonus of 21 to execution speed. Thus, performing HGT, which only requires
a single instruction - HGT-Uptake, was rewarded similarly.
The goal was to identify a probability of recombination that would, without a grazing
bonus, result in a reduced HGT uptake level as compared to with a grazing bonus. Further,
we wanted the recombination probability to not be so high as to result in mutational meltdown, thus frequently killing the populations. We found that a level of 0.1 probability met
these characteristics. That is, recombination probabilities of less than 0.1 had similar HGT
expression rates with and without a bonus, while probabilities above 0.1 tended to have
many many fewer surviving populations (Fig B.1).

B.2

Bonus Sweep

Figure B.2: Survey of HGT use for a series of bonus values in a static environment.
The left plot shows a time-series of HGT fragment uptakes, while the right-hand plot
shows final uptake values at the end of the experimental runs. With recombination
probability at 0.1, bonus values of zero depress HGT use. A bonus of 0.1 increases uptake
dramatically, indicating a very high use. Bonuses at 0.5 and greater show diminishing
returns in increasing HGT use.

101

Similarly, in nature, the amount of nutritive benefit derived from taking up DNA fragments from the environment is difficult to quantify. In Avida, when populations are presented
with instructions that provide a direct boost to execution speed, use of these instructions
is strongly selected for. Populations rapidly fill their genomes with these instructions, to
the exclusion of virtually all else. Thus, our goal in selecting potential bonus levels lay in
finding a range of minimal value that would balance the presumably deleterious effects of the
HGT uptake instruction, without completely overwhelming the balance of selective pressures
we wished to apply to our experiments. As expected, and coupled with the recombination
probability above, values around 21 seemed to perform the best (Fig B.2). Above a value of
22 , there seem to be diminishing returns.

B.3

Comparable Bonus Values

Figure B.3: Survey of HGT use, across a series of comparable bonus values in a
static environment, with a recombination probability of 0.1. This figure shows a sweep of
bonus values, demonstrating a largely linear progression of increasing HGT use as bonus
values increase, thus balancing negative effects caused by recombination in a static
environment.

For later experiments, in order to identify the relationship between HGT uptakes prompted
by grazing bonus, and uptakes prompted by evolvability pressures in changing environments,
102

we surveyed a series of bonuses to find a value that, in a static environment, would yield
an HGT fragment uptake rate similar to that found in changing environments without a
grazing bonus. We found that a bonus value of 20.8 yielded similar HGT fragment uptake
levels (Fig B.3).

103

APPENDIX C
CHANGING ENVIRONMENTS ELEVATE ALL INSTRUCTION USE DUE
TO REPEATED BOTTLENECKS

Figure C.1: Die instruction executions across a series of artificial bottlenecks. We
observe that the Die instruction is elevated in a harsh changing environment as compared
to a static environment. We apply a pair of bottlenecking procedures. In the ”Serial
Transfer” treatments, we kill the population, but select increasingly fewer organisms to
seed from. As the number of seed organisms become fewer, the expression of the Die
instruction increases. This is consistent with founder effects being likely the cause of
increasing expression of strongly deleterious traits in harsh changing environments.

In Chapter 4, we observed that the Die instruction control is elevated in the changing
environments treatment, as compared to the control treatment. This counterintuitive effect
is due to the repeated bottlenecking of the populations subjected to the harsh changing
environment (Fig C.1). We observe that under increasingly harsh bottlenecks, rates of
execution of the Die instruction increase to levels comparable to what is seen in the changing
104

environment treatments. Because not all instructions contained in an organism’s genome are
necessarily executed (due to genetic flow-control structures), it is possible for any instruction
to remain dormant. Thus, not all organisms with the ”die” instruction in their genome will
express it. Thus, the selective pressures of the environmental change may ultimately outweigh
that of the Die instruction if it were initially dormant in a genome that survived a harsh
environmental change and reproduced.

105

BIBLIOGRAPHY

106

BIBLIOGRAPHY

[1] John Maynard Smith and Eors Szathmary. The major evolutionary transitions. Nature,
374(6519):227–32, March 1995.
[2] Marc Kirschner and John Gerhart. Evolvability. Proceedings of the National Academy
of Sciences, 95(15):8420–8427, 1998.
[3] Richard Dawkins. 13 - The evolution of evolvability. In Sanjeev Kumar and Peter J.
Bentley, editors, On Growth, Form and Computers, pages 239–255. Academic Press,
London, 2003.
[4] Lee Altenberg. The evolution of evolvability in genetic programming. Advances in
genetic programming, 3:47–74, 1994.
[5] Ronald Aylmer Fisher. The genetical theory of natural selection. Clarendon Press,
Oxford, 1930.
[6] David Houle. Comparing Evolvability and Variability of Quantitative Traits. Genetics,
130(1):195–204, 1992.
[7] Terry Van Belle and David H. Ackley. Code Factoring And The Evolution Of Evolvability. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO
’02, pages 1383–1390, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers
Inc.
[8] Gunter P. Wagner and Lee Altenberg. Perspective: complex adaptations and the evolution of evolvability. Evolution, pages 967–976, 1996.
[9] Andreas Wagner. Robustness, evolvability, and neutrality. FEBS letters, 579(8):1772–
1778, 2005.
[10] Hiroaki Kitano. Biological robustness. Nature Reviews Genetics, 5(11):826–837, November 2004.
[11] P. Alberch. From genes to phenotype: dynamical systems and evolvability. Genetica,
84(1):5–11, 1991.
[12] J. F. Y Brookfield. Evolution: The evolvability enigma. Current Biology, 11(3):R106–
R108, February 2001.
[13] Massimo Pigliucci. Is evolvability evolvable?
2008.

Nature Reviews Genetics, 9(1):75–82,

[14] Samir Okasha. Evolution and the Levels of Selection, volume 16. Clarendon Press
Oxford, 2006.

107

[15] Stephen Jay Gould and Richard C. Lewontin. The spandrels of San Marco and the
Panglossian paradigm: a critique of the adaptationist programme. Proceedings of the
Royal Society of London B: Biological Sciences, 205(1161):581–598, 1979.
[16] Sewall Wright. Evolution in Mendelian Populations. Genetics, 16(2):97–159, March
1931.
[17] Nadav Kashtan, Elad Noor, and Uri Alon. Varying environments can speed up evolution.
Proceedings of the National Academy of Sciences, 104(34):13711–13716, August 2007.
[18] Brian D. Connelly, Katherine J. Dickinson, Sarah P. Hammarlund, and Benjamin Kerr.
Negative niche construction favors the evolution of cooperation. Evolutionary Ecology,
pages 1–17, October 2015.
[19] Barbara McClintock. The significance of responses of the genome to challenge. Singapore: World Scientific Pub. Co, 1993.
[20] Anton Crombach and Paulien Hogeweg. Evolution of Evolvability in Gene Regulatory
Networks. PLOS Comput Biol, 4(7):e1000112, July 2008.
[21] Claus O. Wilke, Jia Lan Wang, Charles Ofria, Richard E. Lenski, and Christoph Adami.
Evolution of digital organisms at high mutation rates leads to survival of the flattest.
Nature, 412(6844):331–3, July 2001.
[22] Matthew R. Goddard, H. Charles J. Godfray, and Austin Burt. Sex increases the efficacy
of natural selection in experimental yeast populations. Nature, 434(7033):636+, March
2005. 636.
[23] Thomas F. Hansen and David Houle. Measuring and comparing evolvability and constraint in multivariate characters. Journal of evolutionary biology, 21(5):1201–1219,
2008.
[24] Trevor Price and Dolph Schluter. On the Low Heritability of Life-History Traits. Evolution, 45(4):853–861, 1991.
[25] Thomas F. Hansen, Christophe Plabon, and David Houle. Heritability is not Evolvability. Evolutionary Biology, 38(3):258–277, June 2011.
[26] Dusan Misevic, Charles Ofria, and Richard E Lenski. Sexual Reproduction Reshapes
the Genetic Architecture of Digital Organisms. Proceedings. Biological Sciences / The
Royal Society, 273(1585):457–464, February 2006.
[27] Gnter P. Wagner and Jianzhi Zhang. The pleiotropic structure of the genotypephenotype
map: the evolvability of complex organisms. Nature Reviews Genetics, 12(3):204–213,
2011.
[28] E. Ravasz, A.L. Somera, D.A. Mongru, Z.N. Oltvai, and A.-L. Barabasi. Hierarchical
organization of modularity in metabolic networks. (Reports). Science, 297(5586):1551+,
August 2002. 1551.

108

[29] Thomas F Hansen. Is modularity necessary for evolvability?: Remarks on the relationship between pleiotropy and evolvability. Biosystems, 69(23):83–94, May 2003.
[30] Mihaela Pavlicev and Gnter P. Wagner. A model of developmental evolution: selection,
pleiotropy and compensation. Trends in Ecology & Evolution, 27(6):316–322, June 2012.
[31] Jason G. Mezey, James M. Cheverud, and Gnter P. Wagner. Is the Genotype-Phenotype
Map Modular?: A Statistical Approach Using Mouse Quantitative Trait Loci Data.
Genetics, 156(1):305–311, September 2000.
[32] J. Arjan G. M. de Visser, Joachim Hermisson, Gnter P. Wagner, Lauren Ancel Meyers,
Homayoun Bagheri-Chaichian, Jeffrey L. Blanchard, Lin Chao, James M. Cheverud,
Santiago F. Elena, Walter Fontana, Greg Gibson, Thomas F. Hansen, David Krakauer,
Richard C. Lewontin, Charles Ofria, Sean H. Rice, George von Dassow, Andreas Wagner,
and Michael C. Whitlock. Perspective: Evolution and Detection of Genetic Robustness.
Evolution, 57(9):1959–1972, 2003.
[33] James M. Whitacre. Degeneracy: a link between evolvability, robustness and complexity
in biological systems. Theoretical Biology and Medical Modelling, 7(1):6, 2010.
[34] Andreas Wagner. Distributed robustness versus redundancy as causes of mutational
robustness. BioEssays, 27(2):176–188, February 2005.
[35] Jack E. Baldwin and Hans Krebs.
291(5814):381–382, June 1981.

The evolution of metabolic cycles.

Nature,

[36] Jrg Stelling, Uwe Sauer, Zoltan Szallasi, Francis J. Doyle III, and John Doyle. Robustness of Cellular Functions. Cell, 118(6):675–685, September 2004.
[37] Gunter P. Wagner, Mihaela Pavlicev, and James M. Cheverud. The road to modularity.
Nature Reviews Genetics, 8(12):921+, December 2007. 921.
[38] Andreas Wagner. Robustness and evolvability: a paradox resolved. Proceedings of the
Royal Society of London B: Biological Sciences, 275(1630):91–100, 2008.
[39] Charles Ofria and Christoph Adami. Evolution of genetic organization in digital organisms. In Evolution as Computation, pages 296–313. Springer, 2002.
[40] P. McKinley, B. Cheng, C. Ofria, D. Knoester, B. Beckmann, and H. Goldsby. Harnessing Digital Evolution. Computer, 41(1):54–63, January 2008.
[41] Daniel C. Dennett. Darwin’s dangerous idea. The Sciences, 35(3):34–40, 1995.
[42] Francis J. Ryan. Evolution observed. Scientific American, 189:78–82, 1953.
[43] Richard E. Lenski, Michael R. Rose, Suzanne C. Simpson, and Scott C. Tadler. Longterm experimental evolution in Escherichia coli. I. Adaptation and divergence during
2,000 generations. The American Naturalist, pages 1315–1341, 1991.

109

[44] Jennifer L. Anderson, Levi T. Morran, and Patrick C. Phillips. Outcrossing and the
Maintenance of Males within C. elegans Populations. Journal of Heredity, page esq003,
January 2010.
[45] S. C. Stearns, M. Ackermann, M. Doebeli, and M. Kaiser. Experimental evolution of
aging, growth, and reproduction in fruitflies. Proceedings of the National Academy of
Sciences, 97(7):3309–3313, March 2000.
[46] Frank Wilcoxon. Individual Comparisons by Ranking Methods. Biometrics Bulletin,
1(6):80–83, 1945.
[47] William H. Kruskal and W. Allen Wallis. Use of Ranks in One-Criterion Variance
Analysis. Journal of the American Statistical Association, 47(260):583–621, December
1952.
[48] William R. Rice. Analyzing tables of statistical tests. Evolution, 43(1):223–225, 1989.
[49] Charles Spearman. The proof and measurement of association between two things. The
American journal of psychology, 15(1):72–101, 1904.
[50] Aisha I. Khan, Duy M. Dinh, Dominique Schneider, Richard E. Lenski, and Tim F.
Cooper. Negative Epistasis Between Beneficial Mutations in an Evolving Bacterial
Population. Science, 332(6034):1193–1196, June 2011.
[51] Ivan G. Szendro, Martijn F. Schenk, Jasper Franke, Joachim Krug, and J. Arjan G.
M. de Visser. Quantitative analyses of empirical fitness landscapes. Journal of Statistical
Mechanics: Theory and Experiment, 2013(01):P01005, 2013.
[52] Daniel M. Weinreich, Nigel F. Delaney, Mark A. DePristo, and Daniel L. Hartl. Darwinian evolution can follow only very few mutational paths to fitter proteins. Science,
312(5770):111–114, 2006.
[53] Joshua R. Nahum, Peter Godfrey-Smith, Brittany N. Harding, Joseph H. Marcus, Jared
Carlson-Stevermer, and Benjamin Kerr. A tortoisehare pattern seen in adapting structured and unstructured populations suggests a rugged fitness landscape in bacteria.
Proceedings of the National Academy of Sciences, 112(24):7530–7535, June 2015.
[54] P. Merz and B. Freisleben. Fitness landscape analysis and memetic algorithms for
the quadratic assignment problem. IEEE Transactions on Evolutionary Computation,
4(4):337–352, November 2000.
[55] J. Humeau, A. Liefooghe, E.-G. Talbi, and S. Verel. ParadisEO-MO: from fitness landscape analysis to efficient local search algorithms. Journal of Heuristics, 19(6):881–915,
June 2013.
[56] Leila Kallel, Bart Naudts, and Alex Rogers. Theoretical aspects of evolutionary computing. Springer Science & Business Media, 2013.
[57] Sergey Gavrilets. Fitness landscapes and the origin of species (MPB-41). Princeton
University Press Princeton, NJ, 2004.
110

[58] Dusan Misevic, Charles Ofria, and Richard E. Lenski. Experiments with Digital Organisms on the Origin and Maintenance of Sex in Changing Environments. The Journal of
Heredity, 101(suppl 1):S46–S54, March 2010.
[59] Luis Zaman, Justin R. Meyer, Suhas Devangam, David M. Bryson, Richard E. Lenski,
and Charles Ofria. Coevolution drives the emergence of complex traits and promotes
evolvability. PLoS Biol, 12(12):e1002023, 2014.
[60] Justin R. Meyer, Devin T. Dobias, Joshua S. Weitz, Jeffrey E. Barrick, Ryan T. Quick,
and Richard E. Lenski. Repeatability and Contingency in the Evolution of a Key
Innovation in Phage Lambda. Science, 335(6067):428–432, January 2012.
[61] Guillaume Martin, Thomas Lenormand, and C. Goodnight. The fitness effect of mutations across environments: a survey in light of fitness landscape models. Evolution,
60(12):2413–2427, December 2006.
[62] Daniel J. Kvitek and Gavin Sherlock. Reciprocal Sign Epistasis between Frequently Experimentally Evolved Adaptive Mutations Causes a Rugged Fitness Landscape. PLOS
Genetics, 7(4):e1002056, April 2011.
[63] Christopher D. Bayliss, Dawn Field, and E. Richard Moxon. The simple sequence contingency loci of Haemophilus influenzae and Neisseria meningitidis. Journal of Clinical
Investigation, 107(6):657–666, March 2001.
[64] Heewook Lee, Ellen Popodi, Haixu Tang, and Patricia L. Foster. Rate and molecular spectrum of spontaneous mutations in the bacterium Escherichia coli as determined by whole-genome sequencing. Proceedings of the National Academy of Sciences,
109(41):E2774–E2783, October 2012.
[65] Peter A. Lind and Dan I. Andersson. Whole-genome mutational biases in bacteria.
Proceedings of the National Academy of Sciences, 105(46):17878–17883, November 2008.
[66] Ashley J. R. Carter, Joachim Hermisson, and Thomas F. Hansen. The role of epistatic
gene interactions in the response to selection and the evolution of evolvability. Theoretical Population Biology, 68(3):179–196, November 2005.
[67] Ines Chen and David Dubnau. DNA uptake during bacterial transformation. Nature
Reviews Microbiology, 2(3):241+, March 2004. 241.
[68] Joshua Lederberg and Edward L. Tatum. Gene recombination in Escherichia coli. Nature, 158:558, 1946.
[69] Norton D. Zinder and Joshua Lederberg. Genetic Exchange in Salmonella. Journal of
Bacteriology, 64(5):679–699, November 1952.
[70] E. S. Lennox. Transduction of linked genetic characters of the host by bacteriophage
P1. Virology, 1(2):190–206, July 1955.

111

[71] Tal Dagan, Yael Artzy-Randrup, and William Martin. Modular Networks and Cumulative Impact of Lateral Transfer in Prokaryote Genome Evolution. Proceedings of the
National Academy of Sciences of the United States of America, 105(29):10039–10044,
2008.
[72] J. E. Davies. Origins, acquisition and dissemination of antibiotic resistance determinants. Ciba Foundation Symposium, 207:15–27; discussion 27–35, 1997.
[73] Jos L. Martnez. Antibiotics and Antibiotic Resistance Genes in Natural Environments.
Science, 321(5887):365–367, 2008.
[74] Michiel Vos. Why do bacteria engage in homologous recombination? Trends in Microbiology, 17(6):226–232, June 2009.
[75] R. J. Redfield, M. R. Schrag, and A. M. Dean. The Evolution of Bacterial Transformation: Sex with Poor Relations. Genetics, 146(1):27–38, May 1997.
[76] Ralph Bock. Witnessing Genome Evolution: Experimental Reconstruction of Endosymbiotic and Horizontal Gene Transfer. Annual Review of Genetics, December 2015.
[77] Shannon M. Soucy, Jinling Huang, and Johann Peter Gogarten. Horizontal gene transfer: building the web of life. Nature Reviews Genetics, 16(8):nrg3962, July 2015.
[78] Ana Paula Jacobus and Jeferson Gross. Optimal Cloning of PCR Fragments by Homologous Recombination in Escherichia coli. PLOS ONE, 10(3):e0119221, March 2015.
[79] Sbastien Wielgoss, Jeffrey E. Barrick, Olivier Tenaillon, Michael J. Wiser, W. James
Dittmar, Stphane Cruveiller, Batrice Chane-Woon-Ming, Claudine Mdigue, Richard E.
Lenski, and Dominique Schneider. Mutation rate dynamics in a bacterial population reflect tension between adaptation and genetic load. Proceedings of the National Academy
of Sciences, 110(1):222–227, January 2013.
[80] Jeff Clune, Dusan Misevic, Charles Ofria, Richard E. Lenski, Santiago F. Elena, and
Rafael Sanjun. Natural Selection Fails to Optimize Mutation Rates for Long-Term
Adaptation on Rugged Fitness Landscapes. PLoS Comput Biol, 4(9):e1000187, 2008.
[81] Jonathan M. Solomon and Alan D. Grossman. Who’s competent and when: regulation
of natural genetic competence in bacteria. Trends in Genetics, 12(4):150–155, April
1996.
[82] Patrick Seitz and Melanie Blokesch. Cues and regulatory pathways involved in natural competence and transformation in pathogenic and environmental Gram-negative
bacteria. FEMS Microbiology Reviews, 37(3):336–363, May 2013.
[83] Laetitia Fontaine, Cline Boutry, Marie Henry de Frahan, Brigitte Delplace, Christophe
Fremaux, Philippe Horvath, Patrick Boyaval, and Pascal Hols. A Novel Pheromone
Quorum-Sensing System Controls the Development of Natural Competence in Streptococcus thermophilus and Streptococcus salivarius. Journal of Bacteriology, 192(5):1444–
1454, March 2010.
112

[84] Fen Peng, Scott Widmann, Andrea Wnsche, Kristina Duan, Katherine A. Donovan,
Renwick C. J. Dobson, Richard E. Lenski, and Tim F. Cooper. Effects of beneficial
mutations in pykF gene vary over time and across replicate populations in a long-term
experiment with bacteria. Molecular Biology and Evolution.
[85] Bryan Wilder and Kenneth Stanley. Reconciling explanations for the evolution of evolvability. Adaptive Behavior, 23(3):171–179, 2015.
[86] Joel Lehman, Bryan Wilder, and Kenneth O. Stanley. On the Critical Role of Divergent
Selection in Evolvability. Frontiers in Robotics and AI, 3, 2016.

113