Myriam Badawi

Isabelle Giraud

Fabrice Vavre

Pierre Gre `ve

Richard Cordaux
email: richard.cordaux@univ-poitiers.fr.

Signs of Neutralization in a Redundant Gene Involved in Homologous Recombination in Wolbachia Endosymbionts

Keywords: endosymbiosis, gene loss, molecular evolution, selection relaxation, genomic reduction, nonorthologous gene displacement. GBE

Genomic reduction in bacterial endosymbionts occurs through large genomic deletions and long-term accumulation of mutations. The latter process involves successive steps including gene neutralization, pseudogenization, and gradual erosion until complete loss.

Although many examples of pseudogenes at various levels of degradation have been reported, neutralization cases are scarce because of the transient nature of the process. Gene neutralization may occur due to relaxation of selection in nonessential genes, for example, those involved in redundant functions. Here, we report an example of gene neutralization in the homologous recombination (HR) pathway of Wolbachia, a bacterial endosymbiont of arthropods and nematodes. The HR pathway is often depleted in endosymbiont genomes, but it is apparently intact in some Wolbachia strains. Analysis of 12 major HR genes showed that they have been globally under strong purifying selection during the evolution of Wolbachia strains hosted by arthropods, supporting the evolutionary importance of the HR pathway for these Wolbachia genomes. However, we detected signs of recent neutralization of the ruvA gene in a subset of Wolbachia strains, which might be related to an ancestral, clade-specific amino acid change that impaired DNA-binding activity. Strikingly, RuvA is part of the RuvAB complex involved in branch migration, whose function overlaps with the RecG helicase. Although ruvA is experiencing neutralization, recG is under strong purifying selection. Thus, our high phylogenetic resolution suggests that we identified a rare example of targeted neutralization of a gene involved in a redundant function in an endosymbiont genome.

Introduction

Host-restricted intracellular bacteria, either as parasites, commensals or mutualistic symbionts, exhibit multiple distinguishing genomic features in comparison with their free-living relatives. Hence, obligate bacterial endosymbionts (that live and replicate exclusively in the cytoplasm of the host cells) are characterized by reduced genomes, accelerated DNA sequence evolution, and strong A+T nucleotide compositional bias [START_REF] Wernegreen | For better or worse: genomic consequences of intracellular mutualism and parasitism[END_REF][START_REF] Moran | Genomics and evolution of heritable bacterial symbionts[END_REF][START_REF] Moya | Learning how to live together: genomic insights into prokaryote-animal symbioses[END_REF][START_REF] Mccutcheon | Extreme genome reduction in symbiotic bacteria[END_REF][START_REF] Van Leuven | An AT mutational bias in the tiny GC-rich endosymbiont genome of Hodgkinia[END_REF]. These features are the consequences of the process of genomic reduction, which is triggered by enhanced genetic drift and relaxation of selection because of effective population size reduction and stable environmental conditions [START_REF] Moran | Accelerated evolution and Muller's ratchet in endosymbiotic bacteria[END_REF][START_REF] Nilsson | Bacterial genome size reduction by experimental evolution[END_REF][START_REF] Toft | Evolutionary microbial genomics: insights into bacterial hos adaptation[END_REF].

The initial stages are characterized by large genomic deletions mediated by recombination between proliferating mobile genetic elements [START_REF] Moran | Genomic changes following host restriction in bacteria[END_REF][START_REF] Plague | Extensive proliferation of transposable elements in heritable bacterial symbionts[END_REF][START_REF] Walker | Does my genome look big in this ?[END_REF]Cerveau, Leclercq, Bouchon, et al. 2011). On the long term, relaxed purifying selection leads to the accumulation of slightly deleterious mutations and the inactivation of nonessential genes or genes with redundant functions [START_REF] Ohta | Development of neutral and nearly neutral theories[END_REF][START_REF] Silva | Genome size reduction through multiple events of gene disintegration in Buchnera APS[END_REF][START_REF] Tamas | 50 million years of genomic stasis in endosymbiotic bacteria[END_REF][START_REF] Dagan | The "domino theory" of gene death: gradual and mass gene extinction events in three lineages of obligate symbiotic bacterial pathogens[END_REF][START_REF] Moran | The dynamics and time scale of ongoing genomic erosion in symbiotic bacteria[END_REF]) (fig. 1). Coupled with a deletion bias, newly formed pseudogenes are ultimately lost along with mobile genetic elements [START_REF] Mira | Deletional bias and the evolution of bacterial genomes[END_REF][START_REF] Moran | The process of genome shrinkage in the obligate symbiont Buchnera aphidicola[END_REF][START_REF] Ogata | Mechanisms of evolution in Rickettsia conorii and R. prowazekii[END_REF][START_REF] Go ´mez-Valero | The evolutionary fate of nonfunctional DNA in the bacterial endosymbiont Buchnera aphidicola[END_REF][START_REF] Fuxelius | Visualization of pseudogenes in intracellular bacteria reveals the different tracks to gene destruction[END_REF])(fig. 1). In addition, gene loss can involve genes carrying essential functions such as DNA repair, which further increases the rate of gene loss [START_REF] Dale | Loss of DNA recombinational repair enzymes in the initial stages of genome degeneration[END_REF][START_REF] Rocha | Comparative and evolutionary analysis of the bacterial homologous recombination systems[END_REF]. In particular, genes involved in the homologous recombination (HR) pathway are often depleted in these genomes, implicating fewer recombination events [START_REF] Dale | Loss of DNA recombinational repair enzymes in the initial stages of genome degeneration[END_REF][START_REF] Rocha | Comparative and evolutionary analysis of the bacterial homologous recombination systems[END_REF][START_REF] Moran | Genomics and evolution of heritable bacterial symbionts[END_REF]. This is consistent with the long-term genomic stability observed in various ancient endosymbiont genomes [START_REF] Tamas | 50 million years of genomic stasis in endosymbiotic bacteria[END_REF][START_REF] Silva | Why are the genomes of endosymbiotic bacteria so stable?[END_REF]. Although the later stages of gene loss in endosymbionts (from gene inactivation to complete loss) have been well-documented (fig. 1 and references therein), few studies have described examples of the initial step of gene loss, that is, neutralization preceding inactivation. This is because most analyzed genomes are from ancient endosymbionts with highly reduced genomes, in which the process of gene loss is already at an advanced stage.

Various mechanisms can lead to gene neutralization in endosymbiont genomes, either by altering all genes of the genome in the same manner or by targeting specific genes. In the first case, enhanced genetic drift and less efficient purifying selection, coupled with a Muller's ratchet effect due to reduced opportunities for recombination, lead to the global accumulation of slightly deleterious mutations in many genes. This scenario explains the general acceleration in DNA sequence evolution observed in endosymbiont genomes [START_REF] Moran | Accelerated evolution and Muller's ratchet in endosymbiotic bacteria[END_REF][START_REF] Ohta | Development of neutral and nearly neutral theories[END_REF][START_REF] Wernegreen | Evidence for genetic drift in endosymbionts (Buchnera): analyses of protein-coding genes[END_REF][START_REF] Itoh | Acceleration of genomic evolution caused by enhanced mutation rate in endocellular symbionts[END_REF][START_REF] Woolfit | Increased rates of sequence evolution in endosymbiotic bacteria and fungi with small effective population sizes[END_REF][START_REF] Wernegreen | Mutation exposed: a neutral explanation for extreme base composition of an endosymbiont genome[END_REF][START_REF] Fry | The roles of positive and negative selection in the molecular evolution of insect endosymbionts[END_REF][START_REF] Blanc | Reductive genome evolution from the mother of Rickettsia[END_REF][START_REF] Mccutcheon | Extreme genome reduction in symbiotic bacteria[END_REF]. Gene neutralization can also occur due to targeted relaxation of selection on a gene that became superfluous for the endosymbiont, as in the case in which a gene is involved in a redundant function with another gene [START_REF] Moran | Genomics and evolution of heritable bacterial symbionts[END_REF][START_REF] Moya | Learning how to live together: genomic insights into prokaryote-animal symbioses[END_REF]. This is well illustrated by functional complementation, which may happen when multiple endosymbionts co-occurring within a single host can fulfill the same function. This has been demonstrated for the endosymbionts Buchnera aphidicola BCc and Serratia symbiotica in the insect Cinara cedri,i nw h i c h B. aphidicola is undergoing genome degradation and functional replacement by the coexisting S. symbiotica [START_REF] Pe ´rez-Brocal | A small microbial genome: the end of a long symbiotic relationship?[END_REF]. Alternatively, functional redundancy may occur within a single endosymbiont genome. However, to our knowledge, there has been no report clearly demonstrating targeted relaxation of selective pressures in such functionally redundant genes leading to neutralization. This is because gene neutralization is a transient stage preceding actual pseudogenization, whose detection requires a high phylogenetic resolution and, thus, investigation of a large set of closely related endosymbiont strains.

In this study, we report an example of likely gene neutralization in a redundant portion of the HR pathway within the bacterial endosymbiont Wolbachia. Wolbachia are maternally inherited microorganisms that have been associated with arthropod and nematode hosts for greater than 100 Myr and are able to manipulate arthropod host reproduction to increase their own transmission [START_REF] Bandi | Phylogeny of Wolbachia in filarial nematodes[END_REF][START_REF] Werren | Wolbachia: master manipulators of invertebrate biology[END_REF][START_REF] Cordaux | The impact of endosymbionts on the evolution of host sex determination mechanisms[END_REF]. Wolbachia endosymbionts present a large genetic diversity, with multiple phylogenetic supergroups defined with capital letters [START_REF] Lo | Taxonomic status of the intracellular bacterium Wolbachia pipientis[END_REF]. In particular, Wolbachia strains from supergroups A and B are found in arthropods and Wolbachia strains from supergroups C and D are found in nematodes. Multiple Wolbachia genomes have been sequenced; they show typical features of long-term obligate endosymbionts, such as reduced genome size, accelerated DNA sequence evolution, and A+T nucleotide bias [START_REF] Wu | Phylogenomics of the reproductive parasite Wolbachia pipientis wMel: a streamlined genome overrun by mobile genetics elements[END_REF][START_REF] Foster | The Wolbachia genome of Brugia malayi: endosymbiont evolution within a human pathogenic nematode[END_REF][START_REF] Klasson | Genome evolution of Wolbachia strain wPip from the Culex pipiens group[END_REF][START_REF] Klasson | The mosaic genome structure of the Wolbachia wRi strain infecting Drosophila simulans[END_REF][START_REF] Darby | Analysis of gene expression from the Wolbachia genome of a filarial nematode supports both metabolic and defensive roles within the symbiosis[END_REF]). Yet, despite their ancient association with invertebrates, many Wolbachia genomes contain recently active mobile genetic elements [START_REF] Cordaux | Intense transpositional activity of insertion sequences in an ancient obligate endosymbiont[END_REF][START_REF] Kent | Phage WO of Wolbachia: lambda of the endosymbiont world[END_REF][START_REF] Cerveau | Short-and long-term evolutionary dynamics of bacterial insertion sequences: insights from Wolbachia endosymbionts[END_REF][START_REF] Leclercq | Remarkable abundance and evolution of mobile group II introns in Wolbachia bacterial endosymbionts[END_REF]). In addition, several Wolbachia strains experience recombination [START_REF] Werren | Recombination in Wolbachia[END_REF][START_REF] Ellegaard | Comparative genomics of Wolbachia and the bacterial species concept[END_REF]) and gene conversion [START_REF] Cordaux | Gene conversion maintains nonfunctional transposable elements in an obligate mutualistic endosymbiont[END_REF]. Strikingly, the HR pathway, which is commonly depleted in long-term endosymbionts [START_REF] Akman | Genome sequence of the endocellular obligate symbiont of tsetse flies, Wigglesworthia glossinidia[END_REF][START_REF] Tamas | 50 million years of genomic stasis in endosymbiotic bacteria[END_REF][START_REF] Dale | Loss of DNA recombinational repair enzymes in the initial stages of genome degeneration[END_REF][START_REF] Gil | The genome sequence of Blochmannia floridanus:comparative analysis of reduced genomes[END_REF][START_REF] Rocha | Comparative and evolutionary analysis of the bacterial homologous recombination systems[END_REF], is apparently intact in some [START_REF] Wu | Phylogenomics of the reproductive parasite Wolbachia pipientis wMel: a streamlined genome overrun by mobile genetics elements[END_REF][START_REF] Foster | The Wolbachia genome of Brugia malayi: endosymbiont evolution within a human pathogenic nematode[END_REF], but not all [START_REF] Darby | Analysis of gene expression from the Wolbachia genome of a filarial nematode supports both metabolic and defensive roles within the symbiosis[END_REF]), Wolbachia genomes.

The HR pathway is involved in DNA repair of single-and double-strand breaks and is responsible for large-scale genomic rearrangements and incorporation of homologous foreign DNA [START_REF] Aravind | SURVEY AND SUMMARY: Holliday junction resolvases and related nucleases: identification of new families, phyletic distribution and evolutionary trajectories[END_REF][START_REF] Kowalczykowski | Initiation of genetic recombination and recombination-dependent replication[END_REF][START_REF] Zun ˜iga-Castillo | The recombination genes AddAB are not restricted to gram-positive bacteria: genetic analysis of the recombination initiation enzymes RecF and AddAB in Rhizobium etli[END_REF])( fig. 2). Interestingly, a crucial step of the HR pathway (branch migration) may be fulfilled by genes with overlapping functions, that is, the RuvAB complex or the RecG helicase, although efficiency is reduced when only one of the two possibilities is active [START_REF] Meddows | RecG helicase promotes DNA double-strand break repair[END_REF]). In the context of genomic reduction undergone by Wolbachia, such functional redundancy is predicted to be dispensable [START_REF] Mendonc ¸a | Loss of genetic redundancy in reductive genome evolution[END_REF]). These observations raise the question whether the HR pathway in general and functional redundancy in this pathway in particular are maintained by purifying selection in Wolbachia because they are essential, or HR happens to take place merely because the pathway has not been pseudogenized yet. To address this question, we assessed the distribution of 12 major genes of the HR pathway in 20 sequenced genomes from the four major Wolbachia supergroups A-D [START_REF] Lo | Taxonomic status of the intracellular bacterium Wolbachia pipientis[END_REF][START_REF] Comandatore | Phylogenomics and analysis of shared genes suggest a single transition to mutualism in Wolbachia of nematodes[END_REF]. This prompted us to analyze selection patterns of HR genes in Wolbachia supergroups A and B, using an extended set of Wolbachia strains comprising both sequenced genomes and strains for which we performed targeted resequencing. This high phylogenetic resolution enabled us to uncover signs of recent neutralization of the redundant ruvA gene in a subset of Wolbachia strains from supergroup B hosted by isopods.

Materials and Methods

Identification of HR genes

We selected 12 genes encoding the major proteins predicted to be involved in the HR pathway in Wolbachia [START_REF] Aravind | SURVEY AND SUMMARY: Holliday junction resolvases and related nucleases: identification of new families, phyletic distribution and evolutionary trajectories[END_REF][START_REF] Kowalczykowski | Initiation of genetic recombination and recombination-dependent replication[END_REF][START_REF] Zun ˜iga-Castillo | The recombination genes AddAB are not restricted to gram-positive bacteria: genetic analysis of the recombination initiation enzymes RecF and AddAB in Rhizobium etli[END_REF][START_REF] Rocha | Comparative and evolutionary analysis of the bacterial homologous recombination systems[END_REF][START_REF] Cromie | Phylogenetic ubiquity and shuffling of the bacterial RecBCD and AddAB recombination complexes[END_REF])( fig. 2). The genes are: recJ, recF, recO and recR (which initiate the repair of singlestrand DNA breaks), addA and addB (which initiate the repair of double-strand DNA breaks), recA (which catalyzes strand exchange), ruvA and ruvB (which perform branch migration), ruvC (which resolves Holliday junction intermediates), and priA (which initiates replication during double-strand break repair). In addition, we selected recG whose protein function overlaps with that of the RuvAB complex [START_REF] Meddows | RecG helicase promotes DNA double-strand break repair[END_REF]).

We analyzed these 12 genes in a diverse set of Wolbachia strains encompassing the four major supergroups A-D of Wolbachia diversity. We obtained sequences of HR genes by similarity searches using BLASTp [START_REF] Altschul | Basic local alignment search tool[END_REF])against 20 sequenced Wolbachia genomes from supergroups A-D, as described in table 1. We also performed targeted resequencing of 14 additional Wolbachia strains from supergroups A a n dB( supplementary table S1, Supplementary Material online). Total DNA extraction, polymerase chain reaction (PCR), and sequencing were performed as previously described [START_REF] Cordaux | Intense transpositional activity of insertion sequences in an ancient obligate endosymbiont[END_REF]. In brief, DNA was extracted using a standard phenol-chlorophorm protocol, PCR was performed using the PCR primers and conditions provided in supplementary table S2, Supplementary Material online, and purified PCR products were directly sequenced on an ABI Prism 3130 Genetic Analyzer. The nucleotide sequences generated in this study have been deposited in GenBank under accession numbers KM066817-KM0066942.

Sequence Analyses of Wolbachia Supergroups A and B Nucleotide sequences of HR genes from 29 Wolbachia strains were aligned together by codons using the Muscle algorithm implemented in MEGA5 software [START_REF] Tamura | MEGA5: molecular evolutionary genetics analysis using maximum likelihood, evolutionary distance, and maximum parsimony methods[END_REF]. We removed seven palindromic regions because they were difficult to align with confidence. These regions, resembling Wolbachia palindromic elements (WPE) [START_REF] Ogata | Discovery of protein-coding palindromic repeats in Wolbachia[END_REF], were located in addA (nucleotide positions [np] 289-459, 907-1146, and 3076-3387), addB (np 778-1023 and np 2452-2655), and priA (np 523-1365 and 2587-2790). As these WPE-like sequences are inserted in frame and do not generate premature stop codons, they apparently do not inactivate the HR genes. The only exception is addA in the six Wolbachia strains from supergroup B hosted by isopods, in which a premature stop codon was generated at np 3100-3102, resulting in the deletion of the entire nuclease domain. This deletion may have limited functional consequences, as it has been shown that the loss of the nuclease domain significantly reduces efficiency of the exonuclease activity of the AddAB complex, but repair can still operate [START_REF] Amundsen | Dual nuclease and helicase activities of Helicobacter pylori AddAB are required for DNA repair, recombination, and mouse infectivity[END_REF]). Nevertheless, we conservatively split addA into two parts for our evolutionary analyses: addA_1 encompasses np 1-3099 and addA_2 encompasses np 3103-3837.

To avoid biased evolutionary analyses due to poor resolution, we removed all but one representative for all groups in which Wolbachia strains showed less than 0.2% pairwise nucleotide divergence across the 12 HR genes. This filter resulted in the removal of ten Wolbachia strains from analyses Locus tags are provided for the seven completed genomes (identified by *). The 14 other genomes are incomplete; therefore missing genes may be truly absent or may just be absent from the genome assembly.

ACFP00000000 M F F F F F F F M F F F Klasson et al. 2009 wWil Drosophila willistoni AAQP00000000 F F F F M F M F F F F F Remington et al. unpublished wSuzi Drosophila suzukii CAOU00000000 F F F F F F F F F F F F Siozios et al. 2013 B wPip-Pel* Culex quinquefasciatus AM999887 WP0175 WP0219 WP0766 WP0932 WP0901 WP0482 WP0630 WP0359 WP0769 WP0988 WP0987 WP1146 Klasson et al. 2008 wAlbB Aedes albopictus CAGB00000000 F F F F F F F F F F F F Mavingui et al. 2012 wDi Diaphorina citri AMZJ0000000 F F F F F F F F F F F F Saha
(supplementary table S3, Supplementary Material online). Our final data set then consisted of the 19 remaining Wolbachia strains.

Because intragenic recombination may alter phylogenetic and selection signals, we tested our data set for evidence of intragenic recombination using RDP3 [START_REF] Martin | RDP3: a flexible and fast computer program for analyzing recombination[END_REF], using seven different algorithms (rdp, geneconf, chimaera, maxchi, bootscan, siscan, and 3seq), linear sequences, and uninformative sequences masked. A recombination event was accepted when it was detected by at least four of the algorithms. Then, phylogenetic correlation of the recombinant was checked with the tree generated by RDP. After each confirmation, a rescan was launched. Intragenic recombination was detected in three regions: 1) np 1-346 of ruvC in strain wNo, 2) np 2657-3051 of addB in strain wDi, and 3) np 1024-1122 of addB in all strains. These recombining sequences were removed from the analyses.

Selection Analyses

Selection analyses were performed by calculating the ratios of the rates of nonsynonymous (Ka) to synonymous (Ks) nucleotide substitutions per site on each HR gene as implemented in codeml PAML4 software [START_REF] Yang | Neutralization of Redundant Gene in Wolbachia GBE Genome[END_REF]. Ka/Ks ratios >1, <1, and =1 are indicative of positive selection, purifying selection, and neutral evolution, respectively. Pairs of models were compared using likelihood ratio tests (LRTs), as described in [START_REF] Yang | Likelihood ratio tests for detecting positive selection and application to primate lysozyme evolution[END_REF].WhentheP value of an LRT was significant at the 5% level, the model with the highest likelihood value was considered as the best-fit model. Otherwise, the two models were not significantly different, which means that adding complexity to the model does not improve its likelihood. As a result, the simplest model was considered as the best-fit model. We performed four successive types of comparisons.

First, we investigated global patterns of selection by comparing two models: 1) The neutral model with the Ka/Ks ratio forced to 1 in all branches of the phylogenetic tree (the simplest model in the comparison), and 2) a single Ka/Ks ratio model with the same Ka/Ks ratio in all branches.

Second, for HR genes in which the single Ka/Ks ratio model was the best-fit model, we searched for selection heterogeneity by comparing two models: 1) The single Ka/Ks ratio model from the previous analysis (the simplest model in the comparison), and 2) a 3-Ka/Ks ratio model that implements a different Ka/Ks ratio for each of three monophyletic clusters (supergroup A, supergroup B hosted by insects, and supergroup B hosted by isopods; fig. 3).

Third, for HR genes in which the 3-Ka/Ks ratio model was the best-fit model, we searched for neutralization signal in the cluster with the highest Ka/Ks ratio in the 3-Ka/Ks ratio model by comparing two models: 1) the 3-Ka/Ks ratio model with the Ka/ Ksratioforcedto1intheclusterwiththehighestKa/Ksratioin the 3-Ka/Ks ratio model (the simplest model in the comparison), and 2) the 3-Ka/Ks ratio model from the previous analysis.

Fourth, for the HR gene showing signs of neutralization, we searched for positive selection on codons (which may have inflated the Ka/Ks ratio) by using the branch-site model [START_REF] Yang | Bayes empirical Bayes inference of amino acid sites under positive selection[END_REF][START_REF] Zhang | Evaluation of an improved branch-site likelihood method for detecting positive selection at the molecular level[END_REF].

To evaluate the robustness of our analyses, we used multiple phylogenetic frameworks based on a resampling strategy. Specifically, following a jackknife procedure, we removed each gene in turn from the concatenated alignment of the 12 HR genes and recalculated a phylogenetic tree based on the remaining genes. For each of the 12 alignments, we used MEGA5 to identify the best substitution model (GTR+G with gamma=5 in all cases). Next, each alignment was used to build a maximum-likelihood tree with 1,000 bootstrap replicates (85% partial deletion), using MEGA5. Hence, we obtained 12 phylogenetic trees, each of which was used as a phylogenetic hypothesis for selection analyses. The 12 trees corresponded to five different topologies exhibiting minor variations in terminal branching patterns (supplementary fig. S1, Supplementary Material online). This enabled us to calculate confidence intervals for LRTs.

Results and Discussion

Distribution of HR Genes in Wolbachia Strains

Analysis of the distribution of the 12 HR genes in 20 sequenced Wolbachia genomes from supergroups A-D (table 1) revealed that most of the HR genes from supergroup C Wolbachia FIG. 3 . -Maximum-likelihood phylogenetic tree of the 12 concatenated HR genes, based on the GTR+G model (gamma = 5) and 85% partial deletion. Bootstrap scores (%) are shown on branches (based on 1,000 replicates). The phylogenetic tree reveals three highly supported monophyletic groups, each composed of six Wolbachia strains including: Strains from supergroup A, from supergroup B hosted by insects and from supergroup B hosted by isopods. Intragroup mean distances are noted besides each group. Intergroup mean distances are: 10.2% between A and B from insects, 9.3% between A and B from isopods, and 5.9% between B from insects and B from isopods. strains were pseudogenized [START_REF] Darby | Analysis of gene expression from the Wolbachia genome of a filarial nematode supports both metabolic and defensive roles within the symbiosis[END_REF][START_REF] Godel | The genome of the heartworm, Dirofilaria immitis, reveals drug and vaccine targets[END_REF], indicating that the HR pathway has been inactivated in these strains. In addition, most of the HR genes were missing in all supergroup D strains except wBm, which has an apparently intact HR pathway [START_REF] Foster | The Wolbachia genome of Brugia malayi: endosymbiont evolution within a human pathogenic nematode[END_REF]. Because wBm is the only finished supergroup D genome [START_REF] Foster | The Wolbachia genome of Brugia malayi: endosymbiont evolution within a human pathogenic nematode[END_REF], we cannot conclude whether some HR genes have not been sequenced or the HR pathway has been inactivated in other supergroup D genomes. In contrast, the HR pathway is apparently intact in Wolbachia strains from supergroups A and B [START_REF] Wu | Phylogenomics of the reproductive parasite Wolbachia pipientis wMel: a streamlined genome overrun by mobile genetics elements[END_REF][START_REF] Klasson | Genome evolution of Wolbachia strain wPip from the Culex pipiens group[END_REF]. The difference in completeness of the HR pathway or lack thereof is not really surprising given the contrast in host range (arthropods vs. nematodes for supergroups A/B and C/D, respectively) and lifestyle (reproductive parasite vs. mutualist for supergroups A/B and C/D, respectively) of these supergroups. Based on these observations, we focused our selection analyses on supergroups A and B. To obtain a more extensive sampling of HR genes in supergroups A and B, we performed targeted resequencing of 14 additional Wolbachia strains. After removal of strains showing less than 0.2% pairwise nucleotide divergence across the 12 HR genes (see Materials and Methods), our final data set consisted of 18 supergroups Aa n dBWolbachia strains and wBm (supergroup D) as an outgroup.

Selective Pressures on HR Genes

To measure the selective pressures acting on HR genes in supergroups A and B Wolbachia strains, we compared the Ka/Ks ratios of the 12 genes by using LRTs as implemented in PAML 4 [START_REF] Yang | Neutralization of Redundant Gene in Wolbachia GBE Genome[END_REF]. To evaluate the robustness of our results, we performed analyses using multiple phylogenetic frameworks, based on a jackknife resampling strategy (see Materials and Methods). Assuming a single Ka/Ks ratio in each HR gene tree, the best-fit to the data was obtained for Ka/Ks ratios ranging from 0.05 (for recA)t o0 . 3 5( f o raddB), which are all significantly less than 1 (all P < 0.001; table 2 and supplementary table S4, Supplementary Material online). This is indicative of purifying selection globally acting on all 12 HR genes. This strong conservation suggests that the HR pathway is evolutionarily important for Wolbachia strains from supergroups A and B. HR, together with repeats, creates high levels of genomic variation in prokaryotes [START_REF] Rocha | Comparative and evolutionary analysis of the bacterial homologous recombination systems[END_REF][START_REF] Treangen | Genesis, effects and fates of repeats in prokaryotic genomes[END_REF]. Strikingly, Wolbachia genomes from supergroups A and B bear an unusually high proportion of repeats and experience recombination [START_REF] Werren | Recombination in Wolbachia[END_REF][START_REF] Kent | Phage WO of Wolbachia: lambda of the endosymbiont world[END_REF][START_REF] Cerveau | Short-and long-term evolutionary dynamics of bacterial insertion sequences: insights from Wolbachia endosymbionts[END_REF][START_REF] Leclercq | Remarkable abundance and evolution of mobile group II introns in Wolbachia bacterial endosymbionts[END_REF][START_REF] Ellegaard | Comparative genomics of Wolbachia and the bacterial species concept[END_REF]. Genome plasticity (and the factors favoring this plasticity) may represent an appreciable evolutionary advantage for Wolbachia, perhaps in relation with its ability to horizontally transfer between various arthropod host species [START_REF] Cordaux | Wolbachia infection in crustaceans: novel hosts and potential routes for horizontal transmission[END_REF]) and with the fact that most of these strains are involved in an evolutionary arms race with their hosts [START_REF] Cordaux | The impact of endosymbionts on the evolution of host sex determination mechanisms[END_REF].Forexample,ithas been shown that recombination caused by repeats and HR genes enables some parasites to respond specifically to the adaptative immune system of the host [START_REF] Finlay | Common themes in microbial pathogenicity revisited[END_REF][START_REF] Mehr | Differential roles of homologous recombination pathways in Neisseria gonorrhoeae pilin antigenic variation, DNA transformation and DNA repair[END_REF].

Heterogeneity and Relaxation of Selection Pressures

To investigate whether purifying selection patterns have been stably maintained throughout Wolbachia evolution, we tested for heterogeneity in Ka/Ks ratios in each HR gene by comparing the above results to a model in which different Ka/Ks ratios were allowed in the three monophyletic clusters of the ingroup, each consisting of six Wolbachia strains: supergroup A, supergroup B hosted by insects, and supergroup B hosted by isopods (fig. 3). In this clustering scheme, average nucleotide divergence across the 12 HR genes ranged from 1% to 2% within groups and 6-10% between groups (fig. 3).

The model with three Ka/Ks ratios was significantly better than the model with a single Ka/Ks ratio under all 12 jackknifed phylogenetic hypotheses for four HR genes: addA_1, addB, recO,andruvA (all P < 0.05; table 2 and supplementary table S5, Supplementary Material online). The 3-Ka/Ks ratio model was also better for recF and ruvC albeit for only a subset of jackknifed phylogenetic hypotheses. Given the limited robustness of the results for recF and ruvC, we conservatively rejected heterogeneity in Ka/Ks ratios for these two genes. In contrast, the results are robust for the four other genes addA_1, addB, recO,a n druvA, as all jackknifed trees consistently support heterogeneity in Ka/KS ratios. Heterogenous selection patterns have already been observed among different endosymbiont strains and were found to result from the effect of strong genetic drift or enhanced mutation rate [START_REF] Wernegreen | Evidence for genetic drift in endosymbionts (Buchnera): analyses of protein-coding genes[END_REF][START_REF] Itoh | Acceleration of genomic evolution caused by enhanced mutation rate in endocellular symbionts[END_REF][START_REF] Woolfit | Increased rates of sequence evolution in endosymbiotic bacteria and fungi with small effective population sizes[END_REF][START_REF] Wernegreen | Mutation exposed: a neutral explanation for extreme base composition of an endosymbiont genome[END_REF][START_REF] Fry | The roles of positive and negative selection in the molecular evolution of insect endosymbionts[END_REF][START_REF] Blanc | Reductive genome evolution from the mother of Rickettsia[END_REF], as expected in the context of genomic reduction undergone by Wolbachia.

To investigate whether heterogeneity in Ka/Ks ratios in these four HR genes may reflect relaxation of selective pressures leading to neutralization in a subset of the Wolbachia strains, we tested whether the highest Ka/Ks ratio in the 3-Ka/ Ks ratio model was different from 1. We predicted that the elevated Ka/Ks ratio should be significantly different from 1 under relaxed selection without neutralization, and not significantly different from 1 under neutral evolution. For addA_1, addB,andrecO, we found that the 3-Ka/Ks ratios model was significantly better than the model assuming neutralization in a subset of Wolbachia strains, under all 12 jackknifed phylogenetic hypotheses (all P < 0.01; table 2 and supplementary table S6, Supplementary Material online). In contrast, for ruvA, the two models were not significantly different from each other, implying that the highest Ka/Ks ratio (0.44) in the 3-Ka/Ks ratio model is not significantly different from 1. This result was robust, as it was supported by all 12 jackknifed phylogenetic hypotheses (P ranging from 0.066 to 0.094). In other words, these results indicate relaxed selection leading to neutralization in ruvA in supergroup B Wolbachia strains from isopods. To test whether the neutralization signal was specific to the isopod Wolbachia group or also characterized the other Wolbachia groups, we tested whether there was a significant difference when assuming a Ka/Ks ratio of 1 for any of the other two groups (i.e., A supergroup strains and B supergroup strains from insects). In both cases, neutral evolution was rejected (supplementary table S6, Supplementary Material online), indicating that the signal of neutralization in ruvA specifically applies to supergroup B Wolbachia strains from isopods.

To substantiate these results, we further analyzed ruvA molecular evolution in Wolbachia strains of isopods. Average genetic distance between isopod Wolbachia strains for ruvA was 1.2% (range 0.2-2.0%) (supplementary fig. S1, Supplementary Material online). There was also no obvious sign of pseudogenization in ruvA, as it does not contain any inactivating mutation (i.e., frameshift or premature stop codon) or homopolymeric tract of poly(A) (>9 bp) which could induce slippage of RNA polymerase [START_REF] Tamas | Endosymbiont gene functions impaired and rescued by polymerase infidelity at poly(A) tracts[END_REF]. In addition, to test whether positive selection, rather than neutral evolution, may have inflated the Ka/Ks ratio, we used the branch-site model of PAML to search for positively selected codons in ruvA [START_REF] Yang | Bayes empirical Bayes inference of amino acid sites under positive selection[END_REF][START_REF] Zhang | Evaluation of an improved branch-site likelihood method for detecting positive selection at the molecular level[END_REF]. No codon was found to be under positive selection (P =0.71). Therefore, there is no evidence to support an effect of positive selection in our results.

To further investigate the evolutionary history of ruvA in supergroup B Wolbachia strains from isopods, we searched for potential ancestral substitutions specific to isopod Wolbachia strains that might have contributed to impair RuvA functional efficiency and, possibly, triggered gene neutralization. Inspection of the ruvA sequence alignment revealed 14 nucleotide substitutions exclusively shared by isopod Wolbachia strains, all located in functional domains, eight of which being nonsynonymous substitutions (table 3). Interestingly, five of these amino acid changes modify the physicochemical properties of the RuvA protein, in terms of charge, hydrophobicity or aliphatic property. Unfortunately, Wolbachia endosymbionts are unculturable bacteria. Therefore, the actual consequences of these five amino acid changes on RuvA functionality cannot be directly tested. Nevertheless, to hint at the potential functional consequences of these amino acid changes, we reviewed the literature and collated a list of 51 amino acid sites in the approximately 200 amino acid-long RuvA protein that are considered important for proper folding, multimerization or DNA binding, based on crystallography [START_REF] Rafferty | Crystal structure of DNA recombination protein RuvA and a model for its binding to the Holliday junction[END_REF][START_REF] Nishino | Functional analyses of the domain structure in the Holliday junction binding protein RuvA[END_REF][START_REF] Nishino | Modulation of RuvB function by the mobile domain III of the Holliday junction recognition protein RuvA[END_REF][START_REF] Roe | Crystal structure of an octameric RuvA-Holliday junction complex[END_REF][START_REF] Ariyoshi | Crystal structure of the Holliday junction DNA in complex with a single RuvA tetramer[END_REF][START_REF] Yamada | Crystal structure of the RuvA-RuvB complex: a structural basis for the Holliday junction migrating motor machinery[END_REF][START_REF] Prabu | Structure of Mycobacterium tuberculosis RuvA, a protein involved in recombination[END_REF][START_REF] Prabu | Crystallographic and modelling studies on Mycobacterium tuberculosis RuvA additional role of RuvB-binding domain and inter species variability[END_REF] or mutagenesis studies [START_REF] Nishino | Functional analyses of the domain structure in the Holliday junction binding protein RuvA[END_REF][START_REF] Privezentzev | The role of RuvA octamerization for RuvAB function in vitro and in vivo[END_REF][START_REF] Baharoglu | ruvA mutants that resolve Holliday junctions but do not reverse replication forks[END_REF][START_REF] Fujiwara | Functional significance of octameric RuvA for a branch migration complex from Thermus thermophilus[END_REF][START_REF] Masson | ruvA and ruvB mutants specifically impaired for replication fork reversal[END_REF][START_REF] Mayanagi | Electron microscopic single particle analysis of a tetrameric RuvA/RuvB/Holliday junction DNA complex[END_REF][START_REF] Bradley | Formation of a stable RuvA protein double tetramer is required for efficient branch migration in vitro and for replication fork reversal in vivo[END_REF]. We found that one amino acid change inducing a physicochemical modification in isopod Wolbachia RuvA falls in this list of 51 important amino acids (Lys-118). In Escherichia coli, Lys-118 plays an important role in DNA binding through nonpolar interaction with its aliphatic chain [START_REF] Ariyoshi | Crystal structure of the Holliday junction DNA in complex with a single RuvA tetramer[END_REF]. In all supergroup A and supergroup B Wolbachia strains from insects, Lys is replaced by Leu, but this change is not expected to impair function as Leu is also an aliphatic amino acid. In contrast, in the ancestor of all supergroup B Wolbachia strains from isopods, the aliphatic Leu was replaced by the nonlinear aliphatic Pro, which may have altered RuvA DNA-binding activity. Strikingly, in the wAse isopod Wolbachia strain, an additional nonsynonymous substitution resulted in the replacement of Pro by Ser (which is a nonaliphatic amino acid). We speculate that this substitution was not eliminated by purifying selection because the ancestral Pro had already contributed to impair RuvA function in isopod Wolbachia strains. If so, Leu-118-Pro might have played a key role in ruvA neutralization in these Wolbachia strains.

Although we cannot formally ascertain which (if any) the five amino acid changes may have been primordial in the initiation of the ruvA neutralization process in isopod Wolbachia strains, a plausible evolutionary scenario is that a nonsynonymous substitution occurred in the ancestral ruvA gene of isopod Wolbachia that significantly affected RuvA functionality (possibly the one leading to Leu-118-Pro). RuvA is part of the RuvAB complex, which performs branch migration during the HR process. Interestingly, RuvAB and RecG functions overlap [START_REF] Meddows | RecG helicase promotes DNA double-strand break repair[END_REF]) and our results indicate that RecG has been consistently evolving under strong purifying selection throughout supergroups A and B Wolbachia evolution (Ka/Ks =0 . 1 3 ;P < 0.001). Therefore, the impaired RuvA function may have resulted in a decreased efficiency of the RuvAB complex, which may have been compensated by RecG in the isopod Wolbachia a n c e s t o r ,a sp a r to fap r o c e s so fn o northologous gene displacement [START_REF] Koonin | Non-orthologous gene displacement[END_REF]. As soon as RuvA function was impaired, gene sequence could start undergoing independent neutral evolution in each lineage derived from this ancestor (table 3), thereby reinforcing functional impairment and gene neutralization. As a result, a pair of genes with redundant functions is now experiencing contrasting selective pressures in Wolbachia strains from isopods, with recG experiencing strong purifying selection, whereas ruvA has been neutralized. In support to our inferences, it is noteworthy that nonorthologous gene displacement has already been documented for recombination functions, as exemplified by the substitution of ruvC by recU or recBCD by addAB [START_REF] Ayora | Bacillus subtilis RecU protein cleaves Holliday junctions and anneals singlestranded DNA[END_REF][START_REF] Rocha | Comparative and evolutionary analysis of the bacterial homologous recombination systems[END_REF][START_REF] Cromie | Phylogenetic ubiquity and shuffling of the bacterial RecBCD and AddAB recombination complexes[END_REF]).

Conclusion

In the context of genomic reduction undergone by Wolbachia genomes, redundancy is expected to be lost through the process of pseudogenization [START_REF] Ogata | Mechanisms of evolution in Rickettsia conorii and R. prowazekii[END_REF][START_REF] Silva | Genome size reduction through multiple events of gene disintegration in Buchnera APS[END_REF][START_REF] Moya | Learning how to live together: genomic insights into prokaryote-animal symbioses[END_REF]. Numerous reports have focused on global pseudogenization events affecting the overall repertoire of genes of a genome due to enhanced genetic drift and less effective purifying selection [START_REF] Moran | Accelerated evolution and Muller's ratchet in endosymbiotic bacteria[END_REF][START_REF] Itoh | Acceleration of genomic evolution caused by enhanced mutation rate in endocellular symbionts[END_REF][START_REF] Woolfit | Increased rates of sequence evolution in endosymbiotic bacteria and fungi with small effective population sizes[END_REF][START_REF] Fuxelius | Visualization of pseudogenes in intracellular bacteria reveals the different tracks to gene destruction[END_REF][START_REF] Mccutcheon | Extreme genome reduction in symbiotic bacteria[END_REF]. In contrast, studies reporting relaxation of selection targeting redundant genes are scarce. This has been reported in the case of the functional replacement of B. aphidicola BCc by S. symbiotica in the host C. cedri (Pe ´rez- [START_REF] Pe ´rez-Brocal | A small microbial genome: the end of a long symbiotic relationship?[END_REF]. However, in this example, redundancy occurs between two different but closely interacting genomes, whereas we report a case of probable gene neutralization in the context of functional redundancy within a single genome.

Our results provide empirical evidence to support that relaxation of selection on specific genes and genetic drift act in synergy with the process of Muller's ratchet [START_REF] Moran | Accelerated evolution and Muller's ratchet in endosymbiotic bacteria[END_REF][START_REF] Mccutcheon | Extreme genome reduction in symbiotic bacteria[END_REF]. It is even plausible that genetic drift triggers specific relaxation of selection while slightly and mildly deleterious mutations are accumulating. In the case of redundant genes, these mutations would render the gene less "efficient" in its function in comparison with the analogous gene. As a result, the analogous gene would be favored to fulfill the function relative to the gene affected by slightly deleterious mutations and/or some compensatory measures would be set up. On the long-term, this would render the gene nonessential and thus initiate the process of specific neutralization, ultimately leading to pseudogenization and complete loss. In any event, targeted neutralization of RuvA indicates that genomic reduction is an ongoing process in Wolbachia endosymbionts.

FIG. 1

 1 FIG.1 . -Gene loss through pseudogenization. Starting from a functional gene under selection (a) relaxation of selective pressures leads to accumulation of slightly deleterious mutations and neutralization of the gene (b) until the gene is effectively inactivated and pseudogenized (c). A bias in favor of deletions (yellow bars) relative to insertions (blue bars) leads to gradual erosion of the pseudogene (d) until its complete loss (e).

FIG. 2

 2 FIG.2.-Schematic representation of the HR pathway. Repair of DNA single-and double-strand breaks is initiated by RecJ/RecFOR and AddAB, respectively. The initiation step promotes the recruitment of RecA filament that catalyzes strand exchange. Then, branch migration and resolution of Holliday junction is completed by the RuvABC complex or RecG helicase. Repair of DNA double-strand breaks is finally completed with PriA which mediates primosome assembly for replication.

Table 1

 1 Distribution of 12 HR Genes in 20 Wolbachia Genomes

	Super	Strain	Host	Accession	addA	addB	priA	recA	recF	recG	recJ	recO	recR	ruvA	ruvB	ruvC	Reference
	group			Number
	A	wMel*	Drosophila	AE017196	WD_0359	WD_0912	WD_1200	WD1050	WD_1286	WD_0824	WD_0312	WD_0219	WD1180	WD_1113	WD_1112	WD_0142	Wu et al. 2004
			melanogaster
		wRi*	Drosophila	CP001391	WRi_004270	WRi_008710	WRi_011780	WRi_010830	WRi_013130	WRi_007900	WRi_004620	WRi_002090	WRi_011550	WRi_012870	WRi_012860	WRi_001110	Klasson et al. 2009
			simulans
		wHa*	Drosophila	CP003884	wHa_04850	wHa_07710	wHa_10020	wHa_08760	wHa_10710	wHa_06960	wHa_05160	wHa_01890	wHa_09860	wHa_09320	wHa_09310	wHa_00600	Ellegaard et al.
			simulans														2013
		wUni	Mudiscidifurax
			uniraptor

Table 2

 2 Summary of Selection Analysis for 12 HR Genes in 18 Wolbachia Strains

	Gene	Best-Fit Model P Value (Range)	Ka/Ks Values (Range)
	addA_1 3 Ka/Ks	<0.02	A: 0.214-0.221;
				B insects: 0.277-0.291;
				B isopods: 0.175-0.193
	addA_1 1 Ka/Ks	<0.001	0.187-0.199
	addB	3K a / K s	<0.001	A: 0.324-0.343;
				B insects: 0.431-0.447;
				B isopods: 0.382-0.395
	priA	1K a / K s	<0.001	0.143-0.147
	recA	1K a / K s	<0.001	0.049-0.050
	recF	1K a / K s	<0.001	0.225-0.239
	recG	1K a / K s	<0.001	0.128-0.136
	recJ	1K a / K s	<0.001	0.112-0.113
	recO	3K a / K s	<0.02	A: 0.294-0.307;
				B insects: 0.158-0.182;
				B isopods: 0.283-0.289
	recR	1K a / K s	<0.001	0.075-0.081
	ruvA	Neutral	0.066-0.094	A: 0.299-0.316;
		foreground		B insects: 0.211-0.216;
				B isopods: 1
	ruvB	1K a / K s	<0.001	0.072-0.074
	ruvC	1K a / K s	<0.001	0.218-0.221
	NOTE.-Detailed results are provided in supplementary tables S4-S6,
	Supplementary Material online.

Table 3

 3 Nucleotide Substitutions of ruvA Specific to B Supergroup Wolbachia Strains from Isopods II are implicated in tetramerization of the protein and junction-DNA binding; domain III is implicated in branch migration through heteroduplex contact with RuvB.

	Substitution	Nucleotide	Functional	Amino Acid	Amino Acid
	Type	Substitution	Domain a	Substitution	Property Change
	NS	G70A	I	V24I
		T76C	I	Y26H	Neutral > positive
		G125A	I	S42N
		T353C	II	L118P b	Aliphatic > nonaliphatic
		G493A c	III	D165N	Negative > neutral
		T497C c	III	T166M	Nonhydrophobic > hydrophobic
		C524A c	III	P175Q	Hydrophobic > nonhydrophobic
		A539G	III	K180R
	S	T87C	I
		T280C	II
		A357G	II
		T457C	III
		A498G	III
		A513G c	III

a Domains I and b Si nwAse due to an additional mutation at np 352. c Except for wCon.

Genome Biol. Evol. 6(10):2654-2664. doi:10.1093/gbe/evu207 Advance Access publication September 17, 2014

Acknowledgments

This research was funded by a European Research Council Starting Grant (FP7/2007-2013, grant 260729 EndoSexDet) to R.C. and intramural funds from the Centre National de la Recherche Scientifique (CNRS) and the French Ministe `re de l'Education Nationale, de l'Enseignement Supe ´r i e u re td el a Recherche. The authors thank Cle ´ment Gilbert for comments on an earlier version of the manuscript.

