How the workers have been rendered sterile is a difficulty; but not much greater than that of any other striking modification of structure; for it can be shown that some insects and other articulate animals in a state of nature occasionally become sterile; and if such insects had been social, and it had been profitable to the community that a number should have been annually born capable of work, but incapable of procreation, I can see no especial difficulty in this having been effected through natural selection. But I must pass over this preliminary difficulty. The great difficulty lies in the working ants differing widely from both the males and the fertile females in structure, as in the shape of the thorax, and in being destitute of wings and sometimes of eyes, and in instinct. As far as instinct alone is concerned, the wonderful difference in this respect between the Now it is clear that what takes place among the individuals of a species must also occur among the several allied species of a group. and If [...] any species should produce a variety having slightly increased powers of preserving existence, that variety must inevitably in time acquire a superiority in numbers.

. . . but even in the limit it is incorrect to identify b ijS with Wright's coefficient of relationship. Wrigth's coefficient is a correlation coefficient whereas the coefficient required here is the corresponding regression coefficient.

 explains Hamilton rule as follows:

. The reasoning of Wynne-Edwards is contestable because he takes this kind of evolvability suppression for granted on the sole motive that it allows homeostasis and optimality. It is an interesting but very finalist view: while it is remarkable that Wynne-Edwards alluded to evolvability suppression in 1963, he failed to consider it as an evolving "trait". It would have made more sense to consider the

List of Tables

Part I Introduction 1 Cooperation in biological systems: a spaghetti introduction

Since Darwin, the dominant paradigm in evolution has been "survival of the fittest", and cooperation has often been seen as a conceptual challenge to evolutionary theory. Why would some biological agents pay a cost to help others? Altruistic behavior seems ubiquitous in nature, from bacteria or social insects to ape societies, and exists at several levels including the most basics. For example the assembly of several cells, some of whom loose reproductive behavior, into a complex multi-cellular organism is a cooperative system itself.

The question of cooperation is not new, and the answer has historically been group selection (natural selection applied between groups of individuals and not directly between individuals), even if the term itself is recent. Several major conceptual advances have however been made in the last decades: introduction of kin selection by J.B.S. Haldane and W.D. Hamilton, application of game theory to evolutionary biology by J. Maynard Smith, re-conceptualization of group selection by V.C. Wynne-Edwards and E.O. Wilson, and huge dispute over the respective merits of group selection and kin selection in explaining social behavior.

Several researchers who participated in or commented on the recent social evolution debate have stated that Darwin himself already spoke about cooperation as a major challenge to his theory [START_REF] Nowak | The evolution of eusociality[END_REF][START_REF] Axelrod | The Evolution of Cooperation[END_REF]. We can indeed read in [START_REF] Darwin | On the Origin of Species: By Means of Natural Selection[END_REF]: I [...] will confine myself to one special difficulty, which at first appeared to me insuperable, and actually fatal to the whole theory. I allude to the neuters or sterile females in insect communities.

However if we go a little bit deeper than the aforementioned researchers did, and actually read the next few lines of Darwin's book, we will notice two interesting things: workers and the perfect females would have been better exemplified by the hive-bee. If a working ant or other neuter insect had been an ordinary animal, I should have unhesitatingly assumed that all its characters had been slowly acquired through natural selection; namely, by individuals having been born with slight profitable modifications, which were inherited by the offspring, and that these again varied and again were selected, and so onwards. But with the working ant we have an insect differing greatly from its parents, yet absolutely sterile; so that it could never have transmitted successively acquired modifications of structure or instinct to its progeny. It may well be asked how it is possible to reconcile this case with the theory of natural selection?

The key message in these lines is quite different from the one people usually cite! First, the challenge Darwin is referring to is not the altruistic behavior in itself, but what we would today call phenotypic plasticity. Second, the answer to the problem that Darwin considered simple (altruistic behavior) is clearly here group selection ("profitable to the community. . . ").

I believe this is more than a mere anecdotal story of selective reading: knowing that natural selection theory has incorporated an evolutionary explanation for cooperative behavior since its very beginning but that Darwin was struggling to understand the actual mechanistic "genetics" of eusociality should send a strong signal. It pushes us towards a rather pessimistic estimate of the significance that several decades of mostly conceptual studies have for our understanding of social evolution.

This brief and partial analysis should not however let us obliterate the huge positive impact of the three already mentioned conceptual advances (game theory, kin selection and revisiting group selection) not only on modern evolutionary biology but also on evolutionary psychology and on cognitive ethology. In this part of the introduction, I will discuss these major frameworks, how they have shaped our thinking about cooperation in biological systems, as well as their histories, their convergence points and their differences.

Main evolutionary theories: kin selection and group/multilevel selection

The two big frameworks to understand social behaviors are kin selection and multi-level selection (also referred as group selection).

Kin selection, attributed to Haldane [START_REF] Haldane | Population genetics[END_REF] and Hamilton (Hamilton, 1964a), emphasizes that kin interact more often together than random (this can be achieved by several mechanisms including population viscosity or kin recognition), causing an altruistic behavior controlled by a gene to be statistically more often directed to a kin carrying the same gene than random. Thus while performing an altruistic act decreases the fitness of the actor, it can increase the fitness of the recipient (often bearing the same allele at the locus controlling cooperation) enough for the total fitness of the allele causing the altruistic behavior to increase. The measure of interest becomes what has been referred as "inclusive fitness" (total fitness of the allele of interest, taking into account potential copies of this allele in kin of focal individual). Hamilton's rule states that an altruistic behavior will be selected if r * b -c > 0, where b is the benefit of the altruistic act for the recipient, c is the cost for the actor, and r is relatedness, which is a proxy for chances that the recipient carries the same allele than the actor at the locus of interest. More precisely, most authors call relatedness a measure of genetic similarity between spatially close individuals at a given locus [START_REF] Grafen | A geometric view of relatedness[END_REF]. However as we will see in next part, other authors have made a larger use of relatedness, causing several semantic issues [START_REF] Wilson | Eusociality: origin and consequences[END_REF][START_REF] Wilson | Kin selection as the key to altruism: its rise and fall[END_REF], and we will discuss other potential definitions of relatedness.

This theory clearly fits into a gene-centered view of evolution, or at least did at the time of its development by Haldane and Hamilton. It stresses that a behavioral (for example cooperative) trait is just a strategy controlled by a gene to maximize its evolutionary "survival" and dispersal: a gene can be detrimental to its host (reducing the part of its own fitness that relies on survival and reproduction of the host) if it brings a benefit to other hosts carrying other copies of the same gene. What we already described as inclusive fitness is just a way to account for this effect. We must however stress that the gene-centered view of evolution goes further than inclusive fitness and kin selection, and also considers the competition of several genes inside a host [START_REF] Dawkins | The selfish gene[END_REF] leading to fascinating conflicts such as meiotic drive or addiction systems.

The other important framework for the evolution of cooperation is multi-level selection, also referred as group selection. It emphasizes the spatial partitioning of a population between several groups and the differences in fitness between these groups according to their compositions. In the case of cooperation, while inside each group cooperators have a selective disadvantage over non-cooperators because of the individual cost they pay for the benefits that are shared, the groups with more cooperators will expand ("reproduce") faster or be less prone to extinction. This difference in fitness at group level could potentially compensate or overtake the difference of fitness within groups, leading to selection of cooperation.

Recent developments of group selection owe a lot to V.C. Wynne-Edwards (Wynne-Edwards, 1963) and E.O. Wilson [START_REF] Wilson | Eusociality: origin and consequences[END_REF]. However this theory is not new, and it is remarkable to notice that Wallace almost exclusively talked about selection at "variety" level [START_REF] Wallace | On the tendency of varieties to depart indefinitely from the original type[END_REF]:

The equivalence of these two theories have been extensively discussed, with more or less interesting arguments [START_REF] Nowak | Five rules for the evolution of cooperation[END_REF]West et al., 2007b). A recent debate emerged following claims by [START_REF] Nowak | The evolution of eusociality[END_REF] on the prevalence of group selection in explaining the evolution of social behavior. According to Nowak, kin selection does not bring anything to social evolution because it is at best (when properly formalized) equivalent to group selection. On the other end, several hundreds of researchers had no doubt that the inclusive fitness view (and thus kin selection) was one of the most important conceptual advance since Darwin [START_REF] Abbot | Inclusive fitness theory and eusociality[END_REF]. Without entering too much into the details, here I will discuss a few particular key points that I think are particularly important and can lead to major misunderstandings.

One important historical difference between group and kin selection is the question of isolation. While several (if not most) of the recent developments of group selection theory can cope with groups of various compositions (and not only groups of only cooperators or non cooperators) and with migrations, the question of how much the groups should be isolated (and what is the difference with kin selection when there is a spatial continuum) has historically been subject to debate. John Maynard Smith for example stated [START_REF] Smith | Group selection and kin selection[END_REF]:

By kin selection I mean the evolution of characteristics which favour the survival of close relatives of the affected individual, by processes which do not require any discontinuities in population breeding structure and The distinction between kin selection and group selection as here defined is that for kin selection the division of the population into partially isolated breeding groups is a favourable but not an essential condition, whereas it is an essential condition for group selection, which depends on the spread of a characteristic to all members of a group by genetic drift.

As already mentioned, more recent developments of group selection are less stringent regarding the question of isolation of groups. I should emphasize that it is entirely possible to conduct mathematical analysis of the spread of social traits relying on different fitness of groups without requiring homogeneity at the locus of interest within a group. [START_REF] Chuang | Simpson's paradox in a synthetic microbial system[END_REF] did so in a framework based on Price equation [START_REF] Price | Selection and covariance[END_REF], relaunching the question of the equivalence between group and kin selection by eliminating what was once considered as a key difference between the two frameworks. Similarly to the emphasis that J. Maynard Smith put on the role of genetic drift to create several groups of different compositions, [START_REF] Chuang | Simpson's paradox in a synthetic microbial system[END_REF] showed that strong bottlenecks can indeed create the variability in group composition necessary for selection between groups to operate. Plasmid conjugation is another mechanism known to favor and increase (but not necessary create) the within group homogenization [START_REF] Nogueira | Horizontal gene transfer of the secretome drives the evolution of bacterial cooperation and virulence[END_REF][START_REF] Dimitriu | Genetic information transfer promotes cooperation in bacteria[END_REF], which leads to between groups diversity. We will also show in the fifth chapter that selection on non-cooperative traits is yet another mechanism creating (or increasing) the population structure necessary for kin/group selection to operate.

Although not always accepted in evolutionary biology, this idea of group selection had a huge influence in evolutionary psychology and cognitive sciences. It is however important to note that while group selection makes us talk about the fitness of a group (in the same way that kin selection and gene-centered view of evolution makes us talk about the fitness of an allele), the unit of reproduction remains the individual. We must stress that most modeling work relying on multi-level selection does not actually explicitly represent birth and death of groups. That lead Michael Doebeli and collaborators to develop a more restrictive variant of group selection in which birth and death events explicitly occur at both group and individual level [START_REF] Simon | Towards a general theory of group selection[END_REF], which is even more controversial but has the merit of being a true leap forward in the paradigm of social evolution.

Focus on microbes

To better understand the aforementioned theories of cooperation, I will discuss a few examples of experimentally studied cooperative traits primarily in microbes. Microbes are amazing model organisms when it comes to experimental studies of evolution. Their short generation time, ease of growth in laboratory conditions, the possibility to freeze and unfreeze them, and well developed molecular biology tools gave them a leading role in the development of molecular evolution. Several kinds of cooperation systems have been identified in different microbes, a majority of which relies on public good sharing. Public goods are molecules that are costly to produce but are secreted into the environment around the producing individuals, diffuse and benefit its neighbors. For example, the phage φ6, a well studied RNA virus, is known to have genes coding for several diffusible intra-host compounds that are thus shared with other viruses infecting the same bacteria, and that are necessary for reproduction. When a mutant bearing a deletion of some of these genes appears in a group of φ6 infecting the same cell, it has a higher relative fitness (higher reproduction rate thanks to shorter genome size). However the invasion of this genotype will cause a drop in fitness of the whole group because less compounds will be accessible. Groups of cooperators infecting the same cells are thus likely to win the competition with groups of non cooperators, however within each cell cooperators will loose the competition. The outcome of this complex dynamics depends on the multiplicity of infections [START_REF] Turner | Prisoner's dilemma in an rna virus[END_REF]. Similarly, several species of bacteria produce a wide diversity of extra-cellular public goods, one of the most studied experimentally being pyoverdine (iron chelator) in Pseudomonas aeruginosa [START_REF] Buckling | Siderophore-mediated cooperation and virulence in Pseudomonas aeruginosa[END_REF]. Examples of cooperation also exist in yeast, where invertase degrades saccharose into fructose and glucose, a large part of which is then exported outside of the cell [START_REF] Koschwanez | Sucrose utilization in budding yeast as a model for the origin of undifferentiated multicellularity[END_REF]). Another remarkable Introduction example of cooperation is the sacrifice of a fraction of the cells to form a non-reproducing stalk which supports and increases the chances of dispersal of the reproducing spores in Dictyostelium discoideum [START_REF] Strassmann | Altruism and social cheating in the social amoeba dictyostelium discoideum[END_REF]. Other interesting works investigate the context of multicellularity, or at the most basic form, sticking together. For example, biofilm production is in itself a kind of cooperation [START_REF] Rainey | Evolution of cooperation and conflict in experimental bacterial populations[END_REF] because of the production cost of polymers and group level benefits they offer. Moreover biofilm production is often linked to other social traits [START_REF] Harrison | Siderophore production and biofilm formation as linked social traits[END_REF] that it could support because it creates a spatial structure, making assortment between individuals non-random. The cooperative view should however be nuanced by considering the work of [START_REF] Xavier | Cooperation and conflict in microbial biofilms[END_REF], who suggest that biofilm production does not reduce to a simple prisoner dilemma type game because simple physical mechanisms may restrict the benefit only to other producers, and when producers are dominant a single non-producer could even be "strangled" by the polymers produced by its neighbors. More generally, for all the examples that we mentioned we should keep in mind that we are usually not studying bacteria in their natural habitats. In the lab both life-history traits and physical environments are taken into account only very partially or not at all, but may have a non-negligible impact on cooperation. This deliberate emphasis on microbes is not meant to minimize the importance of other striking examples of cooperation in higher organisms from vampire bats to clownfish or apes. Cooperation is at the heart of the existence of more complex organisms, themselves being effectively a collection of cooperative traits [START_REF] Szathmáry | The major transitions in evolution[END_REF]. However it is microbial cooperation that has inspired the majority of the work presented here.

The role of synthetic systems in understanding the evolution of cooperation

While there are as we saw rich and diverse natural cooperative systems, biological engineering can allow for the creation of easier to understand and to control cooperative systems [START_REF] Chuang | Simpson's paradox in a synthetic microbial system[END_REF]Tanouchi et al., 2012a;[START_REF] Dimitriu | Genetic information transfer promotes cooperation in bacteria[END_REF][START_REF] Pai | Optimality and robustness in quorum sensing (qs)-mediated regulation of a costly public good enzyme[END_REF], whose parameters can be varied and fine-tuned [START_REF] Chuang | Cooperation and Hamilton's rule in a simple synthetic microbial system[END_REF]. In general, synthetic systems can help to better understand evolution (Tanouchi et al., 2012b). They may seem reductive and artificial, but precisely because everything is controlled they can help to test debated hypothesis. We will present in the third chapter a synthetic system that will help us to test an hypothesis we introduce in the second chapter.

Evolution of virulence

Beyond public good games that we already discussed, I would like to briefly mention another kind of social (or anti-social) behavior that can be understood in the light of these advances in social evolution. Considering microbes as social organisms had a huge impact on our understanding of the evolution of virulence, an interesting part of evolutionary biology of microorganisms, with very practical applications. Weakening and potentially killing the host can be seen as detrimental to the fitness of a parasite at "high", population scale: keeping the host alive and healthy is usually the best way to get a chance to colonize other hosts. Simultaneously there is also a competition between multiple parasites (of the same species or not) inside the host that can lead to an increase in virulence. For example, spreading the infection to blood or to other organs increases relative fitness compared to other individuals living within the same host, even though it could cause the whole population of parasites to die with the host. The same goes for an over-exploitation of the host resources. These findings turn the question of the evolution of virulence into a social dilemma between parasites [START_REF] Frank | Models of parasite virulence[END_REF][START_REF] Brown | Does multiple infection select for raised virulence?[END_REF]Brown et al., , 2009a)). Moreover as emphasized by [START_REF] Brown | Does multiple infection select for raised virulence?[END_REF], the parasites inside a host are often sharing some public goods on which virulence can rely. Spite toward other parasites through the triggering of a immune response is also common [START_REF] Brown | Evolution of virulence: Triggering host inflammation allows invading pathogens to exclude competitors[END_REF], and can go as far as the self-sacrifice of a fraction of the population to trigger this competitor-excluding immune response [START_REF] Ackermann | Self-destructive cooperation mediated by phenotypic noise[END_REF]. To conclude, depending on the system and the scale we consider, virulence can be the result of a selfish behaviour, can rely on cooperative traits, or can be a cooperative trait itself, making social evolution particularly relevant [START_REF] Harrison | Bacterial cooperation in the wild and in the clinic: Are pathogen social behaviours relevant outside the laboratory?[END_REF]. The evolution of virulence and social dynamics involved remains an important application and motivation for the studies of social evolution.

Relatedness and associated problems

The analysis of relatedness has been a cornerstone of theoretical and even experimental studies of cooperation. It is also as we said one of the very controversial parts of the social evolution debate, and the fact that different authors use the same term with different meanings does not facilitate communication. In this part of the introduction I will discuss several particular points of the debate whose origin is a divergence between several authors in the definition of relatedness, and that are thus easy to solve. This discussion should not be seen as an attack against relatedness, but on the opposite an emphasize on how powerful can be kin selection and inclusive fitness theory when properly formalized.

Single gene relatedness is (very) different from whole genome relatedness

Whole genome relatedness hints at a sociobiology idea that the individual's behavior is the sum of the interests of its genes. Many papers use Sewall Wright's coefficient of relationship, which is a whole genome measure of genetic relationship between two individuals. This is very different from relatedness based on identity by state or identity by descent at a given locus (the one controlling the cooperative behavior). I believe one part of the confusion comes from the (incorrect) way Haldane's famous sentence is often cited. Every evolutionary biologist has heard at least once some version of the "I would jump into the river to save two brothers or eight cousins" sentence, attributed to J.B.S. Haldane. To the best of my efforts, the paper in which Haldane is usually assumed to have written this [START_REF] Haldane | Population genetics[END_REF] was impossible to find online (the journal changed name, was acquired by a new editor and then closed more than forty years ago). Emailing several persons citing this article lead to results that made me worry about the durability and accessibility of scientific information. I was however eventually able to get a copy emailed to me, and here is the original statement from [START_REF] Haldane | Population genetics[END_REF]:

Let us suppose that you carry a rare gene which affects your behaviour so that you jump into a flooded river and save a child, but you have one chance in ten of being drowned, while I do not possess the gene, and stand on the bank and watch the child drown. If the child is your own child or your brother or sister, there is an even chance that the child will also have this gene, so five such genes will be saved in children for one lost in an adult. If you save a grand-child or nephew the advantage is only two and a half to one. If you only save a first cousin, the effect is very slight. This is much more informative than the usual cited sentence: Haldane strongly emphasizes the role of whole genome relatedness as an approximation for single locus relatedness, which is clearly what really matters. He firmly and without any shade of doubt places himself in a gene centered view of evolution, embracing the yet-to-appear concept of inclusive fitness.

As hinted by Haldane, whole genome relatedness can be used as an approximation for singlelocus relatedness. Indeed the coefficient of relationship between two individuals is closely linked to the probability that for any given locus (including locus controlling cooperative behavior), the two individuals share the same allele, once a few population genetics hypotheses and approximations are taken into account. [START_REF] Grafen | A geometric view of relatedness[END_REF] discusses in more details than one can ask for this link between single locus relatedness and whole genome relatedness.

It is interesting to notice that while Hamilton (1964a) used Wright coefficient of relationship, [START_REF] Hamilton | Selfish and spiteful behaviour in an evolutionary model[END_REF] uses a "regression", i.e. a statistical association at one particular locus:

Or again in [START_REF] Wilson | Eusociality: origin and consequences[END_REF]:

The degree of relatedness, the similarity across the whole genome of individuals as a result of recent common ancestry. This is a particularly eloquent example of the unfortunate and misplaced use of the whole genome relatedness. As we saw Hamilton (1964a,b) was not very clear regarding this issue of single locus versus whole genome relatedness. However I think that because he redid his framework based on [START_REF] Price | Selection and covariance[END_REF], [START_REF] Hamilton | Selfish and spiteful behaviour in an evolutionary model[END_REF] actually makes a step toward unifying kin selection with (one particular variant of) group selection. I think that this view of relatedness as a statistical association ("Considerations of genetical kinship can give a statistical re-association of the effects with the individuals that cause them", as stated by [START_REF] Hamilton | Selfish and spiteful behaviour in an evolutionary model[END_REF]) is particularly important to establish a "core" theory of altruism, based on what is common between kin selection and group selection.

In the Results part of my manuscript, I will thus often call relatedness a measure of statistical association between individuals of the same "type" regarding cooperating behavior, directly based on [START_REF] Hamilton | Selfish and spiteful behaviour in an evolutionary model[END_REF] and [START_REF] Grafen | A geometric view of relatedness[END_REF]. I hope that senior readers will forgive me for taking this freedom, but if not, I would like to emphasize that this mess is much more their fault than mine.

A digression about phenotypic plasticity and eusociality

We already briefly discussed eusociality at the beginning of this introduction as being the first "official" mention of altruism in evolutionary theory. [START_REF] Wilson | Kin selection as the key to altruism: its rise and fall[END_REF] also makes another interesting statement about Darwin's explanation of eusociality: That hereditary type, not the plastic forms it produces, is therefore the unit of selection. The altruistic castes, he said, are like the well-flavored vegetable part in a single crop strain produced by selective breeding [START_REF] Darwin | On the Origin of Species: By Means of Natural Selection[END_REF].

We believe that the second part of this statement is extremely important: the cooperative trait here is not the phenotype "do not reproduce" (obviously not inheritable), but the genotype leading to a phenotypic differentiation between a reproductive cast and a non-reproductive cast. The problem is thus not the competition between reproducing and non-reproducing individuals, but between "worker generating" and non-"worker generating" genotypes, as we will discuss in the fourth chapter. This was however not always clear in the earlier applications of kin selection and inclusive fitness theory by Hamilton to explain eusociality in Hymenopterans (Hamilton, 1964b), and the resulting confusion has been a serious point of friction between group and kin selection proponents. Indeed, Hamilton (1964b) states that:

According to our theory, these [relatedness] values indicate that workers should be much less inclined to give up their male-producing in favour of the queen's than they are to give up their female-producing in favour of a singly-mated queen.

Which alludes to the evolutionary interest ("should be more/less inclined to ...") of the workers, which is hard to define since they do not reproduce. Of course the core of the idea is that some of the worker genes are also present in the queen and in other workers, but this is not enough to fully understand this statement and brings us back to other questions such as whole genome versus single locus relatedness.

Although I do not model eusociality in this work, the themes of plasticity and genotypic versus phenotypic control of cooperative traits are analogous and central to the analysis presented in the fourth chapter.

Relatedness is an evolving variable and not a parameter

In the model presented by [START_REF] Nogueira | Horizontal gene transfer of the secretome drives the evolution of bacterial cooperation and virulence[END_REF], it is interesting to explicitly have r as one of the key variables of the model, but it is important to notice that relatedness is an evolving variable and not an "input" nor a predictor. This is something rather general: even in island models where spatial structure is very constrained and not emergent, it is a priori not possible to calculate relatedness without solving the iterative system, which usually means finding the fixed point. This is important because it means that relatedness is itself shaped by selection, making hard to establish a causal link between relatedness and cooperation.

Relatedness does not (anymore) necessarily imply a gene-centered view of evolution

In the case where relatedness is calculated as a single locus regression coefficient, it is effectively telling us what is the expected number of individuals of type A (at this locus) in the neighborhood of an individual of type A, compared to what it would be in a well-mixed population. This single locus relatedness is then a relevant measure of "spatial assortment" even without adopting a gene-centered view of evolution.

To defend this idea, let us move to a more "game theory centered" framework and examine a spatially structured population playing a simple public good game leading to the classical prisoner dilemma. To calculate the average payoff of cooperators and compare it to the average payoff of defectors, we precisely need this measure of spatial assortment, and it is not aberrant to call it "relatedness". It has however a priori nothing to do with inclusive fitness which relies on the maximization of fitness of all copies of the gene of interest: it only states that the reward one individual gets depends on the behaviour of other actors, and that this behaviour is not random in spatially structured population. It is thus easy to derive a variant of Hamilton rule stating that cooperative behavior will be favored if and only if the benefit over cost ratio is greater than something close to relatedness as emphasized by [START_REF] Nowak | The evolution of eusociality[END_REF]. The interpretation made by [START_REF] Nowak | The evolution of eusociality[END_REF] is however very reductive, and its most interesting parts (partial equivalence between evolutionary stable strategy and inclusive fitness) have already been extensively discussed by [START_REF] Taylor | How to make a kin selection model[END_REF].

Several problems with infectivity versus kin selection, especially in the context of plasmid conjugation

Information transfer can in itself be seen as a type of cooperative behavior: teaching in meerkats or apes is costly for the actor (time spent teaching is not spent feeding) and has an obvious benefit for the recipient. Modern cognitive ethology went beyond Lorenz and Tinbergen studies of instinct and emphasizes that in several species the juveniles are entirely dependent of learning to survive [START_REF] Ewer | The behaviour of the meerkat, suricata suricatta (schreber)[END_REF]. But it is also important to note that in bacterial world, plasmid conjugation (one particularly well studied type of information transfer) is also supporting other types of cooperation. Indeed, several studies show that plasmids are enriched for genes coding for "cooperative" proteins, for example bacteriocins [START_REF] Riley | Bacteriocins: Evolution, ecology, and application[END_REF] or generally extracellular proteins [START_REF] Nogueira | Horizontal gene transfer of the secretome drives the evolution of bacterial cooperation and virulence[END_REF]. Several somewhat conflicting theories attempted to explain this observation.

The first explanation was infectivity [START_REF] Smith | The social evolution of bacterial pathogenesis[END_REF]: what is on a plasmid spreads to neighbors, and thus when cooperative genes are on plasmids they can "infect back" the cheaters that lost the social behavior by mutations. This view is however very limited if one considers that plasmids bearing cooperation genes are competing with "cheating plasmids", ones that lost the cooperation gene, and that can "infect" other cells as well as their cooperative competitors can.

Then the infectivity hypothesis does not a priori explain why cheating plasmids do not invade, it just moves the dilemma at the plasmid level. That lead to the second explanation of the relative prevalence of social genes on plasmids, which is that since plasmid transfer happens locally, it increases relatedness in spatially structured populations [START_REF] Nogueira | Horizontal gene transfer of the secretome drives the evolution of bacterial cooperation and virulence[END_REF][START_REF] Rankin | What traits are carried on mobile genetic elements, and why?[END_REF][START_REF] Mc Ginty | The interplay between relatedness and horizontal gene transfer drives the evolution of plasmid-carried public goods[END_REF][START_REF] Dimitriu | Genetic information transfer promotes cooperation in bacteria[END_REF]. The aforementioned papers place themselves in kin selection frameworks, or at least use island models (i.e. more group selection inspired frameworks) with a variable called relatedness and still call their work kin selection. In all cases the key idea is that plasmid transfer happens locally in structured populations, so it tends to 'homogenize' the neighborhood, which is favorable to cooperation (increased relatedness). next section. Their second argument highlights a weakness of the model, which does not really allow to disentangle the effects of kin selection and of infectivity. [START_REF] Mc Ginty | The interplay between relatedness and horizontal gene transfer drives the evolution of plasmid-carried public goods[END_REF] and [START_REF] Dimitriu | Genetic information transfer promotes cooperation in bacteria[END_REF] provide much stronger theoretical and experimental evidences of the role of horizontal transfer on increasing relatedness and favoring selection of cooperative alleles by kin/group selection, the question of the role of infectivity remains open. Indeed if we must obviously take into account competition with mutants plasmids, which [START_REF] Smith | The social evolution of bacterial pathogenesis[END_REF] did not consider, I believe there still may be room for complementary theories relying on the role of infectivity. To study such possible complementary explanations we must consider the many finer points and details about the mechanisms of infectivity such as potential non-linearity of transfer dynamics, potential plasmid recognition and/or exclusion mechanisms, copy number and dominance. Finally we should maybe consider the consequences of plasmids/chromosome genome partitioning under the angle of competition for "plasmid space". From a gene point of view, being on a plasmid comes with the benefit of higher infectious replication and transmission rate, but at the cost of high chances of being lost by segregation and maybe of higher mutation and recombination rate [START_REF] Cooper | Why genes evolve faster on secondary chromosomes in bacteria[END_REF]. The question of the role of infectivity thus goes a little bit deeper than just saying "everything that is on a plasmid will invade". In the last potential case we described, we could imagine something like a "sir Philip Sidney game" if the evolutionary "rescue" provided by plasmids comes at a cost that is acceptable for some genes only. This would then be a similar dynamics to those we can encounter when considering signaling theory: honest signaling equilibrium emerge when the benefit is higher or cost is smaller for the "honest" signalers [START_REF] Zahavi | Mate selection-a selection for a handicap[END_REF][START_REF] Smith | Animal signals[END_REF].

While Mc

The reason why we discussed the role of horizontal transfer in selection for cooperation is that there is a strong similarity between the paradigm shift that happened from "plasmids make cooperation genes invade" to "actually they also make cheating genes invade, but since they increase relatedness they still favor the spread of cooperation genes" and between the paradigm shift we are trying to introduce in the fifth chapter regarding the role of hitch-hiking in the evolution of cooperation.

Does increased relatedness balance increased competition among kin in structured environments?

While viscosity (limited dispersal) was one of the original mechanisms suggested by Hamilton as permitting kin selection, there has been some controversy about whether viscosity actually promotes cooperation. Indeed, it has been suggested several times that limited dispersal also increases competition (for resources and reproduction) among kin, countering the effect of kin selection and preventing the evolution of altruism.

There are two distinct problems with the work about the conflict between local increase in relatedness and in competition due to population viscosity:

The first one is a very restrictive group-selection view in which groups are so isolated that competition between groups does not exist anymore. For example [START_REF] Wilson | Can altruism evolve in purely viscous populations?[END_REF] and [START_REF] Taylor | Altruism in viscous populations-an inclusive fitness model[END_REF] apply population-size regulation at the group/patch level, preventing a group of cooperators to do better than a group of cheaters: fitness is effectively normalized inside the isolated groups. This obviously does not question kin selection, but does only question the ability of a very restrictive variant of group selection to give a real understanding of cooperation and competition.

