What email address or phone number would you like to use to sign in to Docs.com?
If you already have an account that you use with Office or other Microsoft services, enter it here.
Or sign in with:
Signing in allows you to download and like content, and it provides the authors analytical data about your interactions with their content.
Embed code for: Coevolution Drives the Emergence of Complex Traits and Promotes Evolvability
Select a size
Coevolution Drives the Emergence of Complex Traits and Promotes Evolvability Luis Zaman1,2*¤a, Justin R. Meyer3¤b, Suhas Devangam4, David M. Bryson1, Richard E. Lenski1,5, Charles Ofria1,2* 1BEACON Center for the Study of Evolution in Action, Michigan State University, East Lansing, Michigan, United States of America, 2Department of Computer Science and Engineering, Michigan State University, East Lansing, Michigan, United States of America, 3Department of Systems Biology, Harvard Medical School, Boston, Massachusetts, United States of America, 4School of Medicine, Wayne State University, Detroit, Michigan, United States of America, 5Microbiology and Molecular Genetics, Michigan State University, East Lansing, Michigan, United States of America Abstract The evolution of complex organismal traits is obvious as a historical fact, but the underlying causes—including the role of natural selection—are contested. Gould argued that a random walk from a necessarily simple beginning would produce the appearance of increasing complexity over time. Others contend that selection, including coevolutionary arms races, can systematically push organisms toward more complex traits. Methodological challenges have largely precluded experimental tests of these hypotheses. Using the Avida platform for digital evolution, we show that coevolution of hosts and parasites greatly increases organismal complexity relative to that otherwise achieved. As parasites evolve to counter the rise of resistant hosts, parasite populations retain a genetic record of past coevolutionary states. As a consequence, hosts differentially escape by performing progressively more complex functions. We show that coevolution’s unique feedback between host and parasite frequencies is a key process in the evolution of complexity. Strikingly, the hosts evolve genomes that are also more phenotypically evolvable, similar to the phenomenon of contingency loci observed in bacterial pathogens. Because coevolution is ubiquitous in nature, our results support a general model whereby antagonistic interactions and natural selection together favor both increased complexity and evolvability. Citation: Zaman L, Meyer JR, Devangam S, Bryson DM, Lenski RE, et al. (2014) Coevolution Drives the Emergence of Complex Traits and Promotes Evolvability. PLoS Biol 12(12): e1002023. doi:10.1371/journal.pbio.1002023 Academic Editor: Laurent Keller, University of Lausanne, Switzerland Received June 3, 2014; Accepted October 31, 2014; Published December 16, 2014 Copyright: 2014 Zaman et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Data Availability: The authors confirm that all data underlying the findings are fully available without restriction. All data and configuration files are available from the Dryad Digital Repository (doi:10.5061/dryad.485qq). Funding: This work was supported by the BEACON Center for the Study of Evolution in Action (NSF Cooperative Agreement DBI-0939454), an AT&T Research Labs Fellowship to L.Z., and NSF Grant CCF-0643952 to C.O. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. Competing Interests: The authors have declared that no competing interests exist. Abbreviations: MRCA, most recent common ancestor * Email: firstname.lastname@example.org (LZ); email@example.com (CO) ¤a Current address: Department of Biology, University of Washington, Seattle, Washington, United States of America ¤b Current address: Division of Biological Sciences, UC San Diego, La Jolla, California, United States of America Introduction Life emerged on Earth some 4 billion years ago and has evolved increasingly complex traits, including intricate biochemical path- ways, elaborate developmental networks, and powerful neural architectures [1,2]. However, the processes responsible for promoting this complexity remain poorly understood [1–9]. Is adaptation by natural selection largely responsible for this complexity and, if so, what is the nature of that selection? Or is this apparent trend an artifact that reflects the initial conditions and lower bounds to complexity? Given the limitations of historical data for answering these questions, experimental evolution offers an alternative approach to explore these issues and test specific hypotheses. However, the emergence of complexity in nature is a slow process, one not readily replicated in the laboratory [8,10]; and without an objective way to measure the complexity of organismal traits [11,12], rhetorical arguments may obscure and delay empirical research on this fundamental problem. Fortunately, computational approaches have advanced beyond traditional numerical simulations, and it is now possible to test evolutionary hypotheses by running experiments with computer programs that self-replicate, mutate, compete, and evolve . In one study, Lenski and colleagues  used the Avida  system to examine the role of selection for intermediate steps along many evolutionary paths to a particularly complex trait, the EQUALS (EQU) logic function. Because Avida is computational, the authors could readily observe changes over thousands of generations; moreover, the complexity of traits could be objectively quantified as the number of building blocks (in this case, NAND instructions) required for their execution. By allowing initially identical populations to evolve in different environments, Lenski and colleagues demonstrated that the most complex traits emerged only when simpler functions were also selectively favored, which promoted the accumulation of the necessary building blocks . Here we use this system to ask whether coevolution— specifically, parasite-host interactions—can drive complexity to higher levels than would otherwise be achieved. Several authors, PLOS Biology | www.plosbiology.org 1 December 2014 | Volume 12 | Issue 12 | e1002023 including Dawkins and Krebs  and Vermeij , have proposed that coevolutionary ‘‘arms races’’ lead to increased complexity as adaptations and counter-adaptations favor more and more extreme traits . Indeed, we show that host-parasite coevolution produced substantially more complex host traits than did evolution in the absence of parasites. Moreover, we show that this complexity arose in the evolving computer programs, in part, by an unexpected process: selection for increased evolvability, which was achieved by genetic mechanisms reminiscent of so-called ‘‘contingency loci’’ that are found in many pathogenic bacteria . In Avida, both host and parasite organisms are self-replicating programs that must expend CPU cycles to execute instructions in their genomes . The genetic instruction set includes basic arithmetic and input/output operations as well as operations that allow storage and manipulation of binary numbers in temporary memory via a set of stacks. Coordinated execution of appropriate sets of instructions allows organisms to obtain resources (in the case of hosts) or infect hosts (in the case of parasites) and copy their genomes instruction-by-instruction to produce offspring. The copy- ing process occasionally introduces mutations including point mutations, insertions, and deletions that may affect the progeny’s phenotype. As in nature, most mutations are deleterious or neutral, but occasional beneficial mutations improve an organism’s ability to acquire resources, infect hosts or resist parasites, or reproduce. These benefits may enable genotypes to increase in frequency as they displace less fit conspecifics because of their faster acquisition and more efficient use of CPU cycles. Thus, populations of digital organisms, like their counterparts in nature, typically evolve to better fit their environments . Figure 1 shows a schematic overview of the relationships between hosts, functions, resources, and parasites in our experiments. Hosts obtain the resources necessary for their reproduction by performing one or more logic functions, but those functions also make the host vulnerable to infection by a parasite that can perform the same function. Thus, an infection can occur only if a particular host and parasite share at least one function, although the specific genetic encoding that a host and parasite employ to perform that function rarely, if ever, correspond at the sequence level. After a successful infection, the parasite acquires 80% of the infected host’s CPU cycles, which the parasite uses to execute and copy its own genome, while imposing a severe cost on the host. As a consequence, coevolution occurs when hosts and parasites acquire and lose functions. The experimental configuration allowed for nine different logic functions, which require varying numbers of NAND instructions to be executed with the proper inputs used for each; NAND is the only logic function available in the genetic instruction set. Although there are many potential measures of functional complexity, the Avida logic environment provides an intuitive metric, as follows. The minimum number of NAND operations required for each function’s performance is known and provides a simple, objective measure of the complexity of that function . The most complex function, EQU, requires five NAND operations, and the shortest program that can perform EQU requires nearly 20 precisely interacting instructions, although there are many longer programs that also encode EQU . In the absence of parasites, a previous study found that 23 of 50 populations evolved the ability to perform EQU when the other eight functions were rewarded with additional CPU cycles that increased with their complexity (i.e., minimum Figure 1. Hosts, parasites, functions, and resources in Avida. (A) A host organism with stacks used to store binary values, a circular genome with pointers used to execute its code, and three functions— , AND, and OR—shown in different colors. Functions vary in complexity as measured by the number of NAND gates (shown as 1, 2, and 3 logic gates within the respective colored function circuits) required to perform them. (B) These functions enable organisms to take up resources from their environment. (C) Parasites target the resource- uptake mechanisms of the hosts in this system by performing the corresponding function. Note that some parasites can perform multiple functions (shown by multiple colors) and thus infect hosts via multiple uptake systems. When a parasite infects a host, it acquires a portion of the host’s CPU cycles. Executing a single operation costs an organism a single CPU cycle. Time in these experiments is measured in ‘‘updates,’’ which corresponds to a per capita average of 30 executed CPU cycles. doi:10.1371/journal.pbio.1002023.g001 Author Summary Over billions of years, life has evolved into the extraordi- narily diverse and complex organisms that populate the Earth today. Although evolution often proceeds toward increasing complexity, more complex traits do not necessarily make organisms more fit. So when and why is greater complexity favored? One hypothesis is that antagonistic coevolution between hosts and parasites can drive the evolution of more complex traits by promoting arms races with increased defenses and counter-defenses. Here, by using populations of self-replicating host com- puter programs and parasitic programs, which steal processing power from their hosts, we demonstrated that coevolution promotes complexity and dissected how it does so. Instead of simple escalation, we found that a diversity of coevolving lineages must arise for coevolution to drive complex traits. Surprisingly, coevolution had a second effect; it promoted the evolution of more evolvable hosts. As a consequence, mutations in the evolved host genomes that confer resistance to parasites occur at high rates, which help the coevolved hosts outrun their parasites. Our experiments with an artificial system demonstrate how the naturally ubiquitous process of coevolution can promote complexity and favor evolvability. Coevolution Drives Complexity and Evolvability PLOS Biology | www.plosbiology.org 2 December 2014 | Volume 12 | Issue 12 | e1002023 Ne OT required NANDs), thus allowing essential building blocks to accumulate in the evolving genomes . Here, we test whether host-parasite coevolution can drive increased complexity without explicitly rewarding building blocks. To that end, we ran similar experiments except with coevolving parasites in one-half of the replicates and without the progressive reward structure used in the previous work. Results and Discussion Parasites Drive Greater Host Complexity Figure 2 shows that coevolution with parasites drove host populations to evolve more complex functions in order to obtain the resources necessary for their replication, without any greater reward for performing the more difficult functions. Host complexity increased in both the presence (red) and absence (blue) of parasites, but it did so much faster and reached much higher levels in the coevolution treatment (p%0.001, Mann-Whitney U=2,304). The effect of parasites on the rise of complexity is exemplified by EQU, the most complex function; the ability to perform EQU evolved in 17/50 host populations that coevolved with parasites, but in none that evolved without parasites (p%0.001, Fisher’s exact test). In a third treatment, parasites were removed at the mid-point of the runs, and the cured host populations (green) evolved substantially reduced complexity relative to the coevolution treatment (p%0.001, Mann- Whitney U=543.5), although the cured hosts retained greater complexity than those that never saw the parasites (p=0.002, Mann-Whitney U=1,703). The increased complexity relative to the ancestor observed in the absence of parasites (p%0.001, Wilcoxon signed-rank W=1,275) accords with a simple model that couples a random walk in com- plexity with a selective constraint that limits functional degradation; Gould dubbed this model the ‘‘drunkard’s walk,’’ alluding to how a patron leaving a pub eventually stumbles to the curb because the pub itself limits backward movement . In our experiments, all populations started from the same ancestral program that could perform only the simplest function, NOT, and hence they were the least complex programs able to obtain resources and reproduce. Any less complex genotypes generated by mutation could not reproduce and were thus eliminated. More complex organisms also arose by mutation; although they obtained no additional resources for performing more complex functions (and, in fact, might replicate more slowly), they nonetheless could reproduce and thereby persist. Over time, this asymmetrical constraint allowed complexity to increase, albeit slowly and to a limited extent. This explanation of complexity evolving as a ‘‘drunkard’s walk’’ does not imply that evolution as a whole operates as a random walk; instead, it only implies that complexity might follow such a pattern. The coevolutionary process clearly produced greater functional complexity in the hosts. In broad outline, this effect occurs because parasites constantly select for new host phenotypes and thereby cause host populations to explore adaptive landscapes more broadly than hosts that are evolving alone . However, it is not obvious why the effect was so large and continued for so long. Understanding the initial increase in complexity is seemingly straightforward—hosts must evolve some function other than NOT to avoid infection yet still reproduce, and all except one of the other functions have higher complexity than NOT. But this explanation alone cannot explain even the initial step, because the first new function to arise by mutation was, in the vast majority of cases, the one other function, NAND, that also requires executing only a single NAND instruction. In fact, the average complexity of the first new function was only 1.10 (1.01–1.19 95% confidence interval), and the maximum was only 2 in any case. What then might account for the large and sustained rise in complexity? One plausible explanation is an escalatory arms race that gives rise to progressively more extreme and complex adaptations [7,19,20]. For example, coevolution between cheetahs and gazelles may have favored ever-increasing speed, which was achieved by evolving more complex musculoskeletal systems. In many systems, howev- er, coevolution does not occur along a single axis, but instead involves many traits  and can lead to fluctuating frequency- dependent selection instead of an arms race . For example, such frequency-dependent fluctuations appear to dominate the interactions between Daphnia magna and its parasite Pasteuria ramosa, as determined by reviving eggs and spores from various sediment depths representing different historical states of the interaction . Escalating arms races and negative frequency-dependent cycling, in general, are the two main outcomes of host-parasite coevolution. Escalation could lead to an increase in complexity if, for example, more complex tasks provided hosts with resistance to any less complex parasites. However, there is no such task ‘‘dominance’’ in Avida. Instead, a particular parasite can infect a particular host provided they share at least one function. Given that requirement, there is no inherent reason that escalation must occur [24,25]—for example, the host and parasite populations could cycle repeatedly between two states—and so we can reject the arms-race hypothesis as a sufficient explanation for the emergence of more complex traits in hosts that coevolved with parasites. Nonetheless, it is important to note that frequency- dependence and escalation are not mutually exclusive processes. Parasites Retain ‘‘Memory’’ of Previous Hosts How could negative frequency-dependence drive a sustained increase in host complexity rather than producing simple cycles? One possible explanation is that parasites maintain a ‘‘memory’’ of Figure 2. Parasites promote the evolution of host complexity. Complexity was measured as the minimum number of NAND instructions that must be executed by a host to perform its most complex logic function, averaged over all individuals in a population. The blue trajectory shows the grand mean complexity across 50 replicate populations (i.e., runs) that evolved in the absence of parasites. The red trajectory shows the corresponding values for 50 host populations that coevolved with parasites. In 12 runs, the parasites went extinct, in all but one case after 22,000 updates and after the hosts had evolved either the XOR (complexity 4) or EQU (complexity 5) function. The green trajectory shows mean values for the same 50 parasite populations, except here they were ‘‘cured’’ by experimentally eliminating the parasites after 250,000 updates. All populations started with a single host genotype that performs only the NOT function. Updates are arbitrary Avida time units (see Materials and Methods). Error bars are 62 standard errors of the mean (SEM). doi:10.1371/journal.pbio.1002023.g002 Coevolution Drives Complexity and Evolvability PLOS Biology | www.plosbiology.org 3 December 2014 | Volume 12 | Issue 12 | e1002023 previously encountered host states. If so, then hosts can escape infection only by evolving in a previously unexplored direction—in the Avida system, by evolving an entirely new and therefore usually more complex function to acquire resources, rather than recycling one that was previously discarded after it was targeted by the parasite. The simplest way to achieve such memory is if a para- site population evolves generalist phenotypes that can infect mul- tiple hosts, including types no longer common in the community. Indeed, the coexistence of multiple host types maintained by negative frequency-dependent selection would favor parasites with broad host-ranges. To examine whether this population-genetic memory existed, we quantified the average number of functions that parasites could perform. Consistent with the memory hypoth- esis, parasites evolved to become generalists that often performed four or five functions and thereby could infect several different host types (Figure 3). By contrast, we expect the hosts to evolve primarily as specialists because an individual needs to perform only one function to obtain resources, and performing multiple functions makes it vulnerable to a broader range of parasites. Indeed, most hosts performed only a single function (Figure 3), although that function became much more complex over time (Figure 2). To verify that the parasite’s population-genetic memory drove the evolution of host complexity, we performed another set of coevolution experiments using a ‘‘challenge’’ design. This design is analogous to a microbiological approach in which bacteria are challenged with phage, a single resistant mutant is isolated, the phage are then challenged with the resistant host, a single host- range mutant is isolated that can overcome the resistance, and the cycle is repeated . Using this design, diversity is lost because only individual mutants are retained at each step, and the advan- tage to the parasite of retaining a broad host-range (i.e., memory of prior hosts) is reduced or eliminated. Therefore, if the parasite’s population-genetic memory drove the evolution of host complexity in the original coevolution treatment (Figure 2), then we expect hosts to achieve reduced complexity under the challenge regime. Indeed, the resulting host complexity was much lower in the chal- lenge treatment than with coevolution (p%0.001, Mann-Whitney U=2,373); in fact, the challenge treatment was indistinguishable from the populations that had evolved without parasites (p=0.43, Mann-Whitney U=1,298). We can form an intuitive understanding of the parasite’s population-genetic memory and its effects on the evolution of complexity using the imagery of an adaptive landscape. Consider the case where increasing complexity is disadvantageous because performing more complex functions requires more resources than performing simpler tasks. In the absence of parasites, hosts will evolve the simplest viable functions (Figure 4A). However, when this host is targeted by parasites, the landscape is deformed, creating a new peak at a slightly more complex task (Figure 4B). As coevolution continues, additional hosts and parasites will evolve and a diverse set may be maintained through negative frequency- dependent selection. This community further depresses the landscape, thus moving the peak toward even higher levels of complexity (Figure 4C and 4D). To evaluate whether our experi- ments supported this intuitive model, we measured the proportion of parasites unable to infect hosts performing each one of the nine logic functions on its own. That proportion represents a critical fitness component of the host because it reflects the host’s ability to resist infections by the parasites present in its environment. Figure 4E–4H shows the empirical relationship between average host fitness (i.e., resistance) and the complexity of the task performed over evolutionary time. In support of our population-genetic memory hypothesis, the fitness peak shifted strikingly toward higher levels of complexity as coevolution progressed. Thus, the diversity of parasites—with their individually and collectively broad host- ranges—sustained a memory of previously evolved host phenotypes and generated an adaptive landscape for the host that favored increasingly complex tasks. Effects of Breaking the Coevolutionary Feedback To test whether the fitness landscape shaped by a coevolved population of parasites was sufficient to drive the evolution of complexity observed in our original coevolution treatment, we per- formed a new treatment in which the parasite population began with genotypes ‘‘frozen’’ at the frequency they occurred within each original replicate at 250,000 updates (the halfway point, Figure 3. Parasites evolve generalist strategies while hosts remain specialists. The purple trajectory shows the average number of different functions performed by individual parasites across 50 replicates of the coevolution treatment. In 12 cases, the parasite population eventually went extinct, and so the number of replicates declines to 38 over time. The black trajectory shows the corresponding average for individual hosts; host populations were excluded from the average after the corresponding parasite populations had gone extinct. Error bars are 62 standard errors of the mean (SEM). doi:10.1371/journal.pbio.1002023.g003 Coevolution Drives Complexity and Evolvability PLOS Biology | www.plosbiology.org 4 December 2014 | Volume 12 | Issue 12 | e1002023 when the majority of host complexity and parasite diversity had evolved), but further evolution of the parasite was precluded. To maintain constant frequencies of the parasite genotypes, each newly reproduced parasite was assigned a random genotype from the 250,000-update set. After 500,000 updates in this complex- but-static environment of frozen parasite frequencies, hosts evolved significantly higher complexity than in the treatment without parasites (p=0.003, Mann-Whitney U=1,684). However, the hosts confronted with the complex-but-static parasite popula- tions did not reach as high a level of complexity as when the parasites coevolved (p%0.001, Mann-Whitney U=1,946) (Fig- ure 5). This disparity may indicate an effect of fluctuating environments, such that dynamic parasite environments favor increased host complexity more than complex-but-static parasite environments. To test this hypothesis, we then allowed hosts to evolve in environments where we ‘‘replayed’’ the changing para- site genotype frequencies over time from the coevolution treat- ment, but where these parasite genotypes did not respond to the host evolution that was occurring within any particular replicate. Again, the host populations that evolved in this replay treatment achieved significantly greater complexity than those that evolved without the parasites (p=0.034, Mann-Whitney U=1,529), but the hosts in the replay treatment still did not reach as high levels of complexity as the coevolved hosts (p%0.001, Mann-Whitney U=1,908) (Figure 5). Thus, coevolved parasites—whether constant (frozen) or vary- ing over time (replayed)—favored the evolution of hosts with more complex functions than hosts that evolved without parasites at all. Nonetheless, the hosts under these treatments failed to evolve the highest level of complexity, which they achieved with coevolving parasites. Coevolution involves reciprocal changes in which the host population influences how the parasite population responds, both ecologically and evolutionarily, and vice versa. Although the parasite population was diverse in both the frozen and replayed treatments, and while it varied in time in the latter treatment, the evolution of the parasite population was decoupled from the evolutionary changes that occurred in the host population. Taken together, these experiments thus indicate that the special push- and-pull of coevolution played a major role in the evolution of host complexity. They also imply a more dynamic view of population- genetic memory, one in which negative frequency-dependence constantly tunes the parasite population in response to host evolu- tion. Without coevolutionary reciprocity, the interactions between host and parasite populations are dissonant and population-genetic memory is ineffective. Figure 4. Effects of parasites on the host’s adaptive landscape. (A) Assuming that unnecessary complexity is costly in the absence of any direct benefit, the fitness peak corresponds to the simplest host phenotype. (B) Once parasites are introduced, the landscape is deformed and selection favors a more complex host phenotype. (C, D) As coevolution continues, the parasites maintain a population-genetic memory of host phenotypes, which pushes the fitness peak toward higher and higher levels of complexity. (E–H) In the coevolution runs, we quantified the effect of parasites on the host adaptive landscape as the proportion of parasites that were unable to infect hosts performing each of the nine logic functions. doi:10.1371/journal.pbio.1002023.g004 Figure 5. Frozen and replayed parasite genotypes fail to recapitulate the level of complexity seen in the coevolution treatment. Host complexity was measured as in Figure 2, and the coevolved (red) and evolved-without-parasites (blue) treatments are shown as before. The grey trajectory indicates the mean level of host complexity that evolved when parasite genotype frequencies were frozen at the values observed after 250,000 updates of coevolution. The orange trajectory shows the level of complexity that hosts evolved in the replay treatment, where they faced changing, but not coevolving, parasite populations. In this treatment, the parasite genotype frequencies were set to the levels observed during coevolution runs at 1,000-update intervals. The parasites went extinct before 250,000 updates in one of the coevolution replicates, and so the frozen treatment started with 49 replicates. In three of the 49 replicates of the frozen treatment, the hosts overcame the parasites and drove them extinct. In the replay treatment, a total of 30 host populations drove the replayed parasites extinct (including the 12 that went extinct during coevolution). Error bars are 62 standard errors of the mean (SEM). doi:10.1371/journal.pbio.1002023.g005 Coevolution Drives Complexity and Evolvability PLOS Biology | www.plosbiology.org 5 December 2014 | Volume 12 | Issue 12 | e1002023 Effects of Starting Condition on Evolved Complexity We started the previous experiments with hosts and parasites capable of performing only the simplest logic functions in order to understand how coevolution might drive the emergence of complex functions from simpler ones. However, we can also ask whether coevolution would sustain the greater functional com- plexity if the experiments began with hosts and parasites that could perform the most complex function, EQU. Indeed, coevolution maintains much higher complexity than evolution alone from this alternative starting point (Figure 6). In these runs, host complexity initially declined rapidly when the parasites were present because the hosts readily escaped by performing new, simpler, tasks. However, as the hosts exhausted the simple tasks that were easily evolved, their complexity leveled off at a higher value than without parasites (p%0.001, Mann-Whitney U=2,305) (Figure 6). Al- though the average complexity across populations never dropped below ,3, genotypes within the host populations explored the simplest functions (Figure S1). In all but one population, the frequency of hosts that performed only the simplest tasks tran- siently exceeded 10%. The apparent equilibrium levels of host complexity with and without coevolving parasites were evidently the same whether the experiments began at low or high comple- xity (compare Figures 2 and 6). Effects of Coevolving Parasites on Host Phylogeny Coevolution with parasites also had profound effects on the phylogenetic structure of host populations and on the phenotypic evolvability of host genomes. With respect to phylogenies, the frequency-dependent nature of host-parasite interactions promotes not only greater diversity at any given moment but also deeper branches that reflect the preservation of diversity through time. In Avida, we can track genealogies precisely and thus construct exact phylogenetic trees, avoiding uncertainty about historical states and branch lengths. Figure 7 shows representative trees for host populations that evolved in the presence and absence of parasites, and they differ strikingly in their coalescence profiles. To formalize this difference, we calculated the time since the most recent common ancestor (MRCA) for all 50 host populations in the coevolution and evolution-without-parasites treatments (Figure 8). The MRCA in coevolved host populations usually arose soon after the experiment began (median 3% of the total elapsed time), whereas the MRCA in the absence of parasites typically dated to well after the midpoint (median 70%), and this difference is highly significant (p%0.001, Mann-Whitney U=1,742). Thus, coevolution not only affects the outcome of adaptation, but also fundamentally changes how those outcomes are reached. Coevolutionwas similarly found to increase the rate of adaptation when embedded in multispecies networks of mutualists . Although the systems and form of interactions are different, their similar results suggest the important role reciprocity plays in evolving systems. Effects of Coevolving Parasites on Host Evolvability Previous research using Avida showed that different treatments could drive populations into qualitatively different regions of the fitness landscape; specifically, populations that experienced higher mutation rates evolved onto lower but flatter regions of genotypic space than populations that evolved at lower mutation rates, a phenomenon dubbed ‘‘survival of the flattest’’ . Here we examine whether coevolution with parasites produced host genomes that were more evolvable with respect to escaping infections. To that end, we mapped phenotypic changes onto every possible one- step point mutation for the most common host genotype from all evolved and coevolved populations at the end of the experiment. Several types of phenotypic changes are possible including the gain of a function, the loss of a function, or switching which function is performed without changing the total number of functions performed. Mutations in the last category are of particular interest because, in the presence of parasites, the ability to switch functions without requiring intermediate steps (adding a new function before Figure 6. Higher levels of host complexity are also maintained with coevolving parasites when starting from complex ances- tors. As in Figure 2, complexity was measured as the minimum number of NAND instructions that must be executed by a host to perform its most complex logic function, averaged over all individuals in a population. The blue trajectory shows the grand mean complexity across 50 replicate populations that evolved in the absence of parasites. The red trajectory shows the corresponding values for 50 host populations that coevolved with parasites. In nine coevolution runs, the parasites went extinct. All populations started with a single host genotype that performed only the EQU function, the most complex task available to them. Error bars are 62 standard errors of the mean (SEM). doi:10.1371/journal.pbio.1002023.g006 Figure 7. Effect of coevolving parasites on host phylogenies. Representative phylogenies for hosts that evolved in the (A) presence and (B) absence of parasites. The branch leading to the original ancestor is too short to be seen in (A). The phylogenies show all of the host genotypes present at the end of the run, and the phylogenies are known exactly in this system. doi:10.1371/journal.pbio.1002023.g007 Coevolution Drives Complexity and Evolvability PLOS Biology | www.plosbiology.org 6 December 2014 | Volume 12 | Issue 12 | e1002023 losing the old one) could be adaptive. That is, more evolvable hosts would be able to change phenotypes faster and could thereby escape coevolving parasites more readily. While selection does not directly favor hosts with more evolvable genotypes, they are more likely to produce surviving lineages when coevolving with parasites; thus, second-order selection could drive the evolution of evolvability. In strong support of this hypothesis, function-switching mutations were .10-fold more common in hosts that evolved with parasites than in hosts that evolved without parasites (p%0.001, Mann-Whitney U=2,338) (Figure 9). To evaluate whether this effect might some- how merely reflect the more complex tasks typically performed by coevolved hosts, we analyzed pairs of genotypes from the coevolved and evolved host populations that perform identical sets of tasks. The coevolved hosts were still significantly more evolvable than their paired evolved host (P%0.001, Wilcoxon signed-rank W=112,616.5) (Figure 10), although the frequency of task-switch- ing mutations tended to be lower in both treatments after this pairing procedure. Thus, coevolution drove host populations to occupy more evolvable regions of the adaptive landscape. Taken together, our experiments show that parasites pushed hosts to levels of functional complexity that were well beyond what they achieved by random walks (Figure 2). This complexity resulted from population-level processes [29–31], in which frequency- dependent interactions sustained generalist parasites (Figure 3) that were supported by phenotypically and phylogenetically diverse hosts (Figures 7 and 8). If population-level effects were eliminated, as in the challenge experiments, then host complexity remained low. Moreover, if the coevolutionary feedback between hosts and para- sites was broken by freezing or replaying parasite genotypes, then hosts did not evolve such complex tasks as when parasite popula- tions could respond to the changing host population (Figures 4 and 5). Although the form of interactions between the hosts, their resources, and parasites in our study system (Figure 1) strongly constrained host evolution (e.g., hosts performing multiple functions were more broadly susceptible to parasites and rarely observed), hosts nevertheless overcame these limitations by becoming more evolvable (Figure 9). In particular, host genomes evolved such that a much larger proportion of mutations caused a switch from one resource-acquisition function to another, thereby allowing hosts to escape, in a single step, parasites that targeted the first function. These results—from an unusual but highly tractable system—add to growing evidence from experiments and theory that coevolutionary processes promote biological diversity, new functions, and evolva- bility [16,17,20–25,29–35]. Figure 8. Effect of coevolution on coalescence times in host phylogenies. The data are shown as box plots and smoothed frequency distributions for the times of origin of the MRCA in 38 host populations that coevolved with parasites (excluding the 12 runs where the parasites went extinct) and 50 populations that evolved without parasites. The MRCAs arose significantly earlier in the coevolution treatment. The tail of the distribution for the coevolution treatment is more pronounced if we include the host populations where the parasites went extinct, but the difference remains highly significant (p%0.001, Mann-Whitney U=1,859). Box hinges depict first and third quartiles and whiskers extend 1.56 interquartile range (IQR) out from their corresponding hinge. doi:10.1371/journal.pbio.1002023.g008 Figure 9. Proportion of point mutations in host genomes that switch functions without changing the number of functions performed. The data are shown as box plots and smoothed frequency distributions. Proportions were obtained by testing all possible one- step point mutations in the genetic background of the most abundant host genotype at the end of all 50 runs with and without parasites. Box hinges depict first and third quartiles and whiskers extend 1.56inter- quartile range (IQR) out from their corresponding hinge. doi:10.1371/journal.pbio.1002023.g009 Figure 10. Proportion of point mutations that switch functions without changing the number of tasks performed in paired genotypes, where each pair includes hosts from the coevolu- tion and evolution treatments that perform identical sets of tasks. Proportions were obtained by testing all possible one-step point mutations in each genetic background. Box hinges depict first and third quartiles and whiskers extend 1.56interquartile range (IQR) out from their corresponding hinge. doi:10.1371/journal.pbio.1002023.g010 Coevolution Drives Complexity and Evolvability PLOS Biology | www.plosbiology.org 7 December 2014 | Volume 12 | Issue 12 | e1002023 Materials and Methods Evolution Experiments All experiments were performed using the Avida 2.13.0 software, which is available without cost (http://avida.devosoft. org/). Configuration files with the parameter settings used and data files have been deposited into the Dryad Repository: http:// dx.doi.org/10.5061/dryad.485qq . Host and parasite popula- tions lived in a well-mixed chemostat-like environment, with a single type of resource entering at a constant rate. Hosts obtained resources required for replication by performing any of nine distinct one- and two-input logic functions, provided there were resources available in the environment. A parasite could infect a host if they performed at least one function in common, and an infecting parasite then acquired 80% of its host’s energy (CPU cycles) . The ancestral hosts and parasites could perform only NOT, one of the two simplest functions. We initially monitored evolution under two main treatments, each with 50-fold replica- tion: host organisms evolved alone in one treatment, and they coevolved with parasites in the other. Each replicate started with a different numerical seed, and the resulting sequence of pseudo- random numbers influenced mutations, parasite-host encounters, and other probabilistic events. The parasites went extinct in 12 coevolution runs; except where otherwise noted, we included those runs in our analyses. In a third treatment, the parasites were experimentally removed halfway through each run, with the first half being identical to a run in the coevolution treatment (i.e., using the same initial seed). All runs lasted for 500,000 updates; an update is an absolute time unit in Avida equal to the execution, on average, of 30 instructions per individual host organism. Generation times for the ancestral host and parasite genotypes were 63 and 23 updates, respectively, although generationtimes changedas genomes evolved. Each host population began with one individual; the carrying capacity was 14,400 in the absence of parasites. In the coevolution treatment, 400 parasites were introduced after 2,000 updates; only a single parasite could infect an individual host. Mutation rates were 0.25 and 0.5 per genome replication for the ancestral host and parasite, respectively, of which 90% were point mutations and 5% each were insertions or deletions of single instructions. Per-site mutation rates were constant, so total genomic rates varied with changes in genome length. Mutations occurred at random with respect to genome position. Challenge Experiment To eliminate all population-level interactions in both species, we screened individual hosts and parasites for defenses and counter- defenses, rather than using evolving populations. Starting from the same ancestral host, we generated thousands of individuals using the same mutation regime as in the evolution experiments, and we randomly chose a single host mutant that was resistant to the ancestral parasite. We then repeated this process for parasites, again using the same mutation regime as in the evolution experi- ments, and we isolated a host-range mutant able to infect that resistant host mutant. We continued the pairwise challenges using the derived host and parasite genotypes for 50 rounds. A challenge experiment was stopped if we failed to isolate a relevant mutant after screening 500,000 individuals. In the comparisons with the evolution and coevolution treatments, we used 56 challenge experiments (out of 100 started) that achieved the full 50 rounds of reciprocal defenses and counter-defenses. However, the truncated runs appeared to be indistinguishable from those that went the full duration. Freeze and Replay Experiments In these experiments, we allowed host populations to evolve with either ‘‘frozen’’ or ‘‘replayed’’ parasites. During the original coevolution experiments, we saved each replicate’s entire set of host and parasite genotypes every 1,000 updates. We modified the Avida source code such that this record of genotypes can be loaded into an on-going run at any point by adding an option to override the normal replication process with one that samples from a genotype list. When organisms reproduce, instead of inheriting their parent’s genome, the offspring is assigned a random genotype from the list. This procedure can be implemented for hosts, para- sites, or both; however, in the freeze and replay experiments presented here, we manipulated only the parasite populations using this new procedure. In both treatments, we injected 1,500 parasites into the host population after 2,000 updates; this number was increased relative to the coevolution treatment to ensure that the frozen and replayed parasite populations, which were some- times poorly adapted to the ancestral host, did not go extinct. In the freeze treatment, each host population confronted a parasite population that was complex and diverse, but constant in its genotypic frequencies over an entire run (except for the fluctuations associated with births and deaths of the parasites). The composition of each parasite population was based on the list of parasites taken at the mid-point (i.e., 250,000 updates) of one of the coevolution treatment runs. Thus, the genetic composition of the parasite population was frozen throughout the run, although the total number of parasites could rise or fall in accord with the dynamics of infections. Under the replay treatment, the frequen- cies of parasite genotypes changed over time, but those changes were based on parasite evolution that had taken place in an earlier coevolution run, rather than on the dynamics that were occurring in the replay itself. That is, the list of parasite genotypes from which new parasites were drawn was changed every 1,000 updates to reflect what had happened in the earlier run. As a consequence, the host could evolve in response to the changing frequencies of the various parasite genotypes, but not vice versa—the coevolu- tionary feedback was broken, although parasite diversity and the temporal changes in that diversity were preserved. Phylogenetic Analysis In Avida, the genealogy of organisms is known perfectly and, when coupled with the asexual lineages studied here, allows con- struction of the exact phylogenetic history for a population. We used the python ete2.1 module to represent (Figure 7) all of the genotypes present in two host populations along with their ances- tries through the various coalescences, the most recent common ancestor for the entire population, and the founding genotype. Evolvability Analysis We tested every possible one-step point mutation in the genetic background of the most abundant host genotype at the end of all 50 evolution and coevolution runs. Each mutant was placed into one of the following categories based on the phenotypic changes relative to its parent: (i) the mutant cannot perform any functions or is otherwise nonviable; or (ii) the mutant is viable and (a) there is no difference in the number or identity of functions performed; (b) the mutant performs more functions; (c) the mutant performs fewer functions; or (d) the identity of functions performed has changed, but the number has not. The last category, which we call ‘‘switching,’’ was the focus of our analysis. We also modified this analysis to take into account possible effects of differences in the number and complexity of tasks performed by pairing host genotypes isolated from the evolved and coevolved populations that performed identical sets of tasks. Coevolution Drives Complexity and Evolvability PLOS Biology | www.plosbiology.org 8 December 2014 | Volume 12 | Issue 12 | e1002023 Genotypes were pooled across the replicate runs based on what tasks they could perform. All of the coevolved populations were compared with all of the evolved populations to identify paired host phenotypes that performed identical sets of tasks. For each pair of phenotypes thus identified, a genotype from the evolved and coevolved populations that performed the appropriate set of tasks was chosen at random, and all possible one-step mutations were then generated for both genotypes. Supporting Information Figure S1 Proportion of hosts at all five levels of complexity over the first 25,000 updates in each of the 50 replicates seeded with the most complex ancestors. White regions represent host genotypes that performed only the simplest tasks, while progressively darker regions represent hosts that performed more complex functions. All of the host populations transiently harbored subpopulations that could perform only the simplest functions, although coevolving parasites drove the host populations to perform more complex functions on average (Figure 6). (TIF) Acknowledgments We thank B. Connelly, I. Dworkin, M. Fortuna, B. Kerr, E. Ostrowski, A. Wagner, and J. Xue for fruitful discussions. Author Contributions Conceived and designed the experiments: LZ JRM DMB REL CO. Performed the experiments: LZ SD. Analyzed the data: LZ SD. Wrote the paper: LZ JRM REL CO. Designed and implemented Avida features: DMB LZ. References 1. Shanahan T (2004) The evolution of Darwinism: selection, adaptation and progress in evolutionary biology. Chambridge: Cambridge University Press. 352 p. 2. Szostak JW, Bartel DP, Luisi PL (2001) Synthesizing life. Nature 409: 387–390. 3. Simpson GG (1967) The meaning of evolution. New Haven (Connecticut): Yale University Press. 386 p. 4. Huxley JS (1953) Evolution in action. New York: Harper & Brothers. 182 p. 5. Lynch M (2007) The frailty of adaptive hypotheses for the origins of organismal complexity. Proc Natl Acad Sci U S A 104: S8597-S8604. 6. Gould SJ (1996) Full house: the spread of excellence from Plato to Darwin. New York: Harmony Books. 256 p. 7. Dawkins R (1997) Human chauvinism. Evolution 51: 1015–1020. 8. Dawkins R, Krebs JR (1979) Arms races between and within species. Proc R Soc Lond B Biol Sci 205: 489–511. 9. Shanahan T (1999) Evolutionary progress from Darwin to Dawkins. Endeavour 23: 171–174. 10. Hazen RM, Griffin PL, Carothers JM, Szostak JW (2007) Functional information and the emergence of biocomplexity. Proc Natl Acad Sci USA 104: 8574–8581. 11. Adami C (2002) What is complexity? BioEssays 24: 1085–1094. 12. Adami C, Ofria C, Collier TC (2000) Evolution of biological complexity. Proc Natl Acad Sci U S A 97: 4463–4468. 13. Pennock RT (2007) Models, simulations, instantiations, and evidence: the case of digital evolution. J Exp Theor Artif Intell 19: 29–42. 14. Lenski RE, Ofria C, Pennock RT, Adami C (2003) The evolutionary origin of complex features. Nature 423: 139–144. 15. Ofria C, Bryson D, Wilke C (2009) Avida: A software platform for research in computational evolutionary biology. Kmosinski M, Adamatzky MA, editors. Artificial life models in software 3. New York: Springer. pp. 3–35. 16. Vermeij GJ (1993) Evolution and escalation: an ecological history of life. New Jersey: Princeton University Press. 544 p. 17. Moxon ER, Rainey PB, Nowak MA, Lenski RE (1994) Adaptive evolution of highly mutable loci in pathogenic bacteria. Curr Biol 4: 24–33. 18. Zaman L, Devangam S, Ofria C (2011) Rapid host-parasite coevolution drives the production and maintenance of diversity in digital organisms. Krasnogor N, editor. Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation 219. New York: ACM. pp. 219–226. 19. Williams HTP (2012) Phage-induced diversification improves host evolvability. BMC Evol Biol 13: 17. 20. Weitz JS, Hartman H, Levin SA (2005) Coevolutionary arms races between bacteria and bacteriophage. Proc Natl Acad Sci U S A 102: 9535–9540. 21. Gilman RT, Nuismer SL, Jhwueng D-C (2012) Coevolution in multidimensional trait space favours escape from parasites and pathogens. Nature 483: 328–330. 22. Woolhouse ME, Webster JP, Domingo E, Charlesworth B, Levin BR (2002) Biological and biomedical implications of the co-evolution of pathogens and their hosts. Nature Genet 32: 569–577. 23. Decaestecker E, Gaba S, Raeymaekers JA, Stoks R, Van Kerckhoven L, et al. (2007) Host-parasite ‘Red Queen’ dynamics archived in pond sediment. Nature 450: 870–873. 24. Thompson JN (2005) Coevolution: the geographic mosaic of coevolutionary arms races. Curr Biol 15: R992–R994. 25. Thompson JN (2005) The geographic mosaic of coevolution. Chicago: University Chicago Press. 400 p. 26. Hofnung M, Jezierska A, Braun-Breton C (1976) LamB mutations in E. coli K12: growth of lambda host range mutants and effect of nonsense suppressors. Mol Gen Genet 145: 207–213. 27. Guimara˜es PR, Jordano P, Thompson JN (2011) Evolution and coevolution in mutualistic networks. Ecol Lett 14: 877–885. 28. Wilke CO, Wang JL, Ofria C, Lenski RE, Adami C (2001) Evolution of digital organisms at high mutation rates leads to survival of the flattest. Nature 412: 331–333. 29. Lawrence D, Fiegna F, Behrends V, Bundy JG, Phillimore AB, et al. (2012) Species interactions alter evolutionary responses to a novel environment. PLoS Biol 10: e1001330. 30. Turcotte MM, Corrin MSC, Johnson MTJ (2012) Adaptive evolution in ecological communities. PLoS Biol 10: e1001332. 31. Johnson MTJ, Stinchcombe JR (2007) An emerging sythesis between community ecology and evolutionary biology. Trends Ecol Evol 22: 250–257. 32. Meyer JR, Dobias DT, Weitz JS, Barrick JE, Quick RT, et al. (2012) Repeatability and contingency in the evolution of a key innovation in phage lambda. Science 335: 428–432. 33. Marston MF, Pierciey Jr FJ, Shepard A, Gearin G, Qi J, et al. (2012) Rapid diversification of coevolving marine Synechococcus and a virus. Proc Natl Acad Sci U S A, 109: 4544–4549. 34. Thompson JN (2013) Relentless evolution. Chicago: University Chicago Press. 512 p. 35. Meyer JR, Kassen R (2007) The effects of competition and predation on diversification in a model adaptive radiation. Nature 446: 432–435. 36. Zaman L, Meyer JR, Devangam S, Bryson DM, Lenski RE, Ofria C (2014) Data from: Coevolution drives the emergence of complex traits and promotes evolvability. Dryad Digital Repository. Available: http://dx.doi.org/10.5061/ dryad.485qq 37. Fortuna MA, Zaman L, Wagner AP, Ofria C (2013) Evolving digital ecological networks. PLoS Comput Biol 9: e1002928. Coevolution Drives Complexity and Evolvability PLOS Biology | www.plosbiology.org 9 December 2014 | Volume 12 | Issue 12 | e1002023 dami C, Ofria C, Collier TC (2000) Evolution of biological complexity. Proc Natl Acad Sci U S A 97: 4463–4468. 13. Pennock RT (2007) Models, simulations, instantiations, and evidence: the case of digital evolution. J Exp Theor Artif Intell 19: 29–42. 14. Lenski RE, Ofria C, Pennock RT, Adami C (2003) The evolutionary origin of complex features. Nature 423: 139–144. 15. Ofria C, Bryson D, Wilke C (2009) Avida: A software platform for research in computational evolutionary biology. Kmosinski M, Adamatzky MA, editors. Artificial life models in software 3. New York: Springer. pp. 3–35. 16. Vermeij GJ (1993) Evolution and escalation: an ecological history of life. New Jersey: Princeton University Press. 544 p. 17. Moxon ER, Rainey PB, Nowak MA, Lenski RE (1994) Adaptive evolution of highly mutable loci in pathogenic bacteria. Curr Biol 4: 24–33. 18. Zaman L, Devangam S, Ofria C (2011) Rapid host-parasite coevolution drives the production and maintenance of diversity in digital organisms. Krasnogor N, editor. Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation 219. New York: ACM. pp. 219–226. 19. Williams HTP (2012) Phage-induced diversification improves host evolvability. BMC Evol Biol 13: 17. 20. Weitz JS, Hartman H, Levin SA (2005) Coevolutionary arms races between bacteria and bacteriophage. Proc Natl Acad Sci U S A 102: 9535–9540. 21. Gilman RT, Nuismer SL, Jhwueng D-C (2012) Coevolution in multidimensional trait space favours escape from parasites and pathogens. Nature 483: 328–330. 22. Woolhouse ME, Webster JP, Domingo E, Charlesworth B, Levin BR (2002) Biological and biomedical implications of the co-evolution of pathogens and their hosts. Nature Genet 32: 569–577. 23. Decaestecker E, Gaba S, Raeymaekers JA, Stoks R, Van Kerckhoven L, et al. (2007) Host-parasite ‘Red Queen’ dynamics archived in pond sediment. Nature 450: 870–873. 24. Thompson JN (2005) Coevolution: the geographic mosaic of coevolutionary arms races. Curr Biol 15: R992–R994. 25. Thompson JN (2005) The geographic mosaic of coevolution. Chicago: University Chicago Press. 400 p. 26. Hofnung M, Jezierska A, Braun-Breton C (1976) LamB mutations in E. coli K12: growth of lambda host range mutants and effect of nonsense suppressors. Mol Gen Genet 145: 207–213. 27. Guimara˜es PR, Jordano P, Thompson JN (2011) Evolution and coevolution in mutualistic networks. Ecol Lett 14: 877–885. 28. Wilke CO, Wang JL, Ofria C, Lenski RE, Adami C (2001) Evolution of digital organisms at high mutation rates leads to survival of the flattest. Nature 412: 331–333. 29. Lawrence D, Fiegna F, Behrends V, Bundy JG, Phillim