Supplementary Material

Supplementary figure S1 and tables S1-S6 a r ea v a i l a b l ea t Genome Biology and Evolution online (http://www.gbe. oxfordjournals.org/).


Carst Tankink
email: carst.tankink@inria.fr

PIDE for Asynchronous Interaction with Coq

. The architecture is aimed at asynchronous, parallel interaction with proof assistants, and is tied in heavily with a plugin that allows the jEdit editor to work with Isabelle.

We have made some generalizations to the PIDE architecture to accommodate for more provers than just Isabelle, and adapted Coq to understand the core protocol: this delivered a working system in about two man-months.

Introduction

Since 2007, the Isabelle proof assistant has an architecture aimed at asynchronous proof processing. To support this architecture, the tool also gained a significant update to its user interface, in the form of Isabelle/jEdit: a plugin for jEdit that supports interaction with Isabelle. jEdit is a generic editor aimed at programmers in any language: the editor's main components are a group of text windows with syntax highlighting, and any other functionality (compilation, version control, project management, . . . ) can be added through the use of plugins. Isabelle's support for jEdit was added through this plugin system, by adding a 'generic' prover plugin that exchanges messages with the proof assistant in order to provide a number of functions for authoring proofs, such as: 1. prover output; 2. syntax highlighting; 3. 'semantic' highlighting, provided by the prover as it processes the text. A prominent example is the addition of links, which point to the location where an entity (such as a lemma) is defined. These links are attached to the locations where this definition is used.

While the plugin aims at being generic, this claim has never been validated in anger: the main development has centered on Isabelle, and while there have been experiments with Coq [START_REF] Wenzel | PIDE as front-end technology for Coq[END_REF] and Why3, these did not invoke actual prover processes, but only provided a shallow interface to (stateless) syntax highlighting. This paper describes the effort, started in February 2014, to integrate Coq with this plugin, by adapting to the generic PIDE architecture as much as possible, and driving further generalizations in that architecture where necessary. The resulting interface is shown in Figure 1. This paper also shows a relatively outsider view of the PIDE architecture, and might therefore be useful to others interested in integrating their formal tools with the jEdit prover plugin. PIDE can been used to build any (JVM-based) tool that uses the proof assistant as some black box, but the flagship application is the Isabelle plugin for jEdit. Building on top of this library, this plugin provides functionality for interacting with the prover from jEdit: it listens to changes in the text areas of the editor, parses these changes into 'command spans', and uses the PIDE functions to send the spans onwards. It uses the prover hooks to react to the proof being processed, storing prover states to be rendered when the user focuses on the corresponding command span, and using 'semantical' information to add highlighting and hyperlinks to the text. The functionality of the plugin goes beyond this, but this is the core functionality we are interested in bringing to Coq.

Generalizing PIDE

We want to use Coq with the architecture, obtaining the interaction model with as little adaption as possible: we want to reuse as much as possible from the existing PIDE and plugin implementations, by generalizing code where possible and writing Coq-specific code where necessary. With that in mind, we have a choice of where exactly to insert the desired functionality. In theory, it is enough to just implement the high-level interface with Coq-specific protocols. Such an interface is required to send textual changes to the prover. It is also required to provide an accumulation function (in a 'snapshot'): this function is called by the editor side of the plugin, and is used to determine what information the prover has on certain spans. This information is then used to provide the various displays of the proof document.

Implementing these functions from scratch is certainly possible, but is a large effort, to obtain code that is partially duplicated by the PIDE implementation for Isabelle. Instead, we take a better look at the elements of the PIDE architecture, focussing on how individual parts can be reused.

Change parsing

The change parsing 'algorithm' takes a sequence of text edits (insertions and deletions) and uses these to determine what the new command spans for the prover are. To do so, the algorithm takes several steps, when a non-empty list of edits is provided. The following description is based on an analysis of the file src/Pure/Thy/thy syntax.scala of the Isabelle source code, changeset bbf4d51. This source file is available through https://bitbucket.org/Carst/pide_notes/src/bbf4d51/src/Pure/Thy/ thy_syntax.scala.

The algorithm works on a previous version of the document, and creates a new version by applying the edits in a specific manner. The steps taken on a specific document are described below.

1. Determine any changes to the header of the proof document. This header is an Isabelle-specific syntax element, that declares the name of the proof document and the other documents it imports.

Determining the changes here is important there, because a dependency can define new commands, that direct the parsing in the next step.

2. The second step 'applies' the edits to the document, as well as reparsing any text that might have been affected by the header changes. We only focus on the first part here. In this procedure, the command spans that are directly affected by an edit are manipulated to reflect the new text, and following this, reparses the resulting text in order to obtain the new command spans.

The first step is specific to Isabelle, but a large part of the second step is generic: it creates a new document version, and runs a language-specific parser in order to obtain the command spans. This parser is a part of the Scala side of PIDE and is used to make certain computations quicker, for example syntax highlighting. It also reduces the communication overhead between the Java-based processes and the prover-specific ones: all communication can be done in terms of pre-defined command spans. This means that we can run this algorithm from our Coq implementation of PIDE, but provide a Coq-specific parser that translates text into command spans. The resulting parser is straightforward: it tokenizes the input, looking for the Coq-specific terminator symbol, the period ('.'). Its implementation can be found at http://tinyurl.com/coq-loader1 (the high-level parser interface) and at http://tinyurl.com/ coq-parser (the actual tokenizer). To allow using this tokenizer with the original change parser, the algorithm had to be changed, to better display this structure: the change parsing step would call the Isabelle parser directly, but after a change, made in collaboration with Wenzel, the algorithm can call any prover-specific parser that implements a generic interface.

The benefit of using this algorithm, is that the data structure that is used to store the results is directly usable by the standard protocol of the PIDE implementation: the resulting changes on the prover level are transformed all the way down to the YXML syntax, and sent to the prover. We did need to implement the protocol stack on the Coq side, which is described in Section 4.

Markup accumulation

The accumulation of prover feedback is done by a generic function that collects all information in the document in an data structure. This data structure is then queried by the plugin to generate markup. The accumulated feedback is expected in a format that was designed for the Isabelle implementation, but can still be mimicked by Coq because most of the specifics are in naming conventions within the messages: these names are, for example, tags that provide markup to a certain region of text, using nomenclature that is standard in the Isabelle ecosystem, but not that of Coq.

Adapting Coq

To make Coq compatible with the PIDE design, we need to add a number of features to the 'top level' of the prover. Until now, all interaction with Coq has been in a procedural 'Read-Eval-Print-Loop': any interface to the system was required to provide both the content of the proof as well as the commands that instruct the prover to process this content. These two types of commands have always been unified in a single transaction: the interface would send a single command span to the prover, the system would process the span, and after that return control to the interface, which could then send a new span.

From an interaction perspective, this is far from ideal, since the user will have to undo steps in order to add information to a proof, and this information might not impact the rest of the proof directly. From a prover perspective, this state of affairs is also not ideal: when the system 'discovers' a proof line by line, it cannot schedule the processing of the lines in any meaningful way. In particular, in the face of parallel computation, it is impossible for the system to pass off computation of an expensive line in order to start working on a next, unrelated line of the proof.

State Transaction Machine

In order to make the system more suitable for PIDE, Enrico Tassi previously [START_REF] Barras | Designing a State Transaction Machine for Coq[END_REF] developed a "State Transaction Machine" (STM) for Coq. This machine no longer depends on a linear, line-by-line model of a proof, but rather provides a computation model based on a DAG: the interface still adds commands to this DAG, but these commands are parsed into a graph that separates commands that can be executed out of order. The commands do not automatically trigger a computation, but the interface can request to start the computation by "observing" any node in the graph. The system will then compute all dependencies of this node, as well as the node itself. The computation itself can now be scheduled by the STM based on this graph, and the computation is scheduled to be executed by slave processes running in parallel. As a result, the computed proof states are also reported asynchronously.

PIDE for Coq

While the PIDE protocol for Isabelle, which we use here, sends out several different types of messages, it is only necessary to implement a reaction to two messages in order to obtain a working integration with the jEdit interface. Symmetrically, the prover needs to send two messages in order to obtain any interaction with the user.

The protocol stack is modelled similarly to the implementation in Isabelle: its lowest layer is a raw FIFO-channel, the messages are parsed into YXML, which is translated to XML. Finally, XML messages are interpreted and mapped to function calls intended for Coq. This architecture is based on the prototype implementation described before by Wenzel [START_REF] Wenzel | PIDE as front-end technology for Coq[END_REF], but is extended with hooks that trigger the prover's computation. Using this organization gave us a running start, as the parts that deal with maintaining an internal 'PIDE document' are already in place.

Currently, we do not mimic the syntax highlighting described in the original architecture. Its implementation was based on the ad-hoc syntax highlighter used for the CoqIDE interface for Coq, and introduced an unwanted dependency on the GTK graphical library. The library is unwanted because it is not used to provide any graphics, and is an optional component to the Coq installation. While it is possible to eliminate the dependency, the resulting highlighting would be rather limited. As a result, it seems better to reconsider the syntax highlighting completely, and integrate it more deeply in the implementation of Coq itself, which would have the added benefit of allowing other interfaces for Coq to use the information.

The adaptations made to Coq to accommodate this protocol can be found in the following branch of the Coq source tree: https://bitbucket.org/Carst/coq-pide/src/?at=PIDE. The files of interest are all contained in the "toplevel" directory. Of particular interest are the files pide protocol.ml and pide document.ml, which implement the high-level protocol.

The Coq implementation follows the Isabelle version of PIDE loosely: it maintains a version history of Documents. Each document version represents the state of the proof at a particular moment in time, both its content and the computations executed on them. For a more complete description of this architecture, we refer to Makarius Wenzel's paper on PIDE [START_REF] Wenzel | Asynchronous User Interaction and Tool Integration in Isabelle/PIDE[END_REF].

Define commands

The first type of message coming from the interface maps identifiers to the contents of command spans. All future messages from the interface do not refer to the text, but instead refer to the command identifiers.

To handle this situation, Coq maintains a lookup table for the defined commands in the document module, that allows it to search for command spans whenever an identifier is given.

Update The update message is the center of the protocol: it notifies the prover of the changes by giving the insertions and deletions as command identifiers. In Coq, we use this message to update an internal representation of the proof document, by executing the insertions and deletions of the edit. Afterwards, we map each command in the new document to a future computation of a proof state, retaining the computations that have been executed on the prefix of commands that are unchanged between the two versions: currently, we do not attempt to keep computations on shared commands after the first difference, because the state of these computations can be changed by the differences. At this stage, we only prepare the identifier for that computation, and return this in an 'assign update' message: this is the only message expected by the interface: it confirms that the prover received the update, and notifies the interface of which computations will take place: future messages from the computation will be tagged with this execution identifier.

After the assignment is reported to the interface, Coq continues by adding the new commands to the STM. Once all commands have been executed, it 'observes' the final command of the proof. This triggers the computation of the proof states.

Reporting States When Coq is computing, the states are reported asynchronously, together with the execution identifier and the offset of the part of the command that was computed to obtain this state. The system then wraps this information in a 'writeln' message, and sends it on to jEdit. The PIDE plugin on the jEdit side is equipped to handle these messages, and attach them to the correct piece of text in the editor: when the user places the text cursor on a span, the corresponding state is shown.

Should an error occur while processing the command, this is reported asynchronously, but now wrapped in an 'error' message. These are reported differently in the jEdit interface, by placing a 'squiggly underline' (similar to a spell-checker's in a text editing program) on the offending region: this is shown in Figure 1. Also note that this truly is an asynchronous report: despite an error occurring on the 'Qed' line of the lemma "app assoc", the user is still able to inspect the state after the highlighted line, which uses the 'broken' lemma: its statement is still available at a later point in the proof.

Markup Finally, the PIDE protocol allows for, but does not require, reporting markup. The details of the implementation are very prover specific, and we will not go too deeply into it here. What is worth mentioning, is that we could use the messaging system to obtain hyperlinks for the Coq sources: in the jEdit interface, it is possible to click on a name of a lemma (or theorem, or definition, or . . . ), and be taken to the position where this entity is defined. This was achieved by exporting information in Coq, using the 'report' messages that are part of the PIDE protocol for Isabelle: the plugin is equipped to handle these messages, and transform them into source code hyperlinks.

PIDE in action

To give a better account of the PIDE and STM architecture, we give an overview of the messages and function invocations used to obtain Figure 1. We do truncate messages occasionally, and do not use the actual identifiers, as they change per session. The courageous reader can see all the protocol messages in action by installing and running the jEdit plugin with Coq, while having the 'Protocol' window open.

Defining commands Inserting text (for example, by keyboard entry, copy-paste or by loading a file) triggers an update event from the buffer to the PIDE plugin. This event specifies what region has changed. PIDE then transforms its internal representation based on this event, by removing and inserting text where necessary and then (re)parsing the text where necessary: at least inserted text needs to be parsed, but a larger region might need to be modified, for example when inserting or removing an 'open comment' mark. The language-specific parser returns command spans: for Coq these are all phrases ending with a single period, including the following whitespace2 and preceding comments: "Proof.", "intros l.", . . . . The interface then sends the commands to the prover, each in a separate XML message (the empty arguments are used by Isabelle):

< prover_command name = " Document . define_command " > < prover_arg > -1 </ prover_arg > < prover_arg / > < prover_arg / > < prover_arg > Proof .
</ prover_arg > </ prover_command > This message triggers a function in the prover that stores the key-value pair ("-1", "Proof.") into the lookup table for commands. The key, like any identifier coming from the prover, is a negative number: the prover uses positive numbers to report its identifiers.

Updating document state After all define command messages have been sent out, the prover sends a "Document.update" message (heavily truncated):

< prover_command name = " Document . update " > < prover_arg >0 </ prover_arg > < prover_arg > -1492 </ prover_arg > < prover_arg > <: > . . . <: >/ home / carst / projects / pide / tests / foo . v </ : > <: > <0 > <: > <: / > <: > <: > -1 </ : > </ : > </ : > <: > <: > <: > -1 </ : > </ : > <: > <: > -2 </ : > </ : > </ : > . . .

< /0 > </ : > . . . </ : > </ prover_arg > </ prover_command >
This message triggers a function with three arguments. The first is the version of the document to update from, the second is the version to upgrade to. The third argument is a list of update operations (the '<:>' tags are used as transfer separators for list elements and pairs), consisting of a file name to apply the operation on, and the operation itself: there are several types of operations in PIDE, but the only one implemented for Coq (and the only one necessary for a functioning PIDE-compatible prover) is operation type '0': the Edit operation. This edit operation consists of a list of pairs of optional command identifiers: the first operation encodes the pair (None, -1), which means inserting the command with identifier '-1' at the beginning of the document. The second pair is (-1, -2), which encodes an insertion of the command identified by -2 after the command with identifier -1. The third type of pair, not displayed in this message, would have an identifier as its first element, and 'None' as its second: this encodes the deletion of the command directly after the command identified by the first element.

The triggered update function looks up the old version of the proof 'document' (a list of pairs of command identifiers and execution identifiers) and inserts the new version of the document: it progressively applies the insertions and deletions encoded in the message on the old version. In this case, the old version is empty, and the function starts with the insertion of command '-1'. It then continues on the resulting document, inserting the command '-2' after the '-1' just insert, obtaining the sequence '-1; -2'3 . After obtaining the new document version, the function assigns an execution identifier to each command: the common prefix contains the execution identifiers in the old document, any commands that are new, or succeeding a new command are assigned a freshly generated identifier.

These pairs are then reported back to the prover, using a similar message syntax as used for the update message, the message formatting is slightly different: instead of sending function and argument as a single XML message, the header and body are separated in two messages.

< protocol function = " assign_update " / > <: > <: > <: > -1 </ : > <: > <: > 49 </ : > </ : > </ : > . . .

</ : >

This assigns the execution identifier 49 to the command identifier -1. For Isabelle, it is possible to have multiple execution identifiers, so the second element of the pair is actually a list.

The PIDE plugin does nothing with this message, except storing the assignments in a lookup table. This is message is also used as a confirmation that the update was received.

Computation After the update assignment, the prover adds the commands to the STM where necessary: it finds the last common command between old and new, and instructs STM to insert new commands after this command. The insertion could not be done before sending out the assignment, because the STM parses the commands (for scheduling) and would report syntax errors before an assignment is reported: these messages would never be caught by PIDE, and not reported to the user. Any command added to the STM is accompanied by the execution identifier, that will be used by Coq to report information on that specific command. After adding the commands, the STM is started by asking it to compute the final command in the document: this triggers the computation of all preceding commands.

During the computation, information gets reported asynchronously, including the execution identifier. This information is packed in messages and sent back to jEdit.

The first is the error message:

< error serial = " 7 " id = " 6 " > Error: Attempt to save an incomplete proof </ error > The message has a serial number that is used internally in PIDE, and the execution identifier attached to the "Qed." command. In this particular case, Coq could not recover the offending part of the command, so the message contains only the identifier. As a result, jEdit underlines the entire command. If an offset was reported, it would cause only the problematic command to be underlined. The second is an example of hyperlinks:

< report offset = " 9 " end_offset = " 18 " id = " 16 " > < entity def_id = " 13 " id = " 16 " offset = " 9 " end_offset = " 18 " def_offset = " 7 " def_end_offset = " 16 " name = " app_assoc " kind = " thm " / > </ report > This message can contain multiple reports for a single execution identifier, but in this case it just describes the "app assoc" entity of type "thm", Coq's internal identifier for theorems and lemmas. It includes the location information of the lemma, which in this case is within a command of the same document (it has an assigned "def id") and a certain offset within that command. The message also allows for defining the location in other files, by specifying the "def file" attribute with a line and character offset.

The final message reports goal states. The message for the displayed goal state is: When receiving this message, PIDE stores the data, and retrieves it when the cursor is on the specified line.

There are other messages in the protocol, for example to report prover progress, but these three types are the ones currently implemented for Coq.

Conclusions

Based on the original PIDE implementation for Isabelle with some minor generalizations, and by adding the protocol functions to Coq (at the time of writing, all PIDE functionality is contained in approximately 750 lines of fairly verbose OCaml code), we have obtained a functional, asynchronous editing environment for Coq. The integration was developed in a very short period: going from the STM interface in Coq, and the existing Isabelle code base, jEdit could work with Coq in two man-months of work. This time included reading the PIDE code base in order to understand how the protocol works, and what parts are essential.

Going forwards, there still is more work to be done in making the PIDE architecture more accessible to other provers, but adding Coq is a first step in identifying what elements of the architecture are specific to a particular prover and what parts can be reused regardless of the proof assistant in use. For now, a prover that wants to benefit from the PIDE architecture, needs to supply:

• a parser that can recognize command spans. This parser needs to be added to the Scala code of the PIDE architecture;

• a protocol implementation that can unpack the PIDE messages and provide them to the prover. This implementation is also responsible for supplying feedback and output to the interface.

These recommendations are not fixed edicts, but will provide a running system with a minimum of effort, and are therefore a good starting point for adding specialized messages: this is where we started with Coq, and we are now looking forward to a more asynchronous, declarative future of interaction.

<

  writeln serial = " 144 " id = " 16 " >1 subgoal n : nat l1 : natlist . . . = = = = = = = = = = = = = = = = = = = = = = = = = = = = app (...</writeln>

These tinyurls point to specific source files in the bitbucket repository https://bitbucket.org/Carst/pide_notes/ src//src/Pure/Coq/.

For brevity's sake we do not include whitespace in the examples

In functional programming terms, update is a fold over the list of update operations, starting at the old version of the document

* Supported by the Paral-ITP project: ANR-11-INSE-001 http://paral-itp.lri.fr/ PIDE for Coq

Figure 1: The jEdit plugin working with Coq 2 PIDE and Isabelle/jEdit


Pascal Cuoq

Julien Signoles

Damien Doligez
email: damien.doligez@inria.fr

Lightweight Typed Customizable Unmarshaling

Abstract

The contribution of this work is threefold. First, we offer an OCaml unmarshaling algorithm that uses a lightweight type-directed description of the expected structure of data to make consistency checks. The second contribution is the opportunity to specify functions to be systematically applied on values as they are being unmarshaled. Our third contribution is a type-safe layer for these functions and for the unmarshaling algorithm itself.

Description

The standard OCaml unmarshaling function is input value: in channel → α. The aforementioned first contribution is a function descr input val with type in channel → descr → α. One value of type descr that can be passed as second argument is Abstract, and then the behavior is exactly identical to input value. The programmer can provide as much information as (s)he wants for the additional consistency checks. For instance, (s)he can pass the value (t array Abstract) to specify that the value being read is an array of undescribed values. Our unmarshaling algorithm maintains a cursor into the structure description, allowing it to know what the current loaded value should look like.

A value of type descr can include functions to be applied on the values as they are built. This is necessary for instance when unmarshaling values of hashconsed types: the maximal sharing invariant must be preserved [START_REF] Cuoq | Hashconsing in an incrementally garbage-collected system: a story of weak pointers and hashconsing in OCaml 3.10.2[END_REF]. In this case the programmer may use a description containing a function f of type τ → τ to rehash these values. In order to allow this, our unmarshaling function preserves OCaml's runtime invariants, including for the partially reconstructed values. The historical implementation of marshaling in Ocaml is written in C and does not have this property. The new unmarshal is written in low-level unsafe OCaml. It is compatible with the existing format, so that it can be used with the old marshal function.

Unfortunately, it is not possible to type the function f above in a safe way. The low-level API requires it to have type Obj.t → Obj.t. The programmer must use unsafe coercions to implement it. We lessen this drawback with a type-safe layer that relies on a dynamic representation of OCaml types [START_REF] Signoles | Une bibliothèque de typage dynamique en OCaml[END_REF][START_REF] Signoles | An OCaml Library for Dynamic Typing[END_REF]. The type descr of descriptors becomes a polymorphic phantom type in which the type variable encodes the static type being de-scribed. The type expected for function f above becomes α descr → α → α. Thus f can be written without unsafe operations, by providing an extra argument corresponding to the type of the unmarshaled value. Additionally, we also offer a typed unmarshaling function typed input val: in channel → α descr → α which constrains the unmarshaled value to be used in a context compatible with the type of the descriptor.

Assessment and Availability

The described work has been implemented and has been used for loading analysis projects [START_REF] Signoles | Foncteurs impératifs et composés: la notion de projets dans Frama-C[END_REF] inside Frama-C [START_REF] Cuoq | Experience Report: OCaml for an Industrial-Strength Static Analysis Framework[END_REF]. The lowlevel layer was provided in Frama-C version Boron, and the typesafe layer was made available with version Carbon.

A previous implementation used the standard OCaml unmarshaling function. Disadvantages were numerous: the re-hashing of hashconsed values had to be done in a second pass after unmarshaling. Just before this second pass was done, two versions of the loaded project would exist in memory, causing a peak in memory use. It was necessary to remember which subvalues had already been visited, and the corresponding re-hashed versions. Otherwise, rehashing would produce the expected results but would take a very long time to do so, visiting the highly shared DAG representing the analysis project as if it were a tree.

All these problems are solved by the new unmarshaling function. The re-hashing is done value per value as they are created, and the non-shared value that came from disk can be forgotten immediately, streamlining memory usage. A table mapping node ids to corresponding re-hashed values exists during unmarshaling with the new implementation. However, this table is maintained by the unmarshal function, and the programmer does not need to know about it. By contrast, with the previous implementation, the programmer had to maintain such a table for every type, whether unmarshaled or not. While it was possible to factor the implementation of this table a little, the fact that constructors are not first-class value prevented true genericity.

Related Work

Kennedy [START_REF] Kennedy | Pickler combinators[END_REF] describes a library of marshaling combinators for Haskell. These combinators work at the language level without any magic, but the programmer has to describe the data types in full detail by combining the combinators. The marshaling format is specific to this library. By contrast, our system uses OCaml's lowlevel marshaler and allows the programmer to give an incomplete description of the type being unmarshaled. Kennedy's work is extended and adapted to Standard ML by Elsman in [START_REF] Elsman | Type-specialized serialization with sharing[END_REF], which introduces difficulties due to references and cyclic data structures. In both cases, the programmer can use the wrap combinator to get the same effect as our function f . Combinators are a lot more verbose to use than our type descr.

Rossberg et al.

[RTK07] describe a much more ambitious system: higher-order typed pickles in Alice ML, where they are an important component of the system. Unlike OCaml's marshaled values, they carry type information. In this system, transform nodes can be used to get the effect of our f function.

The programming language Acute [SLW + 05] and its extension HashCaml [START_REF] Billings | Type-safe distributed programming for OCaml[END_REF] provide safe (un)marshaling by marshaling a type representation ty computed by the compiler for each written value v and by comparing ty to the expected type at the time v is unmarshaled. This approach is based on a dedicated language which provides type representations at runtime. It also requires the marshaling of some additional data. Neither is required in our approach.

Henry [START_REF] Henry | Typer la désérialisation sans sérialiser les types[END_REF][START_REF] Henry | Typer la désérialisation sans sérialiser les types[END_REF] provides type-safe unmarshaling for OCaml without marshaling types by verifying the compatibility of the value being unmarshaled with the expected type. Its approach nevertheless modifies the OCaml compiler, while our approach is fully compatible with the standard OCaml compiler.

Neither Acute nor Henry's proposal allow to apply custom functions at unmarshal time, which was our primary goal.

The ATerms library [START_REF] Van Den Brand | Efficient Annotated Terms[END_REF] (in C and Java) has both hashconsing and unmarshaling. Not having to be backwards compatible with an existing format, it marshals data bottom-up (the standard OCaml format, with which our function is compatible, is topdown). Bottom-up complicates marshaling a little, but simplifies unmarshaling a lot. Being untyped, in ATerms many types of data can be represented with a few, fixed kinds of nodes chosen in advance.

Conclusion

We have presented a solution to mix hashconsing and unmarshaling. This solution is implemented and, at the time of publishing, has been used for months inside the analysis framework Frama-C. We get the impression that the problems we had to solve have been discovered and solved many times over in different contexts, and we hope that, in the context of OCaml, the next person who needs something like this will find this implementation rather than going through the same issues again.

Acknowledgements

Norman Ramsey and Jurgen Vinju suggested many of the comparable, existing systems to look at. All core Frama-C developers had to suffer while unmarshaling and hashconsing issues were being understood and solved, but we would like to apologize in particular to Boris Yakobowski, who bore most of the brunt.