Several lattice simulation and graph analysis papers also find an increased competition between kin disfavoring cooperation in a particular condition [START_REF] Taylor | Evolution of cooperation in a finite homogeneous graph[END_REF][START_REF] Ohtsuki | A simple rule for the evolution of cooperation on graphs and social networks[END_REF], which is the use of a birth-death process, where at each time point some individuals are chosen for replication according to fitness, and there is a randomly picked neighbor that dies to give space for each of these new individuals. On the other hand lattice simulations using death-birth processes, where at each time point some individuals are randomly picked for death, and there is a competition among neighboring individuals to decide who is going to reproduce to occupy the free spot, permit the evolution of cooperation [START_REF] Zukewich | Consolidating birth-death and death-birth processes in structured populations[END_REF].

These two problems are partially linked by the concept of 'circles of compensation', developed by [START_REF] Grafen | Natural selection of altruism in inelastic viscous homogeneous populations[END_REF]. The key idea is that when populations are inelastic as described above (fixed number of individuals), giving a fitness benefit to one recipient individual (performing an act of cooperation toward this individual) also implies giving a fitness penalty to all individuals competing with this recipient individual. Differently put, increasing the chances of the recipient to reproduce means decreasing the chances of some other individuals to reproduce or increasing their chances to die, since there is a fixed number of individuals. In the (here simplified) case of the birth-death process, the individuals that receive this penalty are exactly the neighbors (increased chances of death to leave room for the "extra" offsprings of the recipient), so are exactly the ones that (can) perform the cooperative act. It is thus easy to understand that the effects will balance each other. On the other hand in the case of the death-birth process, when a neighbors cooperate with a focal recipient, the benefit is an increase in chances of winning the competition to replace one randomly dying individual in the neighborhood. This competition is not only involving focal recipient and its neighbors, but also the neighbors of the neighbors, diluting the effect of increased competition on a larger scale than the effect of kin selection.

The conclusion of [START_REF] Grafen | Natural selection of altruism in inelastic viscous homogeneous populations[END_REF] is that except in very pathological cases where the two effects balance each other (such as a birth-death process), this increased competition exists but does not inhibit kin selection nor the (potential) spread and maintenance of cooperation:

There is very generally a 'balancing circle of compensation', at which the viscosity of the population slows up selection of altruism, but does not affect its direction, and this holds for altruism towards any individual, not just immediate neighbours.

Several experimental papers reach the same observations [START_REF] Kümmerli | Viscous medium promotes cooperation in the pathogenic bacterium Pseudomonas aeruginosa[END_REF] bringing a widely accepted conclusion: viscosity does promote cooperation, except maybe in a few extremely artificial cases (that may not even be possible in microbial populations), as was also shown by [START_REF] Zukewich | Consolidating birth-death and death-birth processes in structured populations[END_REF] and by [START_REF] Grafen | Natural selection of altruism in inelastic viscous homogeneous populations[END_REF]. It is interesting to notice the important role of models and computer simulations in this debate: they were largely at its origin because of the sometimes ill-advised approximations that are used to make the simulations doable (e.g. inelastic populations using birth-death processes), but were also an important part of its resolution.

To complicate further the picture, we must also stress that many models, including the ones we use in the first, second, fourth and fifth chapters of this thesis, simulate non-overlapping generations (the whole population is competing and replaced at the same time point). It is however easy to see that this is just an extreme case of death-birth process, and there is thus no reason to think this class of models would hinder cooperation. A few papers [START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF]) that claimed otherwise were biased by their use of the snowdrift game, which promotes diversity between neighbors and favor cooperators when at low frequency. For more detailed arguments in favor of non-overlapping generation models, see the fourth chapter.

While as we saw some modeling details may easily bias the outcome, one should not disregard these problems as being mere modeling issues. Indeed, we could argue that the differences between the different classes of models that we just mentioned are exactly the differences between Fisher-Wright and Moran population genetics frameworks. Considering the model details can thus lead to new insights and better understanding of cooperation in the lab and in nature.

The role of game theory in evolutionary biology and in social evolution

Biological evolution is not only a competition between organisms to adapt to an extrinsic environment. Biological agents are themselves shaping the environment and interacting together. Surviving is not just about doing well but it implies doing better than others. The application of Von Neumann's game theory to evolutionary biology has considerably enhanced our vision of evolution, and has provided an extremely powerful class of models and frameworks. These frameworks have proven themselves particularly useful for some classes of evolutionary questions in which the interactions between individuals are critical, including social evolution or host parasite interactions [START_REF] Turner | Prisoner's dilemma in an rna virus[END_REF]. One of the most remarkable parts of this success story is probably that refinements in Von Neumann's work introduced by biologists for their needs have been integrated back into game theory and are now used in other fields such as economics! We can for example cite the concept of evolutionary stable strategy, introduced by Maynard Smith and [START_REF] Smith | lhe logic of animal conflict[END_REF], which is now also a classic concept in economics [START_REF] Friedman | Evolutionary games in economics[END_REF].

One other interesting extension of classical game theory, still in the context of cooperation, is the introduction of the iterated prisoner dilemma by [START_REF] Axelrod | The Evolution of Cooperation[END_REF]. Since players will keep the interactions in memory, the "strategy" is no longer a binary behaviour, but a set of rules defining how to play against one particular individual taking as input his previous moves.

Extending the question of the unit of selection to memes and cognition

The aforementioned iterated prisoner dilemma work raises the question of a parallel between cognitive learning and biological evolution. Learning in animals has for a long time been seen as the association of a behaviour with a result, through repeated trials, leading to the adoption of the behavior that maximizes the outcome in a given situation. This view of learning was the cornerstone of behaviorism [START_REF] Watson | Psychology as the behaviorist views it[END_REF][START_REF] Skinner | Science and human behavior[END_REF], and it inspired an entire field of computer science, Machine learning, that relies on this idea of reinforcement learning. Behaviorism was however extremely limited by its methods and its conceptual choice of considering the individual as a black box who computes an answer for a given stimuli. The mechanistic of learning and the cognitive processes are deliberatively excluded, if not denied.

This behaviorist learning theory is close to biological evolution in the sense that individuals would adapt their behaviour to maximize their payoff. However it is also far in the sense that it entirely denies the possibility of inheritance of behavioral traits. [START_REF] Lorenz | Der kumpan in der umwelt des vogels[END_REF] and [START_REF] Tinbergen | The study of instinct[END_REF] were the first to re-integrate inherited instincts into a biological evolution perspective.

The death of behaviorism relied on two major ingredients that bring an even deeper parallel with biological evolution. The first one is cognitive sciences and evolutionary psychology. The whole field of evolutionary psychology relies on a parallel between cognition and biological evolution. It goes as far as talking about modular brain or modular mind [START_REF] Fodor | The modularity of mind: An essay on faculty psychology[END_REF], suggesting the existence of specific modules of the brain being directly subject to natural selection. A parallel can be made with the introduction of memetics by [START_REF] Dawkins | The selfish gene[END_REF], which emphasizes that ideas, beliefs, cultural elements, visions of the world, which he refers to as memes, are also entities subject to natural selection and evolution. Memes are competing and spreading through their selective value (fitness), which relies on the behavioral traits they cause in their hosts. For example, cooperation, exemplified in humans by charity at a personal and institutional level, might be understood as being the consequence of an idea of fairness or of human dignity that has evolved for the same reasons as a cooperative gene in a bacterial population. Evolutionary psychology historically had a strong affinity with group selection, but nothing prevents the expression of these reasons in another framework. The selection is thus not acting directly on a behaviour ("give money to homeless people") or a gene coding for this behaviour, but on a meme ("human has the right to housing") that causes a behaviour which can be seen as the phenotype.

The second area whose development helped to bring down behaviorism is neuronal studies, teaching us more about the decision making processes. A key advance was the discovery that an individual is able to have neural representations of its possible behaviours, and to associate them with an outcome at a neural -biochemical-level [START_REF] Bush | Dorsal anterior cingulate cortex: a role in reward-based decision making[END_REF]. The neuroscience of behaviour literature is even richer in the context of social behaviour [START_REF] Sanfey | The neural basis of economic decision-making in the ultimatum game[END_REF][START_REF] Clement | The pleasure of believing: Toward a naturalistic explanation of religious conversions[END_REF] and could potentially reveal more about one part of the proximate explanations for social behavior.

We must stress that this proximate state of several mechanisms, often discussed in the context of the evolution of cooperation, is not specific to the question of cognition and learning. In the same way that we must consider the moral side of apes as itself subject to evolution, we already emphasized the need for the same precaution when considering plasmid policing or punishment.

1.8 Moving the dilemma at a higher level (e.g. punishment, signaling or pleiotropy), and why does it matter?

We already saw how horizontal transfer does not fundamentally change the dilemma governing evolution of cooperation but does move it at a different level (competition between cooperative and non-cooperative plasmids). The same reasoning goes for two other mechanisms that have been extensively used in the evolution of cooperation literature: punishment and signaling.

We call punishment the costly act of inflicting a fitness cost to another individual in response to a non cooperative behavior, as we can find plenty of examples in microbial and animal societies [START_REF] Fehr | Altruistic punishment in humans[END_REF][START_REF] Raihani | Punishment and cooperation in nature[END_REF]. While punishment can stabilize cooperation (by making fitness of cheaters smaller than fitness of cooperators), it will be itself subject to "cheating". Starting from a well-mixed population of "cooperators" who are also "punishers", some mutants will stop punishing (but keep cooperating) and will invade because they are not paying the punishment cost. This invasion will happen because the population is well-mixed and thus the benefits of punishment are equally distributed between all cooperators while the cost is only paid by the punishers. The evolved lack of punishment that could prevent cheaters from invading would then lead to the extinction of cooperation. It is thus clear that punishment is a 'second-order' cooperating behavior, subject to the same dilemma (beneficial for the group, costly for the individual) and thus to cheater invasion when in a well-mixed population.

Another mechanism that has been suggested as a potential way to avoid cheating is recognition of other cooperators, to preferentially direct toward them the benefits of cooperation. This recognition can entirely change the fate of cooperation and lead to a vast sub-domain of the evolution of cooperation where agents keep a memory of the interactions [START_REF] Axelrod | The Evolution of Cooperation[END_REF], or even share knowledge of other agents' behavior to build a reputation system. However the complex human cognitive systems should not distract us from the underlying evolutionary biology question: if recognition abilities as well as phenotypic traits making possible such recognition are themselves subject to selection and evolution, how will they affect the selection at cooperative loci?

While we could imagine that cooperators express a visible phenotype (a "signal") and only cooperate with individuals displaying this visible phenotype, they would still be subject to invasion by mutants that express the visible phenotype but do not express cooperation ("signal blind" cheaters). This is for example what happens for Pseudomonas aeruginosa where several cooperative traits are controlled by a "quorum sensing", and as expected this does not avoid cheater invasion in well mixed populations. This is what lead Hamilton and Dawkins to theorize "green-beard" genes, that would both code for the expression of the signal and the answer to the signal (cooperate with signal producer), preventing the appearance of signal blind mutants by gene loss, since they would then not be able to produce the signal (Hamilton, 1964a,b;[START_REF] Dawkins | The selfish gene[END_REF]. These green-beard genes remained pure theory for several years before some experimental examples were found [START_REF] Keller | Selfish genes: a green beard in the red fire ant[END_REF][START_REF] Smukalla | Flo1 is a variable green beard gene that drives biofilm-like cooperation in budding yeast[END_REF]. We must however stress that while pleiotropy is quite common in the microbial world, mutations that un-couple the two effects would still be possible, but one could imagine "constrained" enough pleiotropy between signal production and cooperation that would decrease the risk of cheater mutants appearing [START_REF] Traulsen | Chromodynamics of cooperation in finite populations[END_REF].

Expanding a little bit on this last idea, we must mention that pleiotropy between cooperation phenotype and some essential private (impacting only focal individual) phenotype has been suggested several times as a possible mechanism to reduce the evolutionary potential toward cheaters. Indeed, [START_REF] Foster | Pleiotropy as a mechanism to stabilize cooperation[END_REF] found that in the social amoeba Dictyostelium discoideum, a common "cheating" mutation (decreasing chances of being part of the stalk that will die to give the spores better spreading chances) also induces a private fitness cost. Similarly, [START_REF] Dandekar | Bacterial quorum sensing and metabolic incentives to cooperate[END_REF] found that in Pseudomonas aeruginosa, the same promoter (regulated by a complex quorum sensing) controls the expression of both a public good (protease) and a "private" trait (ability to use adenosine as a carbon source), making a large part of "cheater" mutants also suffer from a private fitness cost (one of the "easiest" way to entirely silence a gene without "side-effects" being inactivating its promoter). This work on cooperation and pleiotropy is closely related to one key idea we will develop in this manuscript (chapters 2 and 3), which is that gene overlap can be selected for as an evolutionary constraint that reduces the evolutionary potential of some sequences.

Considering that these mechanisms (punishment, signaling, pleiotropy) that were suggested to "protect" cooperation are themselves subject to selection (the cooperation dilemma repeating itself at the loci controlling them), we must wonder: do they bring any new insights into the evolution of cooperation?

If we just think in terms of selection for or against cooperation, then these additional mechanisms do not matter: they just move the cooperate / do not cooperate dilemma to a different level (punish the cheaters / do not punish the cheater, respond to signal / do not respond to signal, . . . ).

But punishment, signaling and pleiotropy are important if we see cooperation as a dynamical equilibrium. Simulations of simplistic binary genotypes on lattices, such as the ones performed by [START_REF] Nowak | Spatial games and the maintenance of cooperation[END_REF], will easily convince us that what we can measure as an apparently stable "average outcome" (proportion of cooperators) is actually the result of averaging (over the population) a complex dynamics that involves a permanent "birth" and "death" of "patches" of cooperators. When two or more cooperators are in the same neighborhood, relatedness can be high enough for the patch of these individuals to "expand". This co-occurrence of cooperators can randomly happen by genetic drift if selection coefficients1 of the cooperative mutations are low enough or more artefactually by several independent mutations. The expanding patch will still maintain high relatedness, the cooperators "inside" it potentially bringing enough benefit to the cooperators "at the edges" to sustain the expansion. At some ineluctable point, a mutation will make a cheater appear at the "middle" of the patch and reproduce faster than the surrounding cooperators, eventually leading to all the cooperators in the patch going extinct. So what can appear as a stable cooperative system if only looking at average among the population is actually a dynamical equilibrium between two selective dynamics happening at different scales: cooperators constantly forming expanding patches that take over patches of non cooperators, and these cooperator patches constantly being invaded "from the inside" by cheater mutants.

There is thus no doubt that any change in the rate of mutating from cooperator to cheater (or in other key parameters of the system) may have a huge impact on the average evolutionary outcome at the cooperative locus, by moving the equilibrium between these two dynamics. It can slow down cheater invasion enough at the within patch level so that more (relative) weight will be given to the competition between patches. This is exactly the kind of effect that punishment [START_REF] Baranski | High-order punishment and the evolution of cooperation[END_REF], signaling [START_REF] Jansen | Altruism through beard chromodynamics[END_REF] or pleiotropy [START_REF] Frénoy | Genetic architecture promotes the evolution and maintenance of cooperation[END_REF] may have. They do not change the dilemma, but they move the equilibrium between the two key dynamics to a region more favorable to cooperators. Same goes for horizontal transfer, that may homogenize the neighborhood and thus increase relatedness [START_REF] Dimitriu | Genetic information transfer promotes cooperation in bacteria[END_REF].

Even when not necessary for cooperation, these mechanisms can be selected because they move the equilibrium in a higher "group fitness" zone or because they increase relatedness. As we will see in the second and third chapters, it is in the light of the shifting equilibrium we have just described that our results on the evolutionary consequences of overlapping genes should be interpreted.

A benefit of group/multi-level selection framework: the dynamical equilibrium is more explicit

While we previously saw that kin selection frameworks sometimes tend not to make explicit enough the fact that relatedness is an evolving, dynamical, non-predictive parameter, the group selection framework has the advantage of making more obvious that there is no binary outcome but an equilibrium between two dynamics. The group selection frameworks directly consider both the cheater invasion (tragedy of the commons) inside patches and the competition between patches promoting cooperators higher fecundity.

Some group-selection frameworks make this equilibrium even more obvious by making birth and deaths of groups mathematically explicit [START_REF] Simon | Towards a general theory of group selection[END_REF] however we loose the 'emergence' property of our individual-based models. In individual based simulations, such as the Aevol platform I use in this work, groups do not need explicit representations and spatial structure is itself evolving. Island models are an intermediate option: they impose a strong spatial structure, but usually do not go as far as making group reproduction/death explicit.

Second order selection

From a computational biologist point of view, second order selection is just the fact that the "parameters" of natural selection, e.g. mutation rate, genome size or percentage of non-coding DNA, are themselves properties of the individual that are subject to selection. These parameters are evolving to maximize the fitness of the individual (or of its genes) in a broader sense than usual: we must not only consider an individual's number of offsprings, but also the fitness of its offsprings, i.e. their ability to survive and themselves generate fit offsprings. The position of an individual on the mutational landscape then becomes as determinant as its phenotype in assessing its long term evolutionary success.

The vast majority of experimental evidences for second order selection involves microbes or digital systems. Let us first briefly mention "classical" experimental findings about second order selection in microbes, before discussing in more details the contribution of digital systems. We will focus on second order selection for three broad categories of traits: mutation rate, Introduction robustness and evolvability.

Selection for elevated mutation rate

Very high chemical mutation rate was a huge barrier to the early development of life since individuals need to be able to sustain their own information in order to evolve complex features. Bacteria have evolved fascinating DNA repair systems to decrease mutation rate well below what their DNA polymerase is able to achieve on its own. It is however not un-common to find in natural isolates of bacteria a fraction of individuals having a higher mutation rate because of a deleterious mutation in this repair system. While this could be non-adaptive mutations only maintained by genetic drift, it seems that a high mutation rate can actually be adaptive [START_REF] Taddei | Role of mutator alleles in adaptive evolution[END_REF][START_REF] Tenaillon | Second-order selection in bacterial evolution: Selection acting on mutation and recombination rates in the course of adaptation[END_REF][START_REF] Woods | Second-order selection for evolvability in a large Escherichia coli population[END_REF], because it allows the fixation of "new" beneficial alleles. A high enough mutation rate can be especially beneficial, if not crucial, when facing changing environments [START_REF] Giraud | Costs and benefits of high mutation rates: Adaptive evolution of bacteria in the mouse gut[END_REF]. Moreover bio-informatics analysis [START_REF] Rocha | Over-representation of repeats in stress response genes: a strategy to increase versatility under stressful conditions?[END_REF] suggested that these DNA repair genes are coded by sequences exhibiting high number of nucleotide repetitions, which are known to be extremely mutagenic sequences. Such encoding would promote the spontaneous generation of "mutators" at a much higher rate than what could be achieved if these DNA repair proteins were encoded in a way less prone to replication errors. Both the aforementioned experiments and bioinformatic analysis suggest that there is a selection for a high stochastic generation of mutator alleles that could then hitch-hike with the beneficial alleles they allow to evolve, and thus temporarily spread in populations.

Stress-induced mutagenesis

The most fascinating (and controversial) part of the second order selection story is stressinduced mutagenesis: it has been suggested (and weakly demonstrated) that when facing many stresses (which are often a precursor of death of the colony, or at least of serious troubles), bacteria increase their mutation rate, increasing genetic diversity among the offsprings and thus the probability that one of them would be able to face the stress. A few recent examples include stress induced by sub-inhibitory doses of antibiotics [START_REF] Foster | Stress-induced mutagenesis in bacteria[END_REF][START_REF] Gutierrez | B-lactam antibiotics promote bacterial mutagenesis via an rpos-mediated reduction in replication fidelity[END_REF][START_REF] Laureti | Bacterial responses and genome instability induced by subinhibitory concentrations of antibiotics[END_REF]. One should however be aware that the validity of these data strongly depends on the ability to correct the estimated mutation rate by the total number of DNA replication events leading to the "observed" final population. In the case of antibiotic treatment even at sub-inhibitory doses, which are not necessary sub-lethal, the estimate of the number of replications can be imprecise and more importantly can vary between the treatment and the control.

Aging has also been suggested to be a stress inducing higher mutagenesis by [START_REF] Bjedov | Stress-induced mutagenesis in bacteria[END_REF], however [START_REF] Katz | Elevated mutagenesis does not explain the increased frequency of antibiotic resistant mutants in starved aging colonies[END_REF] have shown that the observed signal of accumulation of mutants largely comes from a higher fitness in aging conditions arising from one particular mutation.

Going a little bit further than pure mutagenesis, diverse stresses are also known to increase the uptake of exogenous DNA in bacteria [START_REF] Slager | Antibiotic-induced replication stress triggers bacterial competence by increasing gene dosage near the origin[END_REF], or again to increase recombination rate [START_REF] Guerin | The sos response controls integron recombination[END_REF], both of these effects also increasing the variability among the descendants and thus the chances that one of them will have a genome able to face the stress.

Selection for or against robustness and evolvability at the sequence level: bio-informatics evidences

There are two main ways of achieving mutational robustness at the sequence level: having a sequence not prone to replication errors (e.g. avoiding repeated nucleotides) and having a sequence for which a large fraction of the likely-to-happen mutations are neutral. There are bioinformatics evidence of selection for mutational robustness using both of these mechanisms. The second one is obviously more interesting, and it seems that redundancy of the genetic code favors a rather large proportion of synonymous mutations. But because genetic-code has co-evolved with coding sequences and is subject to important biochemical constraints, it is hard to have a "neutral expectation" of what should be the proportion of deleterious mutants if there was no selection for mutational robustness. One interesting path can then be to study differential codon usage between several classes of genes. It is however hard to distinguish between "optimizations" to avoid replication errors or diminish their effect on fitness and optimizations of translational efficiency and accuracy [START_REF] Rocha | An analysis of determinants of amino acids substitution rates in bacterial proteins[END_REF][START_REF] Drummond | Mistranslation-induced protein misfolding as a dominant constraint on coding-sequence evolution[END_REF]. For example the most used codons are often also the ones that correspond to a higher abundance of tRNAs (because of a higher number of copies of these tRNAs on the genome), leading to a higher speed of synthesis.

Despite these methodological difficulties, there is some convincing bio-informatics evidence for second-order selection against replication errors [START_REF] Ackermann | DNA sequences shaped by selection for stability[END_REF], and for higher evolvability of surface antigens [START_REF] Graves | Natural selection promotes antigenic evolvability[END_REF]. However, these phenomena are generally not receiving much consideration from bio-informaticians. The use of Ka/Ks ratio to identify sites under selection is particularly prone to biases caused by these second order selective pressures, and is quite symptomatic of how little attention is given to the fact that some mutations are more likely to happen than others, and that the mutational landscape is itself subject to selection.

The particular selection against the generation of specific mutants is also referred as "evolvability suppression", term which emphasizes the "removing" of some evolutionary paths. The concept is slightly different from "mutational robustness" which designates the ability to avoid mutations or to cope with them in general. Evolvability suppression is quite interesting (Al-tenberg, 2005), because it generally concerns evolutionary paths that are increasing fitness in the short term, but will decrease it on the longer-term. If the path was not giving a short-term fitness increase, there would be no need for evolvability suppression since first order natural selection would eliminate mutants following this path. The long-term fitness decrease may for example arise from a decrease in mutational robustness leading to the accumulation of deleterious mutants.

Artificial-life evidences

There are two main historical Artificial life lines of evidence of the importance of second-order selection. The first one comes from experiments with the Avida in silico platform, and has been termed "Survival of the flattest" by [START_REF] Wilke | Evolution of digital organisms at high mutation rates leads to survival of the flattest[END_REF]. The key idea is that given a high enough mutation rate, genomes will favor occupying a flat region of the fitness landscape even if not obtaining the highest possible fitness rather than occupying a region with a higher fitness but steeper fitness slope. In the former case the ineluctable accumulation of mutations will keep the genomes in the same fitness peak, while in the latter case if the peak is narrow enough, most mutants would suffer an important fitness loss. This idea has latter been experimentally confirmed by [START_REF] Codoñer | The fittest versus the flattest: experimental confirmation of the quasispecies effect with subviral pathogens[END_REF] in RNA viroids and by [START_REF] Sanjuán | Selection for robustness in mutagenized rna viruses[END_REF] in RNA viruses.

The second evidence comes from Aevol, a different digital evolution system, and shows the spontaneous evolution of genome size in response to different mutation rates. The change in genome size creates a balance between mutational robustness (ability to maintain the integrity of the genome) and evolvability (ability to generate rare beneficial mutants driving adaptive evolution) that remains constant for populations facing different biochemical mutation rates [START_REF] Knibbe | Self-adaptation of genome size in artificial organisms[END_REF](Knibbe et al., , 2007a,b),b).

Both of these now classical results suggest that what we should call fitness is not directly the expected number of direct offsprings an individual produces. Instead we should integrate the fitness of the offsprings and their own probability of themselves generating fit descendants to construct a more accurate fitness measure.

As we saw, selection for mutational robustness (and a tradeoff between this robustness and evolvability) is now well established, theoretically and experimentally. But we should go a little bit further: building on this idea that more information is contained in the mutational landscape than in the phenotype of a focal individual only, we must keep in mind that mutational robustness in not the only selectable property of the fitness landscapes. We could imagine a selection to generate a particular type of mutants, with a different phenotype. For example [START_REF] Colizzi | Evolution of functional diversification within quasispecies[END_REF] show the evolution of a "master sequence" that generates "cooperative" mutants that "work together". This can been seen as a division of labour, but instead of relying on a phenotypic switch it relies on a genetic mutation.

In Chapter 4, we show the evolution of a dominant subpopulation of individuals "gener-ating" cooperators at a high rate, which can been seen as a division of labour, or as a soma and germ-line. This is a substantial example of how we should consider the phenotypes of the descendants of a focal individual when computing its fitness. In this case the "cooperatorgenerating" genotype becomes a cooperative trait in itself.

As we saw, Artificial life has helped a lot to investigate and conceptualize these ideas of second-order selection. One important point is that in digital systems, 'parameters' are usually much more separated from 'data' than in microbial systems. In microbes the proteins performing replication, synthesis and error correction are encoded by genes not biochemically different from other genes. To this regard, in electrical engineering nomenclature bacteria could be considered to have a Von Neumann architecture, like at least partially Avida, while Aevol has a Harvard architecture.

Artificial life, and its role in understanding evolution

We have emphasized how microbes make wonderful model organisms regarding the study of evolution in the laboratory, but they still have some limitations. While molecular biology tools are advancing fast, we still know (very) little about genotype to phenotype mapping in even the simplest microorganisms. This knowledge is necessary for a deeper understanding of the distribution of the phenotypic effects of genetic mutations, which is in turn necessary if we wish to study mutational robustness and evolvability.

In this context, in silico evolution systems have proved to be extremely powerful complementary tools for the study of evolution. While artificial life is quite old, the first platform to gain a broad recognition in the evolutionary biology community was "Avida". Initially developed by Chris Adami and Charles Ofria, it was soon adopted by some key evolutionary biologists, such as Richard Lenski, the collaboration between scientists from different disciplines from its early developments likely playing an important role in its success. We already mentioned one of the most striking (but not the only one, see also [START_REF] Lenski | The evolutionary origin of complex features[END_REF] and [START_REF] Misevic | Sexual reproduction reshapes the genetic architecture of digital organisms[END_REF]) insight got from Avida, "survival of the flattest".

In line with its predecessor Tierra [START_REF] Ray | An approach to the synthesis of life[END_REF], Avida is largely inspired by computer science and electrical engineering: the organisms that evolve are computer programs, competing for "ressources" that allow them to be "evaluated". Avida is an interesting point of convergence between biology and computer science: while several fields of computer science owe a lot to biology, for example cellular automata or genetic algorithms, they quickly "diverged" to develop on their own, irrespectively of evolutionary biology, and only very recently we started considering that these fields could bring something back to the study of organic living systems.

One of the main advantages of Aevol over Avida is its bacterial inspired genomic layer, which allows us to get better biological insights about the selective pressures shaping genome organization. We already described how Aevol has been used to study the evolution of genome size and proportion of non coding DNA. A large part of this PhD work relies on an extended version of the Aevol model, which includes a basic spatial structure and the ability for the organisms to cooperate by public good secretion.

These simulations are very different from what one usually calls "modeling" where one may, for example, build a system of differential equations to describe and investigate a phenomenon. As emphasized by [START_REF] Peck | Simulation as experiment: A philosophical reassessment for biological modeling[END_REF], performing Aevol or Avida simulations is closer to doing experiments, in the sense that we actually "run" something, then observe and interpret the results.

Individual based modeling (including both Avida and Aevol) can be particularly interesting in evolutionary biology. While more traditional approaches of population genetics rely on analytical models, we know that variables capturing average properties (and maybe a few measures of dispersion around the average) are often not enough to understand or predict complex evolutionary dynamics. The stochasticity of both mutations and selection are important complications for analytical modeling, and often lead to simplistic steady state approximations and to under-estimating the role of space [START_REF] Durrett | The importance of being discrete (and spatial)[END_REF]. On the other hand the explicit simulation of each individual is now often tractable on modern computing platforms. This is particularly true in the field of evolution of cooperation, where even simplistic binary systems with spatial structure must often be simulated because they are impossible to solve analytically due to space and stochasticity.

Having argued for the importance of simulations in the context of evolution, we still must stress important conceptual limitations of the approach. The goal of these models is neither to simulate nor to predict the evolution of a particular organism. Instead the goal of Aevol is to study the evolutionary processes, and the system is particularly well suited for studying the selection pressures on the genome structure connected with robustness and evolvability. It is in no way an accurate representation of E. coli, nor any other micro-organism, but should rather be seen as a model organism in itself, with different strengths and weaknesses (as a model organism) than E. coli. In the same way than microbial models played a huge role in molecular evolution, we believe that in silico systems such as Aevol and Avida have a great potential to expand our knowledge of second order evolution. Hopefully, these advances will happen in parallel with advances in bio-informatics of second-order evolution, and with higher availability of experimental data. Introduction evolutionary biology questions in the next few years.

My PhD work: links between second order selection and evolution of cooperation

While conducting a literature review and reading some rather old papers on social evolution to understand the "history" of the ideas I presented above, I found quite striking that the three big ideas that I developed in the "results" part my PhD were already alluded in a debate between V. C. Wynne-Edwards and J. Maynard Smith in 1963-1964 (debates were quite slow before the internet). I thus decided to briefly present these ideas in the context of this debate, by referring to specific arguments. An attentive reader might have noticed that I already referred to further development of this thesis in the above introduction, but for the sake of consistency I believe it is useful to summarize the questions and results here.

The question of second-order selection on social behavior, and specifically of evolvability suppression, is actually not new. It is fascinating to notice that one point of dispute between Wynne-Edwards and Maynard Smith was the potential selection against the occurrence of anti-social mutations. In the words of Wynne-Edwards ( 1963):

There appears therefore to be no great difficulty in resolving the initial problem as to how intergroup selection can override the concurrent process of selection for individual advantage. Relatively simple genetic mechanisms can be evolved whereby the door is shut to one form of selection and open to the other, securing without conflict the maximum advantage from each; and since neighbouring populations differ, not only in genetic systems but in population parameters (for example, mean fecundity) and in social practices (for example, local differences in migratory behaviour in birds, or in tribal conventions among primitive men), there is no lack of variation on which intergroup selection can work.

The answer of Maynard Smith (1964):

In fact, 'anti-social' mutations will occur, and any plausible model of group selection must explain why they do not spread.

Introduction evolution of this evolvability suppression, e.g. the outcome of a competition between individuals having this evolvability suppression and individuals not having it.

Idea 1, developed in chapter 1, 2 and 3, is that because of the huge effect of "cheater invasion" (tragedy of the commons), cooperative traits seem particularly prone to benefit a lot from "evolvability suppression" mechanisms. When an essential gene is (deleteriously) mutated during replication, one can "rely" on natural selection to purge the deleterious alleles. But when a cooperative gene is mutated, the mutant allele has a short-term, selfish, fitness benefit, so is likely to spread and be strongly detrimental to the whole population on the longer term.

Another fascinating point we should note in these sentences is that the idea of "population parameters" evolving themselves is not recent! There were already in these earlier works two ideas that are important in the context of this thesis: what is selected (a trait only meaningful at individual level or a 'population parameter') and at what level is it selected (gene level, individual level or group level).

Non-reproducing casts (e.g. in social insects) is an other problem that Maynard Smith (1964) also addresses:

There is one special form of group selection which is worth considering in more detail, because it can, perhaps, explain the evolution of 'self-sterilizing' behaviour; that is behaviour that leads an individual not to breed in circumstances in which other members of the species are breeding successfully. . . . The difficulty is that if the difference between breeders and non-breeders is genetically determined, then it is the breeders whose genotype is perpetuated. A possible explanation is that what is inherited is the level of responsiveness to the presence of other breeding individuals.

Maynard Smith concludes by acknowledging that group selection can indeed account for this kind of eusocial behavior encoded in an isogenic way (reproducing and non-reproducing individuals carry the same genes) under some specific hypotheses. He however clearly considers that these hypothesis (low gene flow between colonies, colonies founded by a very small number of individuals) are very restrictive, limiting the interest and appeal of this framework.

Idea 2, developed in chapter 4, further extends the concept of selecting a probability of performing a social behavior and not directly a 'constitutive' cooperative behavior.

If we zoom out a little bit, it is important to notice that eusociality and the existence of non-reproductive casts have been a huge point of friction between proponents of kin selection and group selection [START_REF] Fletcher | What's wrong with inclusive fitness?[END_REF].

A last point I would like to highlight from Maynard Smith paper is the question of 'homogenization' within groups as enhancing group selection:

The only difficulty is to explain how it comes about that all members of a group come to have the characteristic in the first place . . . There is also the possibility that it might spread through a group by cultural transmission, but this is unlikely to be important in animals other than man.

While Maynard Smith is a little bit dismissive of the possibility that cultural transmission may play an important role in the evolution of social behavior, he was still visionary! As we explained above, the problem here is that the first "versions" of group selection frameworks required isolated groups with homogeneity inside (groups of cooperators would be in competition with groups of cheaters), and one key question is then: how could these groups have formed? Except for very small group size, genetic drift seems unlikely to have such a strong effect. Even with more modern versions of group selection that can cope with non homogeneous groups, there is still the requirement of variations in the original group compositions for group selection to act.

And indeed this question of horizontal transmission (I use this intentionally more general term to include plasmid conjugation) as a mechanism creating homogeneity within and heterogeneity between groups, or relatedness according to one's favorite framework, has been and is still hotly debated. This is where idea 3 comes in, developed in chapter 5: in addition to genetic drift and horizontal transmission, we show that genetic hitch-hiking is a mechanism that can promote the evolution of cooperation because it increases the spatial assortment between kin, favoring the magnitude of kin/group selection. While it has previously been suggested that hitch-hiking helps to stabilize cooperation when already dominant because the most numerous population is more likely to find a beneficial "private" mutation [START_REF] Morgan | Selection on non-social traits limits the invasion of social cheats[END_REF][START_REF] Waite | Adaptation to a new environment allows cooperators to purge cheaters stochastically[END_REF], this same mechanism would also maintain a dominant cheater population. The idea that we introduce is that genetic hitchhiking increases relatedness: it is beneficial for cooperation not because only cooperative alleles can hitchhike, but because when considering that both cooperative and non cooperative alleles can hitchhike we will see an increase in relatedness (at locus coding for cooperation) due to the local spread of beneficial mutations (at other private loci).

So this last idea is very similar to the paradigm shift that happened regarding plasmid conjugation between infectivity and relatedness [START_REF] Mc Ginty | The interplay between relatedness and horizontal gene transfer drives the evolution of plasmid-carried public goods[END_REF][START_REF] Dimitriu | Genetic information transfer promotes cooperation in bacteria[END_REF]. Of course hitchhiking is not eternal and loci can unlink (otherwise any deleterious trait could infinitely hitchhike) but once again it is more about moving the dynamical equilibrium than changing the nature of the dilemma.

Synthetic biology: tools and applications

In the third chapter, we use a mix of algorithmic and synthetic biology tools to experimentally test the idea of evolvability suppression by gene overlap. The synthetic biology is there mainly as a tool to test evolutionary hypotheses. It is however interesting to note that evolvability suppression has also been discussed in biological engineering, because one key problem of the field is the evolution of engineered genetic circuits. The evolution generally proceeds in a direction that does not satisfy the engineer, bacteria tending to have their own evolutionary "goals" that rarely include over-expression of a fluorescent protein. As once said our friend E. Coline (personal communication), "t'es bien gentil avec ta GFP surpuissante, mais moi je vis dans un rectum, pas dans une boite de nuit".

The ability to design a genetic circuit in a way that would minimize some evolutionary paths (principally the ones involving gene loss) is thus an interesting challenge with a high potential [START_REF] Sleight | Designing and engineering evolutionary robust genetic circuits[END_REF][START_REF] Yang | Rationally designed bidirectional promoter improves the evolutionary stability of synthetic genetic circuits[END_REF][START_REF] Renda | Engineering reduced evolutionary potential for synthetic biology[END_REF], and while we do not think that we can be smarter than evolution, our tools are easy to sell in this context and may actually be effective, at least temporarily.

Part II

Results

Chapter 1

Robustness and evolvability of cooperation: the evolutionary history affects selection on secretion

This work has been published in the proceedings of Artificial Life XIII as [START_REF] Frénoy | Robustness and evolvability of cooperation[END_REF]. Only very minor typographic modifications have been made between the article and the chapter presented below.

Abstract

Robustness and evolvability are indirectly selected properties of biological systems that still play a significant role in determining evolutionary trajectories. Understanding such second order evolution is even more challenging when considering traits related to cooperation, as the evolution of cooperation itself is governed by indirect selection. To examine the robustness and evolvability of cooperation, we used an agent-based model of digital evolution, Aevol. In Aevol individuals capable of cooperating via costly public good secretion evolve for thousands of generations in a classical tragedy of the commons scenario. We varied the cost of secreting the public good molecule between and within individual experiments and constructed and evaluated millions of mutants to quantify the organisms' position in the fitness landscape. Populations initially evolved at different regimes selecting against secretion, and then continued the evolution at a reasonably low cost of secretion. The populations that experienced a very strong selection against cooperation evolved less secretion than the ones that initially experienced a less drastic selection against cooperation via a high secretion cost. The mutational analysis revealed a correlation between the number of mutants with increased secretion and the secretion level across all costs of secretion. We also evolved several clones of each population to highlight a strong effect of history in general on cooperation. Our work shows that the history Chapter 1 of cooperative interactions has an effect on evolutionary dynamics, a result likely to be relevant in any cooperative systems that are frequently experiencing changes in cost and benefit of cooperation.

Introduction

The interplay between robustness and evolvability is one of the central questions in evolutionary biology [START_REF] Wagner | Robustness and Evolvability in Living Systems[END_REF][START_REF] Lenski | Balancing robustness and evolvability[END_REF]. While mutation robustness should be beneficial, due to avoiding deleterious mutations and maintaining the organism's phenotype, without the ability to adapt to a novel environment the organism may perish in a changing world. Both selection for robustness and for evolvability are indirect, making these properties potentially difficult to investigate experimentally. Past research has found evidence that evolvability [START_REF] Bedau | Evolution of evolvability via adaptation of mutation rates[END_REF][START_REF] Earl | Evolvability is a selectable trait[END_REF][START_REF] Wagner | Perspective: Complex adaptations and the evolution of evolvability[END_REF][START_REF] Woods | Second-order selection for evolvability in a large Escherichia coli population[END_REF], as well as robustness can be selected for [START_REF] Altenberg | Evolvability suppression to stabilize far-sighted adaptations[END_REF][START_REF] Wilke | Evolution of digital organisms at high mutation rates leads to survival of the flattest[END_REF][START_REF] Misevic | Sexual reproduction reshapes the genetic architecture of digital organisms[END_REF][START_REF] Azevedo | Sexual reproduction selects for robustness and negative epistasis in artificial gene networks[END_REF] under a range of circumstances. However, in most of these studies the traits that evolved different robustness and evolvability had direct fitness benefit and were thus under direct selection. We extend this work by studying aspects of evolvability and robustness of an indirectly selected trait, specifically cooperation via public good secretion.

Cooperation among individuals is frequently present in natural world and yet it remains a fascinating evolutionary enigma. When helping others comes at a direct personal cost, natural selection predicts that individuals who do not cooperate would be favored over cooperating ones. A number of theories exist to explain the diversity and abundance of stable cooperation systems in nature, primarily relying on inclusive fitness, kin and group selection arguments [START_REF] Axelrod | The Evolution of Cooperation[END_REF][START_REF] Sober | Unto Others: The Evolution and Physiology of Unselfish Behavior[END_REF][START_REF] Lenski | Balancing robustness and evolvability[END_REF][START_REF] Nowak | Five rules for the evolution of cooperation[END_REF][START_REF] Lehmann | The evolution of cooperation and altruism-a general framework and a classification of models[END_REF][START_REF] Lehmann | Group selection and kin selection: two concepts but one process[END_REF]. Public good secretion in microbes has been a particularly successful model system for the study of the evolution of cooperation, allowing for great insight into the forces that shape its emergence and persistence (West et al., 2007a;[START_REF] Racey | The effect of elevated mutation rates on the evolution of cooperation and virulence of Pseudomonas aeruginosa[END_REF].

The majority of both theoretical and experimental work on robustness and evolvability has been done under either fixed environmental conditions or traits that have direct fitness effects. Here we study cooperation, a trait under indirect selection, during evolution in variable environment, where the fitness cost of cooperation changes. To investigate the effect of evolutionary history in general, and changing costs of cooperation in particular, on the evolution of cooperation, we use a digital evolution platform, Aevol. As in bacteria, the public good in Aevol is a molecule that is secreted into the environment at a cost and can then benefit both the producer and all its neighbors, acting as an agent of cooperation. After establishing the parameter range allowing for the appearance of secretion, we performed experiments investigating whether strong selection against secretion will lead to genotypes residing in regions of the fitness landscape far away from cooperation. In other words, we wanted to test the hypothesis of strong selection against secretion not only causing a direct pressure against secretion genes, but also an indirect pressure on the genome structure that will modify the generic architecture and make secretion genes less likely to appear via mutations. In nature, cooperative phenotype may have to repeatedly evolve after being outcompeted by "cheaters", organisms benefiting from the cooperation without contributing to it. Depending on phenotype frequencies and ecological interactions between different types of individuals present, the cost to benefit ratio of cooperation would change. Understanding these history effects is necessary for understanding the long-term evolution of cooperation and may also be relevant to treatment of bacterial infections whose pathogenicity depends on cooperation among individuals, such as Pseudomonas aeruginosa [START_REF] Griffin | Cooperation and competition in pathogenic bacteria[END_REF].

Methods

Description of the model system

In this study we use the Aevol platform [START_REF] Knibbe | The topology of the protein network influences the dynamics of gene order: From systems biology to a systemic understanding of evolution[END_REF][START_REF] Parsons | Sélection indirecte en évolution Darwinienne : méchanismes et implications[END_REF], an individualbased, genetic algorithm-inspired model aimed at studying the evolutionary processes. It is especially well suited for examining the indirect selection pressures on the genome structure due to microbial-inspired, complex genotype-phenotype map [START_REF] Parsons | Importance of the rearrangement rates on the organization of genome transcription[END_REF]. The genomic layer of Aevol is inspired by bacterial genomic, but should be general enough for our needs.

Aevol is an open-source project and is freely available at www.aevol.fr/download. In all our experiments we used the default parameters unless otherwise noted.

The genome of Aevol individuals is encoded by a double-stranded string of zeros and ones. The phenotype is a collection of traits that are represented by a 2D curve, each point on the curve specifying performance level for an abstract biological process, a metabolic trait. A single protein is obtained by transcription and translation of the binary genome strings, through a mathematical transformation. To be expressed, protein sequence must be found between start and stop codons, that in turn must be between a promoter and terminator sequences, and be preceded by a Shine-Dalgarno sequence. A protein can affect a number of different processes simultaneously, to a different degree, depending on its expression level. There is no explicit genetic regulation in this version of Aevol, but there are functional interactions (combining the effect of two proteins contributing to the same trait). The transcription efficiency, and thus the protein expression level can be affected by mutations in the promoter region. Such genotypeto-phenotype map is directly inspired by the complexities of bacterial genomics and allows us to study not only the evolutionary dynamics of phenotypic traits, but also the evolution of the genetic architecture supporting these traits, including the genome length, percentage of coding/non-coding DNA, number of genes, and number of operons (Knibbe et al., 2007a,b;[START_REF] Parsons | Importance of the rearrangement rates on the organization of genome transcription[END_REF][START_REF] Parsons | Sélection indirecte en évolution Darwinienne : méchanismes et implications[END_REF].

The fitness of an Aevol digital organism is a decreasing function of the gap between the curve representing its phenotype and a target curve representing the "perfect phenotype" for the chosen environment. This target phenotype is a combination of several gaussians, chosen by the researcher and fixed during the experiments. There may be many ways to encode the same protein and thus many genotypes may map to the same phenotype. Moreover, different phenotypes may have the same fitness. In our system, selection acts on the phenotypic variation created by random mutations of organisms' genome. We distinguish between two types of mutations: small mutations (single base substitutions, insertion or deletion of up to 6 neighboring bases) and large mutations (duplication, deletion, inversion, or translocation of a section of the genome whose size and location are chosen at random). The mutation rates we used are 5 * 10 -5 per nucleotide per generation for small mutations, and 5 * 10 -6 for large mutations. Given the typical genome size of 10 4 bases, for each individual we expect about one small mutation per generation and one large mutation every 5 generations. The stochastic nature of our model is derived from the random choice of mutations at each generation, combined with the probabilistic selection which we describe below. By modifying the random number seed, we can perform multiple experiments with the same set of parameters and analyze the statistical significance of our results.

In order to study robustness and evolvability of cooperation we extended the Aevol system to include the possibility of secreting and consuming a public good, a diffusible, degradable molecule that is produced at a cost but confers a benefit to each individual absorbing it (West et al., 2007a;[START_REF] Racey | The effect of elevated mutation rates on the evolution of cooperation and virulence of Pseudomonas aeruginosa[END_REF]. Based on the studies of public good dynamics in Aevol and other systems [START_REF] Brown | The durability of public goods changes the dynamics and nature of social dilemmas[END_REF][START_REF] Misevic | Effects of public good properties on the evolution of cooperation[END_REF], we set the degradation rate to 10% per generation (the amount of the public good molecule that degrades each generation) and diffusion rate to 5% (the percentage of the public good that diffuses into each of the neighboring cells in the classical 3x3 Moore neighborhood). Under this scenario, 54% of the initially present public good remains in the grid cell after each generation.

To allow for the encoding of the public good production, we modified the genotype to phenotype map as follows: half of the phenotypic traits remain related to the "classical" metabolic phenotype and their levels have a direct effect on fitness, while the other half specifies the secretion-related phenotype. The metabolic fitness component is inversely proportionate to the gap between the metabolic part of the phenotype and the target phenotype. The gap between the secretion part of the phenotype and the secretion target phenotype is inversely proportionate to the amount of public good secreted by an individual. The total fitness of an organism is the combination of its metabolic fitness, the cost it pays for secreting the public good and the benefit it gets from any public good present in its local environment. To be precise, W = W met * (1 + B * (P G -C * S)), where W is the total fitness, W met is the metabolic fitness, P G is the amount of public good present in the local environment, S is the amount of the public good secreted by the individual, B is the contribution of cooperation to fitness (set to 0.5 in all our experiments), and C is the cost of secretion that we will vary in some of our experiments. As an individual does not directly benefit from the public good it secretes, but only from the public good secreted by its ancestors and neighbors, the selection for cooperation is indirect. Spatial structure is thought to have a major impact on the evolution of public-good secretion: cooperation is likely to be favored by kin selection when related individuals are spatially close to each other (West et al., 2007a;[START_REF] Nowak | Evolutionary games and spatial chaos[END_REF][START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF].

In order to enable the potential evolution of cooperation, our individuals evolve in a square toroidal grid with 1024 positions (32x32). Each position is inhabited by a single individual and there are no empty positions. The selection is done on a purely local basis: to compute a new generation, for each grid position we synchronously compete the nine individuals in its neighborhood. The higher the fitness of an individual is, the higher is the probability it will reproduce. All mutations happen during the reproduction step, after which the fitness of the new individual is recomputed, based on the changed levels of the available public good and mutations that occurred. To avoid the drastic decrease of the selection pressure as organisms approach the target phenotype, we use rank based, rather than fitness based selection in the neighborhoods. Additionally, the rank contributes exponentially to the probability of being selected for reproduction, in line with previous work on genetic algorithms in general and Aevol in particular [START_REF] Blickle | A comparison of selection schemes used in genetic algorithms[END_REF]Knibbe et al., 2007a). We choose the exponential rank selection parameters that give the individual with the highest fitness in the neighborhood a 31.3% probability of reproducing in the central cell of that neighborhood, while that probability is 1.8% for the individual with the lowest fitness. We determined these selection probabilities by testing a range of parameters and choosing ones that result in evolution of the highest level of secretion over time (data not shown).

Experimental design 1.3.2.1 Secretion cost and the evolution of cooperation.

The ratio between the cost paid by the individual that produces the public good and the benefit received from its consumption is a crucial parameter affecting the evolution of cooperation (Hamilton, 1964a,b;[START_REF] Nowak | Five rules for the evolution of cooperation[END_REF]West et al., 2007a). In order to quantify the dynamics of cooperation in Aevol under different cost-benefit ratios, we performed 50 experiments for each of the 7 different levels of secretion cost, C = 0.01, 0.05, 0.1, 0.2, 0.3, 1 and 2. Each experiment lasted 30, 000 generations and we recorded the average amount of the public good secreted by the individuals over time. We used the results from these experiments to inform our parameter

Historical cost of secretion and the evolution of cooperation.

To quantify the strength of the historical effects, as well as robustness and evolvability of cooperation in Aevol, we performed a series of experiments in which populations evolved for 10, 000 generations at one of the three regimes with different cost of secretion, specifically C = 0.8, C = 0.5, C = 0.35. We also tested an additional regime, N oSec, where the biological processes that were assigned to the secretion part of the phenotype are associated with metabolism instead and their optimal expression level is set to zero. The cost parameters we chose should completely inhibit the evolution of cooperation, or allow for it only at extremely low levels.

After 10, 000 generations the cost of secretion is set to C = 0.25 for all treatments, and the secretion target phenotype in N oSec treatment becomes the same as in the three other treatments. Specifically, the values y for all processes in the target phenotype with x ∈ (0, 1) are described by four Gaussian functions of the form y = He -(x-M ) 2 /2W 2 , where (H, M, W ) = {(0.35, 0.3, 0.04), (0.5, 0.2, 0.02), (0.5, 0.7, 0.02), (0.35, 0.8, 0.04)}. All processes with x-values less that 0.5 are associated with metabolism while the others are associated with secretion.

During all these experiments we recorded the average amount of secreted compound.

Mutational robustness.

We analyzed the genetic architecture of all the individuals from each population at generation 10, 000 by performing large number of mutations and recording the overall fitness and the amount of the public good secreted by the mutants. Each organism was reproduced 10, 000 times with its offspring having the probability of acquiring mutations in the same way as during the reproduction in typical experiments, for a total of 10, 240, 000 mutants analyzed from each population. We evaluated the frequency of beneficial, neutral and deleterious mutations as well as their magnitude.

History versus chance.

To quantify the effect of history (versus chance) on the amount of secretion after generation 10, 000, we performed an experiment similar to the classic "adaptation, chance and history" studies [START_REF] Travisano | Experimental tests of the roles of adaptation, chance, and history in evolution[END_REF][START_REF] Wagenaar | Influence of chance, history, and adaptation on digital evolution[END_REF]. In these experiments, for each of our cost treatments, we selected 10 populations at random as the available computational power did not allow us to study all 100 populations per treatments. Each of these 10 populations was cloned 10 times when releasing the secretion cost (generation 10, 000), to obtain 10 groups of 10 replicates. We measured the average amount of secreted compound during 3, 000 additional generations for each of these populations. An analysis of the variance between the different groups compared to the variance within each group provides a measure of the influence of history and chance on the evolution of these populations. We do not specifically discuss the effects of adaptation here as they are apparent from the change in amount of cooperation in all treatments.

Results and discussion

1.4.1 Direct relationship between evolved secretion and its cost.

The cost of secreting the public good had a direct and strong effect on the average amount of secreted public good molecule (Fig. 1.1). This is in accordance with our expectations, both in terms of the direct trade-off between cost and benefit of cooperation and in relation to classical results (West et al., 2007a;[START_REF] Nowak | Five rules for the evolution of cooperation[END_REF]. We used these experiments to establish a baseline cost of cooperation for which no population would evolve and maintain significant levels of secretion during at least the initial 10, 000 generations of evolution. In particular, we find that costs higher than 0.3 have this property and are thus suitable for use in the experiments from the second part of our study.

History affects future secretion levels.

The phenotype of individuals that evolved for 10, 000 generations under high costs of secretion or N oSec regime was generally identical: they did not secrete any public good molecules, as expected. However, once the selection pressure against secretion was released (at generation 10, 000), the fates of different populations quickly diverged. By 10, 000 generations, mutations and evolution erased any statistical differences between the treatments so we used an earlier time point in our analysis. Rather than using just the final secretion which may be strongly affected by stochastic factors, we measured the amount of cooperation that evolved by averaging the amount secreted during the first 3, 000 generations after releasing secretion cost (Fig. 1.2), and used the Mann-Whitney non-parametric test to compare different treatments. We find a general trend of lower secretion in populations that underwent the N oSec regime (strong direct selection against secretion) compared to the ones that experienced a high cost of secretion (less drastic selection against secretion) in their past (Mann-Whitney U test, p = 0.010). However we did not found any significant difference between the three secretion costs. This trend, although very noisy at our levels of replication, indicates that genotypes have preserved some information of their evolutionary history. The ones that evolved with strong direct pressure against secretion (N oSec treatment) are more robust and less likely to change, while the ones that evolved with less strong pressure via secretion cost are more evolvable.

Mutational robustness is strongly correlated with future secretion levels.

Specifically, we suspect that the genotypes that evolved robustness against secretion were located in regions of the fitness landscape mutationally far away from genotypes that confer the secretion phenotype. To test for such genotypic memory, we performed a mutagenesis test (Fig. 1.3), as described in the methods. We found a strongly significant difference in the proportion of mutants with increase in secretion (weighted by the magnitude of these effects) between on one side the three high cost treatments and on the other side the N oSec treatment (Welch's t-test, p = 0.0001), but no significant difference when comparing the three different costs between them. We furthermore found a very strong within-treatment correlation between the proportion of mutants with increase in secretion (weighted by the magnitude of these effects) and the average amount of public good secreted during the first 3, 000 generations after regime change (Table 1.1). This correlation is still present if we pool all the data, with the coefficient of correlation of 0.37 and p < 10 -13 , and suggests that history, encoded as genotypic memory, does strongly matter.

ANOVA shows a strong effect of history versus chance.

Following the experimental protocol described in the methods, we performed a one-way ANOVA to assess the influence of history (versus chance) on the evolution of secretion (Table 1.2). We found a significant influence of history for each of our three cost treatments, even if this history is not necessarily dependent on the cost of secretion, as we expected initially. As our previous experiments already found the N oSec treatment to have different historical effect on robustness and evolvability of the cooperation phenotype, here we omitted it from the analysis and focused instead on the historical effect of the three cost treatments.

Conclusion

Using the Aevol digital system we performed a series of experiments to test the effect of evolutionary history on the robustness and evolvability of cooperation. Our results generally showed a weak effect of the strength of selection against secretion on the future evolution of secretion, and a strong effect of history in general. The data was extremely noisy and may require a much greater number of replicates than we could produce for this study. The difference in the mutational neighborhood occupied by populations that have evolved at different secretion costs was not significant; however, the difference between the three cost-driven regimes (indirect pressure against secretion due to moderately high cost) and the NoSec regime (strong direct pressure against secretion) was large. Moreover the accessibility of beneficial mutations for secretion did strongly correlate with the amount of secretion in our experiments, generally validating the mutational analysis approach. The analysis of several clones of each population highlighted a strong influence of history on the robustness and evolvability of cooperation, however the cost of cooperation does not seem to be the main factor creating this history. Much research remains to be done in terms of fully understanding these complex interactions.

Chapter 2

Emergent genetic architecture promotes the evolution and maintenance of cooperation

This work has been published in PLoS Computational Biology as [START_REF] Frénoy | Genetic architecture promotes the evolution and maintenance of cooperation[END_REF]. Only very minor typographic modifications have been made between the article and the chapter presented below.

Abstract

When cooperation has a direct cost and an indirect benefit, a selfish behavior is more likely to be selected for than an altruistic one. Kin and group selection do provide evolutionary explanations for the stability of cooperation in nature, but we still lack the full understanding of the genomic mechanisms that can prevent cheater invasion. In our study we used Aevol, an agent-based, in silico genomic platform to evolve populations of digital organisms that compete, reproduce, and cooperate by secreting a public good for tens of thousands of generations.

We found that cooperating individuals may share a phenotype, defined as the amount of public good produced, but have very different abilities to resist cheater invasion. To understand the underlying genetic differences between cooperator types, we performed bio-inspired genomics analyses of our digital organisms by recording and comparing the locations of metabolic and secretion genes, as well as the relevant promoters and terminators. Association between metabolic and secretion genes (promoter sharing, overlap via frame shift or sense-antisense encoding) was characteristic for populations with robust cooperation and was more likely to evolve when secretion was costly. In mutational analysis experiments, we demonstrated the potential evolutionary consequences of the genetic association by performing a large number of mutations and measuring their phenotypic and fitness effects. The non-cooperating mutants arising from Chapter 2 the individuals with genetic association were more likely to have metabolic deleterious mutations that eventually lead to selection eliminating such mutants from the population due to the accompanying fitness decrease. Effectively, cooperation evolved to be protected and robust to mutations through entangled genetic architecture. Our results confirm the importance of second-order selection on evolutionary outcomes, uncover an important genetic mechanism for the evolution and maintenance of cooperation, and suggest promising methods for preventing gene loss in synthetically engineered organisms.

Author Summary

Cooperation is a much studied and debated phenomenon in the microbial world marked by a key question: given the survival of the fittest evolutionary paradigm, why do individuals act in seemingly altruistic ways, paying a cost to help others? Kin selection and group selection, together with mathematical tools from areas such as economics and game theory, have provided some answers. However, they largely ignored the underlying genetic and genomic mechanisms that drive the evolution of cooperation. In this study, we show that the architecture of the genomes has a major role in shaping the fate of cooperating populations. Specifically, we use an in silico evolution platform and discover that genes for cooperative traits are "hiding" behind metabolic ones by overlapping their sequences or sharing operons. In conditions where cheaters may outcompete the cooperators, this entangled architecture evolves spontaneously and effectively protects cooperation from invasion by cheater mutants. We describe a novel genetic mechanism for the evolution and maintenance of cooperation and, by taking into account the second order selection pressures on the genomes, highlight the need for going beyond simple game theory models in its study.

Introduction

The evolution of cooperation in microbial populations is a fascinating, rich and controversial evolutionary problem (Hamilton, 1964a;[START_REF] Axelrod | The Evolution of Cooperation[END_REF][START_REF] Buckling | Siderophore-mediated cooperation and virulence in Pseudomonas aeruginosa[END_REF][START_REF] Griffin | Cooperation and competition in pathogenic bacteria[END_REF][START_REF] Damore | Understanding microbial cooperation[END_REF]West et al., 2007a). The theoretical understanding of cooperation has been gradually advancing for decades, and recently those insights have also been applied to practical, medical problems, such as the treatment of infections triggered by cooperating, pathogenic bacteria (Brown et al., 2009b;[START_REF] Inglis | Spite versus cheats: Competition among social strategies shapes virulence in Pseudomonas aeruginosa[END_REF]. Most evolutionary explanations of cooperation rely on kin selection and group selection theories and are constantly being improved and refined by a host of mathematical tools [START_REF] Grafen | Natural selection, kin selection and group selection. Behavioural ecology: an evolutionary approach[END_REF][START_REF] Lehmann | Group selection and kin selection: two concepts but one process[END_REF]. Among them, the game theory and meta-population models have proved to be especially useful in the analysis of long term versus short term, as well as the individual versus population benefit of cooperation [START_REF] Axelrod | The Evolution of Cooperation[END_REF][START_REF] Kerr | Individualist and multi-level perspectives on selection in structured populations[END_REF][START_REF] Doebeli | Models of cooperation based on the Prisoner's Dilemma and the Snowdrift game[END_REF][START_REF] Antal | Mutation-selection equilibrium in games with multiple strategies[END_REF]. However, those methods tell us practically nothing about the evolutionary pressure on the structure of genomes that encode the cooperative traits. They typically do not distinguish between genotypes and phenotypes and consider only a finite set of possible behaviors (often only two: cooperate or not) with a constant extrinsic probability of switching between them. Although some recent papers do go further than evolving classical binary behavior by considering more complex stochastic strategies that take into account past interactions [START_REF] Iliopoulos | Critical dynamics in the evolution of stochastic strategies for the iterated prisoner's dilemma[END_REF], they also remain "one locus = one parameter" models, unable to consider genetic architecture of cooperation genes. Several experimental studies have shown the need to go beyond these limitations to understand cooperation in microbial systems. Specifically, Foster et al. demonstrated that the pleiotropic effect of a D. discoideum gene involved in a cooperative behavior (differentiation into prestalk cells) causes the mutations inducing cheating behavior to be associated with a direct fitness cost to the individual [START_REF] Foster | Pleiotropy as a mechanism to stabilize cooperation[END_REF]. Similarly, cheating mutations induce a cost in P. aeruginosa because of coregulation of public and "private" goods via the same quorum-sensing mechanism [START_REF] Dandekar | Bacterial quorum sensing and metabolic incentives to cooperate[END_REF].

We postulate that genomic architecture of metabolic and secretion genes -achieved by senseantisense coding or frameshifts -can provide a mechanism for the evolution and maintenance of cooperation that is similar but more basic than ones relying on genetic pleiotropy or coregulation. Here we investigate how two specific types of genomic architecture of cooperation genes may affect the evolutionary fate of cooperation itself. The first type relies on the concept of operons, already well described and investigated in the context of co-regulation or co-transfer of genes in the same operon [START_REF] Jacob | Genetic regulatory mechanisms in the synthesis of proteins[END_REF][START_REF] Lawrence | Selfish operons: the evolutionary impact of gene clustering in prokaryotes and eukaryotes[END_REF]. We specifically consider metabolic and secretion genes that have the same promoter and terminator sequence, thus sharing an operon. The second architecture type is the overlap, base-pair sharing between metabolic and secretion genes due to being in different reading frames or on different DNA strands. Although more rare in bacterial context, gene overlaps may be caused by the strong constraints on maximum genome size and have similar evolutionary explanations and properties as operons [START_REF] Normark | Overlapping genes[END_REF]. We describe and quantify the role of both these genetic architecture types and show that physical association of cooperation and metabolic genes, via operon and overlap, introduces an evolutionary constraint, pleiotropy in the broad sense, which prevents non-cooperating, cheater individuals from prospering and protects cooperation. Even though the same DNA coding for multiple proteins can, in a broad sense, be viewed as pleiotropy at the sequence level, as far as we know, its importance has never been described in the context of cooperation.

In all our experiments we use the Aevol platform (Knibbe et al., 2007a,b), an in silico experimental evolution system. While similar to existing individual-based, genetic-algorithm simulations, Aevol embodies a number of features inspired by microbial genetics that make it especially well suited for our study. For example, the phenotype of an Aevol digital organism is a continuous function comprised of a potentially unlimited number of biological processes and their performance level, which in turn allows for a continuous cooperating phenotype instead of the classical binary one. When it evolves, the cooperation among individuals is based on a public good molecule that diffuses and degrades in the environment. Individuals live in a spatially structured world, suitable for the evolution of cooperation [START_REF] Nowak | Spatial games and the maintenance of cooperation[END_REF][START_REF] Oliphant | Evolving cooperation in the non-iterated prisoner's dilemma: The importance of spatial organization[END_REF] and more similar to natural microbial populations than classical metapopulation models. The public good is costly to secrete but may benefit any neighboring organisms. Both indirectly selected secretion genes and metabolic genes contributing to fitness directly are encoded in the double-stranded genomes strings of zeros and ones. A set of rules for transcription, translation and protein synthesis governs the complex genotype to phenotype to fitness mapping. Phenotypically similar or even identical individuals can have different genotypes, thus also having different evolvability, robustness, and evolutionary fate [START_REF] Frénoy | Robustness and evolvability of cooperation[END_REF]. All these properties of Aevol set the stage for evolutionary experiments where genetic architecture constraints of cooperation can be both observed and described. We first demonstrate the existence of differences in the resistance to cheater invasion among several phenotypically equivalent populations. We then correlate the maintenance of cooperation genes with the abundance of promoter sharing or overlapping between metabolic and secretion genes. We hypothesize that such non-random encoding of the secretion is indirectly selected for in situations when cooperation is favored. Indeed, when evolving populations start from a naive, non-secreting ancestor, the cooperators employed this protective encoding, and more so when the cooperation cost was high. Mutational analysis confirmed that the constrained genetic architecture resulted in cooperation-destroying mutations also having a direct negative fitness effect. Overall, our results highlight the need for considering appropriately detailed and realistic computational systems and generally show the importance of second-order selection pressures and genetic architecture in the study and understanding of the evolution and maintenance of cooperation.

Results

Creating a bank of cooperators: general properties

In our modified version of Aevol dedicated to the study of cooperation, the phenotype is divided into two groups of traits: metabolism (biological processes allowing the individual to live and reproduce) and secretion (processes relating to the costly secretion of a diffusible public good molecule). Starting from an ancestor with a single, metabolic gene, we independently evolved 50 populations for 20, 000 generations. We effectively put cooperation under direct selection by using a particular fitness calculation in which secretion genes were treated the same as the metabolic ones during evolution. At the end of this phase, we chose the fittest individual from each replicate and, by simply reassigning half of the phenotype from metabolism to secretion, obtained 50 cooperators with high secretion levels. Specifically, their average secretion was 96.2% of the maximal secretion in Aevol, and the standard deviation in secretion was 3.89% of the mean. These individuals had generally comparable metabolic and secretion part of their phenotype with on average 19.2 genes in each.

Cheater invasion dynamics differs between populations

Using the cooperators from previous experiments, we started with 50 clonal populations that we then let evolve for an additional 5, 000 generations with a possibility of secreting at a moderately high cost (c = 0.4, see Materials and Methods for the effect of public good cost and fitness calculation details). Each of these populations was replicated 50 times, for a total of 2500 experiments. In all cases the amount of secretion greatly decreased, but not by the same amount or at the same rate (Fig. 2.1). To quantify these differences, we performed a one-way ANOVA on the average secretion between generation 200 and generation 1, 000, the visually chosen time interval during which cooperation is stabilizing to a new level after a quick and strong decay. We found a highly significant between groups effect (F = 138.2, p < 10 -37 ), each group consisting of the 50 populations that share a common ancestor, confirming that some cooperators are intrinsically more resistant to cheater invasion than others, even though they initially had very similar phenotypes. Moreover, there was no significant correlation between the ancestral cooperation level and the final one (r = 0.11, p = 0.44), eliminating the possibility of our results being driven by an initial difference in the population cooperation level.

When visually inspecting the phenotype of a randomly chosen cooperator and its descendants from the previous experiment, we also noticed that it was the same secretion genes that survived cheater invasion between several independent replicates of evolution. One such example, where the phenomenon was especially striking, is presented in Fig. 2.2. While we did not perform any statistical analysis because of the computational difficulty of tracking every protein for several thousands of generations, this observation motivated further experiments: it supports the idea that our 50 populations are different (in their resistance to cheater invasion) because their secretion genes are somehow different.

Genetic architecture and resistance to cheater invasion

To quantify the genetic architecture of 50 ancestral organisms we measured the percentage of secretion genes that (1) share an operon with at least one metabolic gene, (2) overlap with at least one metabolic gene, (3) satisfy at least one of (1) and (2), or (4) satisfy both (1) and (2) (see In the main figure each line represents the average secretion, over time, of 50 replicate populations started from the same ancestor. For clarity, we did not include the standard error of each group of replicate populations. The insert figure shows all 50 replicate populations for the two most extreme population groups, zoomed in on the time period of interest for our analyses. Specifically, of all the population groups sharing a common ancestor, the blue populations had the highest and red the lowest average secretion between generation 200 and generation 1, 000. Note that average secretion in the inset represents the average secretion within each population, whilst in the main figure it is the average of the secretion of all the individuals from the 50 replicate populations that share the same ancestor.

Material and Methods for more details). We then compared the genetic architecture measures with the resistance to cheater invasion, expressed as the average remaining secretion between generation 200 and generation 1, 000, as before (Fig. 2.3). We found that all four genetic architecture properties strongly correlate with the remaining secretion amount (r = 0.60 and p < 10 -5 for operon sharing, r = 0.57 and p < 10 -4 for overlapping, r = 0.63 and p < 10 -5 for at least one of them, r = 0.56 and p < 10 -4 for both of them), supporting our hypothesis that physical linkage between secretion and metabolic genes confers resistance to cheater invasions.

Mutation effects and resistance to cheater invasion

In order to confirm the effect of genetic architecture on cheater resistance, rather than examining the exact locations and interactions between genes and using them to infer population's Figure 2.2: Example of the preferential maintenance of certain secretion genes of a single cooperator from our bank. The bottom row of the graph (ancestor) shows the location on the phenotypic axis of the genes coding for secretion proteins in one cooperator organism from our bank. Above, the secretion genes from the best individual after 1, 000 generations of evolution in each of the 50 replicate populations descending from this ancestor are shown. Colors represent the height of the proteins encoded by the genes (see Materials and Methods for detailed explanation of protein properties in Aevol).

evolutionary fate, we directly quantified the effect of mutations on secretion and fitness. We constructed 10, 000, 000 mutants of each of the 50 ancestors, and calculated the mutational effect as the percentage of mutations that decrease the amount secreted without decreasing metabolic fitness, weighted by their negative effect on secretion. We found significant correlations between the mutation effect and both the robustness to cheater invasion (calculated as before, r = -0.367, p = 8.8 × 10 -3 ) and the genetic architecture (here defined as the percentage of secretion genes sharing an operon or overlapping with at least one metabolic gene, r = -0.430, p = 1.8 × 10 -3 ). Simply put, the individuals with genetic architecture that groups together metabolism and secretion genes exhibit higher resistance to cheaters, because they are subject to fewer mutations that would convert cooperators into cheaters without any direct fitness loss.

We thus have two measures that predict well the resistance to cheater invasion: genetic architecture and accessibility of mutations. Since the generation range used to quantify cheater resistance was chosen ad hoc, we also examined the effect of different ranges on the correlations. Interestingly, we found that genetic architecture is better correlated with cheater resistance when it is measured between generations 1, 000 and 2, 000 (r = 0.62 and p = 1.4 × 10 -6 ) than between generations 1 and 500 (r = 0.50 and p = 2.1 × 10 -4 ). Conversely, mutational effects are better correlated with cheater resistance measured in the early (generations 1 to 500, r = -0.56 and p = 2.1 × 10 -5 ) than late interval (generation 1, 000 to 2, 000, r = -0.26 and p = 6.6 × 10 -2 ). Overall, both genetic architecture and mutation effects are good predictors of how easily cooperators may be invaded by cheaters, but genetic architecture is better at predicting long-term effects, while mutational effects are more strongly correlated with shortterm ones. Mutations may affect long-term maintenance of cooperation in many ways and genetic architecture captures but one of them. As we elaborate in the Discussion section below, these results indicate that while all mutational constraints play a role, it is the overlap and operon ones that have the strongest long-term evolutionary consequences.

Preferential maintenance of secretion genes based on genetic architecture

We tested the importance of gene overlap and operon sharing in maintenance of cooperation by examining the extent of genomic connections between secretion and metabolism before and after the increase in secretion cost and the accompanying decrease in cooperation. After 2, 000 generations of evolution at a higher cost, the secretion genes still present are over 7 times more likely to overlap or share an operon with metabolic genes than the secretion genes a the start of the experiment (Fig. 2.4), with the difference being highly significant (Welch's t test, p < 10 -4 ). The proportion of all four categories of association between metabolic and secretion genes (share an operon, overlap, do at least one of them, do both) has increased, and all increases were significant (Welch's t test, p < 10 -5 for operon sharing, p = 1.9 × 10 -3 for overlapping, p = 1.1 × 10 -5 for doing at least one of them, p = 6.8 × 10 -4 for doing both). Note that these categories do not exactly correspond to the partitioning done on Fig. 2.4 (see Material and Methods for detailed explanation), but capture the same general properties of genetic architecture.

Evolution of genetic links between metabolic and cooperation genes

In the previous experiments we worked with already evolved cooperators, measured their resistance to cheater invasion and genetic architecture. We now turn to de novo evolution of cooperation, in order to show that gene overlap and operon sharing will evolve, via indirect selection pressures, in conditions moderately favorable for cooperation. Naive ancestors evolved for 20, 000 generations with cooperation cost of 0.3. In the final populations, individuals on average had 19 metabolic genes and 1.8 secretion genes. While the number of secretion genes is low, by pooling data of all 1024 individuals from each population we obtained a large number of genes that we could analyze. We compare the shared operons and gene overlap for metabolic and secretion genes with the same measures applied only within metabolic genes, as a control. The genetic architecture links between metabolic and secretion genes are on average 3 times stronger than within metabolic genes alone, the difference being highly significant (Fig. 2.5a, comparing the sum of the three bottom categories -dark blue, light blue and green -, Welch's t test, p = 1.0 × 10 -3 ). The proportion of all four genetic architecture categories differed between the two gene groupings, and all differences were significant (Welch's t test, p = 2.6 × 10 -3 for operon sharing, p = 3.0 × 10 -3 for overlapping, p = 1.0 × 10 -3 for at least one of them, p = 6.4 × 10 -3 for both). We repeated the analysis for 50 more populations that evolved under a lower secretion cost (c = 0.01) and we observed no difference in genetic association between metabolic and secretion genes compared to associations with metabolic genes alone (Fig. 2.5b, Welch's t test, p = 0.50). Comparison of the two sets of experiments performed at different secretion costs shows that the preferential association between secretion and metabolic genes evolves only when the cost of cooperation is relatively high.

Discussion

Our research was motivated by two simple observations: (1) phenotypically near-identical populations have different evolutionary fates (Fig. 2.1), and (2) for a given cooperator, the secretion genes that survive cheater invasion seem to be always the same between several replicates (Fig. 2.2); and by two straightforward questions: what were the differences between theses populations, and what were the differences between these genes? In our initial experiments we found that when populations cooperating at near-maximal level suddenly faced a direct, high cost of public good secretion, the cheaters were quick to invade. However, the invasion dynamic was qualitatively different across populations, with some ancestors predictably evolving In both cases, we quantified the presence of operons or overlaps between secretion genes and metabolic genes (S vs M) as well as between metabolic genes and other metabolic genes (M vs M). Genes were partitioned in four categories, labeled as in the Fig. 2.4: sharing a promoter (an operon) without overlapping with a metabolic gene (dark blue), overlapping and sharing an operon with a metabolic gene (light blue), overlapping without sharing an operon with a metabolic gene (green), not sharing an operon nor overlapping with any metabolic gene (red). Error bars represent plus and minus one standard error of the mean for the fifty replicate populations and their color corresponds to the genetic architecture category they relate to. into populations without any cooperation, while others kept low but non-zero levels of secretion (Fig. 2.1).

We propose that these diverging evolutionary fates for otherwise phenotypically similar populations are due to differences in the ancestral genetic architecture of cooperative traits. In a previous paper we showed that the accessibility of mutations impacting secretion may lead to different future secretion dynamics for phenotypically similar individuals [START_REF] Frénoy | Robustness and evolvability of cooperation[END_REF].

Here we show that in the case of cooperation decay, beyond the simple effect triggered by the accessibility of mutations impacting secretion, the way secretion genes "share" the genome with metabolic genes also has an effect on the selection of these mutations. More precisely, we suggest that secretion genes that are physically connected with a metabolic gene, for example belonging to the same operon, or physically overlapping, are more robust to cheater invasion: a deleterious mutation in one of these genes is more likely to also deleteriously affect a metabolic gene, and thus is less likely to be selected for. Similar mechanisms, coupling cooperative traits with metabolic, individualistic traits have been described before [START_REF] Foster | Pleiotropy as a mechanism to stabilize cooperation[END_REF][START_REF] Dandekar | Bacterial quorum sensing and metabolic incentives to cooperate[END_REF], but instead of relying on gene coregulation or genes with multiple effect, we report a more basic genetic mechanism of entanglement for genes with singular effects. Additionally, these studies remain two isolated data-points and are thus not enough to show the existence of second order selection pressures leading to such architecture. Bio-informatics methods could provide much more information to support or deny this hypothesis, however there have been very few relevant studies of the genes involved in cooperative behavior, the primary reason being the difficulty of identifying such genes. There is one notable exception [START_REF] Nogueira | Horizontal gene transfer of the secretome drives the evolution of bacterial cooperation and virulence[END_REF], where the authors use the prediction of cellular localization: outer membrane and excreted proteins are more likely to be related to cooperative traits than cytoplasmic, inner membrane and periplasmic proteins. Their main result is about the role of horizontal transfer in the evolution of cooperation, however they also show that genes coding for outer membrane and excreted proteins are more likely than others to be "genome neighbors" of addictive systems (e.g. toxin-antitoxin). As the experimental data is suggestive but overall still insufficient, the use of an appropriate individual based model dedicated to the study of evolutionary processes and selection pressures acting on the genome, such as Aevol, is a way to fill the void. Of course, each model has biases and limitations, however, the strong point of Aevol is that we implement only simple, easy to understand, small-scale rules inspired by bacterial genomics, and all other properties and processes are emergent. For example, in Aevol there is no parameter like "probability that two neighboring genes overlap". Thus, the outcomes we describe here are not directly driven by the model and are not something we necessarily expected to evolve.

Using Aevol we were able to directly test our hypothesis about the effects of genetic architecture on the evolution and maintenance of cooperation we generated and analyzed a total of 500, 000, 000 mutant organisms. About half of the mutants are phenotypically perfectly similar to the original individual (no mutations or only neutral mutations happened). The calculated probability of having no mutations for typical organism with genome length of 10,000 is 0.18. The calculated probability of having exactly one mutation is 0.31, and the one of having strictly more than one mutation is 0.51. We emphasize that a large part of the analyzed mutations are neutral but of course focus on the ones that change organisms fitness and secretion. We recorded the effect of all mutations, specifically searching among "cheating" mutations, the ones that would decrease the amount of secretion, for mutations that do not simultaneously decrease metabolic fitness, and may thus be selected for, or at least not immediately purged by selection. We find that the proportion of these mutations, weighted by their negative effect on secretion, directly and significantly correlates with the population's vulnerability to cheater invasion, which supports our hypothesis. Interestingly, when we measured the remaining cooperation later in time it correlated more strongly with amount of genetic architecture linkage between secretion and metabolism than the measured effect of the introduced mutations. The higher durability of genetic architecture constraints, compared to immediate mutation effects, may be due to the higher durability of the genetic architecture itself. As we saw from the comparison between different gene association categories at generation 0 and generation 2, 000, it is exactly the secretion genes that do overlap or share an operon with metabolic genes that may be preserved (Fig. 2.4). On the other hand, our mutational analysis explored only a small, nearby portion of the immense fitness landscape. As organisms evolve, and move around that landscape, the particular mutants we constructed and analyzed may become less accessible via mutations and thus also less relevant for the evolutionary dynamics. Finally, the enrichment of genotypically connected metabolic and secretion genes among all secretion genes present in the individuals strongly suggests that this type or architecture may generally be created and maintained via indirect selection in cooperative systems.

We should note that in our first set of experiments we used individuals that evolved under an altered fitness calculation regime that enabled us to directly select for future cooperators of similar phenotype but different genotype. We could have as well designed these individuals by hand, directly writing the zeros and ones in their genomes. However, this would have likely generated fragile and generally poorly adapted individuals, as evolution is typically better in organism design than us humans. The change between the alternative fitness calculation and the regular one may appear somewhat artificial or arbitrary, but it can also be seen as a transition from producing a private, non-secreted good, to a public, secreted one. Still, while these results show the effect that architecture may have on cooperation, they do not by themselves prove the existence of second order selection pressure that would be sufficient to create operon and overlap type constraints during the evolution and maintenance of cooperation. We thus turn to our second set of experiments, in which secretion evolves de novo, without ever being directly selected for.

The results of this second set of evolution experiments strongly support the hypothesis that when costly cooperation does evolve and persist, there is a selection pressure grouping secretion genes with metabolic genes to protect them from removal. Such selection pressure is necessarily indirect, since cooperation via public good secretion does not directly increase the fitness of the cooperating organisms. Additionally, it would not prevent any "cheaters" from appearing but would reduce their likelihood of having a greater fitness than cooperators and spreading, making overall conditions more favorable for cooperation by reducing the effective mutation rate for switching from being a cooperator to being a potentially invading cheater. Previous work has already established this "mutation rate" (in a binary, game theory vocabulary) is one of the very important parameters controlling the dynamics of cooperation in spatially structured populations [START_REF] Michod | Cooperation and conflict in the evolution of individuality. ii. conflict mediation. Proceedings of the Royal Society of London[END_REF][START_REF] Allen | How mutation affects evolutionary games on graphs[END_REF]. Here we extend these results by showing a specific genetic mechanisms that would allow evolution to modulate the rate of switching between potentially invading cheaters and cooperators. The total rate of production of cheaters may not be different between populations, but because of the genetic entanglement of cooperation and metabolism, a large proportion of cheaters is unable to invade and thus such cheater mutants are evolutionary dead-ends.

The role of constraints introduced by second-order selection, such as the one we exemplified here, in assuring the best long-term outcomes has been proposed before in a more general and abstract context [START_REF] Altenberg | Evolvability suppression to stabilize far-sighted adaptations[END_REF]. Specifically, our results may provide a set of new potential explanations for the evolution of operons and overlaps, important building blocks of life. While in the past operon and overlap existence has been linked to co-regulation and co-transfer of genes working together and belonging to the same sets of biological processes [START_REF] Lawrence | Selfish operons: the evolutionary impact of gene clustering in prokaryotes and eukaryotes[END_REF], here we highlight their role as an evolutionary constraint. Specifically, operons and overlaps may protect genes that are at risk of removal because of a short-term cost and in spite of the long-term benefit they may provide. Of course, the particular combination of short-term cost and long-term benefit is not unique to cooperation and it underlies other biological processes, most notably sex and recombination, which also continue to be intensely studied [START_REF] Rice | Experimental tests of the adaptive significance of sexual recombination[END_REF]. In terms of cooperation itself, genetic architecture constraints may be highly relevant in understanding the much studied siderophore-mediated cooperation in P. aeruginosa, where cooperative as well as essential metabolic traits are under the control of a quorum sensing mechanism [START_REF] Dandekar | Bacterial quorum sensing and metabolic incentives to cooperate[END_REF]. However, our idea also has large implications outside of the field of cooperation: going beyond explaining evolutionary outcomes, the genetic architecture coupling mechanism we describe here could be actively used to prevent mutations from removing of genes introduced into bio-engineering organisms, one of the major problems in the field of synthetic biology [START_REF] Sleight | Designing and engineering evolutionary robust genetic circuits[END_REF].

Conclusion

The study of the evolution and maintenance of cooperation is rich in theories, majority of which rely on higher level properties of individuals, such as relatedness, fitness, or group structure. Our experiments investigate basic, genome-level properties and show that the presence of genetic associations between metabolism and secretion genes aids the maintenance of cooperation across thousands of generations. Operon sharing and gene overlap are selected for when cooperation is costly and directly change populations' evolutionary fate. Second order selection is known to play a major role in the rapid evolution of microbial populations [START_REF] Tenaillon | Second-order selection in bacterial evolution: Selection acting on mutation and recombination rates in the course of adaptation[END_REF]) and here we contribute to understanding the specific and much studied case of cooperation via public good secretion. We used an in silico experimental platform, Aevol, which has enabled us to collect and analyze genetic architecture and evolutionary dynamics data in detail previously unattainable with either mathematical or experimental systems. The role of second-order selection and genetic constraints in evolution will undoubtedly continue to motivate experimental and theoretical research but in our case it also has the potential to inform bio-engineering and synthetic biology applications.

Chapter 2

Materials and Methods

Aevol digital evolution system

In this study we use the Aevol platform, an individual-based model of evolution, especially well suited for the study of selection pressures on genomic architecture (Knibbe et al., 2007a,b;[START_REF] Parsons | Importance of the rearrangement rates on the organization of genome transcription[END_REF][START_REF] Frénoy | Robustness and evolvability of cooperation[END_REF]. It is free and open-source software and is downloadable from http://www.aevol.fr/download. The specific version of the platform we used in this study, including analysis routines, parameter files, other minor modifications, is available on request. Aevol has already been used in several peer-reviewed publications including some that studied cooperation, so we invite the reader to refer to [START_REF] Misevic | Effects of public good properties on the evolution of cooperation[END_REF] for more information on how cooperation has been implemented and for characterization of the related parameters, and to (Knibbe et al., 2007b[START_REF] Knibbe | The topology of the protein network influences the dynamics of gene order: From systems biology to a systemic understanding of evolution[END_REF] for more general details about the original version of Aevol that did not incorporate cooperation.

In Aevol, the individuals are living on a toroidal, two-dimensional square grid, with each location being occupied by exactly one individual. In our experiments the grid contains 32 × 32 positions, for a total of 1024 individuals. Selection and reproduction are performed locally in a synchronous way: at each generation, for each position in the grid, we compete the nine individuals in the neighborhood to determine which one's descendant in going to occupy this position in the next generation.

The phenotype of an individual is represented by a two-dimensional curve describing the level of performance for each point of a continuous set of abstract biological processes. This is a very general way of encoding a phenotype without any restriction on the type of biological processes that can be represented. The genotype is a string of zeros and ones, which is transcribed and translated according to a bacterial genomics-inspired process: promoters and terminators are identified to allow transcription, then the transcribed sequences are searched for ribosomal binding site and start codon, followed by what will be a gene and then by an in-frame stop codon, to allow translation.

Our genetic code is an abstract mathematical function transforming the gene, i.e. the binary sequence between the start and stop codons, into three numbers, interpreted as a triangle on the axis of biological processes. These three numbers are M (mean position of the triangle on the phenotypic axis), W (half-width of the triangle), and H (height of the triangle). Base-pairs are read three by three, and our amino-acid space has eight symbols: START and STOP, M0 and M1 which are used to specify M , W0 and W1 which are used to specify W , H0 and H1 which are used to specify H (Fig. 2.6). Each of these eight amino-acids is assigned to exactly one of the eight (2 3 ) possible triplets. There is no redundancy in the codon-amino-acid mapping, however there is still a large redundancy in the gene-protein mapping because codons inside genes can be reordered without impacting phenotype. Specifically, what matters is the order of codons specifying the same triangle property (M , W , or H), while the relative order of codons for different properties can be altered freely. Once a coding sequence has been detected using the rules explained above and transformed into an amino-acid sequence, we extract from there three binary words (for M , W and H) according to the following process: amino acid X0 adds a 0 to the binary word of X and X1 adds a 1 to the binary word of X, where X is any of M, W, or H. We obtain an integer value for each of the three binary words by interpreting them using Gray code. Gray code is an alternative binary encoding in which two successive integers are encoded by binary numbers differing in only one digit. The integer values are then normalized by 2 n-1 where n is the number of codons used, and scaled to a [0, 1] interval for M , [0, 0.033] for W , and [-1, 1] for H. Finally the H value is multiplied by the transcription efficiency -a property of the promoter explained below. The mean position specifies the primary trait the protein affects, and as it is a real number, it allows for an infinite number of different traits. The height specifies protein's performance level for the primary trait, while the width determines all the traits a protein affects. Individual's phenotype is computed by summing up all the triangles encoded in its genome. There is no genetic regulation via transcription factors in this version of Aevol, however there are protein-protein interactions (two proteins contributing to the same biological processes) and transcription efficiency is regulated by the strength of the promoter (defined as the distance to a consensus sequence). As in natural systems such as bacteria or phages, this genomics allows two genes to cluster on the same mRNA (operon) or to physically use the same DNA basis in different reading frames or different senses (overlap). Examples of these different configurations are represented on Fig. 2.7.

The environment is represented by a two-dimensional curve indicating what is, for every possible biological process, the optimal level of performance in the given environment. The fitness of an individual is a decreasing function of the distance between the individual's phenotype and the optimal phenotype. Individuals are locally selected according to their rank in the neighborhood, with a probability of reproduction exponentially decreasing with the rank. The chosen individual will undergo reproduction with mutations (insertion, deletion or substitution of a small number of basis and duplication, inversion, translocation or deletion of a larger portion of the genome). The rates of different mutation types are parameters of the model and have been set to 5 × 10 -5 per basis for small mutations, and 5 × 10 -6 for large mutations. Ancestral genome is 5, 000 bases long and contains a single gene, while the typical genome length after several thousands of generations of evolution is around 10 4 basis. Aevol is a stochastic simulation, the variability coming from the randomness of mutations and the probabilistic selection. One of the parameter is the random seed used to initialize the random number generator. We can replicate an experiment by running it several times with the same exact parameters, but different random seeds.

In our experiments, we distinguish two categories of biological processes: the "metabolic" Figure 2.6: Aevol genetic code. Here we use an example of a functioning gene from an Aevol individual to explain the transcription and the translation processes. The gene is flanked by a promoter and terminator regions and preceded by a ribosome binding site (RBS). The codons for mean position, the width, and the height of the protein are identified, transformed into Gray code using the Genetic code table (box on the right), and finally scaled and normalized, as we summarize in the box on the left and describe in more detail in the Methods. Note that a gene with re-shuffled codons, for example H1 H1 M1 M1 M0 W1 W0 W1, would encode exactly the same protein. START codon may occasionally be found inside a gene, in which case it is interpreted as H0. The promoter differs from the consensus sequence by 1 base out of the maximal 4 differences allowed, giving it a 0.80 efficiency ones (all traits positioned before M = 0.5 on the axis of the biological processes), that allow an individual performing them to live and reproduce, and the "secretion" ones (position after M = 0.5 on the axis), that determine the level of the production of the public good. We note that under our setup, while genes are generally pleiotropic, simultaneously influencing multiple traits, it is not possible for a gene to affect both metabolic and secretion traits. The public good is costly to secrete, but diffuses in the environment and is beneficial to every individual that comes in contact with it. The cost for the production of one unit of public good varies in our experiments, but is always equal to the cost coefficient (parameter we set) multiplied by the amount of the public good produced. The fitness of an individual is given by this equation:

F m × (1 + 0.2 × (Get P G -cost × P roduce P G ))
Where F m is metabolic fitness (calculated as explained before but only considering the left part of the axis), Get P G is the amount of public good present in the environment at the location the individual inhabits, cost is the per-unit cost of the public good production, and P roduce P G is the amount of pubic good produced by the individual (computed similarly to metabolic fitness but considering the right part of the axis). 0.2 is a constant chosen based on previous experiments [START_REF] Frénoy | Robustness and evolvability of cooperation[END_REF]. As is often the case in natural systems, here the two digital genes belong to the same operon. They share a promoter and a terminator sequence and are thus being expressed at the same level. These hypothetical genes would belong to the "operon only" category from Fig. 2.4 and Fig. 2.5. (B) These two genes also share the same operon but additionally their sequences overlap, putting them in the "operon and overlap" category. In this case, the genes are in different reading frames and do not share a STOP codon, although such configuration is also possible. As the black gene boxes indicate, the left STOP codon corresponds to the left START codon, while the right STOP codon corresponds to the right START codon. (C, D) Two examples of genes from the "overlap only" category which are encoded on different strands. This is not an exhaustive list of possible genetic constraints, as a gene may, for example, share an operon with a gene on the same strand while simultaneously overlapping with a gene on an opposite strand.

The diffusion parameter is 0.05 per generation, meaning that five percent of the public good present at one position will diffuse in each of the eight neighboring positions during one generation. The degradation rate is set to 0.10 per generation, meaning that ten percent of the public good at each location will degrade during one generation. This degradation can be thought of as replacing any explicit consumption of the public good, but also as specifying the public good durability. Overall, in all our experiments, 54% of the public good present at generation n at some position will remain at this position at generation n + 1. In the Supporting Text S1, we experimentally show that the secretion mechanism implemented in Aevol, as described above, leads to the usual cooperation dilemma.

Evolving a bank of cooperators

To evolve a large number of strong cooperators, we assigned biological processes that were usually in the secretion part of the phenotype to the metabolic part of the phenotype, allowing a strong direct selection on them. After 20, 000 generations of evolution under these conditions, the whole phenotype of the individuals closely matches the target phenotype. Thus, when picking the best individual and re-assigning half of the trait axis back to secretion, we get a "near-perfect" cooperator, one that secretes close to the maximal possible amount of the public good. Evolving cooperators in this way makes secretion genes evolve in the same way as the metabolic ones, to a high level, increasing the potential signal in further experiments. We repeated this experiment 50 times, extracted the fittest individual from each population, and obtained a bank of 50 independently evolved cooperators.

Analysis of the genomic architecture

For each of the 50 cooperators we evolved in the first set of experiments, we analyzed the architecture of all its secretion genes and classified them in four different categories: (1) genes that share an operon with at least one metabolic gene without overlapping with a metabolic gene, (2) genes that overlap with at least one metabolic gene without sharing an operon with a metabolic gene (this is possible because our digital DNA is double stranded and thus allows for two reading senses, in addition to three reading frames for each sense), (3) genes that overlap with at least one metabolic gene and share an operon with at least one metabolic gene (not necessarily the same one), and (4) genes that share neither operon nor overlap with a metabolic gene. There are multiple ways one could classify the different genes, for example, by distinguishing the number of metabolic genes a secretion gene overlaps or shares an operon with. The four categories we chose have the benefit of intuitive simplicity in addition to including all secretion genes in exactly one category, and we have used them in Fig. 2.4 and Fig. 2.5. The number of genes in each category is always shown as a percentage of all the secretion genes and standardized by the genes' phenotypic area. Here, the phenotypic area refers to the area of the protein (triangle) the gene encodes for, and allows us to give more weight to the genes that have a strong impact on secretion as well as enable comparison between replicate experiments that may have different secretion levels.

However, when performing the statistical analyses to determine the correlation between the presence of overlap and the resistance to cheater invasion, it does not makes sense to, for example, exclude the secretion genes that also share an operon (in addition to overlapping) with a metabolic gene. So we use slightly different, larger, categories for secretion genes: share an operon with at least one metabolic gene (which is exactly the addition of categories 1 and 3 of our previously explained partitioning), overlap with at least one metabolic gene (addition of categories 2 and 3), do at least one of them (addition of categories 1, 2 and 3), do both of them (same than category 3), do none of them (same than category 4). The difference is that these categories are no longer exclusive: one gene can be in more than one of the new categories at the same time. The genes are standardized by their phenotypic area, as before. These regrouped categories are used in the statistical analyses throughout the paper, and can easily be visually inferred from the categories of the bar graphs in Fig. 2.4 and Fig. 2.5.

De novo evolution of cooperation

In these experiments, each population starts from a randomly constructed organism with a 5,000 base pair genome. As random sequences of 0's and 1's are generated, they are screened for the presence of open reading frames with genes. Thousands of sequences are tested and the first one that has exactly one metabolic gene with a positive effect on fitness is selected. This genome is then cloned to fill the population grid and form the starting population. Reason for starting with a single, valid gene rather than an organism with effectively empty genome is that in both cases all the genes except the first one have a very high probability of evolving from duplication followed by divergence of one already existing gene. Indeed, promoters and ribosome binding sites are hard to evolve from scratch. Starting from purely random sequence would only greatly slow down the evolution process (genomes could evolve for thousands of generation before the first gene appears (Knibbe et al., 2007b)) without qualitatively changing the understanding of the evolutionary process in our system. After 20, 000 generations of de novo evolution, we pooled the proteins from all the individuals in each replicate to obtain a measure of average genetic architecture within a population. As before, rather than using just a protein count, we standardized the contribution of each protein by its phenotypic area.

Supporting Information: cooperation in Aevol

Simulations have historically played a major role in increasing our understanding of the evolution and maintenance of cooperation in nature. Much of the research has followed a game theory paradigm, where at each generation, each individual is playing a prisoner's dilemma-like game with each of their neighbors. In such a setup it is rather easy to demonstrate that the exhibited behavior is indeed cooperation, as it just depends on the specific game played and parameters used. However, in our research platform, Aevol, cooperation is the production of a secreted public good that is explicitly subject to diffusion and degradation dynamics. Such implementation of cooperation makes things a little bit more complicated: the interactions between individuals can not be described using a pure game theory framework, because fitness/payoff of a focal individual depends not only on its own and its neighbors' behavior/strategy, but also on the history of the public good production in a large, neighboring portion of the space population inhabits.

In order to support our main finding, that genetic architecture is selected because it allows the maintenance of cooperation, we would first need to demonstrate that the secretion we see in Aevol is not just a deleterious/neutral bi-product of generic drift or constrained genetic architecture, but a process that is indeed favorable to the individuals performing it. We can briefly summarize the usual requirements for cooperation dynamics as follows: (1) for any individual, it pays more to defect than to cooperate, and (2) in a group of cooperators, the individuals do better than in a group of cheaters. In order to show this, we performed additional analysis of the 50 replicate populations evolved in our second experiment (de novo evolution of cooperation, cost of cooperation c = 0.3), at generation 20, 000. Besides recording the average amount of public good secreted by each individual and their fitness w, we also calculated two other, hypothetical fitness values: w no_sec , a fitness individual would have if it were not secreting but could still benefit from the public good present in the environment, and w no_coop , a fitness individual would have if it would experience neither the cost nor the benefit of cooperation. This allows us to compute both the cost of cooperation, w no_secw, as well as the benefit gained by cooperating, ww no_coop . Finally, rather than only looking at average values across the population, for all individuals in a population we also calculate the correlation between the amount secreted and the benefit of cooperation.

Using the empirical calculations of cost and benefit of cooperation, we can directly show that in all our experiments, there indeed is a temptation to stop cooperating, as on average, in each of our 50 populations the fitness of an individual would always increase if it would stop secreting (requirement (1) above, Supporting Figure 2.8). We also show that in the group of cooperators, individuals do better than in the group of cheaters, as the average fitness in the population would decrease if cooperation was completely disabled (requirement (2) above, Supporting Figure 2.9). Finally, we examined the 34 populations in which the average amount of secretion was significantly greater than zero (Wilcoxon signed rank test, with p < 0.05), and in all but three we find that there is a positive significant correlation between the amount an individual secretes and the benefit he gets from cooperation (measured as the Pearson's correlation coefficient r, with p-value p < 0.05), Supporting Figure 2.10. This reinforces the point that cooperation process in Aevol satisfies the requirement (2) and is a direct consequence of the spatial structure (viscosity) of the population, allowing non-random assortment of individuals.

Based on the analysis above, we can rule out the possibility that secretion is detrimental for the population but is maintained due to constrained genetic architecture or genetic drift. Instead, we conclude that the secretion behavior that evolves in our experiments satisfies the usual definition of cooperation and causes the standard dilemma (interest of the individual versus interest of the group), and that it may be selected for due to spatial structure. This provides a solid basis for Aevol to be used as an digital platform for the study of cooperation in the current, as well as previous and future studies. . Individuals that cooperate more are the ones that benefit more from secretion. For each of the 50 populations, we plot the correlation between how much individuals secrete, and how much they benefit from secretion (i.e. the average fitness drop individuals would experience if cooperation was disabled), against the average amount secreted by an individual in the population. Except in the populations where no cooperation has evolved (red points), the correlation is significant and positive for all but 3 populations.

Chapter 3 Experimental use of gene overlaps to protect costly genes: from algorithms to synthetic biology

This work was conducted in collaboration with Antoine L. Decrulle, Aude Bernheim, and Ariel B. Lindner.

Introduction

For evolutionary biologists

Overlapping genes are common in nature, more frequently in viruses but they also exist in bacteria, plants, and mammals [START_REF] Ellis | Genes within genes within bacteria[END_REF][START_REF] Veeramachaneni | Mammalian overlapping genes: the comparative perspective[END_REF]. They are usually thought to have evolved for the same reasons as operons: co-regulation of genes working together, co-transfer of genes working together, and more importantly compression of information (shorter genome size) [START_REF] Normark | Overlapping genes[END_REF][START_REF] Krakauer | Stability and evolution of overlapping genes[END_REF]. All these reasons do make perfect sense and are backed up by the fact that most gene overlaps are also operons [START_REF] Fukuda | On dynamics of overlapping genes in bacterial genomes[END_REF][START_REF] Sabath | Same-strand overlapping genes in bacteria: Compositional determinants of phase bias[END_REF], and that smaller genomes usually exhibit a higher number of overlaps. However, the work that we presented in the previous chapter suggests a possible additional role: evolutionary constraint [START_REF] Frénoy | Genetic architecture promotes the evolution and maintenance of cooperation[END_REF], or evolvability suppression, since the use of the same part of the genome to encode two proteins makes it harder for these proteins to evolve independently. This chapter focuses on building genetic overlaps using tools from computer science and synthetic biology. We conduct this work hoping both to add an element of proof to our hypothesis, and to suggest a new method to engineer evolutionary robust synthetic circuits.

For synthetic biologists

A large part of synthetic biology (new, fancy term for something not much different from goodold molecular biology) focuses on engineering bacteria to do "useful" things. A big problem in the field is that after synthetic systems are built and integrated in microbes, they will evolve and often inactivate the costly and over-expressed introduced genes because they decrease the fitness of the bacteria. Several labs have tried to reduce the evolutionary potential of these synthetic systems [START_REF] Sleight | Designing and engineering evolutionary robust genetic circuits[END_REF][START_REF] Yang | Rationally designed bidirectional promoter improves the evolutionary stability of synthetic genetic circuits[END_REF][START_REF] Renda | Engineering reduced evolutionary potential for synthetic biology[END_REF]. For example, Sleight et al. ( 2010) constructed an operon grouping the costly gene of interest (GFP, green fluorescent protein giving a phenotype measurable at population scale) with an antibiotic resistance gene (KanR), but showed only a minor and non-significant improvement of the evolutionary stability of the GFP when kanamycine is present in the medium. While this shows that an operon is not enough to protect GFP from loss of function mutations, the authors sequenced bacteria evolved in different setups (with or without the operon, with or without kanamycine) to understand how the GFP phenotype was lost. They found that without the selection pressure to maintain the activity of KanR in the same operon, the most common GFP-loss of function mutation happened in the (shared) promoter. However when they added kanamycine to the medium, the most common mutation was a frame-shift in the coding sequence of GFP. So while creating an operon with an "essential" gene was not enough to maintain the costly GFP, at least a part of the mutations causing loss of function of GFP, those that modify the promoter, are counter-selected thanks to this operon. The work presented in this chapter investigates the possibility of protecting costly genes by making them overlap with essential genes.

For computer scientists

We are interested in overlapping genes, and would like to better understand their potential role as an evolutionary constraints. To do so we want to construct, analyze, and evolve in the lab a synthetic system involving two overlapping sequences. Making two genes overlap without modifying the encoded proteins is a difficult algorithmic problem. We will present here two algorithms partially solving it: the first one, the RiBoSor, is by-passing a major algorithmic difficulty by creating a "fake" overlap (Figure 3.1) that is still an evolutionary constraint as we will show. The second one, the overlapor, is a smartly modified version of the Needleman-Wunsch algorithm. We extended the sequence alphabet to consider combinations of possible amino-acids at a given position, and made sure to keep the rewriting rules context-independent. However, to be efficient it requires a list of possible amino-acid changes that do not affect the protein function, similar to what has been done for lacI by [START_REF] Markiewicz | Genetic studies of the lac repressor. xiv. analysis of 4000 altered escherichia coli lac repressors reveals essential and non-essential residues, as well as "spacers" which do not require a specific sequence[END_REF] and for TEM-1 by [START_REF] Jacquier | Capturing the mutational landscape of the betalactamase tem-1[END_REF]. With the increased availability of genotype/phenotype mapping data, we expect that this algorithm could permit de novo engineering of long gene Chapter 3 overlaps in the next few years.

Why using synthetic biology (as a tool)?

As shown on table 3.1, there are relatively few big gene overlaps in E. coli. While the ones that do exist are potentially interesting and probably have complex and fascinating evolutionary stories, they are a priori not easy to work with, in the sense that the genes involved do not give visible nor selectable phenotypes. We report the name of the two involved genes, the configuration of the overlap ("Type", in the nomenclature described later in this chapter), the size of the overlap and the fraction of each of the two genes that is included in the overlap. The annotated genome was retrieved from NCBI GenBank and parsed with a Python script.

The RiBoSor

Explanation and proof of principle

RBS

Non-sense mutation can inactivate both genes plLacO gene2 gene1 RBS LacI IPTG gene2 starts here Figure 3.1: Fake overlap: we move the RBS-start of gene2 inside gene1 so any frameshift occurring between this new RBS-start and the end of gene1 will also be deleterious for gene2.

Chapter 3

The RiBoSor relies on the fact that a large portion of the most deleterious mutations are frameshifts, not base-pair substitutions. We put two genes under the control of the same promoter (pLac), gene1 being the costly gene we want to protect and gene2 being an essential gene under strong purifying selection. We remove the RBS and START codon of gene2 and create inside gene1 a new RBS-START in frame with the coding sequence of gene2. This new RBS-START will be the point of the translation initiation of gene2. We create it without changing the amino-acid sequence encoded by gene1 thanks to redundancy in codon to aminoacid mapping. We also remove every STOP codon in the frame of gene2 inside gene1, more specifically those that are downstream of the new RBS-START we created for gene2. The protein encoded by gene1 is not changed since we only made synonymous changes. The protein encoded by gene2 is now fused with a "random" sequence (the end of gene1 in another frame) on its 5' end, which hopefully will not affect the protein function. The assumption of conserved function for this fused protein might be a little optimistic, as it will probably depend on the protein encoded by gene2. Any frameshift mutation, i.e. indels of size that is not multiple of 3, occurring between this new RBS-START of gene2 and the end of the coding sequence of gene1, will affect both gene1 and gene2. Put differently, among all the mutations affecting gene1, a significant portion is also affecting gene2. The bigger the overlap, i.e. the closest our new RBS-START is to the 5' end of gene1, the bigger the proportion of mutations affecting both genes simultaneously. These mutations would be purged by natural selection if gene2 is under a strong purifying selection (for example, an antibiotic resistance gene in presence of the antibiotic). We are thus effectively protecting gene1 from some mutations thanks to the fake overlap 1 with gene2.

It is however not obvious how strong the protection of gene1 will be: it depends on the expected effect of a frameshift mutation in the coding sequence on protein function compared to the effect of a base-pair substitution, and of course on the proportion of mutations that are frameshifts. To have an estimate of the protection we can expect from our design, we performed Monte-Carlo simulations of mutations in our construct, evaluating the "deleteriousness" of each mutation for gene1 and for gene2. We modeled protein loss of function as a result of amino-acid change (non-synonymous mutation) as a Bernoulli process. We assumed that each amino-acid change gives P e chances of turning a fully functional gene into a non-functional gene. This is of course a simplification, since the activity of a protein is not binary. However, performing a large number of simulations allows us to say that "each amino-acid change has P e chances of making the protein non-functional" rather than saying, more biologically accurately, that "the average effect of each amino-acid change on continuous protein activity is P e , combined multiplicatively".

More formally, let us call f (i) the probability that the protein is still functional (or equiv-1 That we will also denote as riboverlap.

alently the average continuous protein activity normalized by the wild-type protein activity) as a function of i the number of amino-acid changes. Let us call e(i) the probability that the protein is not functional (or the average "impact" of amino acid changes) also as a function of i. We of course have f (i) + e(i) = 1, but sometimes it is easier to reason about the chances of the protein still being functional after mutations, sometimes it is easier to reason about the impact of the mutations, so we use both functions. We can calculate e(i) thanks to the recursion equation e(i + 1) = e(i) + (1 -e(i)) × P e , with e(0) = 0, and we get e(i) = 1 -(1 -P e ) i and f (i) = (1 -P e ) i . The parameter P e is probably strongly sequence dependent, and is hard to measure. Most of the "distribution of fitness effects" literature focused on RNA viruses, for which the estimate are quite high and vary from 0.19 [START_REF] Sanjuán | The distribution of fitness effects caused by single-nucleotide substitutions in an rna virus[END_REF] or 0.37 [START_REF] Peris | Distribution of fitness effects caused by single-nucleotide substitutions in bacteriophage f1[END_REF] to 0.76 [START_REF] Carrasco | Distribution of fitness and virulence effects caused by single-nucleotide substitutions in tobacco etch virus[END_REF]. The literature seems to suggest that bacteria would be closer to the middle or lower end of this fitness effect range [START_REF] Markiewicz | Genetic studies of the lac repressor. xiv. analysis of 4000 altered escherichia coli lac repressors reveals essential and non-essential residues, as well as "spacers" which do not require a specific sequence[END_REF][START_REF] Jacquier | Capturing the mutational landscape of the betalactamase tem-1[END_REF].

The other important parameter is f s, the proportion of frameshifts among all mutations, that is estimated in the literature to be between 0.1 and 0.4 for wild-type E. coli and up to 0.7 or 0.9 for specific frameshift prone mutators [START_REF] Lee | Rate and molecular spectrum of spontaneous mutations in the bacterium Escherichia coli as determined by whole-genome sequencing[END_REF][START_REF] Drake | A constant rate of spontaneous mutation in DNA-based microbes[END_REF]. From this, we can perform the Monte-Carlo simulations for each possible size of the overlap, or more precisely for all possible proportions of gene1 that are part of the overlap. The output measure of our simulations is: how much of the mutations impacting gene1 will be purged out by natural selection because they also impact gene2? We can see on figure 3.2 that it is possible to create a reasonably high protection, going up to 80% for an entire riboverlap in a wild-type strain, under most favorable assumptions.

Chapter 3

With less stringent assumptions, the protection is lower but should still be measurable even for a relatively smaller riboverlap size. It is however obvious from these graphs that because our hypothetical construct does not protect from base pair substitutions which are also deleterious, it is impossible to get "full" protection. Mutations impacting gene1 without impacting gene2 will eventually happen. However, reducing the "effective" rate of mutations that have a chance to fix can, in some cases, make a big difference on the evolutionary outcome. One example of such situation are the cooperation genes, which we already discussed in the previous chapter.

More detailed description of the algorithm

We do not have to make coding sequences overlap, we only need to create an RBS-START (with a small spacer in between) motif in the coding sequence of the costly gene. Note that our algorithm has only one input (the costly gene gene1), since the essential gene (gene2) that we are going to "plug" at the end of our construct does not matter at this stage as long as it is in the right frame. The accuracy of our algorithm will depend on how good we are at evaluating whether a given sequence is a RBS. We tried the RBS calculator by Salis lab, however we found it to be very inaccurate when evaluating an RBS inside a coding sequence. This tool has other important drawbacks: it is much too slow to run it on the whole genome of E. coli, and nor binary program nor source code is available for download, restricting the use to a crowded server. We thus decided to use a much simpler approximation: we estimate the strength of a RBS using the distance to the consensus motif (AGGAGG + 3 to 7 base pair + START). This is a very simplistic approximation and may lead to bad surprises by, for example, not considering the secondary structure on the messenger RNA that could make our potential START unaccessible to the ribosomes. However, since our algorithm produces a library of possible constructs, we should be able to conduct a first screen of these candidates using a more accurate thermodynamic model of translation initiation, or even to directly perform an experimental screen.

Because our approximation makes finding whether a subsequence is a good RBS a local problem, we can "brute-force" smartly, by considering all the synonymous sub-sequences in a sliding window of the correct size to limit combinatorial explosion. This local evaluation is necessary because for a 300 amino-acids sequence, there are up to 3.2 300 possible synonymous sequences, which is much bigger than the number of atoms in the universe. However, if our sliding window is the upper limit of the biggest possible motif (18 nucleotides: 6 (consensus) + 7 (spacer) + 3 (start) rounded to the next codon), then in the worst case (which corresponds to codon redundancy distributed equally) we have 3.2 18 possible sequences to consider for each position inside the costly gene1. So in total we have 300 × 3.2 18 or about 3 × 10 9 candidate sequences to evaluate, which is perfectly doable in a reasonable time, since for each of these candidates we just need to perform an alignment of a size smaller than 18.

Chapter 3

We present (Algorithm 1) a pseudo-code that summarizes the structure and the key steps of this algorithm. We implemented this algorithm in Python. On a gene of 1000 nucleotides, the RiBoSor takes a few minutes to run. It is of course possible to further optimize both the algorithm and its implementation, but we decided that this version is good enough for our needs in this project. Any further optimization would come at the cost of a loss in modularity and maintainability.

for i ∈ [1, len(Gene1)/3] do //

Algorithm results for Escherichia coli genes

We ran in parallel the RiBoSor for each gene of Escherichia coli K12 MG1655, and recorded the relative position of the first RBS-START we can create inside a gene. The first is also the best candidate, since we start by attempting to place the RBS-START at the beginning of gene1, and the smaller the relative position of RBS-START, the bigger the overlap and the bigger the protection. We plot the cumulative distribution function of the relative position of the best candidate for all E. coli genes in figure 3.3.

Experimental validation: preliminary results

To test our prediction about the effect of gene overlap on the evolutionary potential of a gene, we decided to choose a candidate gene that we can both select, counter-select, and that can give a visible phenotype without selection. While extensive, these requirements simplify a lot most of the experimental protocols. Galacto-kinase (galK) is one of the very few genes that satisfies all three previous conditions. It is (1) positively selected when using M9 galactose as a food source, (2) counter-selected when using M9 glycerol + DOG as a food source, and (3) visible using MacConkey galactose plates. The second condition is achieved thanks to DOG, or Deoxy Galactose, which is an analogue to galactose that can be imported by the same pathway than galactose and processed by galK, but can not be further processed by the rest of the galactose pathway and will accumulate into toxic intermediates [START_REF] Warming | Simple and highly efficient BAC recombineering using galk selection[END_REF]. M9 glycerol is used as a carbon source to avoid catabolite repression. The third condition is achieved because the fermentation of the galactose by E. coli will change the color of the colonies formed by bacteria using it as a carbon source2 . We thus decided to use galK as our first experimental candidate. See figure 3.4 for a visual summary of the complex regulation of the galactose pathway.

Running the RiBoSor on the 1149 base-pairs long galK coding sequence gave us several RBS candidates summarized in Table 3.2. We synthesized and successfully cloned one of them, starting at nucleotide 675, under the control of the pLac promoter, using aph3' as the second (essential) gene. aph3' confers resistance to kanamycin by catalyzing the intracellular As we previously said, the two parts of the design (creating the RBS-START in the upstream gene and "plugging" in a downstream gene) are independent and modular. aph3' is a good choice for the downstream gene because it codes for a monomeric enzyme (less chances that the fusion we made with rubbish sequence at 5' interferes with the activity of the enzyme), acts mainly inside the cell (a fraction of bacteria expressing the enzyme thus can not sustain the growth of another fraction of the population not expressing it), and is essential (kanamycin is bactericidal and not only bacteriostatic).

Our overlapped construction was able to grow on LB supplemented with 25µg/µL of kanamycin and 0.5mM of IPTG (inducer), confirming that aph3' is expressed and is functional. We also confirmed that galK was expressed, functional and giving the expected phenotype by diluting our construction in M9 glycerol supplemented with IPTG and 0.032% of DOG. The culture showed no growth after 48 hours at 37 • C, while it grew in the same medium without DOG. This confirms that galK is functional, and can be used as a costly gene. The concentration of DOG we used was lethal in presence of galK, but we can diminish it to modulate the cost.

We also constructed a control, non-overlapped strain in which galK and aph3' just share the same operon, without any riboverlap, to be able to disentangle the effects of the protection coming from the operon (shared promoter and terminator) and from the riboverlap.

We are currently conducting mutagenesis experiments to check our hypothesis that purifying selection on aph3' will protect galK from some of the deleterious mutations, and trying to design, synthesize and clone some of the other possible constructs to test whether a bigger overlap confers more protection. We also plan to test the effect of a frame-shift prone mutator on the result of the mutagenesis experiments. More interestingly, we will compete the overlapping and non-overlapping strains in conditions of cycling selection, to check whether the evolvability suppression conferred by the overlap could be adaptive under these conditions, because it limits the chances of following some short-sighted evolutionary paths.

The Overlapor

Description of the algorithm

Knowing the limitations of the riboverlaps we just described, we continue the work by trying to design "real" overlaps of coding sequences. Our goal is to write an algorithm that takes as inputs two coding sequences, and that designs the biggest overlap allowing the expression of both sequences. We must distinguish several possible configurations for overlapping genes: two genes on the same strand but in different reading frames, two genes on different strands with the 5' end overlapping, and two genes on different strands with the 3' end overlapping (see Figure 2.7 for a graphical view of these three configurations). The last two possibilities allow a special case that makes the problem simpler: both genes could be encoded with the same codon boundaries (i.e. one codon of the first gene is exactly the reverse complement of one codon of the second gene). Let us first discuss this simpler case that we will call "r0" to better understand how to solve the problem for the more complicated general case.

Simpler case of "r0" configuration

Since the codon boundaries are the same for both genes, we will work on codons and aminoacids, and not on nucleotides. Let us first break the symmetry of the problem by arbitrarily choosing one of the two input sequences (A) that we will just translate: we get a string of amino-acids A 1 ..A n (we do not need to explicitly consider genetic code redundancy here since we are working at amino acid level). If we take the reverse-complement of the second input sequence (B) and also translate it, we would get an amino-acids string B ′ 1 ..B ′ n . We could then try to align it with the A 1 ..A n amino-acid sequence, however we would miss a large part of potential matches because we do not use the genetic code redundancy on the second sequence. Indeed when taking the translated reverse-complement of a synonymous sequence of B (instead of directly B), we can get some very different amino-acid sequence than B ′ 1 ..B ′ n . So we should consider every synonymous variant of B, reverse-complement it and translate it, and check whether we can align it with A 1 ..A n with a good score.

The previous sentence gives us a good sketch of the algorithm. However, even for short genes, there is an astronomical number of synonymous sequences, and it is obvious that we can not test all of them. To avoid this combinatorial explosion, we change our alphabet. Instead of having one symbol per amino-acid, we will have one symbol per set of possible amino-acid (at a given position). For example if in the sequence B there is a codon ATC, instead of working on its reverse-complement GAT (amino-acid D), we also take the set of the reverse-complements of its synonymous codons. Synonymous of ATC are ATT and ATA, their reverse complements are GGT and TGT which correspond to amino-acids G and C. This position in sequence B can thus align with amino-acids D, G and C (and not only with D as the too naive algorithm would have considered). The best way to represent a subset of the set of 22 amino-acids (we include stop codon as one amino-acid) is to use a positive integer coded on 22 bits. Such integers form a vector space of dimension 22 whose a base is (2 0 , 2 1 , ..2 21 ): each amino-acid corresponds to an exponent of 2, and to represent a subset of possible amino-acids we sum these powers of two. Thus a subset is represented as an integer, each digit in its binary encoding indicating whether a particular amino-acid (given by the position of the digit) is inside the subset (table 3.3). This encoding is bijective, fast, and at each position the alignment algorithm will compute the intersection of the two sets of possible amino-acids. In this version of the algorithm, one set will simply be a singleton, describing the amino-acid encoded by the input sequence A at the considered position. The other set will contain all possible amino-acids encoded by the reverse complement of the synonymous3 codons of B at the considered position. Finding the intersection can be achieved by performing a bitwise logical AND on the integers encoding the sets, which is not only very fast but also allows us to easily get the "chosen" synonymous sequence and not only the score for the alignment.

So for this simple case ("r0" configuration of the overlap), we start by making a transformation of our sequences into a different alphabet (integers between 0 and 2 22 -1): A is just "embedded" inside this alphabet while each codon of B is transformed into a superposition of the possible amino-acids encoded on the opposite strand. Then we apply an alignment algorithm on our transformed strings, and we transform back our alignment to get the "chosen"

Chapter 3 A R N D C Q E G H I L K M F P S T W Y V U STOP Amino-

Detail on the alignment algorithm

The alignment algorithm that we wrote is a variant of Needleman-Wunsh and Smith-Waterman algorithms that works on 32-bit unsigned integers (instead of nucleotides), using a logical AND as the core of its scoring function. The key difference with the two aforementioned classical alignment algorithms is the scoring of the gaps. Needleman-Wunsh algorithm restricts the search to a global alignment by giving to each gap a penalty depending on the length of the gap (for example proportional to this length), no matter whether the gap is at the beginning or at the middle of the alignment. This is too restrictive for our case, because even if our two sequences would have the same length it would be overly optimistic to expect an overlap that entirely includes both of them. On the other hand, Smith-Waterman algorithms gives up this restriction and allows the search for local alignments, in a way that makes it too permissive. It is very likely to give us small portions of the two genes that could overlap (with very good score), which is useless for us if these portions are at the middle of the two genes. This is due to the fact that at each step of the dynamic programming algorithm, the Smith-Waterman scoring scheme considers whether stopping the alignment at this stage (without any penalty) gives a better score than expanding the alignment. Our solution is to allow (potentially large) gaps at the beginning of one of the sequences with a low (or inexistent) penalty by initializing the scoring matrix differently, and same thing for the end of one of the sequences (that can potentially be the same than the one that has a gap at the beginning), but to keep the Needleman-Wunsh scoring scheme "inside" the sequences to impose a global alignment. Instead of drowning the reader in further details regarding the algorithm and its implementation, we make some key parts of the code available as an appendix.

(almost) General case: same strand shifted overlap

The complication with other kinds of overlaps (non "r0") is that the boundaries of the codons are not the same for the two sequences. Let us first consider the "p1" and "p2" cases, where the overlapping genes are on the same strand, with a reading frame shifted by 1 or 2. We can always swap the input sequences of the "p2" case to get back to the "p1" case, so we will only discuss this "p1" case, where sequence B is shifted by one downstream compared to A. The approach we used for "r0" will not work here, because using codon redundancy to change one amino-acid of A will affect the alignment with two different codons of B simultaneously. Since our alignment algorithm uses dynamic programming, the scoring codon choice at position (i, j) should be purely local, determined independently of the choice of codon at position (i -1, j) for example. Figure 3.5 presents a more graphical explanation of why we can not directly apply the previous idea to the "p1" situation.

G TAC CTA GAT CAT TA

TGT AGG GGC TTG TGA The algorithm developed for r0 case will not directly work on p1 case. At position 4, if we consider all the amino-acids that could be encoded in the frame of B (in which codon boundaries are delimited by spaces) by making all possible synonymous changes in the sequence A (top sequence, codon boundaries are indicated by a color code), we would consider replacing TCA by AGC (both are Serine), which would also affect the amino-acid encoded in frame of B at position 3 (go from GAT to GAA, which is not synonymous). This is a problem because due to the way dynamic programming works, we need to be able to score at position 4 without changing the score of position 3 and even without knowing what "path" lead us to the current scoring.

It thus seems that we are stuck and can not go any further with our approach of "extended" alignment algorithm. We could again expand our alphabet to consider groups of n consecutive codons as single symbols if the positions where changes are needed were rare enough, but this is not the case. But if for a minute we stop considering this as a pure algorithmic problem and think a little bit more about the biology behind it, we can find an imperfect but viable solution. We know that the redundancy is not equally distributed on the three nucleotides of a codon: there is much more redundancy on the third and sometimes on the second position than on the first one. As a matter of fact only Arginine and Serine display redundancy on the first base of their codons. So we do not loose a lot of information if we decide not to use possible redundancy on the first bases of the codons of A. Note that after this simplification the problem is not symmetrical anymore, since we re-ordered A and B so that B is shifted by 1 compared to A. We can now consider the superposition of amino-acids that can be encoded by A in the frame of B (making synonymous changes on A without changing the first base-pair of each codon), and align it with the amino-acids encoded by B (embedded into the expanded alphabet) using the alignment algorithm from before.

We implemented these algorithms in a mix of C and Python. By using similar reasonings, we can design algorithms that work for the two other cases we did not explicitly consider (r1 and r2, corresponding to the setup where the two strains are on different strands and in different reading frames), which we did not implement yet.

Using information about non-synonymous possible changes

We have successfully written and implemented the algorithms for creating overlaps exploiting the genetic code redundancy. It is however unsure that synonymous changes alone provide enough redundancy to design big overlaps using our methods. We thus looked in the literature for data about the conditions for the neutrality of non-synonymous substitutions, and considered integrating such data into our algorithms.

While it is extremely difficult to find general rules predicting which particular mis-sense mutations will be deleterious, for a few specific genes the effect on protein function of a very large number of amino-acid changes has been experimentally tested [START_REF] Markiewicz | Genetic studies of the lac repressor. xiv. analysis of 4000 altered escherichia coli lac repressors reveals essential and non-essential residues, as well as "spacers" which do not require a specific sequence[END_REF][START_REF] Jacquier | Capturing the mutational landscape of the betalactamase tem-1[END_REF]. Our alphabet transformation makes the integration of this kind of information relatively easy: it just extends the superposition to non-synonymous codons that do not change the protein function.

For example, in the case of p1, if we have information about the effect of amino-acid changes in B, instead of aligning the superposition of amino-acids that can be encoded by A+1 (A shifted by one) with B we will align it with the superposition of amino-acids in B that do not alter protein function. However it is not as simple if have information about the effects of amino-acid changes in A, because we will only be able to use non synonymous changes that preserve the first nucleotide of the codon for the reason already explained above. In the case of r0, because the problem is symmetrical and the codon boundaries are the same for the two genes, we can always integrate all the information we have. This extensions to use non-synonymous neutral changes only affect the alphabet transfor-Chapter 3 mation part of our algorithm. We successfully implemented and integrated them inside the Overlapor.

Proof of concepts: finding Escherichia coli genes that could overlap with lacI or TEM-1

We used the aforementioned data about the effects on non-synonymous changes on protein functions for lacI (repressor of the pLac promoter) and for TEM-1 (beta-lactamase, degrading beta-lactam antibiotics) to find genes from Escherichia coli MG1655 that could overlap with these two genes. Results are summarized on Table 3.4. We can notice that our algorithm found generally smaller but much more accurate overlaps for lacI than for TEM-1. This is due to the fact that the data for TEM-1 show a much smaller fraction of neutral non-synonymous changes. However, according to [START_REF] Jacquier | Capturing the mutational landscape of the betalactamase tem-1[END_REF], TEM-1 is one base-pair away from a stabilizing mutation that considerably reduces the effect of the other base-pair substitutions, whose a large part then becomes neutral. The authors support this claim with a thermodynamical model of TEM-1 folding and activity. They only test the effect of the stabilizing mutation (according to their model) on a small set of amino-acid changes, with very promising findings. We did not include the results of their model in our input data about the effects of specific non-synonymous changes. Doing so would considerably increase the quantity of allowed amino-acid changes and is thus likely to significantly improve the potential overlaps found by our algorithm in term of percentage of similarity.

The results are generally very promising. Indeed if we keep in mind that [START_REF] Markiewicz | Genetic studies of the lac repressor. xiv. analysis of 4000 altered escherichia coli lac repressors reveals essential and non-essential residues, as well as "spacers" which do not require a specific sequence[END_REF] only tested the effects of about half of the possible amino-acid changes at each position of lacI, we can assume that having data for the other half could significantly improve our results to reach similarity close to 100% for some candidates.

We also tested the possible overlap of lacI with TEM-1 in the r0 configuration (the only one that allows to fully take into account redundancy and non-synonymous changes for both genes), and found a possible overlap of 918bp, with 89% similarity, confirming that providing slightly more biological information can significantly improve the findings of the overlapor.

This last result gives us a strong candidate to test experimentally. We are likely to reach a protection close to 100% if we use the thermodynamical model of [START_REF] Jacquier | Capturing the mutational landscape of the betalactamase tem-1[END_REF], potentially allowing us in the next few months to clone the first synthetic overlap ever designed. (b) TEM-1 results. We only output overlaps bigger than 273bp with similarity higher than 65%.

Table 3.4: Genes that could overlap with lacI or with TEM-1. For each possible overlap we output the size of the overlap, the percentage of similarity, and the configuration (so far we only tested r0 and p1).

Chapter 4

Evolution of second-order cooperation by selection for high switching rate

The work presented in this chapter is in its almost final shape and should be submitted for publication in the next few weeks.

Introduction: second order cooperation

The last twenty years have seen the rise of individual based computer simulations as tools to understand the evolution of altruism. In these game theory inspired binary simulations, individuals usually have a fixed probability of switching from one behavior to one other (we can call this parameter mutation rate). And as predicted by both kin selection and multilevel selection views, a higher "mutation rate" is without surprise less favorable to cooperation, since it will diminish the probability of neighboring individuals having the same behavior (decreased relatedness), or at the group level it will increase the chances of a cheater (defector) appearing inside a group of cooperators and invading. This "classical" result of spatial assortment promoting cooperation can be nuanced by a few works using different games [START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF]), but remains the dominant paradigm and is consistent with experimental results [START_REF] Harrison | Hypermutability impedes cooperation in pathogenic bacteria[END_REF].

Here we are interested in the case where the mutation (switching) rate between cooperators and defectors can evolve. Classical paradigm can a priori predict at least one regime: with low enough cost of cooperation (parameter), cooperators will invade (first-order selection for cooperation) and a low mutation rate from cooperators to defectors will be selected (secondorder selection for cooperation). It is not difficult to predict that under a high enough cost of cooperation, defection will invade (first-order selection against cooperation). However, when defectors are the dominant type in the population the direction of the selection on the locus controlling the mutation rate becomes unclear: the amount of cooperators (they never totally Chapter 4 disappear, there is a mutation-selection balance maintaining a small fraction of cooperators) may be too low to cause a selection at the locus controlling the mutation rate from cooperators to cheaters, and one can find arguments going in both directions about the selection for the mutation rate from cheaters to cooperators. In this chapter I mainly address this second question: what is the direction of selection at the locus controlling the mutation rate from defectors to cooperators in a regime where cooperators are counter-selected? But before going further in the details, I believe that a few semantic precisions are necessary. While the simple class of simulations we use here often makes the approximation that genotype = phenotype = binary behavior, genes that are constitutively expressed in bacterial world are actually more the exception than the rule. In this perspective, several recent papers raise important questions: Martin Ackermann's team [START_REF] Ackermann | Self-destructive cooperation mediated by phenotypic noise[END_REF][START_REF] Diard | Stabilization of cooperative virulence by the expression of an avirulent phenotype[END_REF] recently studied an extreme altruistic behavior: Salmonella typhimurium is a pathogenic bacteria living in the gut that has a fascinating mechanism to exclude competitors: a small fraction of the population invades the mucosa and secretes a product inducing inflammation and thus immune response of the host. Both the cost of expression of this product and the immune response induce such a large cost for this sub-population that it usually dies. This raises important issues: designating only individuals that express the secretion system as cooperators is too restrictive. In the mathematical model developed by Ackermann's team to support their results, the cooperators are the individuals bearing the gene coding for this secretion system, and not only the individuals actually expressing it. They show that when competing wild-type S. typhimurium (cooperators, bearing this secretion gene but expressing it stochastically) with a mutant variant not bearing it (cheaters), we come back to a classical social evolution dilemma that can be "solved" by non random assortment (individuals bearing the gene, but not necessarily expressing it, benefiting more from the altruistic behavior than individuals not bearing the gene).

But in our opinion the story should not end there: while in such an extreme case cooperation could not be constitutively expressed (because individuals bearing cooperative traits usually die without reproducing), we can still imagine more classical systems where the cooperation has a less extreme cost and where the cooperation gene is not constitutively expressed. The question then is "what is the difference between a system where cooperation is constitutively expressed and a system where cooperation depends on a stochastic switch". To answer this question, we developed a system where the mutation rate from cooperators to cheaters and from cheaters to cooperators can evolve. This problem is more fundamental and widespread than one could guess on first look. Indeed, while it is well known that altruistic behavior was cited by Darwin as a complication in his theory [START_REF] Darwin | On the Origin of Species: By Means of Natural Selection[END_REF], the real problem Darwin saw in eusocial insects is much less often remembered: while he considered the existence of non-reproductive individuals easy to explain because of potential benefits at community level, his real problem was to explain the many phenotypic (including behavioral) differences that exist between the queen and the workers, since workers do not transmit their characteristic and thus could not have "gradually acquired" them in Darwin's view. The answer is of course obvious today: phenotypic plasticity. The inherited social behaviour is not "infertility and propensity for brood care of the queen's eggs", but "stochastic differentiation of one part of the eggs into infertile individuals with a propensity for brood care of the queen's eggs".

More recently eusociality has been a serious point of friction between proponents of group and kin selection [START_REF] Fletcher | What's wrong with inclusive fitness?[END_REF], with one point of misunderstanding being precisely the applications of inclusive fitness to understand the evolutionary interest of the workers (or the workers' genes) in not reproducing instead of trying to understand the evolutionary interest of the queen (or the queen's genes) into having a large part of sterile offsprings. Of course our evolution of cooperation simulation is much less drastic than eusociality both quantitatively (the fraction of non-reproductive offsprings is smaller) and qualitatively (the cooperative act we model does not imply suicide / total loss of reproduction), although we will show that this second assumption can be relaxed and does not actually make a qualitative difference. But the problem of inheriting a conditional or probabilistic cooperative behavior is much broader than eusociality, as shown for example by [START_REF] Ackermann | Self-destructive cooperation mediated by phenotypic noise[END_REF].

Another point of interest of our work in this context is our 2D spatial structure. It is important because most of researchers that extended this question of division of labour in the way we are trying to do are strong proponents of group selection, place themselves in the context of isolated subpopulation (island / deme models), and formalize their work in the context of interest of the subpopulation. By using these square lattices, we firmly place ourselves in the context of viscous populations, and show that as for all properly formalized models of social behaviors, kin selection (properly understood, maybe we should rather call it "non random spatial assortment in the context of viscous populations") is largely equivalent to group selection, the difference being as usual that we emphasize a greater than random spatial proximity between second-order cooperators and benefits of cooperation instead of accounting for this effect at the level of isolated sub-groups. If we want to make a parallel with more classical public-good based cooperation systems, we could consider the individuals expressing cooperation (the workers) as the public good, being produced by the second-order cooperators.

Material and methods

Description of the system

We simulate the evolution of individuals living on a square 100x100 lattice, whose genotype is represented by three binary loci: one controlling cooperative behavior (C or D, for cooperator or defector), one controlling probability of mutation from C to D (L CD or H CD for a low or high mutation rate), and one controlling probability of mutation from D to C (L DC or H DC ). The simulations are synchronous: at each time point, for each location on the lattice, we compete the focal individual with its eight neighbors to decide who is going to replace it in the next generation. Reproduction is done with mutations, first locus having a probability of mutations controlled by the two other loci, whose probability of mutations is extrinsically fixed to 0.001.

We can call individuals of genotype (D, *, H DC ) "second order cooperators", because while they do not express the cooperation themselves, they produce more offsprings that do. While in our system the cooperative behavior is heritable, taking high mutation rates for H CD and H DC can make it more representative of a trait controlled by a phenotypic switch (with epigenetic inheritance) than a genotypic trait. This setup allows keeping the synchronous non-overlapping generations setup, since we do not need to explicitly simulate the switch of an individual from one behavior to one other (this switch happens at reproduction).

At each time point, fitness score of each focal individual i is calculated as

f i = basef itness + benef it * k∈N i C k /9 -cost * C i where N i is neighborhood of the individual i (including the focal individual i itself), C k is 1 if individual k
bears allele C and 0 otherwise. Probability of reproduction of an individual i with fitness f i is a local normalization of this fitness:

P i = f m i /( k∈N i f m k )
where m is the strength of selection. When m = 0, there is no selection (every individual has equal probability of reproduction) and the population evolves only by genetic drift. When m = 1, selection is linear (probability of reproduction is proportionate to fitness). When m = inf inity, the best individual is always the one picked for reproduction ("fittest" selection scheme).

To be compatible with classical parameters in the literature [START_REF] Nowak | The spatial dilemmas of evolution[END_REF], we take basef itness = cost -1/8 and benef it = 9/8. Thus the only remaining free parameter in the fitness calculation is cost.

Relevance of our individual-based synchronous framework to study the evolution of cooperation

Simulations have been frequently used to advance our understanding of cooperation. Much work over the past twenty years has focused on inelastic lattices filled with individuals, playing a Chapter 4 prisoner dilemma game, whose behavior is described with a single binary locus (C, "cooperate", or D, "defect"). While simplistic, this class of models is sufficient to a significant part if not most of our knowledge in social evolution: this spatial structure gives a non random spatial assortment between individuals with the same behavior, supporting the use of a kin selection and/or group or multilevel selection framework.

While the first models were classically synchronous, there were a few arguments about the possibility for this synchronous behavior to create strong artifacts. Indeed, one of the first published synchronous simulations [START_REF] Nowak | The spatial dilemmas of evolution[END_REF] displayed "perfect" geometric patterns that have been criticized [START_REF] Huberman | Evolutionary games and computer simulations[END_REF] as being due to "time granularity" of the synchronous reproduction (at each time point the whole population is playing a public good game and is replaced according to the results). However, further studies [START_REF] Oliphant | Evolving cooperation in the non-iterated prisoner's dilemma: The importance of spatial organization[END_REF][START_REF] Nowak | Spatial games and the maintenance of cooperation[END_REF] have shown that while Nowak and May results were indeed partly artifactual, the problem did not lie in the time granularity but in the determinism of the selection and reproduction scheme (synchronously selecting the best individual in each neighborhood to reproduce and replace the individual at the center of the neighborhood).

Synchronous simulations with local (within the neighborhood) probabilistic selection are thus a well suited framework to study the evolution of cooperation, or at least there is to this day no strong element of proof of this selection scheme biasing the output, as long as the selection is probabilistic (an individual of higher fitness has higher chances to reproduce) and not deterministic (the best individual is always the one picked for reproduction). One paper [START_REF] Hauert | Spatial structure often inhibits the evolution of cooperation in the snowdrift game[END_REF]) that is often cited as an example of synchronous updating hindering cooperation is actually biased by using a game that gives higher reward when the neighbors have different behaviors.

The past few decades have seen the rise of a lot of asynchronous simulations. Although computing is never truly asynchronous, replacing a part of the population at each "time point" better represents a real population of individuals of different life spans, with several overlapping generations. Thus, the "time point" becomes the unit of discretization of computing and not the lifespan of individuals. While there is no doubt these asynchronous models can be useful in some cases where the synchronous models are too far from reality to study a particular point of interest, I believe that much of the published work using asynchronous models would have lead to the same conclusion if using a synchronous model, and it is difficult to justify going for a more complex model when there is no explicit reasons to think simpler models would bias the result. Additionally, complex models are likely to introduce more problems than they solve, and asynchronous models have suffered from important biases that took several years to be fully understood, an important one being the difference between birth-death and death-birth updating rule [START_REF] Grafen | Natural selection of altruism in inelastic viscous homogeneous populations[END_REF].

It should however be noted that these questions go beyond mere modeling preferences and Chapter 4 have important roots in the history of population genetics: the difference between synchronous replacement of the whole population and replacement of only a few individuals at the same time is the difference between Fisher-Wright and Moran models of population genetics.

The real weak point of synchronous simulations of lattices is however somewhere else: the inelasticity makes competition being only local, i.e. only relative (to the neighborhood) fitness matters, while in bacterial world we know that individuals can "push" each other, giving a more global scale to competition. Indeed, several papers wondered whether the "viscosity" could, by making competition local, promote competition between kins and counter the effect of kin selection [START_REF] Wilson | Can altruism evolve in purely viscous populations?[END_REF][START_REF] Mitteldorf | Population viscosity and the evolution of altruism[END_REF][START_REF] Taylor | Altruism in viscous populations-an inclusive fitness model[END_REF]. However, using the idea of "compensated relatedness" developed by [START_REF] Grafen | Natural selection of altruism in inelastic viscous homogeneous populations[END_REF] makes clear that this inelasticity is only partial and will not prevent cooperation. Moreover, it is interesting to note that the updating rule we use in this work (at each generation, for each point of the lattice, compete the nine individuals of the neighborhood to decide who is going to replace the focal individual) is actually a degenerated version of the death-birth updating rule of Moran model, and this death-birth rule is known to permit altruism [START_REF] Grafen | Natural selection of altruism in inelastic viscous homogeneous populations[END_REF].

Experimental setup

For each combination of parameters, we simulate five independent replicates of 2000 generations of evolution. The difference between the replicates is a different initialization of the pseudo-random number generator. Since both selection and mutations are stochastic, different replicates will have numerically different outcomes. The variability between replicates seems rather low (probably owing to the fact that the population is big enough, limiting the effects of genetic drift), allowing us to run only five replicates of evolution for each parameter set. Because our "genomes" are simplistic, 2000 generations is always enough to reach a reasonably stable behavior.

Results

Effect of parameters on the selection at locus controlling cooperation

The two main parameters influencing cooperation are cost and m (intensity of selection). We plot (Figure 4.1, blue bars) the outcome for what we can call "first order" cooperation (proportion of pure cooperators, individuals of type (C, *, *)) as a function of these two parameters. We identify two general rules: the higher the cost, the lower the proportion of pure cooperators; and the higher the intensity of selection, the higher the proportion of pure cooperators.

Evolution of mutation rate in the context of allele C dominant

Without surprise, in most situations where allele C is dominant, we found that allele L CD invades, which is consistent with the idea that higher mutation rate impedes cooperation by making more cheaters appear at the middle of cooperator patches. We confirm this by running two control simulations where we enforce respectively low and high mutation rate (we only let the first loci to evolve, the individuals will have genotypes (*, L CD , L DC ) or respectively (*, H CD , H DC )). We plot (on Figure 4.2) the number of pure cooperators that evolves in these control simulations (cyan bar for H control, purple bar for L control), compared to the number of pure cooperators when mutation rate is free to evolve (blue bar from Figure 4.1).

In most of the parameter combinations where cooperation is dominant, we clearly see that cooperation is still winning in both control simulations, but that average fitness of the population is higher (because total number of "cheaters" ie individuals with genotype (D, *, *) is lower) in the "low mutation rate" control (purple bars) than in main simulation, and it is higher in main simulation than in the "high mutation rate" control (cyan bars). So in this range of parameters a lower cooperator to cheater mutation rate does not change the main outcome (cooperation winning, ie most individuals having genotype (C, *, *)), but does change the mutation-selection equilibrium, giving a higher average fitness (a lower proportion of cheaters) to the group. It is thus important to consider that cooperation is a dynamical equilibrium (patches of cooperators constantly emerge and are constantly invaded by cheaters). It is interesting to notice that for parameters that are more "on the edge" of the space in which C is dominant (for example c = 0.4, m = 50), the effect of mutation rate (difference between number of cooperators in "high mutation rate" control and in "low mutation rate" control) becomes higher, and there may even exist a small parameter range where cooperation would be dominant but so close to invasion by cheaters than mutation rate from cooperators to cheaters would be decisive for the outcome.

Evolution of second order cooperation (high non cooperator to cooperator mutation rate) in some conditions where D is dominant

We observe that in a reasonably large parameter range, allele D fixed at cooperative locus, but allele H DC also fixed, meaning that the dominant subpopulation, with genotype (D, *, H DC ), does not evolve "constitutive" cooperation, but evolves a high probability of having cooperative offsprings. Main parameters influencing this outcome are selection pressure and cost of cooperation.

As previously said we call individuals having this genotype (D, *, H DC ) "second-order" cooperators, because they generate "pure / constitutive" cooperators. It is easy to show that this behavior is subject to the usual cooperation dilemma, the cost of second order cooperation being having one fraction of less fit (or sterile) offspring, and the benefit for the neighbors being a higher chance of encountering a (C, *, *) individual (offspring of the second-order cooperator).

We also plot on fig. 4.1 the proportion of "second-order" cooperators (H DC , green bars), and the proportion of H CD (red bars). It is important to note that in a large part of the parameter space, one of the L/H CD and L/H DC loci is mainly evolving by genetic drift. Indeed, when cooperators invade, the cheaters are too few for L/H DC to have an impact. Similarly, when cheaters invade, the cooperators are too few for L/H CD to have an impact.

Chapter 4

We can measure the benefit population gets from H DC alleles using the two control simulations we already mentioned (one where we enforce H values at both L/H DC and L/H CD loci, and one where we enforce L values at both these loci, only C/D locus being free to evolve in both this simulations).

To check that this behavior is cooperative and evolves via group/kin selection, we performed the same set of simulations but randomized neighborhoods: for each focal individual, instead of calculating its fitness based on the cooperative behavior in the neighborhood, we calculate it based on 9 individuals picked randomly. In this randomized conditions, whatever the parameters are, the outcome is always invasion of D / L DC individuals (nothing meaningful evolves at L C/D locus because there are not enough individuals of type C for selection to happen at this locus).

This clearly shows that H DC is a cooperative allele although individual bearing it do not express cooperation themselves. We can analyze it in a more mathematical way, and again find the usual cooperation dilemma, provided we calculate the fitness properly: the "extended" fitness value should not only take into account the probability of a focal individual to reproduce, but also the ability of its descendant to themselves give birth to viable individuals. Thus the H DC allele has an extended fitness cost even though it does not contribute to the phenotype of an individual: the cost is the total fitness loss over the lineage. If we make the simplifying assumption that chances of constitutive cooperators to reproduce are null (f itness C = 0), then it is reasonable to express the "extended" fitness of individual i corrected for reproductive success of descendants as follow:

EF i = (base + benef it × k∈N i C k ) × (1 -P h × C 2 i )
where N i is the neighborhood of i, C 2 i is 1 if i is a second-order cooperator (H DC ) and 0 otherwise, P h is the probability that a second-order cooperator gives rise to a "pure cooperator" offspring.

Because residing in the neighborhood of H DC individual increases the probability of a C individual also being present in the neighborhood, the H DC allele statistically increase fitness of the neighboring individuals (likely to be kins). It thus makes sense to consider it as a cooperative allele. We can easily see from above equation that it satisfies the usual altruism dilemma.

We exhibit this by calculating the regression coefficient between allele H DC and allele C. We found that indeed these two alleles are more associated than random, so H DC individuals benefit more from cooperation than L DC individuals (Figure 4.3). These assortments are respectively defined as the average number of cooperative neighbors that individuals of type (D, *, H DC ) (respectively (D, *, L DC )) have. It is somewhat similar to the fact that cooperators benefit more from cooperation than cheaters in "classical" one locus binary simulations, but it is interesting to notice that in our setup (D, *, H DC ) individuals may act as a "spatial buffer" between (C, *, *) and (D, *, L DC ) individuals.

Extending to higher switching rates

In the aforementioned simulations, mutation rate was varying between 0.001 (L) and 0.01 (H), which is rather low. Phenotypic switches can allow much higher rates than genotypic mutations. While the reasoning about second-order cooperation remains exactly the same (if there is epigenetic inheritance of the switch state or if most pure cooperators are dying), it can get our simulations closer to what exists in nature. We thus performed the same experiments than before with switching rates varying between 0.001 and 0.1 (fig. 4.4) and between 0.001 and 0.5 (fig. 4.5). Although the "borders" between the three main zones of the parameter space (first order cooperation, second order cooperation and no cooperation) move a little bit, main results remain.

Discussion

Our results can be interpreted in two closely linked ways: this second order cooperation (what evolves is the ability to generate "pure" cooperators, individuals actually performing the cooperative act) can be seen as a division of labour or as a soma/germ-line distinction. We showed that this cooperative trait can be maintained no matter how costly is the cooperative act (even when causing death of actors) provided there is a spatial association between individuals bearing the allele causing a high mutation rate toward cooperation and cooperators themselves, without needing any "interest of the group" type arguments. We defended the idea that such an allele is cooperative and satisfies the usual dilemma of social evolution.

It is interesting because the loss of reproductive behavior in worker casts of eusocial insects has been extensively debated in the context of evolution of cooperation (Hamilton, 1964a). The explanation suggested by Hamilton is confusing, first because he does not clarify the single locus relatedness versus whole genome relatedness issue (see introduction), contrarily to Haldane who was much more explicit [START_REF] Haldane | Population genetics[END_REF], although often cited in a very incomplete way. This does not necessarily put in question the role of kin selection / inclusive fitness theory in explaining eusociality, however there are other points of friction that show through a recent debate [START_REF] Fletcher | What's wrong with inclusive fitness?[END_REF] about respective merits of group and kin selection in explaining eusociality.

We definitely agree with [START_REF] Fletcher | What's wrong with inclusive fitness?[END_REF] that what matters here is not the genetic association between actors (workers) and recipients (queens, reproductive cast) at cooperative locus (nor on a whole genome basis), but association between the cooperative allele (for us H DC ) and the effects of this allele (here presence of individuals bearing allele/phenotype C in the neighborhood).

But this is definitely not contradictory to an inclusive fitness view: this association between our second-order cooperative allele and cooperative phenotype (pure cooperators) falls into the extended inclusive fitness model developed by [START_REF] Queller | Kinship, reciprocity and synergism in the evolution of social behaviour[END_REF] and is quite similar to spatial association between cooperators and public good in more classical setting: the effect of H DC allele (i.e. higher presence of C individuals in neighborhood) are more often than random directed toward other H DC bearing individuals in our viscous population setting. This view of relatedness as a spatial association is not at all contradictory with inclusive fitness [START_REF] Taylor | How to make a kin selection model[END_REF].

When mutation rate is high, we can wonder whether we better capture the process of a phenotypic switching than of genome mutations. The main difference between the two is that in the case of phenotypic switch the cooperative state would not be inherited by potential descendants except in the particular case of epigenetic inheritance [START_REF] Robert | Pre-dispositions and epigenetic inheritance in the escherichia coli lactose operon bistable switch[END_REF]. When pure cooperators have statistically negligible number of offsprings, there is no real difference. However, when they have offsprings (low enough cooperation cost, which is not the case in most of our simulations), it could make a difference because of competition between pure cooperators and second order cooperators.

Getting a little bit further from our simulations, we should think about the very dynamic and changing environment that bacteria are facing in their natural habitats. Most if not all or the studied bacterial cooperative traits are only beneficial (and only expressed) in a fraction of the various environmental conditions bacterial populations are facing during their life cycle (pyoverdine is important when iron is a limiting resource, beta-lactamase is beneficial in presence of beta-lactam antibiotics, invertase in presence of sucrose), and the populations are thus likely to quickly alternate between the two states (cooperators and non cooperators) by either regulation or mutations. When sensing of conditions where the cooperative act would be beneficial is not available, a small fraction of the population could change behavior stochastically to "test" cooperation. Regulation is generally not inherited (epi-genetic inheritance of the bistable state of the lactose operon that we already mentioned being more the exception than the rule), while mutations are. This means that when switching from non cooperative to cooperative state, the bacteria performing the cooperative act are randomly spread in the population in the case of a regulation, but clustered in the case of a mutation (with a selection coefficient low enough so the original bearer of the mutation gets a chance to spread). Signaling provides a way to "synchronize" the neighborhood so that cooperators are not alone, but the mutation is an even simpler way to increase chances that the "first" cooperator can enjoy a cooperative neighborhood.

There is another point, linked to the one we just described, to take into account to estimate the respective relevances of these two models (heritable state or non heritable state of the cooperative trait), which is whether the individuals performing the cooperative act need to work together (i.e. whether the per capita benefit of cooperation is dependent on the density of cooperators). While our choice of making the cooperative behavior inherited may not have a lot of importance when a given fraction of dispersed cooperators (workers) is needed to sustain the population, it may have a major effect when the cooperators need to work together in order to achieve something.

One example one could think of is biofilm formation: having this cooperative behavior on a phenotypic switch would lead to a dispersed one percent of the population expressing the synthesis of the biofilm polymers, which is probably not permitting to initiate the growth of a stable biofilm (the workers are paying the cost and surrounded by individuals that do not, with a minimal or inexistent benefit). But if instead of a phenotypic regulation there is a mutation that activates (or de-represses) the biofilm formation, and if the selection coefficient of this mutation is small enough to allow the mutation to stochastically spread one fraction of the times it appears, then the small fraction of bacteria synthesizing biofilms will be part of a "patch" and will be able to get returns. The same reasoning may go for the stalk formation, which is however known to be controlled by signaling in social amoeba [START_REF] Foster | Pleiotropy as a mechanism to stabilize cooperation[END_REF].

On the opposite, when the workers do not need to work together, a given fraction of individuals expressing the cooperative act will be as efficient is they are randomly dispersed inside the group than if they form a sub-island (we talk about groups and sub-islands and not of population because we must keep in mind than this is done in the context of competition between worker-generating and non worker-generating individuals). This may be the case for extra-cellular antibiotic degradation, or for invasion of the mucosa to induce immune response that excludes competitors, or again for the colicins. Regulation or signaling then seem to be better evolutionary choices to control this type of altruistic behaviors.

To conclude, we showed that a "division of labour" type cooperation, where a dominant population bears an allele increasing chances of having "pure cooperators / workers" offsprings, can evolve and be maintained even with a very high cost for cooperative behavior. This "second order cooperation" can be understood using an inclusive fitness point of views, and relies on the spatial proximity of second-order cooperators and pure cooperators, making the former benefit more from the presence of the latter than non second order cooperators do. Our lattice simulations, although not purely continuous, have a spatial granularity as low as the individual, and we do not need isolated subgroups nor group-level arguments to support our view. We highlighted the importance of applying social evolution theory (e.g. kin selection) at the level of competition between "worker generating" and "non worker generating" genotypes. We also discussed why in some cases mutations may be more suited than regulation to control the change between cooperative and non cooperative states.

Chapter 5

Competing metabolic innovations favor the spread of hitchhiking cooperative alleles by increasing relatedness I present here a very preliminary work that is not yet in a publishable state.

Introduction

The central evolutionary paradigm is survival of the fittest, and computer scientists like me often tend to think about adaptive evolution as the path toward what is the "optimum" in some given condition. This view reflects parts of the evolutionary theory that we borrowed from biology and are applying to algorithmic. However, in biological evolution, the environment is constantly changing and fitness also depends on other individuals and other species that are coevolving with the "focal" one. So rather than envisaging a singular path towards the optimum, the genomes should be thought of as constantly being "on their way" toward a different better solution to an environmental problem. Even in perfectly controlled lab conditions, steady state is only apparent but not actually realized [START_REF] Wiser | Long-term dynamics of adaptation in asexual populations[END_REF]. It is in the light of these results that we should re-assess the significance of one of the most important population genetics ideas developed during the last century: genetic hitchhiking, which is the evolutionary survival or spread of non-adaptive alleles because they are genetically linked to alleles under strong selection [START_REF] Smith | The hitch-hiking effect of a favourable gene[END_REF].

The impact of genetic hitch-hiking on the evolution of cooperation has been studied quite independently in two very different contexts: initial spread of cooperative individuals in an originally non-cooperative population [START_REF] Santos | Genetic hitchhiking can promote the initial spread of strong altruism[END_REF], and maintenance of a dominant population of cooperators [START_REF] Morgan | Selection on non-social traits limits the invasion of social cheats[END_REF][START_REF] Waite | Adaptation to a new environment allows cooperators to purge cheaters stochastically[END_REF], both of them having some limitations. The first work is limited by the unrealistic strong assumptions of the model, and the second one because it only explains maintenance of cooperation when already dominant. The preliminary work we present here complements both these approaches. At the start we must stress that, as discussed in previous chapters, the questions of the spread of cooperative alleles and of their maintenance should not necessary be considered independently. In the long run, even in an apparently stable population where cooperators are dominant, there is a permanent dynamics of local invasion of patches by cheaters.

The forces behind the stable existence and dominance of altruistic individuals has been well understood at a high level for a very long time. The last few decades further solidified our knowledge, thanks to major conceptual advances in social evolution, including kin selection and inclusive fitness, group selection, and evolutionary game theory. However, as we saw in the previous chapters, some of the mechanistic aspects of the evolution and maintenance of cooperation remain to be understood. For example, kin and group selection provide strong and satisfactory explanations about how an established cooperative allele can maintain a high fitness and resist invasion by cheaters despite cooperation cost. At the same time these theories are largely silent on the mechanisms by which an initially rare or non-existent cooperative allele can establish, survive and spread.

While models and simulations have played an important role in the understanding of the evolution of cooperation [START_REF] Axelrod | The Evolution of Cooperation[END_REF][START_REF] Nowak | Spatial games and the maintenance of cooperation[END_REF], they usually have strong assumptions that may result in an unrealistic representation of the initial appearance and spread of altruistic alleles.

Consider simulations of individuals living on a square lattice, with a single locus controlling a binary behavior (cooperate / do not cooperate), starting from a population of non-cooperators. The first cooperative allele to appear will be alone, and the individual bearing it will have nobody to cooperate with and will have a lower fitness than its neighbors. There are only two ways for such a "first" cooperative allele to invade, or at least not to immediately go extinct:

1. A mutation rate high enough to make the simultaneous appearance of two "cooperative mutations" at the same time in the same neighborhood possible.

2. A probabilistic selection scheme that allows for significant genetic drift so that the individual bearing this initial cooperative allele may not be selected out immediately. Instead, by chance it may have one or more offsprings despite its lower fitness compared to other individuals in the population.

In both these cases, via drift or mutations, several cooperators would be co-localized in the same neighborhood, forming a patch, and benefiting from higher fitness due to cooperative interactions. If we think about an initial altruism-promoting mutation (not the derepression of an already existing gene that can happen at a much higher rate) in a microbial population, the first mechanism is unlikely to be significant. However, the second one is likely to be very relevant for several reasons. To start with, in nature the mutations leading to cooperation are gradual, contrary to the binary cooperator/defector simulation tradition. Thus they may have low selection coefficients, which makes the reproductive success difference small. This is in direct contrast to the high selection coefficients arising from the rank-based selection scheme sometimes used in Aevol and other genetic algorithms. More over, a strong enough selection on other (non-social) traits that can make the selection coefficient of altruistic mutations even less important in comparison.

This chapter is primarily discussing the "selection on non social traits affecting selection on social traits" part of this second phenomenon. We will see how hitchhiking allows initially rare cooperative alleles, which are at this stage detrimental to the individuals bearing them, to spatially cluster in patterns favorable to their spread by kin selection.

The main research in this context has been performed by [START_REF] Santos | Genetic hitchhiking can promote the initial spread of strong altruism[END_REF]. However their work relies on strong and specific hypothesis and has several methodological drawbacks. Their findings rely on an island model including a somehow artificial selection for social diversity inside groups. The main result is that hitchhiking will slow down (but not prevent) the loss of cooperative alleles.

The other way genetic hitchhiking has been studied in the context of the evolution of cooperation is the maintenance of an already dominant population of cooperators [START_REF] Morgan | Selection on non-social traits limits the invasion of social cheats[END_REF]. While hitchhiking may permit the maintenance of any allele that randomly happens to be "at the right place" (close to a beneficial allele), there is no reason for altruistic alleles to benefit more from hitch-hiking than the non-cooperative ones. That conclusion was made by [START_REF] Morgan | Selection on non-social traits limits the invasion of social cheats[END_REF] and the authors used both meta population models and microbial experiments to support it. The key idea of their paper is that the already dominant subpopulation will "find" more non-social beneficial mutations by chance, simply because it has more individuals that could mutate. The necessity of cooperation already being dominant in order to benefit from hitchhiking limits the generality of these findings. Still, this work remains essential considering its historical context. While the evolution of social behavior has been theorized a long time ago, the first actual tests on micro-organisms in the lab are quite recent. And while experimentally replicating in the lab a "cheater invasion" dynamics may at first sight seem to be a toy problem or a preliminary step to any interesting study, it is quite striking that several independent research groups attempted to perform this simplistic experiment but did not find the expected, predicted and theorized result (Julien Benard-Capelle, personal communication). I think these failures send a strong signal about how limited are the models and frameworks that we use to think cooperation. [START_REF] Morgan | Selection on non-social traits limits the invasion of social cheats[END_REF] were to my knowledge the first to describe this unexpected "rescue by non-social mutations" dynamics. They were closely followed by [START_REF] Waite | Adaptation to a new environment allows cooperators to purge cheaters stochastically[END_REF], whose elegant experimental design is worth mentioning here. They co-culture a yeast strain consuming adenine and overproducing lysine with a mix of a strain consuming lysine and overproducing adenine ("cooperator") and a strain consuming lysine without producing adenine ("cheater"). They use a meta-population setup consisting of several isolated populations inoculated with equal proportions of cooperators and cheaters, in addition to the complementary adenine producing strain. The outcome of the competition in their setup is determined by the first fitness improving mutation. Most of the observed mutations are related to private traits such as the efficiency of nutrients transport. In some part of the sub-populations, it was a cooperator that got the first beneficial mutation and became dominant. In others, a cheater got the first beneficial mutation and also swept through the subpopulation. The authors conclude that "Thus, the probability of either type eventually dominating a co-culture is related to its initial abundance in the population, because a larger population is more likely to sample better mutations". Put differently, the mechanism is not directional. However, as noted by the authors, the sub-populations in which cheaters become dominant have a high probability of going extinct or at least grow very slowly, potentially affecting the fate of cooperation. These results confirmed the findings of [START_REF] Morgan | Selection on non-social traits limits the invasion of social cheats[END_REF].

One interesting detail of this experimental setup makes it different from the "classical" example of public good production. The cooperative trait in the study is directed toward another subpopulation, which means that adaptation cannot transform a cooperator into a high fitness cheater by simply "sequestering" the public good.

As we said, it is fascinating that several decades of research in social evolution theory are apparently outshone by such a simplistic mechanism. While a general underestimation of the role of genetic hitchhiking is probably not specific to cooperation, there is one precise reason to think that cooperation may benefit more from this mechanism than any other trait. Adaptive sweeps create a strong spatial structure which would affect cooperation more strongly than other, non-social traits (and there social evolution theory comes back). [START_REF] Waite | Adaptation to a new environment allows cooperators to purge cheaters stochastically[END_REF] suggest that this competition for non-social mutations could be one of the mechanisms creating the variance in the composition of the groups and thus the covariance between group composition and increase in group size necessary for maintenance of the cooperative trait [START_REF] Chuang | Simpson's paradox in a synthetic microbial system[END_REF]. However, their experimental setup is limited because cheaters can not grow on their own, and because cooperative alleles cannot evolve "de novo". They assume that there is a large supply of non cooperation-related beneficial mutations whose fitness benefit is high compared to the cost of cooperation, but do not study the durability of this supply nor the mutations affecting cooperation. These limitations do not allow the authors to study the selection for cooperation that could potentially be caused by this change in the composition of the groups due to hitchhiking, nor the next logical question which is: can cooperation be durably selected by iterations of this effect?

In this chapter, we develop and extend this idea using individual based simulations of genome evolution. We show that competition on non-social traits can create the favorable spatial assortment of individuals, and allow cooperation to evolve thanks to the effect of such competition on the spatial structure. Aevol is the perfect tool to study this mechanism: due to a realistic enough genomic layer we can study the linkage between alleles affecting social traits and other alleles, and the effectively open-ended curve-matching fitness function allows us to address the durability of the supply of beneficial mutations. Finally, Aevol spatial structure is less constrained than meta-populations.

We found that the adaptation to a non-cooperative trait, including the rare supply of beneficial mutations but also the more complex balance between "direct" fitness and mutational robustness, favors the evolution of cooperation. We analyzed relatedness created by the spread of beneficial mutations to show that the effect comes from the competition between several beneficial mutations creating spatial assortment, and not from cooperators having a bigger supply of beneficial "private" mutations.

Preliminary experiments and results

Evolving secretion with and without selection for metabolism

The core of our experiments is a comparison of the amount of public good produced between two different setups: (M-S) classical selection on metabolic (non-social) traits and on a cooperative trait (possibility to cooperate by public good secretion), and (N-S) where the group of traits that were metabolic target in previous experiment is considered neutral, not contributing to fitness. Several methodological precautions were taken to limit possible biases in the results: we replaced the "classical" multiplicative fitness computation by an additive combination of the cooperative part with the metabolic part. When there is no metabolic target (N-S setup), metabolic fitness is 1. We also prevent translocations between metabolic/neutral loci and secretion loci, because in the (M-S) setup a strong selection on metabolism will probably cause the adaptive evolution of complex metabolic genes that could otherwise provide a higher mutational supply to evolve secretion genes in the (M-S) setup than in the (N-S) setup. To implement this mutational isolation between M/N and S genes, we restricted the evolution of each of these traits to their own isolated "genetic unit" (in our experiments there is neither horizontal transfer nor homologous recombination, thus using different genetic units is just a way to prevent genetic exchange between different parts of the genome), and disabled transfer of DNA between these two genetic units.

Additionally, because the initial ancestor of an Aevol population is 5000 base pairs long with only a single gene typically taking less than five percent of the genome, the large amount of non-coding DNA and a single potential building block creates a very specific initial dynamics. Typically we first see an explosion in genome size due to many big duplications, followed by the divergence of the copies into new functions. These conditions are not likely to be relevant to study the evolution of cooperation in the context of genetic hitchhiking. Thus we decided to start with genomes that had already evolved their metabolic parts for a few thousands generations. The longer the genome has already evolved, the fewer possibilities there should be for adaptive mutations on the metabolic parts that could permit the potential hitchhiking of secretion-related alleles.

Figure 5.1 shows the evolution of public good secretion in three different setups: (M-S) starting with a metabolism that has evolved for 10k generations, (M-S) starting from a metabolism that has evolved for 480k generations, and (N-S) where previous evolution time is irrelevant (we took the same genome that underwent 10k generations of selection for metabolism, but re-assigned this part of the phenotype to be neutral). 10k), (M-S) starting from a longly evolved metabolism (480k), and (N-S) were there is no metabolism. Shaded zones represent standard error of the mean (50 independent replicates of evolution). Even though M/N and S alleles are "isolated" on the genome, the presence of an adaptive selection on M alleles favors the evolution of cooperative alleles on S loci.

In both (M-S) setups, a significantly higher level of public good secretion evolves than in (N-S) setup. Since we ruled out the possibility of M/N genes mutating into S genes, this result generally supports our hitchhiking hypothesis. However, our first somehow naive prediction regarding the (M-S) treatment that started after 480k generations of adaptation was not confirmed. We expected that no beneficial mutations for metabolism would be easily accessible after such a long time of evolution, and thus that there would not be any spatial assortment beneficial for cooperation that would be created by hitchhiking. This was not entirely the case since we see that the amount of secretion evolved in the (M-S)-480k treatment is lower than in (M-S)-10k but still significantly higher than in (N-S). One possibility is that while the amount of accessible metabolic innovations has indeed decreased, the balance between mutational robustness and direct fitness continues to cause "cycles" of adaptation: a mutant that have a higher fitness but a lower mutational robustness could locally spread, followed by the accumulation of deleterious mutations leading to its extinction. In this scenario the population would be constantly changing without any long-term change in average fitness.

Analysis of the relatedness created by selection on metabolism

We wanted to confirm that the signal we observe in the previous experiment does come from secretion-related alleles (that can be cooperative or non-cooperative) hitchhiking with metabolic innovations. Our hypothesis is that randomly distributing these beneficial metabolic mutations in a population exhibiting heterogeneity at secretion loci will create a particular spatial structure. A few of the competing secretion-related alleles will get a beneficial metabolic mutation and grow into a patch, while the others will be driven to extinction, more or less slowly according to whether they got a neutral or deleterious metabolic mutation. This mechanism will create relatedness (spatial assortment between individuals of the same type) at the secretion loci: since remaining secretion alleles grew into a patch, they are now surrounded by relatives while they were originally randomly distributed. As we already said, this phenomenon is not specific to cooperation since it could create relatedness at any other locus, and is a priori not directional since it would spread non-cooperative alleles as well as cooperative alleles. However this spatial clustering of secretion-related alleles will positively select for cooperation according to classical social evolution theory.

To test the hitchhiking creating relatedness hypothesis, we disabled secretion only keeping the M/N part of the phenotypic target, and tracked full lineages of the population for four thousands generations. At each generation, we have a snapshot of the population in which we tag each individual with a unique number. We can then consider this number as a particular allele at a unique imaginary locus. We propagate these tags into the lineage and can thus analyze how the descendants of the snapshot generation cluster during the next few decades (10 to 500) of generations. To do so we compute a pedigree based relatedness, which we will refer to as identity by descent relatedness, from the full lineage data using the following formula, inspired from [START_REF] Grafen | A geometric view of relatedness[END_REF]:

R = n i=1   k/A k =i P A k ,k × n v -P A k n -P A k   × 1 n
Where A k is the allele (number of the "type", e.g. of the ancestor at "snapshoted" generation) of individual k, P x is total number (in the whole population) of individuals bearing allele x, P x,k is the number of individuals bearing allele x in the neighborhood of individual k, v is the size of the neighborhood, and n is both the total number of individuals and of possible alleles (some of them potentially being extinct) in the population.

For any given composition of the population (P ∈ N n / n x=1 P x = 1), this relatedness measure varies between 0 (what we would get in a well mixed population) and 1 (all the alleles are fully geographically isolated). One question that remains is how to evaluate relatedness when one allele (one tag) entirely invades the population (meaning that all individuals come from the same ancestor): relatedness is here defined as "how close are individuals of type x to other individuals of type x compared to what it would be in a well-mixed population" which has no sense when there is only one type, and the value of the formula is then mathematically undefined ( 0 0 ). The two possible meaningful values we can assign to it are 0 (because interactions happens like in a well-mixed population since there is nothing to mix with) and 1 (because this unique allele is completely isolated since it is unique). We just stated possible arguments for both options, but the best answer is probably that relatedness measure is no longer relevant once one of the alleles entirely fixed. We decided to analyze relatedness using both possible measures (taking 0 and 1 to resolve the undefined case). It conveys more information in the sense that the divergence between these two measures of relatedness indicates a significant number of allele fixation events. Figure 5.2 shows this measure of identity by descent relatedness, which is also the relatedness that would be created at any imaginary locus, by the dynamics of metabolic innovations, in the same setup than on figure 5.1. We pooled all our "snapshots" of evolution, so x axis does not represent the generation in which we started tracking the alleles, but after how many generations of evolution (from the snapshot) we compute relatedness. This is effectively the size of the time window during which we monitor the spread of the tags from the snapshot population before computing the identity by descent relatedness.

We can see that more relatedness is created in both (M-S) setups than in (N-S) setup, and this is true for any "invasion time" after which we compute relatedness. We also see that among the (M-S) setups, the '10k' one is creating more relatedness in fewer generations, however it also lead to the full invasion of one of the alleles more quickly. The signature of these invasion events is the difference between the two variant measures of relatedness, i.e. the dashed line and the full line. Faster and more frequent allele fixation suggests that there are more accessible beneficial metabolic mutations at generation 10k than at generation 480k. Additionally the mutations at generation 480k have a smaller effect or may come with a trade-off, such as lower mutational robustness as we suggested. Although the average fitness is increasing extremely slowly or not at all, there are still wide within population fitness differences after 480k generations of evolution (data not shown). This observation could indicate that a significant amount of beneficial metabolic mutations are still accessible and can start spreading, but do not fix because they lower the mutational robustness. Further analysis of the mutational landscapes will be needed to confirm our interpretation.

Discussion

We examined the role of selection for non-cooperative traits on the evolution of cooperation. Previous work indicated that hitchhiking is in general not directional, and that cooperative and cheating alleles have equal chances of hitchhiking with metabolic innovations. However the spatial assortment (relatedness) between individuals bearing the same alleles that is created benefits cooperative alleles more than non-cooperative ones. We compared the evolution of Aevol individuals bearing two different isolated categories of genes: either metabolic and cooperative (M-S setup), or neutral and cooperative (N-S setup). We found that significantly more cooperation evolves in the (M-S) setup than in the (N-S) setup. We also did compare several variations of the (M-S) treatment, and found that while we expect the availability of beneficial metabolic mutations to decrease during evolution, there may be other dynamics enabling the hitchhiking. Specifically, the balance between fitness and mutational robustness may create its own hitchhiking mechanism, because the fittest individuals are not always able to transmit their genotype accurately and could be selected out.

While the first of the aforementioned mechanisms is a purely positive selection (some beneficial mutations occur and spread), the second one also relies on a purifying selection (the deleterious variants are wiped out). The two types of mechanism are of course strongly interconnected: we can hypothesize that because fittest genomes are "on the edge" of the ability to maintain the integrity of their information, some deleterious mutations will arise and fix, allowing beneficial mutations to happen again. This complex selective process seems to be creating a strong hitchhiking mechanism. We did not have to search very hard for regions of the parameter space where cooperative alleles are mostly lost in the (N-S) setup but do evolve and fix in the (M-S) setup. This allows us to start answering the more general question of the establishment of cooperation that we mentioned before. We understand that cooperation can be maintained because of non-random assortment between individuals giving a higher inclusive fitness to cooperative alleles (or a higher fitness to patches of cooperators). But how can the first (in the evolutionary history) individual performing the cooperative act (i.e. the original bearer of the cooperative mutation) not die right away? One potential answer we alluded to in previous chapters is gene regulation and quorum sensing that could allow to express the cooperative phenotype only when surrounded by other bearers of the cooperative allele. However this answer still raises a somewhat chicken-and-egg type problem. Namely, we then must also explain how this regulation and signaling have evolved, as well as how is the evolution of dishonest signaling prevented.

Our main result is that if selection coefficients of cooperative mutations are generally small compared to the benefits brought by metabolic innovations, then hitchhiking can be a satisfying answer to the problem, with a bigger effect than genetic drift. Hitchhiking works synergistically with spatial structure to promote the establishment and the maintenance of cooperation.

These preliminary results also put in question the use of binary game-theory inspired models to simulate the evolution of cooperation, that entirely fail to account for such dynamics. I would even say that the fact that classical binary simulations of evolution on lattices [START_REF] Nowak | Evolutionary games and spatial chaos[END_REF] can see cooperation evolving is surprising, especially when there is no stochasticity in the selection scheme, and may be due to their unrealistically high switching (mutation) rate allowing cooperative mutants to appear independently several times, in the same neighborhood, at the same generation.

A more precise analysis of the mechanisms permitting the establishment of cooperation may also bring some clarity to the strange debate about whether spatial structure would inhibit cooperation by increasing competition between kins which we discussed in details in the introduction and chapter 4. Many of the presented arguments have relied on simulation results, and the main message of some of these papers could be paraphrased as saying: "we made a simple simulation with spatial structure and did not manage to make cooperation evolve, so spatial structure inhibits cooperation". In retrospective it should not that surprising that cooperation was not the outcome of such simulations since they missed a mechanism allowing the spread of the initial cooperative allele for group/kin selection to happen. Additionally it is hard to disentangle the appearance and maintenance of cooperation: starting with a population of cooperators or of a mix of cooperators and cheaters is not enough. As we already emphasized cooperation is often a dynamical equilibrium involving a constant birth and death of cooperative patches.

In conclusion, while genetic hitch-hiking is often considered as a transient phenomenon, and in modeling as a minor deviation from the sacrosanct steady-state approximation, we have shown that it can play a huge role in creating specific spatial assortment patterns. Regarding the question of the equilibrium between beneficial mutations and mutational robustness, we build on the "survival of the flattest" theory that discusses the case of a population not residing on the highest fitness peak because it is too narrow to confer a high enough robustness to mutations [START_REF] Wilke | Evolution of digital organisms at high mutation rates leads to survival of the flattest[END_REF]. We go further to suggest, but so far not to demonstrate, the existence of a permanent short-term spreading of alleles that give a fitness benefit at the cost of a lower mutational robustness. It would be tremendously interesting to test some of these hypothesis in bacterial populations given how little is known about the real lineages in these populations. Unfortunately mutation-selection balance is very hard to study experimentally, and with current techniques we may not be able to detect some very low fitness organisms who descend from much fitter individuals and may still contribute to strong evolutionary forces. created by the spread of metabolic innovations after n (x axis) generations of evolution, in the same experimental setup as in figure 5.1 but without actually representing secretion. Solid line represents a relatedness measure in which we give the highest possible value (1) in case of invasion events, while dashed line represents a variant relatedness measure in which we give the lowest possible value (0) when such events occur.

In the first chapter, we suggest that traits under indirect selection, especially cooperation, may be particularly sensitive to second-order selection pressures such as the accessibility of beneficial mutations as well as other consequences of the evolutionary history [START_REF] Frénoy | Robustness and evolvability of cooperation[END_REF]. For more classical traits, ones that only affect the individuals bearing them and that are under strong selection, we often consider that adaptive evolution can "overcome" other evolutionary forces such as genetic drift, limited mutational landscape, constrained genetic architecture, influence of history, or genetic hitchhiking. There are specific reasons to think that genes under indirect selection are likely to be much more sensitive to such pressures. Indeed these genes often create a conflict between the evolutionary interests of the individual and the population, are in conflict with other genes, or provide a short-term cost but a longterm benefit. Mechanisms limiting their evolvability might then be essential in maintaining a long-term optimal outcome, which is the case in the context of cooperation, as seen in the second chapter [START_REF] Frénoy | Genetic architecture promotes the evolution and maintenance of cooperation[END_REF].

But we should stress that there is a priori no reason to think that microbial populations should be in this cooperative, optimal (in Pareto sense) state in nature, quite the opposite. So much research is devoted to cooperation exactly because it is the exception, and selfishness is pervasive in nature, at the individual as at the sequence level. Even a quick look at E. coli genome reveals many potentially selfish genetic elements, in conflict with the rest of the genome (e.g. prophages, insertion sequences, toxin-antitoxin systems). And these selfish elements can also benefit from all the mechanisms we mentioned. For example toxin-antitoxin systems encode by definition an evolvability suppression mechanism that makes it hard for the host to get rid of them, and neighboring hitchhiking sequences can also benefit from it. So we should not fall into the trap of considering that all these second-order adaptations (evolvability suppression, punishment or policing) will evolve to maintain cooperation because that would be somehow better for populations in general. Adaptations favoring cooperation will only evolve if cooperation is already dominant because it is favorable to the individuals expressing it, thanks to spatial structure for example, or maybe if they help to reach such a cooperative equilibrium. In all cases none of these mechanisms could permanently keep the population in a state detrimental to the basic units of evolution, genes and individuals. It is thus essential to consider the second-order traits as themselves subject to adaptation and selection at the individual level. Simply saying, as [START_REF] Wynne-Edwards | Intergroup selection in the evolution of social systems[END_REF][START_REF] Wynne-Edwards | Self-regulating systems in populations of animals[END_REF] did, that they evolve to keep the population in an optimal state is not enough. We must consider a competition between individuals bearing them and not bearing them, because reproduction happens at individual level; and a non-selfish outcome is then a priori a surprise. Neglecting the individual-level evolution of second-order traits and "population parameters" is the biggest drawback of the group selection view defended by [START_REF] Wallace | On the tendency of varieties to depart indefinitely from the original type[END_REF] and [START_REF] Wynne-Edwards | Intergroup selection in the evolution of social systems[END_REF].

Both inclusive fitness and modern group selection views 1 emphasize that cooperative behaviours spread when the individuals bearing them have a higher fitness (because they somehow benefit more from cooperation). Then the answer 2 to "why cooperation" is simply that the genes are selfish! Sociobiology emphasized the role of an individual as a reproductive strategy evolved by its genes. An assembly of sequences forming a genome whose reproduction relies on the "group" (of sequences, here the individual) is often considered as a cooperative state. However, sequences themselves are still driven by their own evolutionary interests, and bringing a benefit to the host is just one of many ways in which they can maximize their spread and survival.

All these considerations warn us against the too teleological view of second-order selection making cooperation dominant because of the benefits to the population. On the other hand, when some cooperative behaviours do evolve and spread because the spatial structure (e.g. population viscosity) makes cooperators benefit more from the effects of cooperation, selection is likely to further stabilize this cooperative trait using the aforementioned mechanisms. Indeed, while these second-order adaptations will not change the phenotypes of the cooperators, they will lower the frequency of the appearance of cheaters by mutations. Since we are here only discussing situations where cooperation is dominant even without evolvability suppression, a cheater lineage is always an evolutionary dead-end on the shorter or longer term. Additionally, these temporary patches of cheaters reduce the fitness of their neighbors, making the evolution of evolvability suppression mechanisms plausible. The question that remains is what will happen when cooperation is not dominant without these mechanisms, but could become dominant thanks to them. The only way to provide an answer is to consider the evolvability suppression mechanism as any other trait subject to selection. This leads to thinking about the long-term outcome of a competition (in a spatially structured environment) of individuals bearing it with individuals not bearing it. In this line of thinking and in continuation of the third chapter, we are currently conducting experiments on E. coli investigating the effect of gene overlap as an evolvability suppression mechanism. While we use synthetic constructs -the genetic overlap was algorithmically designed and not evolved -, we plan to compete a strain with the overlapped system and a strain with the same but non-overlapped system in conditions that we suppose would select for evolvability suppression. These experiments could confirm or infirm our hypothesis about the evolutionary origin of gene overlap and tell us more about how bacteria manage frequent transitions between different environments at population scale.

Of course the classical private (non cooperation-related) traits can also evolve and benefit 1 We do not include Wynne-Edwards nor Wallace in modern. 2 At least in the inclusive fitness view.

from the sort of mechanisms described above, like evolvability suppression. However, the key difference is that for the genes with private effect, the deleterious mutations will quickly be purged by natural selection because they reduce the fitness of the host. On the other hand, for cooperation genes, the mutants will temporarily spread and potentially inflict a huge cost on the other individuals. In the case of private traits, the (long-term) cost paid by an individual for generating a small fraction of deleterious mutants is as low as this mutation rate multiplied by the selection coefficient of the mutation. In the second case of a cooperative trait, it can be much higher3 .

One of the fundamental ideas we discussed in this thesis can be summarized as follows. The selection pressure to avoid generating deleterious mutants for private essential genes is low, because one can rely on natural selection to wipe out these mutants (their selection coefficient is high). But the selection pressure to avoid generating deleterious mutants for cooperative genes may be much higher because the selection coefficient of these mutations is low! If the reader allows me a far-fetched analogy, we, apes, do not care about a tiny fraction of our cells dying from an extremely deleterious somatic mutation, but we do care about cancers caused by invasive somatic mutations that are not deleterious to the individual cells bearing them, because these cells will spread and may make the whole organism collapse. But of course the real evolutionary question is not whether we care as cognitive animals, but whether the sequences constituting our genome "care". It is in this view that we should think about the evolution of tumor suppressors genes. As we already said, policing is very similar to evolvability suppression, and could even be considered as a special case and an example of evolvability suppression.

It is surprising that the impact of second-order selection on cooperation has not been a subject of much more research. One potentially powerful tool to explore such questions is bioinformatics. However, as I said in the introduction, bioinformatics has not given much consideration to second-order evolution. It would be extremely interesting to check our prediction of a stronger selection for mutational robustness for cooperative genes than for essential private genes. We are however limited by how little is currently known about the genotypeto-phenotype mapping. As we said in the introduction, there are two processes taking part in what is commonly referred as mutational robustness: avoiding mutations and being tolerant to mutations. To consider the first process, we could use our knowledge of some specific sequence motifs that are particularly prone to replication errors (such as the repetition of a single nucleotide [START_REF] Ackermann | DNA sequences shaped by selection for stability[END_REF][START_REF] Lee | Rate and molecular spectrum of spontaneous mutations in the bacterium Escherichia coli as determined by whole-genome sequencing[END_REF]). However, the same motifs are also likely to cause errors in protein synthesis, which happens at a much higher rate, making the analysis of these sequences unsuitable (or a least prone to hard to correct biases) for our inquiring [START_REF] Rocha | An analysis of determinants of amino acids substitution rates in bacterial proteins[END_REF][START_REF] Drummond | Mistranslation-induced protein misfolding as a dominant constraint on coding-sequence evolution[END_REF]. Indeed since essential genes are often highly expressed they could be under a much stronger selection pressure for avoiding synthesis errors [START_REF] Drummond | Why highly expressed proteins evolve slowly[END_REF], making it difficult to compare them with cooperation genes. We could also consider the ability to cope with mutations, a large part of which may be determined by the proportion of the mutations that are synonymous. If our hypothesis is true, we would then expect a higher selection pressure for the use of codons with synonymous mutational neighborhood (weighted by the sequence-dependent probabilities of specific mutations to happen) to encode cooperation genes than to encode essential private genes. However, there are many potentially much stronger selection pressures shaping codon usage, such as the availability of the tRNAs which strongly affects the speed of synthesis [START_REF] Ikemura | Correlation between the abundance of escherichia coli transfer rnas and the occurrence of the respective codons in its protein genes: a proposal for a synonymous codon choice that is optimal for the e. coli translational system[END_REF]. Since private genes are more likely to be essential and highly expressed, the signal we might observe would also be biased by a higher usage of common codons by these genes. The picture becomes even more complex if we keep in mind that the genetic code has itself evolved, and that the tRNAs are also under selection and are co-evolving with the rest of the genome. It is then no wonder why bioinformaticians have given so little attention to second-order selection so far! We can however hope that a higher availability of biological data (especially on the likeliness and effects of specific mutations) improves the situation and allows a better understanding of the selection pressures shaping the sequences.

Mutations are not the only way to switch between a cooperative and non-cooperative phenotype. A somewhat similar question that is almost absent from this work is regulation. Some bacterial cooperation systems, such as pyoverdine in Pseudomonas aeruginosa, display complex regulatory networks, which allow them to adapt their behaviour to the environmental conditions, including the presence of other bacteria. This is of course interesting in the case of the evolution of cooperation where it could allow organisms to adapt their cooperative behaviour to the behaviour of their neighbors. In Pseudomonas aeruginosa, some of the secretion systems are indeed under the control of a quorum sensing loop, resulting in individuals that secrete more when not alone. However, the same limitations are present as in the case of policing mechanisms: the quorum sensing system is itself subject to evolution, so the signal produced by the neighbors may be unreliable, and some individuals could stop answering the signal.

Gene regulation also raises some semantic questions, such as how to call individuals bearing cooperation genes but not expressing them? In the fourth chapter we extended this question to the genetic control of the rate of switching toward a cooperative state. We showed cases where the dominant population does not express cooperation but does evolve a high probability of switching toward cooperative individuals (meaning that some of the descendants will express the cooperative behaviour). This can be considered as a division of labour and we can find examples in nature where one small fraction of the population performing a cooperative act is sustaining the growth of the whole population [START_REF] Ackermann | Self-destructive cooperation mediated by phenotypic noise[END_REF]. This lead us to call these individuals evolving a high probability of having cooperative offsprings "second-order cooperators". At the same time we could as well consider that they are dooming one part of their lineage to "feed" the other part, which is not that "cooperative".

We implemented this switching as a genetic mutation (or as a phenotypic switch with inheritance), however heritability is not a requirement and our results could hold in the case of a pure phenotypic plasticity (regulation), without inheritance of the cooperative state. We also discuss the case of the cooperative act being a sacrifice, in which case the distinction between genotypic and phenotypic (or heritable and non-heritable) control of the cooperative behaviour is irrelevant. Furthermore, we suggest a case where the difference between heritable and non-heritable control of the cooperative state does make a big difference. When cooperators need to "work together", heritable control will tend to cluster together individuals of the same phenotype, while non-heritable control will produce no spatial assortment.

If we were to abandon the "division of labour" view, we could instead consider the evolved probability of switching toward a cooperative phenotype as an attempt to establish a cooperation. Bacteria frequently alternate between different environments having different spatial structures (e.g. establishing in a host, sporulating, migrating outside of the host, infecting new hosts) and maintaining cooperation may not be possible in every stage of this environmental cycling. There is one particular potential example that I would like to highlight, which is biofilm formation. A very preliminary bioinformatics analysis on the annotated sequence of Escherichia coli K12 MG1655 retrieved from NCBI GenBank shows that several genes that are annotated on EcoCyc as "deletion increases biofilm formation" are extremely prone to mutations due to a high number of single nucleotide repeats. While at first sight repression and de-repression of a regulated cooperation gene could seem to be an easier way to achieve such cycles between cooperative and non-cooperative states, the advantage of the mutation is that it will be transmitted to offsprings, giving a higher chance to establish into a patch of cooperators if the environment is favorable enough (e.g. viscous). One part of this hypothesis may be relatively easy to test, since biofilm polymers can be stained by Crystal Violet, allowing us to easily measure the propensity of a genotype to form biofilms. It could thus be possible to compare this propensity between a wild type strain and a mutant in which we recode differently (less mutagenic patterns) the genes supposed to repress biofilm formation. However, supposing that one effectively finds a very high mutation rate toward a biofilm producer phenotype, testing the adaptiveness of this second-order trait would be extremely hard. It is probably very dependent not only on the environmental conditions but also on the way these conditions change. Independently of these concerns, a first step would probably be to find whether other organisms with a higher propensity to form biofilms than MG1655 also show the same pattern.

The question of what is the difference between using regulation (phenotypic plasticity) and mutations to alternate between multiple phenotypes is not specific to cooperation. The factors determining which of these two evolutionary strategies might be favored include the population size, the mutation rate, the generation time compared to the period of the environmental changes, and potentially the novelty and predictability of the new environments. A high population size, high mutation rate, and short generation time gives to microbes the fascinating ability to rely on mutations to face environmental changes, and it is only recently that we started considering that evolution can happen on ecological time scale.

There is something that I find extremely powerful in this idea that mutation rates, population size and generation times will shape different evolutionary strategies, and this is much broader than the question of regulation versus mutations to adapt to changing environments. In the context of mutational robustness that we already discussed in detail, I would like to mention one paper that I find fascinating. [START_REF] Krakauer | Redundancy, antiredundancy, and the robustness of genomes[END_REF] discuss one part of mutational robustness, which is the evolution of redundancy to be less sensitive to mutations. They consider that a cost of this redundancy is that it will diminish the efficiency of natural selection since the selection coefficients of the mutations will be smaller or even null. Redundancy may thus allow the propagation of the fragile genotypes that would otherwise be wiped out by natural selection. The authors suggest that redundancy would thus only evolve in small populations, because natural selection is there less efficient as a mechanism to remove deleterious variants. On the opposite they suggest that anti-redundancy may evolve in large populations with a high mutation rate (typically microbes) exactly to further increase the strength of natural selection. [START_REF] Elena | Effects of population size and mutation rate on the evolution of mutational robustness[END_REF] have partially confirmed this hypothesis using Avida. I think this idea is very similar to the one we suggest about a lower use of mutational robustness for essential "private" genes because one can then rely on natural selection to purge deleterious alleles.

Another idea discussed in the fifth chapter is the balance between short-term reproductive success and longer term mutational robustness. This balance has been theorized for a long time, for example in the context of "survival of the flattest" and quasi-species theory [START_REF] Wilke | Evolution of digital organisms at high mutation rates leads to survival of the flattest[END_REF], and experimentally tested in RNA viroids [START_REF] Codoñer | The fittest versus the flattest: experimental confirmation of the quasispecies effect with subviral pathogens[END_REF] and viruses [START_REF] Sanjuán | Selection for robustness in mutagenized rna viruses[END_REF]. In the literature, the dominant thinking in this context is a competition between several distant "fitness peaks", isolated in the mutational landscape. One of these peaks typically gives a higher "short-term" fitness but is also stepper [START_REF] Elena | Evolution. climb every mountain?[END_REF], giving a lower mutational robustness4 . In the fifth chapter, we suggest an alternative: such rough fitness peaks may exist and be accessible "on top" of the flatter and lower fitness peak on which a population may already be residing. Under our hypothesis, some individuals are constantly climbing these "secondary" fitness peaks even if they are doomed to accumulate deleterious mutations in the long-term because these fitness peaks are too rough. This is more in line with the "Aevol thinking", where our curve matching problem is de facto open-ended since it is impossible to perfectly match a sum of gaussians with triangles. Individuals can always find mutations that make them closer to the optimum, but the adaptation is still bounded because specifying more precise triangles means a higher genome size, leading to a higher mutational burden. While Aevol "chemistry" is of course far from biological life, it remains obvious that a finite number of nucleotides only allows a finite number of possible phenotypes (performed biochemical processes in the case of Aevol), and the higher the size of the nucleotide sequence the higher the possible number of distinct biochemical processes. This becomes even more striking if one thinks about regulatory networks5 , in which case we can extend our thinking to consider the regulation as part of the phenotype. A very complex and fine tuned regulatory network could determine a phenotype very well adapted to different environmental conditions and different life stages, at the cost of encoding many transcription factors. However, such precise and versatile network would affect mutational robustness at least in part due to the increase in genome size necessary to encode the regulatory elements.

In this frame of thinking, we must not only view the genomes as avoiding too rough fitness peaks, but also as being constantly "on the edge" of their ability to maintain their phenotype under the biochemical mutation rates they are facing. More importantly, we should consider small rough fitness peaks "on top" of the current resident one (and not only as an alternative "on the side" of it). It is always possible to tune a little bit more one protein, to add a new input into a regulatory network, and it will slightly increase the short-term fitness of the individual but the extra mutational burden may as we said doom the lineage in the longterm. The fitness-robustness tradeoff may lead to a permanent polymorphism inside microbial populations, especially the ones adapting to constant environments, consisting of temporarily fitter lines that start invading but eventually collapse and more robust but slightly less fit lines that persist. This somewhat far-fetched hypothesis would require a delicate, potentially frequency-depen-dent driven balance between direct and indirect selection pressures that may not be attainable. Still, testing it in real microbial populations would be tremendously interesting. At first sight RNA viruses may be the best candidates for this kind of experiments because they have a very high biochemical mutation rate. However, as we already pointed out, our hypothesis is more likely to be true (and easier to test) in constant enough environment, when phenotypic changes happen as the result of mutations and not regulation. Fast-changing environments would be less suited for studying this phenomenon because they would probably lead to the accessibility of beneficial mutations without any tradeoffs. It is thus necessary to use a genotype that has adapted to a constant environment for a long time, and such long-term evolution experiments are hard to achieve with viruses that can not reproduce on their own and whose life stages are by definition not constant. Better candidates would thus be some of the long-term Lenski lines that are both well adapted to their environment and experiencing high mutation rates due to a mutator phenotype that evolved a long time ago.

To conclude, we saw that second-order evolution is still a fascinating and open topic, extremely relevant in the context of the evolution of cooperation. While at the beginning of my PhD, I had not the slightest intention of going in that direction, it is some unexpected findings arising from the Aevol system that drove me to consider the links between second-order selection pressures and the evolution of cooperation. While there has been a small war among Artificial Life aficionados to define what systems are really open-ended, I would argue that the mere ability to have unexpected findings with biological relevance tells much more about the promises of an artificial life system than an arbitrary criteria of open-endedness. Our system has certainly provided enough of unexpected over the years, as well as some interesting biological results presented in this work and promising future research directions.

Bibliography

  2.5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Materials and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.1 Aevol digital evolution system . . . . . . . . . . . . . . . . . . . . . . . . 2.6.2 Evolving a bank of cooperators . . . . . . . . . . . . . . . . . . . . . . . 2.6.3 Analysis of the genomic architecture . . . . . . . . . . . . . . . . . . . . 2.6.4 De novo evolution of cooperation . . . . . . . . . . . . . . . . . . . . . . 2.7 Supporting Information: cooperation in Aevol . . . . . . . . . . . . . . . . . . . 3 Experimental use of gene overlaps to protect costly genes: from algorithms to synthetic biology 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 For evolutionary biologists . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 For synthetic biologists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 For computer scientists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Why using synthetic biology (as a tool)? . . . . . . . . . . . . . . . . . . 3.2 The RiBoSor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Explanation and proof of principle . . . . . . . . . . . . . . . . . . . . . 3.2.2 More detailed description of the algorithm . . . . . . . . . . . . . . . . . 3.2.3 Algorithm results for Escherichia coli genes . . . . . . . . . . . . . . . . 3.2.4 Experimental validation: preliminary results . . . . . . . . . . . . . . . . 3.3 The Overlapor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Description of the algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1.1 Simpler case of "r0" configuration . . . . . . . . . . . . . . . . . 3.3.1.2 (almost) General case: same strand shifted overlap . . . . . . . 3.3.2 Using information about non-synonymous possible changes . . . . . . . . 3.3.3 Proof of concepts: finding Escherichia coli genes that could overlap with lacI or TEM-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Evolution of second-order cooperation by selection for high switching rate 4.1 Introduction: second order cooperation . . . . . . . . . . . . . . . . . . . . . . . 4.2 Material and methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Description of the system . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Relevance of our individual-based synchronous framework to study the evolution of cooperation . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Effect of parameters on the selection at locus controlling cooperation . . 4.3.2 Evolution of mutation rate in the context of allele C dominant . . . . . . 4.3.3 Evolution of second order cooperation (high non cooperator to cooperator mutation rate) in some conditions where D is dominant . . . . . . . . . . 4.3.4 Extending to higher switching rates . . . . . . . . . . . . . . . . . . . . . 4.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Competing metabolic innovations favor the spread of hitchhiking cooperative alleles by increasing relatedness 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Preliminary experiments and results . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Evolving secretion with and without selection for metabolism . . . . . . . 5.2.2 Analysis of the relatedness created by selection on metabolism . . . . . . 5.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . of secretion cost on the evolution of cooperation . . . . . . . . . . . . . . 1.2 Average amount of secretion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Beneficial mutations for secretion . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Cheater invasion dynamics in phenotypically similar starting populations . . . . 2.2 Example of the preferential maintenance of certain secretion genes . . . . . . . . 2.3 Correlation between the genetic architecture of cooperation genes and the resistance to cheater invasion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Secretion genes at generation 0 and at generation 2,000 partitioned between four categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Genetic architecture associations after 20,000 generation of de novo evolution of cooperation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Aevol genetic code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Examples of constrained genetic architecture in Aevol . . . . . . . . . . . . . . . 2.8 Individuals are tempted to stop cooperating . . . . . . . . . . . . . . . . . . . . 2.9 Groups of cooperators do better than groups of defectors . . . . . . . . . . . . . 2.10 Individuals that cooperate more are the ones that benefit more from secretion . 3.1 Fake overlap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Protection of the costly gene by the overlap . . . . . . . . . . . . . . . . . . . . 3.3 Distribution of the size of the biggest overlap for all E. coli genes . . . . . . . . 3.4 Galactose operon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 The algorithm developed for r0 case will not directly work on p1 case . . . . . . 4.1 Evolution of cooperation alleles and mutation-rate modifier alleles when mutation rate varies between 0.001 and 0.01 . . . . . . . . . . . . . . . . . . . . . . . 4.2 Effect of mutator alleles on the outcome at cooperation locus, inferred by enforcing high and low mutation rates . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Spatial association between pure cooperators and "second order" cooperators . .4.4 Evolution of cooperation alleles and mutation-rate modifier alleles when mutation rate varies between 0.001 and 0.1 . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Evolution of cooperation alleles and mutation-rate modifier alleles when mutation rate varies between 0.001 and 0.5 . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Average public good secretion in three different conditions . . . . . . . . . . . . 5.2 Identity by descent relatedness created by metabolic innovations . . . . . . . . .

Figure 1

 1 Figure 1.1: Effect of secretion cost on the evolution of cooperation. Each line represents an average of 50 replicate experiments conducted at the same secretion cost. The shaded area is one standard error of the mean. Results for cost = 2 are indistinguishable from cost = 1 and are thus not shown.

  Figure1.2: Average amount of secretion between generation 10, 000 and generation 13, 000, sorted by the cost regime in the first 10, 000 generations. Each point represents a single replicate population. There are 100 independent replicates for each treatment.

  Figure1.3: Beneficial mutations for secretion at generation 10, 000, depending on the regime during the first 10, 000 generations. Each point represents the average effect of 10, 240, 000 mutations within single replicate population. There are 100 independent replicates for each treatment.

  Figure2.1: Cheater invasion dynamics in phenotypically similar starting populations. In the main figure each line represents the average secretion, over time, of 50 replicate populations started from the same ancestor. For clarity, we did not include the standard error of each group of replicate populations. The insert figure shows all 50 replicate populations for the two most extreme population groups, zoomed in on the time period of interest for our analyses. Specifically, of all the population groups sharing a common ancestor, the blue populations had the highest and red the lowest average secretion between generation 200 and generation 1, 000. Note that average secretion in the inset represents the average secretion within each population, whilst in the main figure it is the average of the secretion of all the individuals from the 50 replicate populations that share the same ancestor.

Figure 2 . 3 :

 23 Figure 2.3: Correlation between the genetic architecture of cooperation genes and the resistance to cheater invasion. Resistance is measured by the amount of secretion surviving cheater invasion. The four types of associations between secretion and metabolic genes shown here are: sharing an operon (A, dark blue), overlapping (B, green), having at least one of the previous two properties (C, red), and having both of them (D, light blue).

Figure 2 . 4 :

 24 Figure 2.4: Secretion genes at generation 0 and at generation 2, 000 partitioned between four categories: (a) sharing a promoter (i.e. being on the same operon) without overlapping with a metabolic gene (dark blue), (b) overlapping and sharing an operon with a metabolic gene (light blue), (c) overlapping without sharing an operon with a metabolic gene (green), (d) neither sharing an operon nor overlapping with a metabolic gene (red). Error bars represent one standard error of the mean (fifty original cooperators). The color of the error bars corresponds to the genetic architecture category which they relate to.

Figure 2 . 5 :

 25 Figure2.5: Genetic architecture associations after 20, 000 generation of de novo evolution of cooperation, at (A) high, c = 0.3 and (B) low, c = 0.01 secretion cost. In both cases, we quantified the presence of operons or overlaps between secretion genes and metabolic genes (S vs M) as well as between metabolic genes and other metabolic genes (M vs M). Genes were partitioned in four categories, labeled as in the Fig.2.4: sharing a promoter (an operon) without overlapping with a metabolic gene (dark blue), overlapping and sharing an operon with a metabolic gene (light blue), overlapping without sharing an operon with a metabolic gene (green), not sharing an operon nor overlapping with any metabolic gene (red). Error bars represent plus and minus one standard error of the mean for the fifty replicate populations and their color corresponds to the genetic architecture category they relate to.

Figure 2 . 7 :

 27 Figure 2.7: Examples of constrained genetic architecture in Aevol. (A)As is often the case in natural systems, here the two digital genes belong to the same operon. They share a promoter and a terminator sequence and are thus being expressed at the same level. These hypothetical genes would belong to the "operon only" category from Fig.2.4 and Fig.2.5. (B) These two genes also share the same operon but additionally their sequences overlap, putting them in the "operon and overlap" category. In this case, the genes are in different reading frames and do not share a STOP codon, although such configuration is also possible. As the black gene boxes indicate, the left STOP codon corresponds to the left START codon, while the right STOP codon corresponds to the right START codon. (C, D) Two examples of genes from the "overlap only" category which are encoded on different strands. This is not an exhaustive list of possible genetic constraints, as a gene may, for example, share an operon with a gene on the same strand while simultaneously overlapping with a gene on an opposite strand.

Figure 2 . 8 :Figure 2 . 9 :

 2829 Figure 2.8: Supporting Figure S1. Individuals are tempted to stop cooperating.For each of the 50 populations, we plot the average fitness increase an individual would experience if it would individually stop cooperating, i.e. the temptation to defect, against the average amount secreted by an individual in the population. Except in the populations where no cooperation has evolved (red points), the temptation is always greater than zero.

Figure 3

 3 Figure 3.2: Protection of the costly gene1 by the overlap, as a function of the size of the overlap, for the effect of a single amino-acid change (a) P e = 0.1 and (b) P e = 0.3. Different lines indicate different proportion of frame-shifts among all the generated mutations.

  Figure3.3: Cumulative distribution function of the size of the biggest overlap we can create for all E. coli genes. In about 75% of E. coli genes we can create an overlap bigger than half of the gene (relative position smaller than 0.5).

  acids D,G,C Encoded by 8 + 128 + 16 = 152 or (0000000000000010011000) 2 Table 3.3: Encoding of amino acids as powers of 2 codon at each position in the B string.

  Figure3.5: The algorithm developed for r0 case will not directly work on p1 case. At position 4, if we consider all the amino-acids that could be encoded in the frame of B (in which codon boundaries are delimited by spaces) by making all possible synonymous changes in the sequence A (top sequence, codon boundaries are indicated by a color code), we would consider replacing TCA by AGC (both are Serine), which would also affect the amino-acid encoded in frame of B at position 3 (go from GAT to GAA, which is not synonymous). This is a problem because due to the way dynamic programming works, we need to be able to score at position 4 without changing the score of position 3 and even without knowing what "path" lead us to the current scoring.

Figure 4 . 1 :Figure 4 . 2 :

 4142 Figure 4.1: Spontaneous evolution of cooperation alleles and mutation-rate modifier alleles for different combinations of cost and selection pressure when mutation rate varies between 0.001 (low) and 0.01 (high). Blue bars represents the proportion of "pure cooperators", ie individuals of genotype (C, *, *). Green bars represent the proportion of individuals of genotype (*, *, H DC ). Red bars represent the proportion of individuals of genotype (*, H CD , *).

Figure 4 . 3 :

 43 Figure4.3: Average (5 replicates populations) spatial association between pure cooperators and "second order" cooperators (green) compared to average spatial association between pure cooperators and non cooperators (red) for different combinations of cooperation cost (cost) and selection pressure (m) when mutation rate varies between 0.001 (low) and 0.01 (high). We performed paired one-sided student t-tests for the first association being higher than the second (five independent replicates of evolution). * indicates p-value lower than 10 -2 , ** lower than 10 -3 , *** lower than 10 -4 .

Figure 4 . 4 :Figure 4 . 5 :

 4445 Figure 4.4: Spontaneous evolution of cooperation alleles and mutation-rate modifier alleles for different combinations of cost and selection pressure when mutation rate varies between 0.001 (low) and 0.1 (high).

Figure 5

 5 Figure5.1: Average public good secretion in three different conditions: (M-S) starting from a partially evolved metabolism (10k), (M-S) starting from a longly evolved metabolism (480k), and (N-S) were there is no metabolism. Shaded zones represent standard error of the mean (50 independent replicates of evolution). Even though M/N and S alleles are "isolated" on the genome, the presence of an adaptive selection on M alleles favors the evolution of cooperative alleles on S loci.

Figure 5

 5 Figure5.2: Average (over 125 experiments) of the identity by descent relatedness (y axis) created by the spread of metabolic innovations after n (x axis) generations of evolution, in the same experimental setup as in figure5.1 but without actually representing secretion. Solid line represents a relatedness measure in which we give the highest possible value (1) in case of invasion events, while dashed line represents a variant relatedness measure in which we give the lowest possible value (0) when such events occur.

  1.1 Correlation between accessibility of mutations and future secretion . . . . . . . . 1.2 Influence of history versus chance on secretion . . . . . . . . . . . . . . . . . . . 3.1 Overlaps bigger than 100bp in E. coli K12 MG1655 . . . . . . . . . . . . . . . . 3.2 Candidates found by our algorithm for galK. . . . . . . . . . . . . . . . . . . . . 3.3 Encoding of amino acids as powers of 2 . . . . . . . . . . . . . . . . . . . . . . . 3.4 Genes that could overlap with lacI or with TEM-1 . . . . . . . . . . . . . . . . .

  Table1.2: Influence of history versus chance on secretion. SShist is the sum of squares due to history, while SStot is the total sum of squares (history plus chance).

				Chapter 1
	Cost of secretion Correlation coefficient p-value
	0.35	0.6639		< 10 -13
	0.5	0.3669		< 10 -3
	0.8	0.4134		< 10 -4
	NoSec	0.1790		0.07
	Table 1.1: Correlation between the proportion of mutants with increase in secretion (weighted
	by the magnitude of these effects) at generation 10, 000 and the average amount secreted be-
	tween generation 10, 000 and generation 13, 000 for each treatment.
	Cost of secretion SShist/SStot F statistic p-value
	0.35	0.63	16.9349	< 10 -15
	0.5	0.44	7.7311	< 10 -7
	0.8	0.57	13.3905	< 10 -13

Table 3

 3

	Gene 1 Gene 2 Type Prop. gene 1 Prop. gene 2 Size
	rzpQ	rzoQ	p1	0.51	1 255
	rzpD	rzoD	p1	0.40	1 183
	mokC hokC	p0	0.73	1 153
	sgrS	sgrT	NA	0.58	1 132
	ryeA	ryeB	NA	0.49	1 121
	yigM	metR	r0	0.13	0.12 113
	hokB	mokB	p1	0.73	0.65 110

.1: Overlaps bigger than 100bp in E. coli K12 MG1655.

  We consider the codons from C i to C i+6 to try to create a RBS-start for (S 1 , S 2 , S 3 , S 4 , S 5 , S 6 ) ∈ j∈[1,6] synonymous(C i+j ) do // synonymous(X) is the set of codons synonymous to X, including X if ContainsRBSspacerSTART(S 1 S 2 S 3 S 4 S 5 S 6 ) then newsequence=C 1 ..C i-1 S 1 ..S 6 C i+6 ..C n ;

	AbsPosSTART=3 * i + P osStartInM otif ;
	RemoveSTOPS(&newsequence,AbsPosSTART)// Remove stop codons in
		frame of the START we create
	RemoveConcurrentRBS(&newsequence,AbsPosSTART)// Making only
		synonymous changes in gene1, without creating stop codons in
		new reading frame
	RemoveFShotspots(&newsequence)// Making only synonymous changes
		in gene1, without creating stop codons in new reading frame,
		without creating concurrent RBS in new reading frame
	ReportCandidateSequence(newsequence)
	end
	end
	end	Algorithm 1: the RiBoSor

Table 3

 3

	CRP-cAMP
					spot42
	p3	p2 p1	galE	galT	galK	galM
	oe		oi		RBS
							galP
	galR	galS
					nagC
						CRP-cAMP
	D-galactose		GlcNAc-6-P
	Figure 3.4: Galactose operon. Quite messy, isn't it?
	phosphorylation of kanamycin.
	Start position Frame Syn. changes Non-syn. changes Remaining changes
	475	1		96	1		1
	544	1		91	1		1
	675	2		74	0		0
	742	1		75	1		1
	995	1		61	1		0
	998	1		62	1		0
	1099	1		56	1		0
	1129	2		31	1		0
	1130	2		29	1		0

.2: Candidates found by our algorithm for galK.

Here we use the term selection coefficient to denote the relative deleterious fitness effect of a mutation. A selection coefficient of 1 indicates lethality, and a selection coefficient of 0 indicates neutrality.

Personal motivationsJohn Von Neumann was at the origin of the three main ideas that I developed in this introduction. Firstly, our understanding of the evolution of cooperation owes a lot to game theory, a field invented by Von Neumann. Secondly, second-order evolution is just the ability of natural selection to modify its own "parameters". In electrical engineering, we call "Von Neumann architecture" the category of systems where programs can modify themselves because there is no real distinction between program and data in memory. Thirdly, and finally, the whole field of Artificial Life is entirely built on Von Neumann's idea of self-replicating machines. I hope this answers the question of why a computer scientist like me would do a PhD in evolutionary biology. The question that remains is why would a biologist care about the computer science aspects of my work. I hope that the concepts I discuss here would bring closer the computational beauty of these ideas to biologists, in the same way that working on the bench has made me embrace the beauty of their biological instantiations.

As all good microbiologists, we will assume that there is no genotypic heterogeneity within a colony.

We include a given codon in the set of its synonymous codons.

Note that the proper definition of these costs supposes a definition of fitness that integrates the ability of the offsprings to themselves generate fit offsprings, as we emphasized in the introduction and in chapters

and

We will carefully phrase our arguments as not to leave any doubt about what fitness measure we are referring to.

Not in the sense of a higher mutation rate, but of a higher average deleterious effect of mutations.

Which are partially implemented in Aevol but not in the version we used in this work.

Acknowledgments

Acknowledgments

Acknowledgments Ça y est ! Après trois ans, deux mois, et vingt-deux jours, la fin est proche ! Je fais les dernières corrections à mon tapuscript et les dernières vérifications logistiques (réservation de la salle: ok ; réservation de François Taddei : ok ; prévenir maman : oups ...). Alors que j'avais prévu d'écrire ce matin des remerciements détaillés en bonne et due forme, j'ai péniblement émergé vers midi d'une léthargie ethanolisée, consécutive à la célébration nocturne de mon dernier vendredi en tant que doctorant.

Et oui, on en a passé du temps dans ce rade, à se plaindre de nos directeurs de thèse ou chefs de service. Et c'est d'abord vous, compagnons de galère, que je voudrais remercier. Merci Antoine, Clément, Ariane, Jehanne, Paul, Tatiana, Aleksandra, Jean, et tous les autres ! Cette aventure aurait été beaucoup moins amusante sans vous.

Quand j'ai rencontré François Taddei il y a bientôt cinq ans, je ne connaissais pas grand chose à l'évolution microbienne. Aujourd'hui je ne sais toujours pas grand chose, mais j'ai une idée un peu plus précise de ce que j'aimerais comprendre pendant les soixante prochaines années. Merci François pour m'avoir permis de travailler sur ce projet fantastique et pour m'avoir fait découvrir toutes ces questions passionnantes. Merci aussi pour m'avoir toujours encouragé dans mes explorations (errances ?) transdisciplinaires, pour avoir supporté stoïquement mon humour parfois douteux, et pour ne m'avoir pas tenu rigueur de mon manque d'intérêt envers certains projets pour lesquels ma formation initiale en informatique théorique te semblait plus adaptée. C'est promis, un jour je t'apprendrai à chercher de la musique sur Internet ! Thank you Dule for mentoring me for all these years! I do not think any part of my PhD would have succeeded without your help and advices. Thank you for your tolerance regarding the time I spent wandering on various side projects, and thank you for your help during the last few months with this manuscript.

Ma thèse faisait partie d'un projet plus vaste sur la coopération et le transfert d'information. Merci Julien, Dule et Tatiana. J'ai appris énormément en travaillant avec vous ! Une autre forme de coopération présente dans cette thèse est le travail qu'Antoine et moi avons démarré il y a deux ans, qui est détaillé dans le chapitre trois. Merci Antoine ! Ma thèse aurait été bien ennuyeuse sans toi. Merci Aude pour nous avoir rejoints dans cette aventure et Ariel pour nous avoir conseillés. Merci à vous trois pour ce projet un peu fou. Contraindre l'évolution microbienne, c'est un programme intéressant et un sacré défi ! Merci Marjorie et Chantal pour votre encadrement et votre patience quand j'ai commencé Acknowledgments à travailler à la paillasse ! Merci Julien pour ce stage de M2 qui m'a fait découvrir et aimer la microbiologie, et merci pour tes précieux conseils par la suite. Ces errances expérimentales m'ont permis de prendre du recul sur mes modèles et m'ont fait découvrir des problèmes fascinants sur lesquels j'espère avoir l'occasion de me pencher à nouveau dans le futur.

Part III

Conclusions and Perspectives