Claire Bertrand

Annabelle Thibessard

Claude Bruand

François Lecointe

Pierre Leblond

Bacterial NHEJ: A never ending story

Keywords: Homologous End Joining, Streptomyces, Sinorhizobium meliloti, Bacillus subtilis, Mycobacterium

Double-strand breaks (DSBs) are the most detrimental DNA damage encountered by bacterial cells. DBSs can be repaired by homologous recombination thanks to the availability of an intact DNA template or by Non-Homologous End Joining (NHEJ) when no intact template is available.

Bacterial NHEJ is performed by sets of proteins of growing complexity from Bacillus subtilis and Mycobacterium tuberculosis to Streptomyces and Sinorhizobium meliloti. Here we discuss the contribution of these models to the understanding of the bacterial NHEJ repair mechanism as well as the involvement of NHEJ partners in other DNA repair pathways. The importance of NHEJ and of its complexity is discussed in the perspective of regulation through the biological cycle of the bacteria and in response to environmental stimuli. Finally, we consider the role of NHEJ in genome evolution, notably in horizontal gene transfer.

I-Bacterial NHEJ: A two-component DNA repair mechanism?

Until in silico identification of putative NHEJ actors in bacterial genomes, it was thought that Homologous Recombination (HR) was the major double-strand break (DSB) repair mechanism in prokaryotes. However, HR needs an intact template to ensure repair of the break, a condition encountered by bacteria only during their dividing state and raising the question of the repair of DSB in other phases of their life cycle. The identification of a bacterial NHEJ answered, at least in part, this question since, in eukaryotes, NHEJ was known to ligate DNA ends together without any homologous template. This mechanism has been well documented in eukaryotes and involves a dozen of actors in human, including the Ku70/Ku80 heterodimer, and the ligase IV [START_REF] Chang | Non-homologous DNA end joining and alternative pathways to double-strand break repair[END_REF].

The first hint for the existence of a bacterial NHEJ was provided by in silico approaches leading to the identification of Ku70/80 homologs and ATP-dependent DNA-ligase homologs [START_REF] Doherty | Identification of bacterial homologues of the Ku DNA repair proteins[END_REF][START_REF] Aravind | Prokaryotic homologs of the eukaryotic DNA-end-binding protein Ku, novel domains in the Ku protein and prediction of a prokaryotic double-strand break repair system[END_REF]. These Ku and DNA-ligase encoding genes are often colocalized, or in an operonic structure. The DNA-ligase genes encode a putative ligase domain (LigDom or LIG), fused or not with a polymerase domain (PolDom, POL or Prim-Pol) and/or a nuclease domain (NucDom or PE for Phosphoesterase). Whatever the domain combination, these multifunctional ligases were collectively named LigD, in reference to the main NHEJ ligase in Mycobacteria [START_REF] Gong | Mechanism of nonhomologous end-joining in mycobacteria: a low-fidelity repair system driven by Ku, ligase D and ligase C[END_REF].

The first experimental validation of a bacterial NHEJ came from the study of Weller et al. showing that in vitro the Mycobacterium tuberculosis LigD protein (LigDMtub) is indeed an ATP-dependent DNA ligase that is stimulated by its cognate KuMtub partner, possibly via an interaction between KuMtub bound to DNA and LigDMtub [START_REF] Weller | Identification of a DNA nonhomologous end-joining complex in bacteria[END_REF]. In parallel, authors described the deleterious effect of the deletion of the Bacillus subtilis genes coding for LigDBsub and KuBsub (ykoU-ykoV operon) on the survival of cells in stationary phase after ionizing radiation (IR). IR is a cause of multiple DNA lesions, including DSBs that are particularly hazardous. These two proteins from B. subtilis have been later shown to also perform NHEJ repair in vitro (de [START_REF] Vega | The minimal Bacillus subtilis nonhomologous end joining repair machinery[END_REF]. The Ku and/or LigD-dependent ability of M. tuberculosis and Mycobacterium smegmatis to recircularize linear plasmid DNA after transformation, and the IR sensitivity of M. smegmatis ku and ligD mutants in stationary phase, have given further evidence in vivo that several bacterial species are NHEJ proficient [START_REF] Stephanou | Mycobacterial Nonhomologous End Joining Mediates Mutagenic Repair of Chromosomal Double-Strand DNA Breaks[END_REF].

LigDMtub is not a common ligase. Its PolDom provides LigDMtub with DNA-dependent DNA polymerase, DNA-dependent RNA polymerase and primase and non-templated nucleotide addition activities [START_REF] Della | Mycobacterial Ku and ligase proteins constitute a two-component NHEJ repair machine[END_REF]. Moreover, the Poldom interacts in vitro with KuMtub-DNA complex suggesting that it could be responsible for the recruitment of LigDMtub on Ku-bound DSB in vivo [START_REF] Pitcher | Domain structure of a NHEJ DNA repair ligase from Mycobacterium tuberculosis[END_REF]. LigDMtub also shows a 3'-5' exonuclease activity most probably carried by its NucDom [START_REF] Della | Mycobacterial Ku and ligase proteins constitute a two-component NHEJ repair machine[END_REF]. LigD from Pseudomonas aeruginosa (LigDPaer) and Agrobacterium tumefaciens (LigD2) display similar activities accordingly to their identical domain composition, though different domain organization, compared to LigDMtub (Zhu and Shuman, 2005a;Zhu and Shuman, 2005b;Zhu et al., 2005;[START_REF] Zhu | Characterization of Agrobacterium tumefaciens DNA ligases C and D[END_REF]. Thus, LigD displays all activities allowing to process DNA ends, if necessary, and ligate them without the need for other proteins, except Ku. Accordingly, expression of Ku and LigD from M. tuberculosis i) partially restores NHEJ in yeast ku70 or dnl4 mutant strains [START_REF] Della | Mycobacterial Ku and ligase proteins constitute a two-component NHEJ repair machine[END_REF] and ii) renders Escherichia coli NHEJ-proficient [START_REF] Malyarchuk | Expression of Mycobacterium tuberculosis Ku and Ligase D in Escherichia coli results in RecA and RecB-independent DNA end-joining at regions of microhomology[END_REF].

Altogether, these studies have led to the following model for the bacterial NHEJ: Ku homodimer binds to DNA ends generated by a break and recruits LigD (one multidomain polypeptide, such as LigDMtub, or a holoenzyme consisting of several subunits similar to the LigDom, PolDom and/or NucDom of LigDMtub) probably via a direct physical interaction on the DNA between Ku and the PolDom of the LigD holoenzyme. LigD is able to process DNA ends, if broken ends are non-directly ligatable, thanks to its Poldom and/or Nucdom, before ligation by LigDom (Pitcher et al., 2007a).

Most of the past studies on bacterial NHEJ have already been extensively reviewed [START_REF] Bowater | Making Ends Meet: Repairing Breaks in Bacterial DNA by Non-Homologous End-Joining[END_REF]Pitcher et al., 2007a;[START_REF] Shuman | Bacterial DNA repair by non-homologous end joining[END_REF][START_REF] Gu | Mechanistic flexibility as a conserved theme across 3 billion years of nonhomologous DNA end-joining[END_REF][START_REF] Brissett | Repairing DNA double-strand breaks by the prokaryotic nonhomologous end-joining pathway[END_REF], with the exception of the most recent ones on structural data of different LigD domains and mechanistic details of DNA end processing by NHEJ actors before ligation [START_REF] Nair | Structure of bacterial LigD 3'-phosphoesterase unveils a DNA repair superfamily[END_REF][START_REF] Zhu | Gap Filling Activities of Pseudomonas DNA Ligase D (LigD) Polymerase and Functional Interactions of LigD with the DNA End-binding Ku Protein[END_REF][START_REF] Brissett | Structure of a preternary complex involving a prokaryotic NHEJ DNA polymerase[END_REF];[START_REF] Brissett | Molecular basis for DNA double-strand break annealing and primer extension by an NHEJ DNA polymerase[END_REF]. The archaea Methanocella paludicola contain genes coding for homologs of PolDom, NucDom, LigDom and Ku. Their characterization have also deepened our knowledge on the processing of DNA ends during NHEJ [START_REF] Bartlett | Ribonucleolytic resection is required for repair of strand displaced nonhomologous end-joining intermediates[END_REF][START_REF] Brissett | Molecular basis for DNA double-strand break annealing and primer extension by an NHEJ DNA polymerase[END_REF][START_REF] Bartlett | Molecular basis for DNA strand displacement by NHEJ repair polymerases[END_REF]. In the present report, we wished to focus on recent data obtained with different bacterial models highlighting the complexity of the prokaryotic NHEJ pathway in terms of involved actors, their interactions, their regulation, their links with other DNA repair pathways and finally their impact on bacterial evolution.

II-Multiple components NHEJ pathways

The above model of minimal NHEJ, with one Ku and one LigD holoenzyme performing bacterial NHEJ, does not take into account the existence of other proteins involved in this mechanism.

These proteins can be orthologues of Ku or of domains of the LigD holoenzyme, and/or proteins interacting with them. Figure 1 illustrates diverse levels of NHEJ complexity in four bacterial models.

NHEJ complexity: multiplicity of NHEJ-like genes

A recent and large scale search for ku-like genes suggests the existence of a potential NHEJ repair system in about 25% of the prokaryotes for which a genome was available in public databases [START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF], with a scattered distribution. Among the bacterial species predicted to possess a NHEJ repair system, some actually encode several putative Ku homologs, mainly actinobacteria of the streptomycetes family, and proteobacteria of the α subdivision [START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF]. For instance, more than 70% of Streptomyces species encode more than one ku gene (up to 4 in Streptomyces coelicolor) [START_REF] Hoff | Multiple and Variable NHEJ-Like Genes Are Involved in Resistance to DNA Damage in Streptomyces ambofaciens[END_REF], and more than half of αproteobacteria possessing a ku gene actually have two or more (up to 6 in Rhizobium leguminosarum bv trifolii). Some of the ku genes are located on plasmids, suggesting their putative acquisition via horizontal gene transfer. Importance of multiple ku genes in some NHEJ proficient bacteria is discussed further below.

Putative NHEJ ligases are also often present in multiple copies. However, because of the more variable organization of LigD, it is more difficult in this case to predict whether the genes encode bona fide NHEJ ligases. This difficulty is reinforced by the fact that several ATP-dependent DNA ligases can be used to perform NHEJ in the same bacterium. For instance, M. smegmatis encodes four ATP-dependent DNA ligases (LigBMsme, LigC1Msme, LigC2Msme and LigDMsme) [START_REF] Gong | Mechanism of nonhomologous end-joining in mycobacteria: a low-fidelity repair system driven by Ku, ligase D and ligase C[END_REF].

Among them, LigDMsme is the main NHEJ ligase and contains the PolDom, LigDom and NucDom domains, as its homolog LigDMtub. However, LigC1Msme (a LigDom-only enzyme) can act with Ku in an alternative NHEJ in M. smegmatis [START_REF] Gong | Mechanism of nonhomologous end-joining in mycobacteria: a low-fidelity repair system driven by Ku, ligase D and ligase C[END_REF][START_REF] Akey | Crystal structure and nonhomologous end-joining function of the ligase component of Mycobacterium DNA ligase D[END_REF][START_REF] Aniukwu | The pathways and outcomes of mycobacterial NHEJ depend on the structure of the broken DNA ends[END_REF][START_REF] Bhattarai | DNA ligase C1 mediates the LigD-independent nonhomologous end-joining pathway of Mycobacterium smegmatis[END_REF]. This LigC1Msme-dependent alternative NHEJ requires the PolDom of LigDMsme, the LigDom and NucDom being dispensable for this mechanism [START_REF] Bhattarai | DNA ligase C1 mediates the LigD-independent nonhomologous end-joining pathway of Mycobacterium smegmatis[END_REF]. This result, supplemented by the fact that the PolDom of LigDMsme plays a structural role independent of its polymerase activity in the efficiency of recircularization of linearized plasmid in vivo [START_REF] Aniukwu | The pathways and outcomes of mycobacterial NHEJ depend on the structure of the broken DNA ends[END_REF], highlights that the PolDom could serve as an interaction platform for an ATP-dependent ligase protein containing only a LigDom. Other LigC proteins, LigC1 and LigC2 from A. tumefaciens are endowed with ligase activities that are stimulated by Ku [START_REF] Zhu | Characterization of Agrobacterium tumefaciens DNA ligases C and D[END_REF], suggesting that alternative NHEJ pathways are conserved across bacterial species. It has to be noticed that M. smegmatis contains two polD genes expressing two PolDomonly polymerases that can suppress partially the sensitivity to IR of a mutant encoding a polymerase deficient LigD, suggesting that, as observed with LigC1, several PolDom proteins can be used in the NHEJ pathway in Mycobacteria [START_REF] Bhattarai | DNA ligase C1 mediates the LigD-independent nonhomologous end-joining pathway of Mycobacterium smegmatis[END_REF].

In Streptomyces, PolDom, LigDom and NucDom only exist as stand-alone domains and not as multifunctional proteins, making even more complex the identification of actual NHEJ partners.

The analysis of 38 Streptomyces genomes revealed a conserved gene set, composed of two loci, kuA and its neighbor polK and ligC (encoding a putative ligase displaying an higher level of homology with LigC1 from M. smegmatis compared to LigDMsme) and its neighbor polR (polK and polR being two PolDom encoding genes). Surprisingly, ligD, whose product is the closest homolog of LigDMtub, is not ubiquitous in these genomes (present in 75% of the analyzed species), suggesting that the core ligC gene provides the main NHEJ ligase function. The variable set of Streptomyces NHEJ-like genes also includes kuB and kuC, the latter often being plasmid borne and often laying in the close vicinity of ligD. Although they are not conserved, these genes take part in DNA repair since their mutation in Streptomyces ambofaciens confers spore sensitivity to IR and increases the sensitivity of the core gene set mutants [START_REF] Hoff | Multiple and Variable NHEJ-Like Genes Are Involved in Resistance to DNA Damage in Streptomyces ambofaciens[END_REF]. In S. ambofaciens, the involvement of KuA in a NHEJ system has been demonstrated together with the existence of a secondary illegitimate DSB repair system that could imply these variable genes [START_REF] Hoff | Genome plasticity is governed by double strand break DNA repair in Streptomyces[END_REF].

The Streptomyces organization also questions the role of the two conserved PolDom encoding genes (polK and polR). In this regard, Streptomyces is not an exception since M. smegmatis (see above and below, PolD1, PolD2) and numerous eukaryotes, especially vertebrates, also possess several polymerases involved in NHEJ [START_REF] Ramsden | DNA polymerases in nonhomologous end joining: are there any benefits to standing out from the crowd?[END_REF]. A first hypothesis to explain this observation is based on the difference in expression profile: indeed, S. ambofaciens polR seems constitutively expressed whereas polK transcription was not detected in the tested conditions [START_REF] Hoff | Multiple and Variable NHEJ-Like Genes Are Involved in Resistance to DNA Damage in Streptomyces ambofaciens[END_REF], but might be induced in response to some genotoxic stress.

Alternatively or concomitantly, these PolDoms could display different template requirements, as for the four polymerases of the X family found in vertebrates (Pol, Pol, Polµ and TdT, for review see [START_REF] Ramsden | DNA polymerases in nonhomologous end joining: are there any benefits to standing out from the crowd?[END_REF]. Therefore, each PolDom could act specifically on different types of damaged DNA ends. In favor of this hypothesis, in M. smegmatis, a mutation of the PolDom of LigD abolishes the nucleotide addition but not the fill-in activity suggesting that at least two polymerase activities (probably driven by PolD1 and/or PolD2, [START_REF] Bhattarai | DNA ligase C1 mediates the LigD-independent nonhomologous end-joining pathway of Mycobacterium smegmatis[END_REF] would be required for full DSB repair achievement [START_REF] Aniukwu | The pathways and outcomes of mycobacterial NHEJ depend on the structure of the broken DNA ends[END_REF]. Finally, due to its similarity with the mycobacterial locus encoding ligC1 and prim-polC involved in a BER system [START_REF] Płociński | DNA Ligase C and Prim-PolC participate in base excision repair in mycobacteria[END_REF], we surmise that the Streptomyces ligC-polR locus could also be involved in this DNA repair pathway in addition to its role in NHEJ.

Another bacterium displaying a complex organization is Sinorhizobium meliloti, an proteobacterium which encodes four Ku and four LigD orthologues [START_REF] Galibert | The composite genome of the legume symbiont Sinorhizobium meliloti[END_REF]; here, LigD proteins are defined as multidomain ATP-dependent ligases, with LigD3 and LigD1 lacking a Nuc and a Pol domain, respectively. The Ku proteins of -proteobacteria can be classified in several families based on sequence similarity, but a "representative" Ku protein present in all proteobacteria could not be identified. Single and multiple S. meliloti ku mutations conferred IR sensitivity to stationary phase bacteria, suggesting a role of these genes in DNA repair [START_REF] Kobayashi | Multiple Ku orthologues mediate DNA non-homologous end-joining in the free-living form and during chronic infection of Sinorhizobium meliloti[END_REF][START_REF] Dupuy | DNA double-strand break repair is involved in desiccation resistance of Sinorhizobium meliloti, but is not essential for its symbiotic interaction with Medicago truncatula[END_REF]. Involvement of the various ku and ligD genes in NHEJ was assessed more precisely using a linear plasmid recircularization assay, which showed the existence of at least two distinct NHEJ pathways (Fig. 1) [START_REF] Dupuy | Stress-inducible NHEJ in bacteria: function in DNA repair and acquisition of heterologous DNA[END_REF]. The first major pathway is dependent on ku2 and ligD2, two adjacent genes apparently organized in operon, although they can be transcribed from independent promoters. A second, less efficient pathway, dependent on ku3, ku4 and ligD4 was also detected in stress conditions (see further below). Both ku3 and ku4 are organized in operon, whereas ligD4 is located elsewhere in the genome, but all three genes are co-regulated (see further below) and ku3, ku4 and ligD4 orthologues are often found in close proximity, mostly in operon, in -proteobacterial genomes. Interestingly, genetic analyses showed that both ku3 and ku4 are needed for activity of this second pathway. This observation, together with the quasi-systematic co-occurrence and co-regulation of ku3-and ku4-like genes in NHEJ equipped -proteobacteria, led to the suggestion that Ku3 and Ku4 might function as heterodimers, like eukaryotic Ku proteins. Although LigD4 was systematically found associated to the Ku3-Ku4-dependent pathway, LigD2, and to a much lesser extent LigD3, are also able to function, probably aspecifically, with Ku3 and Ku4 on certain types of DNA ends and in certain genetic contexts. Both ku1 and ligD1 are weakly expressed, and consistently, no NHEJ activity could be associated with these genes in the tested conditions. PolD1 (also called LigD1p, [START_REF] Kobayashi | Multiple Ku orthologues mediate DNA non-homologous end-joining in the free-living form and during chronic infection of Sinorhizobium meliloti[END_REF], encoded by the gene located just downstream ligD1, is likely the vestigial PolDom of a larger ancestral LigD1 protein. Deletions of ligD1 analyzed by [START_REF] Dupuy | Stress-inducible NHEJ in bacteria: function in DNA repair and acquisition of heterologous DNA[END_REF] encompassed polD1, showing that this gene is not involved in NHEJ in the tested conditions. S. meliloti also encodes three ligC and one ligB genes, whose role in NHEJ or another DNA repair system has not been tested so far (Fig. 1).

Inactivation of NHEJ in M. smegmatis and S. meliloti unmasked a background level of Ku-and LigD-independent end-joining activity, called alternative End-Joining (A-EJ), observed during recircularization of linear transforming plasmids [START_REF] Aniukwu | The pathways and outcomes of mycobacterial NHEJ depend on the structure of the broken DNA ends[END_REF][START_REF] Dupuy | Stress-inducible NHEJ in bacteria: function in DNA repair and acquisition of heterologous DNA[END_REF].

Depending on the bacterial species and the DNA end type, the observed efficiencies and fidelity of repair greatly varied. It is unclear whether A-EJ occurs by the same mechanism in all cases, but as it was observed in M. smegmatis ligBCD mutants, it is believed to depend on the replicative ligase LigA. Interestingly, LigA-dependent, LigB-independent A-EJ has been described in the NHEJdeficient E. coli [START_REF] Chayot | An end-joining repair mechanism in Escherichia coli[END_REF]. When not resulting in faithful ligation of compatible DNA ends (which occurred in some cases with 100% efficiency; [START_REF] Aniukwu | The pathways and outcomes of mycobacterial NHEJ depend on the structure of the broken DNA ends[END_REF][START_REF] Dupuy | Stress-inducible NHEJ in bacteria: function in DNA repair and acquisition of heterologous DNA[END_REF], A-EJ repair events mostly involved deletions of variable lengths, with frequent occurrence of microhomologies at the junctions [START_REF] Aniukwu | The pathways and outcomes of mycobacterial NHEJ depend on the structure of the broken DNA ends[END_REF], very similar to the observed products of A-EJ in E. coli [START_REF] Chayot | An end-joining repair mechanism in Escherichia coli[END_REF]. These observations highlight the importance of DNA end resection for homology search, which in E. coli is in part due to RecBCD. The resection enzymes involved in the A-EJ of NHEJ-proficient bacteria have not been characterized yet.

NHEJ complexity: are there other actors involved?

Proteins other than Ku and LigD domains have been suggested to be involved in NHEJ, either via their physical and/or functional interaction with Ku and/or LigD or via the impact of their inactivation on DSB repair. This is the case for the helicase UvrD1 from Mycobacteria, which interacts with Ku in a yeast two-hybrid assay and which forms ternary complex with Ku and dsDNA [START_REF] Sinha | Mycobacterial UvrD1 is a Ku-dependent DNA helicase that plays a role in multiple DNA repair events, including double-strand break repair[END_REF]. The fact that the helicase activity of UvrD1 is stimulated in presence of KuMsme and that the deletion of uvrD1 in M. smegmatis sensitizes this bacterium to IR makes sense with a role of UvrD1 in DSB repair via NHEJ. However, its role in this process remains to be elucidated.

Another protein interacting with the NHEJ actors in Mycobacteria is Sir2. This deacetylase interacts physically with both Ku and LigD and its inactivation decreased the NHEJ efficiency in vivo [START_REF] Li | A Sir2-Like Protein Participates in Mycobacterial NHEJ[END_REF]. Its putative role in the NHEJ process is discussed below (see "Regulation of NHEJ").

NHEJ complexity: the multiple DNA binding abilities of Ku

Bacterial Ku is composed of a N-terminal Ku core domain homologous to the central domain of the Ku70 and Ku80 eukaryotic homologs [START_REF] Aravind | Prokaryotic homologs of the eukaryotic DNA-end-binding protein Ku, novel domains in the Ku protein and prediction of a prokaryotic double-strand break repair system[END_REF]Kushwaha and Grove, 2013a;[START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF]Pitcher et al., 2007a). Ku70/80 heterodimer has been shown to bind DSB and to form a ring (involving the Ku core domains of the two subunits) able to encircle a dsDNA molecule [START_REF] Walker | Structure of the Ku heterodimer bound to DNA and its implications for double-strand break repair[END_REF]. This particular structure of the eukaryotic Ku allows its threading inward the DNA molecule when additional Ku proteins enter by the ends (de [START_REF] Vries | HeLa nuclear protein recognizing DNA termini and translocating on DNA forming a regular DNA-multimeric protein complex[END_REF][START_REF] Paillard | Analysis of the mechanism of interaction of simian Ku protein with DNA[END_REF][START_REF] Downs | A means to a DNA end: the many roles of Ku[END_REF]. This threading ability is conserved at least for Ku from B. subtilis, M. tuberculosis and most probably M. smegmatis [START_REF] Weller | Identification of a DNA nonhomologous end-joining complex in bacteria[END_REF]Kushwaha and Grove, 2013a;[START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF]. The Ku core domain of bacterial Ku is associated to a variable C-terminal (C-ter) tail which contains the ubiquitous minimal C-ter domain and, in most cases, an extended C-ter tail [START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF]. The minimal C-ter is required for the interaction of KuBsub with LigDBsub, is involved in the stimulation of the ligase activity of LigDBsub and LigDPaer and is contained in a segment of KuMtub interacting with LigDMtub in a yeast two-hybrid assay [START_REF] Gong | Mechanism of nonhomologous end-joining in mycobacteria: a low-fidelity repair system driven by Ku, ligase D and ligase C[END_REF][START_REF] Zhu | Gap Filling Activities of Pseudomonas DNA Ligase D (LigD) Polymerase and Functional Interactions of LigD with the DNA End-binding Ku Protein[END_REF][START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF]. These observations led to the proposal that the minimal C-ter is a part of the LigD-interacting domain in bacterial Ku. The extended C-ter is predominantly a domain rich in basic residues (lysine and arginine) that is involved, but not required, in the Ku-dependent stimulation of the ligase activity of LigD in P. aeruginosa and B. subtilis [START_REF] Zhu | Gap Filling Activities of Pseudomonas DNA Ligase D (LigD) Polymerase and Functional Interactions of LigD with the DNA End-binding Ku Protein[END_REF][START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF]. This domain also confers to Ku the ability to bind DNA without free ends (Kushwaha and Grove, 2013b;[START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF] and limits the threading of KuBsub inward the DNA molecule. Its function could be to reduce putative negative effects of this threading inside the chromosome on other DNA repair processes. The regulation of the threading of Ku may also be important for the recruitment of LigD near, or at the DSB site, ensuring an efficient NHEJ repair since LigD alone is a poorly efficient ligase without its Ku partner in vitro [START_REF] Weller | Identification of a DNA nonhomologous end-joining complex in bacteria[END_REF][START_REF] Della | Mycobacterial Ku and ligase proteins constitute a two-component NHEJ repair machine[END_REF][START_REF] Zhu | Gap Filling Activities of Pseudomonas DNA Ligase D (LigD) Polymerase and Functional Interactions of LigD with the DNA End-binding Ku Protein[END_REF][START_REF] Ory | Efficient processing of abasic sites by bacterial nonhomologous end-joining Ku proteins[END_REF][START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF]. The function of Ku in the NHEJ could be more proactive than previously anticipated by allowing the bridging of DNA ends, thanks to its extended C-ter [START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF], an ability shared by the human Ku [START_REF] Ramsden | Ku protein stimulates DNA end joining by mammalian DNA ligases: a direct role for Ku in repair of DNA double-strand breaks[END_REF]. The different functions of this extended C-ter domain raise the question about the efficiency of the NHEJ in bacteria encoding a Ku without this domain and/or about the role of Ku and its extended C-ter in another DNA repair mechanism (for instance the BER process, see below). In Streptomyces, one of the accessory Ku (KuB), present in only 8 of 38 species [START_REF] Hoff | Multiple and Variable NHEJ-Like Genes Are Involved in Resistance to DNA Damage in Streptomyces ambofaciens[END_REF], possesses an extra C-ter domain weakly related to the RhoN domain (Pfam 07498) which role in Ku protein remains to be elucidated.

Finally, a very recent study demonstrated that the eukaryotic Ku orthologue encoded by the bacteriophage Mu (d'Adda di [START_REF] Fagagna | The Gam protein of bacteriophage Mu is an orthologue of eukaryotic Ku[END_REF] is able to promote NHEJ repair of plasmidic and chromosomal DSBs, most probably by interacting with and stimulating the E. coli replicative ligase LigA [START_REF] Bhattacharyya | Phage Mu Gam protein promotes NHEJ in concert with Escherichia coli ligase[END_REF]. Surprisingly, MuGam also stimulates in vitro the LigB ligase of E. coli, although MuGam and LigB do not seem to interact on DNA. These results raise the possibility that a bacterial Ku protein might also increase the ligase activity of a non-NHEJ ligase. In this line, KuMsmeg (Kushwaha and Grove, 2013a), but not KuMtub [START_REF] Weller | Identification of a DNA nonhomologous end-joining complex in bacteria[END_REF], has been shown to stimulate the T4 DNA ligase in vitro. To our knowledge, no study assessed the possibility that a bacterial Ku redirects the activity of a bacterial replicative ligase.

III-Regulation of NHEJ

In eukaryotes, NHEJ repairs DSBs throughout the whole cell cycle and is predominant in G1 phase while HR relies on the presence of an intact sister chromatid and therefore functions in S/G2 phase [START_REF] Ira | DNA end resection, homologous recombination and DNA damage checkpoint activation require CDK1[END_REF][START_REF] Aylon | The CDK regulates repair of double-strand breaks by homologous recombination during the cell cycle[END_REF][START_REF] Clerici | The Yku70-Yku80 complex contributes to regulate double-strand break processing and checkpoint activation during the cell cycle[END_REF]. Similarly, during quiescent states such as sporulation (Bacillus, Streptomyces) or late-stationary phase (Mycobacterium, Sinorhizobium) in bacteria, HR would not be operational because stationary phase cells and spores are assumed to be single genome compartments. Note however that spores [START_REF] Setlow | Role of DNA repair in Bacillus subtilis spore resistance[END_REF][START_REF] Moeller | Role of DNA Repair by Nonhomologous-End Joining in Bacillus subtilis Spore Resistance to Extreme Dryness, Mono-and Polychromatic UV, and Ionizing Radiation[END_REF][START_REF] Hoff | Multiple and Variable NHEJ-Like Genes Are Involved in Resistance to DNA Damage in Streptomyces ambofaciens[END_REF] or stationary phase bacteria (Pitcher et al., 2007b;[START_REF] Dupuy | DNA double-strand break repair is involved in desiccation resistance of Sinorhizobium meliloti, but is not essential for its symbiotic interaction with Medicago truncatula[END_REF] of HR-deficient recA mutants display IR sensitivity. This is most likely because of the involvement of recA in the repair of other DNA damages, in particular via its role in the SOS response, since i) spores of B. subtilis addAB and recJ mutants, deficient in the resection step of HR (no other genes coding for end resection nucleases are known to be involved in HR in B. subtilis), displayed IR resistance similar to the one of wild type spores [START_REF] Vlašić | Bacillus subtilis RecA and its accessory factors, RecF, RecO, RecR and RecX, are required for spore resistance to DNA double-strand break[END_REF], ii) the effects of recA and NHEJ mutations on IR sensitivity of B. subtilis and S. ambofaciens spores or M. smegmatis and S. meliloti stationary phase bacteria were found to be additive [START_REF] Stephanou | Mycobacterial Nonhomologous End Joining Mediates Mutagenic Repair of Chromosomal Double-Strand DNA Breaks[END_REF]Pitcher et al., 2007b;[START_REF] Moeller | Multifactorial resistance of Bacillus subtilis spores to high-energy proton radiation: role of spore structural components and the homologous recombination and non-homologous end joining DNA repair pathways[END_REF][START_REF] Hoff | Multiple and Variable NHEJ-Like Genes Are Involved in Resistance to DNA Damage in Streptomyces ambofaciens[END_REF][START_REF] Dupuy | DNA double-strand break repair is involved in desiccation resistance of Sinorhizobium meliloti, but is not essential for its symbiotic interaction with Medicago truncatula[END_REF]. Thus, DSB repair in quiescent cells would essentially rely on NHEJ using available free nonhomologous DNA ends. Furthermore, DSB repair is essential during these quiescent states because cells are more exposed to harsh environmental conditions such as desiccation, that can damage the DNA. How the balance between NHEJ and HR is regulated is far from understood but crucial regarding the consequences of the repair.

The best characterized bacterial NHEJ regulation comes from a study aiming at characterizing gene expression in the forespore of B. subtilis [START_REF] Wang | The Forespore Line of Gene Expression in Bacillus subtilis[END_REF]. The operon containing kuBsub and ligDBsub is expressed inside the forespore under the control of the sigma factor SigG and the transcriptional factor SpoVT. Their role in the DSB repair during spore germination (LigD is an ATP-dependent ligase and ATP is present at very low levels in spores, [START_REF] Korza | Changes in Bacillus Spore Small Molecules, rRNA, Germination, and Outgrowth after Extended Sublethal Exposure to Various Temperatures: Evidence that Protein Synthesis Is Not Essential for Spore Germination[END_REF] has been demonstrated by the localization of a Ku-GFP fusion on the spore nucleoid after initiation of the germination, and by the high sensitivity of NHEJ deficient spores (mutated for kuBsub or kuBsub and ligDBsub) to dry heat, a cause of DSB inside spores [START_REF] Wang | The Forespore Line of Gene Expression in Bacillus subtilis[END_REF]. Other sources of DNA lesions, such as vacuum desiccation, heavy ions bombardment and ultraviolet radiations have a higher toxic effect on NHEJ deficient compared to wild type spores of B. subtilis [START_REF] Moeller | Role of DNA Repair by Nonhomologous-End Joining in Bacillus subtilis Spore Resistance to Extreme Dryness, Mono-and Polychromatic UV, and Ionizing Radiation[END_REF][START_REF] Moeller | Roles of the Major, Small, Acid-Soluble Spore Proteins and Spore-Specific and Universal DNA Repair Mechanisms in Resistance of Bacillus subtilis Spores to Ionizing Radiation from X Rays and High-Energy Charged-Particle Bombardment[END_REF][START_REF] Moeller | Resistance of Bacillus subtilis spore DNA to lethal ionizing radiation damage relies primarily on spore core components and DNA repair, with minor effects of oxygen radical detoxification[END_REF]. According to the study of Wang et al., expression of kuBsub and ligDBsub was observed three to four hours after B. subtilis cells initiate their sporulation program, concomitantly with the expression of SigG and SpoVT [START_REF] Nicolas | Conditiondependent transcriptome reveals high-level regulatory architecture in Bacillus subtilis[END_REF]. However, it was found that the kuBsub ligDBsub operon was slightly up-regulated (~2 times) compared to its basal level (i.e. in non sporulating conditions) when bacteria encounter a cold stress. In this condition neither SpoVT nor SigG were expressed suggesting that the NHEJ genes in B. subtilis could be regulated by other transcriptional factors [START_REF] Nicolas | Conditiondependent transcriptome reveals high-level regulatory architecture in Bacillus subtilis[END_REF]. The NHEJ proficiency of these cold stressed bacteria remains to be assessed. Besides the overexpression of the kuBsub and ligDBsub genes during the sporulation, lack of impact of inactivation of the HR-end resection genes on the X-ray radiation sensitivity of B. subtilis spores led to the proposal for a mechanism that specifically inhibits the action of AddAB and RecJ nucleases inside germinating spores, rendering the NHEJ pathway the only efficient DSB repair mechanism in this condition [START_REF] Vlašić | Bacillus subtilis RecA and its accessory factors, RecF, RecO, RecR and RecX, are required for spore resistance to DNA double-strand break[END_REF][START_REF] Raguse | Bacillus subtilis DisA helps to circumvent replicative stress during spore revival[END_REF]. Moreover, no trace of ku and ligD expression was observed at the transcriptional [START_REF] Nicolas | Conditiondependent transcriptome reveals high-level regulatory architecture in Bacillus subtilis[END_REF] and translational [START_REF] Sinai | The molecular timeline of a reviving bacterial spore[END_REF] levels during the revival of spores. Ku (Ku-GFP fusion) expressed during sporulation is detectable associated to the nucleoid during the first 30 min of the spore revival [START_REF] Wang | The Forespore Line of Gene Expression in Bacillus subtilis[END_REF], i.e. before initiation of DNA replication and expression of DNA repair genes such as recA [START_REF] Sinai | The molecular timeline of a reviving bacterial spore[END_REF]. Then, in B. subtilis, NHEJ and HR do not seem to compete for the repair of two dsDNA ends.

NHEJ is not a hallmark of bacterial sporulation since ku and ligD genes are also present in nonspore forming bacteria and all spore-forming bacteria do not encode these proteins [START_REF] Aravind | Prokaryotic homologs of the eukaryotic DNA-end-binding protein Ku, novel domains in the Ku protein and prediction of a prokaryotic double-strand break repair system[END_REF][START_REF] Bowater | Making Ends Meet: Repairing Breaks in Bacterial DNA by Non-Homologous End-Joining[END_REF][START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF]. In Mycobacteria and in S. meliloti, ku and ligD inactivation leads to a sensitization against IR of mutant bacteria grown in stationary phase and have no or little effect in logarithmic phase, even if recA is inactivated [START_REF] Stephanou | Mycobacterial Nonhomologous End Joining Mediates Mutagenic Repair of Chromosomal Double-Strand DNA Breaks[END_REF]Pitcher et al., 2007b;[START_REF] Kobayashi | Multiple Ku orthologues mediate DNA non-homologous end-joining in the free-living form and during chronic infection of Sinorhizobium meliloti[END_REF][START_REF] Dupuy | DNA double-strand break repair is involved in desiccation resistance of Sinorhizobium meliloti, but is not essential for its symbiotic interaction with Medicago truncatula[END_REF]. On the other hand, ku and/or ligD inactivation strongly reduces the capacity of logarithmically grown Mycobacteria or S. meliloti to repair enzymatically linearized plasmid DNA upon transformation [START_REF] Gong | Biochemical and genetic analysis of the four DNA ligases of mycobacteria[END_REF][START_REF] Gong | Mechanism of nonhomologous end-joining in mycobacteria: a low-fidelity repair system driven by Ku, ligase D and ligase C[END_REF][START_REF] Aniukwu | The pathways and outcomes of mycobacterial NHEJ depend on the structure of the broken DNA ends[END_REF][START_REF] Dupuy | Stress-inducible NHEJ in bacteria: function in DNA repair and acquisition of heterologous DNA[END_REF] as well as enzymatically induced DSB on the chromosome [START_REF] Stephanou | Mycobacterial Nonhomologous End Joining Mediates Mutagenic Repair of Chromosomal Double-Strand DNA Breaks[END_REF][START_REF] Gupta | Mycobacteria exploit three genetically distinct DNA double-strand break repair pathways[END_REF][START_REF] Dupuy | Stress-inducible NHEJ in bacteria: function in DNA repair and acquisition of heterologous DNA[END_REF]. Moreover, ligD is required in exponentially growing M. smegmatis bacteria for infection by the mycobacteriophages Omega and Corndog, where it is thought to promote circularization at the cos site of the phage genomes, thanks to the Ku expressed by the phages [START_REF] Pitcher | Mycobacteriophage exploit NHEJ to facilitate genome circularization[END_REF]. Altogether, these observations show that although not involved in the repair of DSB induced by IR in logarithmic phase, Ku-and LigD-dependent NHEJ is well active in this growth stage in several bacterial species. This is consistent with the detection of similar amounts of Ku and similar activity of its promoter in logarithmic and early stationary phases in M. smegmatis [START_REF] Bhattarai | DNA ligase C1 mediates the LigD-independent nonhomologous end-joining pathway of Mycobacterium smegmatis[END_REF][START_REF] Zhou | Discovery and characterization of Ku acetylation in Mycobacterium smegmatis[END_REF], even if an increased activity of the Ku promoter was observed in late stationary phase cells [START_REF] Bhattarai | DNA ligase C1 mediates the LigD-independent nonhomologous end-joining pathway of Mycobacterium smegmatis[END_REF]. This is also consistent with the expression of a S. meliloti ku2-lacZ transcriptional fusion in both log and stationary phase, and the visualization of Ku2-YFP foci after X-ray treatment of cells in both phases [START_REF] Kobayashi | Multiple Ku orthologues mediate DNA non-homologous end-joining in the free-living form and during chronic infection of Sinorhizobium meliloti[END_REF]. Together, these observations suggest that the action of NHEJ for repair of IR induced DSBs, which have most probably similar molecular configurations in logarithmic and stationary phases, is negatively regulated in logarithmic phase. The mechanism of this inhibition does not seem dependent on RecA since the deletion of recA in M. smegmatis does not increase the NHEJ [START_REF] Gupta | Mycobacteria exploit three genetically distinct DNA double-strand break repair pathways[END_REF], however it could involve the competition with presynaptic actors of the HR.

In S. meliloti, NHEJ activity as measured using a linear plasmid repair assay, displays a significant stimulation when bacteria enter stationary phase, or are exposed to a thermic stress [START_REF] Dupuy | Stress-inducible NHEJ in bacteria: function in DNA repair and acquisition of heterologous DNA[END_REF]. This stimulation mainly results from the upregulation of ku gene expression. The ku3 ku4 operon, as well as the ligD4 gene, appeared to be under transcriptional control of the general stress response EcfG sigma factor RpoE2. Examination of ku promoter regions in α-Proteobacteria revealed the presence of putative EcfG binding sites upstream at least one ku gene in about 90 % of the species, suggesting that stress control of ku and ligD transcription is widespread in this bacterial class. Accordingly, stress induction of ku and/or ligD gene expression was described in Mesorhizobium loti and Bradyrhizobium japonicum [START_REF] Cytryn | Transcriptional and Physiological Responses of Bradyrhizobium japonicum to Desiccation-Induced Stress[END_REF][START_REF] Alexandre | Global Transcriptional Response to Heat Shock of the Legume Symbiont Mesorhizobium loti MAFF303099 Comprises Extensive Gene Downregulation[END_REF]. How ku2 is up-regulated in stress conditions is currently unknown, but it appears not to be part of the general stress response, the heat shock response, the SOS response, the stringent response nor to be regulated by quorum sensing [START_REF] Kobayashi | Multiple Ku orthologues mediate DNA non-homologous end-joining in the free-living form and during chronic infection of Sinorhizobium meliloti[END_REF][START_REF] Dupuy | Stress-inducible NHEJ in bacteria: function in DNA repair and acquisition of heterologous DNA[END_REF]. Whether stress control of NHEJ gene expression is conserved beyond α-Proteobacteria remains to be tested experimentally. In Streptomyces, major NHEJ genes are expressed in lategrowth phase [START_REF] Hoff | Multiple and Variable NHEJ-Like Genes Are Involved in Resistance to DNA Damage in Streptomyces ambofaciens[END_REF] and gene products accumulate in spores. However, no induction of the NHEJ-like genes could be detected in S. ambofaciens in response to DNA damaging agents (i.e., Mitomycin C, [START_REF] Hoff | Multiple and Variable NHEJ-Like Genes Are Involved in Resistance to DNA Damage in Streptomyces ambofaciens[END_REF].

Besides transcriptional regulation, post-translational modification of NHEJ proteins could also regulate NHEJ activity in bacteria. Indeed the deacetylase Sir2 from M. smegmatis is required for an efficient NHEJ repair in vivo [START_REF] Li | A Sir2-Like Protein Participates in Mycobacterial NHEJ[END_REF]. Overexpression of sir2 leads to a decreased amount of Ku in bacteria, without altering the quantity of the corresponding mRNA. In line with this interaction, KuMsme is acetylated at least at the residue K29, which is conserved among bacterial Ku, and this modification is mainly observed in stationary phase [START_REF] Zhou | Discovery and characterization of Ku acetylation in Mycobacterium smegmatis[END_REF]. Even if the mechanism by which Sir2 regulates NHEJ proteins remains to be clarified, it seems likely that acelylation could regulate the activity of NHEJ [START_REF] Zhou | Discovery and characterization of Ku acetylation in Mycobacterium smegmatis[END_REF].

IV Cross talk with other DNA repair mechanisms

As mentioned in the section III, DSB repair in quiescent cells would essentially rely on NHEJ, but NHEJ and HR repair mechanisms may both co-exist, at least in some NHEJ proficient bacteria during replicating phases. Moreover, in Streptomyces, recent studies [START_REF] Hoff | Genome plasticity is governed by double strand break DNA repair in Streptomyces[END_REF] on the consequences of DSB repair in the terminal region of the linear chromosome revealed events of HR repair involving homologous sequences at distinct loci suggesting that HR can occur even in the absence of a replicated copy of the chromosome (quiescent phases). This raises the question of how the choice between the two pathways is performed and if there is a competition between both mechanisms. In eukaryotes, it is known that Ku proteins rapidly sequester DSB free ends and shield them from unscheduled exonucleases, preventing HR to proceed. The removal of Ku involves multiple pathways including ubiquitination, neddylation, phosphorylation and the nuclease activity of the MRE11-dependent complex MRX (yeast) /MRN (mammals) which plays a pivotal role in NHEJ/HR balance (for review see [START_REF] Shibata | Regulation of repair pathway choice at two-ended DNA double-strand breaks[END_REF]. Similarly, in Mycobacterium, in vitro analyses revealed that KuMtub protects DSBs from resection by AdnAB helicase-nuclease [START_REF] Sinha | AdnAB: a new DSB-resecting motor-nuclease from mycobacteria[END_REF] and KuMtub but not LigDMtub inactivation is compensated by an elevated HR in vivo [START_REF] Gupta | Mycobacteria exploit three genetically distinct DNA double-strand break repair pathways[END_REF]. Likewise, in S. avermitilis, the deletion of kuSave1 and kuSave2 seemed associated with an increased efficiency of HR [START_REF] Zhang | Deletion of ku homologs increases gene targeting frequency in Streptomyces avermitilis[END_REF]. Recent electronic beam irradiation assays in S. ambofaciens (Hoff et al., 2016, Leblond et al., unpublished) also suggest that NHEJ inactivation (kuSamb triple deletion or ligCSamb and ligDSamb double deletion) is compensated for by an increased HR repair. However, unlike in Mycobacterium where loss of HR is not compensated by increased NHEJ, a reciprocal effect is observed in S. ambofaciens since a recA mutant is 100 times more affected by NHEJ inactivation than the wild-type strain.

Ku and LigD proteins may help coupling NHEJ to other DNA repair pathways. IR-induced cellular damages on DNA include oxidized bases, abasic sites and single-strand breaks (SSB). However, due to the presumed "clustered damage" induced by IR [START_REF] Ward | The Complexity of DNA Damage: Relevance to Biological Consequences[END_REF], several DNA lesions can be present in close proximity and, if they are not repaired efficiently, can lead to DSB [START_REF] Ward | The Complexity of DNA Damage: Relevance to Biological Consequences[END_REF][START_REF] Blaisdell | Abortive base-excision repair of radiation-induced clustered DNA lesions in Escherichia coli[END_REF][START_REF] Cox | Deinococcus radiodurans -the consummate survivor[END_REF]. Then, DSBs induced by IR are potentially surrounded by multiple other DNA lesions. Part of these lesions are taken in charge by the base excision repair (BER) pathway, the nicking of the phosphodiester bond 3' to an apurinic/apyrimidinic (AP) site by an AP-lyase being one possible step of this pathway (for review see [START_REF] Almeida | A unified view of base excision repair: lesion-dependent protein complexes regulated by post-translational modification[END_REF]. Human Ku, besides its function as a scaffolder of the NHEJ machinery, is also an AP-lyase suggested to be involved in the repair of AP site near DSBs [START_REF] Roberts | Ku is a 5'-dRP/AP lyase that excises nucleotide damage near broken ends[END_REF]. This activity is conserved in Ku from B. subtilis and P. aeruginosa (de [START_REF] Ory | Efficient processing of abasic sites by bacterial nonhomologous end-joining Ku proteins[END_REF]. As KuBsub is able to thread inward DNA molecules [START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF], via loading on their broken ends, this could facilitate the repair of abasic sites surrounding a DSB. The interplay between NHEJ and BER in bacteria is reinforced by the discovery of an AP-lyase activity driven by the other NHEJ factor: LigD (de [START_REF] Ory | Identification of a conserved 5'-dRP lyase activity in bacterial DNA repair ligase D and its potential role in base excision repair[END_REF]. The involvement of LigC1Msme in BER during stationary phase of M. smegmatis [START_REF] Płociński | DNA Ligase C and Prim-PolC participate in base excision repair in mycobacteria[END_REF] shows that the link between NHEJ and BER can even be extended to alternative NHEJ proteins. This multiplicity of NHEJ actors involved in BER is not specific to bacteria, human DNA polymerase λ is one example (see [START_REF] Bebenek | Structure-function studies of DNA polymerase λ[END_REF].

Remarkably, KuBsub is also able to linearize a supercoiled plasmid containing AP-sites (de [START_REF] Ory | Efficient processing of abasic sites by bacterial nonhomologous end-joining Ku proteins[END_REF]. This counter-intuitive effect for a protein intended to repair DSB is supposed to be dependent on its AP-lyase activity and its ability to bind end-free dsDNA molecules, DSB arising by the nicking of phosphodiester bonds of proximal AP-sites on opposite strands of a dsDNA molecules containing numerous such lesions (de [START_REF] Ory | Efficient processing of abasic sites by bacterial nonhomologous end-joining Ku proteins[END_REF]. Then it is tempting to propose that NHEJ could have evolved from a Ku-dependent BER pathway, primarily independent on the presence of DSB, that has acquired the ability to join Ku-catalyzed broken DNA ends, via the recruitment of LigD, in conditions where the bacterial genome contains numerous AP-sites. This hypothesis and the fact that most of the bacterial Ku proteins contain an extended C-ter tail that is required for their interaction on end-free DNA (Kushwaha and Grove, 2013b;[START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF] but for which the deletion has only a mild effect in vitro on the NHEJ efficiency [START_REF] Zhu | Gap Filling Activities of Pseudomonas DNA Ligase D (LigD) Polymerase and Functional Interactions of LigD with the DNA End-binding Ku Protein[END_REF][START_REF] Mcgovern | C-terminal region of bacterial Ku controls DNA bridging, DNA threading and recruitment of DNA ligase D for double strand breaks repair[END_REF] suggest that the extended C-ter of Ku could play an important role in a Ku-dependent BER acting on AP-sites embedded in duplex regions of DNA.

A recent study has functionally linked the NHEJ of P. aeruginosa to the MutL protein, a component of the mismatch repair (MMR) pathway. Searching for the molecular mechanism at the basis of a large genomic deletion in the P. aeruginosa chromosome allowing to prevent infection by a bacteriophage, [START_REF] Shen | Pseudomonas aeruginosa MutL promotes large chromosomal deletions through non-homologous end joining to prevent bacteriophage predation[END_REF] have shown that MutLPaer is required for getting the deletion. MutLPaer is an endonuclease promoting SSB and, directly or indirectly, DSB (as a consequence of multiple SSB in dsDNA). Surprisingly, the MutLPaer-dependent genomic deletion observed after the bacteriophage infection is not dependent on MutSPaer, the partner of MutLPaer in MMR, suggesting a new function of MutL in this bacterium. Whatever the mechanism, the reduced frequency of the corresponding deletion in a NHEJ deficient mutant led to the proposal that DSB generated by MutLPaer are repaired by the NHEJ pathway in this bacterium [START_REF] Shen | Pseudomonas aeruginosa MutL promotes large chromosomal deletions through non-homologous end joining to prevent bacteriophage predation[END_REF]. On the other hand, the majority of archaeal species and many actinobacteria lack MutHLS system but display genes putatively involved in a novel mismatch repair system, called NucS/EndoMS, which has been shown in Corynebacterium glutamicum to cleave both strands at double-strand DNA mismatched substrate during the repair process [START_REF] Castañeda-García | A non-canonical mismatch repair pathway in prokaryotes[END_REF][START_REF] Ishino | Activation of the mismatch-specific endonuclease EndoMS/NucS by the replication clamp is required for high fidelity DNA replication[END_REF]. Whether these induced DSBs are thereafter processed by NHEJ or HR

is not yet known, but one can suggest that chromosomes of bacteria possessing a NucS/EndoMS system are more prone to DSBs and consequently to mutations and rearrangements, especially if they also feature a NHEJ machinery, like many actinomycetes.

Another mechanism that induces DSBs is the type II CRISPR-Cas (Clustered Regularly Interspaced Short Palindromic Repeats and associated proteins) system which is conferring adaptive immunity against phages and exogenous mobile genetic elements (for review see [START_REF] Marraffini | CRISPR-Cas immunity in prokaryotes[END_REF] and which has been engineered to provide an efficient genome editing method [START_REF] Jinek | A Programmable Dual-RNA-Guided DNA Endonuclease in Adaptive Bacterial Immunity[END_REF]. Since the CRISPR-Cas system generates DSBs, it could display antagonistic interactions with DSB repair systems. Bernheim and co-authors (2017) revealed that NHEJ and type II-A CRISPR-Cas systems do not co-occur in all but one of more than 5000 sequenced bacterial genomes. On the other hand, this strong avoidance of co-occurrence was not observed with type II-C system, which is consistent with the fact that, unlike type II-A system, type II-C system lacks Csn2, a multimeric toroidal binding protein that binds double stranded DNA ends and has similar properties to Ku protein [START_REF] Arslan | Doublestrand DNA end-binding and sliding of the toroidal CRISPR-associated protein Csn2[END_REF]. The binding of Csn2 at DNA ends could block access to Ku and inhibit efficient repair by NHEJ. In contrast, B. subtilis NHEJ system does not impair Streptococcus pyogenes or Streptococcus thermophilus type II-A CRISPR-Cas9 system [START_REF] Bernheim | Inhibition of NHEJ repair by type II-A CRISPR-Cas systems in bacteria[END_REF].

V-NHEJ and genome evolution

NHEJ is inherently unfaithful, as DNA ends of DSB are often remodeled before ligation, thus generating short insertions or deletions at the repair junction (although repair fidelity seems to vary depending on the tested organism, the type of DNA ends being repaired or the enzymes involved). Interestingly, NHEJ is generally more active in stationary phase or during sporulation, and in α-proteobacteria, is activated under stress conditions, in a process dependent on the general stress response sigma factor EcfG. This is reminiscent of the so-called stress-induced mutagenesis of enterobacteria, where the highly faithful HR-dependent DSB repair becomes mutagenic in a process dependent on the general stress response sigma factor RpoS [START_REF] Shee | Impact of a stressinducible switch to mutagenic repair of DNA breaks on mutation in Escherichia coli[END_REF]. NHEJ was also recently suggested to participate in stationary phase mutagenesis in Pseudomonas putida [START_REF] Paris | NHEJ enzymes LigD and Ku participate in stationary-phase mutagenesis in Pseudomonas putida[END_REF]. NHEJ could then significantly contribute to DSBdependent stress-induced mutagenesis in bacteria and could thus participate in their adaptation to adverse environmental conditions.

In addition to the short, non-templated nucleotide insertions usually observed at NHEJ repair junctions, insertion of longer DNA sequences (several tens of nucleotides) of either plasmid or chromosomal origin, was described to have occurred in rare instances at plasmid or chromosome DSB repair junctions in M. smegmatis and S. ambofaciens [START_REF] Akey | Crystal structure and nonhomologous end-joining function of the ligase component of Mycobacterium DNA ligase D[END_REF][START_REF] Aniukwu | The pathways and outcomes of mycobacterial NHEJ depend on the structure of the broken DNA ends[END_REF][START_REF] Hoff | Genome plasticity is governed by double strand break DNA repair in Streptomyces[END_REF]. Although the mechanism of such DNA insertions was not clearly established, it may have resulted from the incidental capture of indigenous DNA fragments at the break by the NHEJ machinery. In eukaryotes, DNA inserted into the genome by NHEJ during evolution include foreign DNA fragments such as mitochondrial DNA, transposable elements, and viral DNA [START_REF] Moore | Capture of retrotransposon DNA at the sites of chromosomal double-strand breaks[END_REF][START_REF] Ricchetti | Mitochondrial DNA repairs double-strand breaks in yeast chromosomes[END_REF]Lin and Waldman, 2001a;Lin and Waldman, 2001b;[START_REF] Nakai | AAV serotype 2 vectors preferentially integrate into active genes in mice[END_REF][START_REF] Hazkani-Covo | Numt-mediated double-strand break repair mitigates deletions during primate genome evolution[END_REF]. In yeast, capture of extranuclear DNA at repaired DSBs was shown to be dependent on DNA end resection and NHEJ complexes [START_REF] Decottignies | Capture of extranuclear DNA at fission yeast double-strand breaks[END_REF]. In the same way, the low level of genome rearrangements in the yeast Lachancea kluyveri since its separation from its ancestor with S. cerevisiae was assigned to the loss of NHEJ genes in this phylum [START_REF] Gordon | Mechanisms of chromosome number evolution in yeast[END_REF]. Interestingly, Dupuy et al. demonstrated that linear DNA of heterologous origin, introduced in S. meliloti by transformation, could be effectively captured in a NHEJ-dependent way at an artificially generated DSB in the chromosome [START_REF] Dupuy | Stress-inducible NHEJ in bacteria: function in DNA repair and acquisition of heterologous DNA[END_REF].

In Streptomyces, since the variable NHEJ genes encode actors of the response to DNA damage [START_REF] Hoff | Multiple and Variable NHEJ-Like Genes Are Involved in Resistance to DNA Damage in Streptomyces ambofaciens[END_REF] that presumably participate to the NHEJ and other DNA repair pathways, it is likely that different combinations of NHEJ genes result in variable recombination profiles, and consequently in variable abilities to integrate DNA from horizontal gene transfer. Like for E. coli mutator strains [START_REF] Giraud | Costs and benefits of high mutation rates: adaptive evolution of bacteria in the mouse gut[END_REF], such recombination proficient lineages could provide a flexible adaption property to the population in the ecological context by allowing rapid and intense diversification of the accessory gene set. This speculation is substantiated by the strong variability of the NHEJ-gene set revealed within a Streptomyces population originating from a forest soil (Leblond et al., unpublished). Altogether, these data suggest that NHEJ could participate in the acquisition of heterologous DNA during lateral transfer events, overcoming the lack of sequence homology between distantly related species. Interestingly, in support of this hypothesis, [START_REF] Popa | Directed networks reveal genomic barriers and DNA repair bypasses to lateral gene transfer among prokaryotes[END_REF] found that gene transfer events from distant donors are more frequent when recipient genomes encode NHEJ proteins. In addition, [START_REF] Kidane | Evidence for different pathways during horizontal gene transfer in competent Bacillus subtilis cells[END_REF] have observed that the absence of Ku reduces natural plasmid transformation and phage DNA transfection in B. subtilis.

Concluding remarks

As mentioned within this review, many NHEJ proficient bacteria contain several stand-alone genes displaying similarities with genes coding for Nucdom, Poldom, LigDom and/or ku genes and their multiplicity renders difficult the identification of the bona fide NHEJ genes. The use of two-hybrid screening coupled with affinity purification of the products of these genes in their host and in conditions where NHEJ is active should help to characterize actual NHEJ complexes, and potentially identify new components of the NHEJ machinery, or new links with other DNA repair pathways (e.g. role of AP-lyase activities in response to genotoxic stresses). Structural information (i.e. cryo-electron microscopy and super-resolution microscopy analyses) associated to 3D structures of stand-alone NHEJ actors (LigD, Ku) and of the complete bacterial NHEJ machinery will be of crucial importance for our basic understanding of this mechanism (e.g. NHEJ synapsis step, DNA extremities tethering, processing of variable DNA ends). Furthermore, alternative NHEJ machineries may be involved depending on the growth phase or growth conditions (see above the stress-induced NHEJ machineries of S. meliloti). This raises the questions of the competition between distinct NHEJ machineries, and between HR and NHEJ, to repair DSBs in conditions where both mechanisms coexist. It is clear, based on our knowledge of the eukaryotic NHEJ, that DNA ends accessibility should be a key point that affects the HR/NHEJ balance. Genetic, biochemical and cellular localization studies of proteins involved in early steps of these pathways over time after DSB induction should help to elucidate preferred routes of DSB repair in different life states. Further, experimental evolution could constitute a powerful approach for testing the involvement of NHEJ in integration of DNA acquired by horizontal gene transfer and its impact on the capacity to create and maintain genetic diversity within bacterial populations in their ecosystems.

Finally, understanding the bacterial NHEJ may have therapeutic interest. Indeed, many human pathogens possess a NHEJ repair system. This is for instance the case for the most deadly human pathogen M. tuberculosis and the nosocomial pathogen P. aeruginosa. Although NHEJ is not directly involved in survival or virulence in different mammal hosts [START_REF] Brzostek | Either nonhomologous ends joining or homologous recombination is required to repair double-strand breaks in the genome of macrophage-internalized Mycobacterium tuberculosis[END_REF][START_REF] Heaton | Deficiency of double-strand DNA break repair does not impair Mycobacterium tuberculosis virulence in multiple animal models of infection[END_REF], it could provide a way to survive to genotoxic conditions in certain non-dividing states. Identifying these states and developing anti-NHEJ compounds based on the highresolution structure of a NHEJ machinery could help to fight against these pathogens.

Acknowledgments

This work was supported by INRA (Institut National de la Recherche Agronomique) -including by the Département Santé des Plantes et Environnement-, by the French Laboratory of Excellence project TULIP (ANR-10-LABX-4), by the French National Research Agency program Streptoflux (ANR Blanc 0096_01), and by ANR through the Laboratory of Excellence ARBRE (ANR-12-LABXARBRE-01). The authors declare that they have no competing interests.


Charles André
email: candre@sophia.inria.fr

Frédéric Mallet
email: fmallet@sophia.inria.fr

Robert De Simone

Modeling of immediate vs. delayed data communications: from AADL to UML MARTE

The forthcoming OMG UML Profile for Modeling and Analysis of Real-Time Embedded systems (MARTE) aims, amongst other things, at providing a referential Time Model subprofile where semantic issues can be explicitly and formally described. As a full-size exercise we deal here with the modeling of immediate and delayed data communications in AADL. It actually reflects an important issue in RT/E model semantics: a propagation of immediate communications may result in a combinatorial loop, with ill-defined behavior; introduction of delays may introduce races, which have to be controlled. We describe here the abilities of MARTE in this respect.

I. Introduction

The modeling phase in Real-Time Embedded design is increasingly required to allow various types of timing analysis prior to final code production and testing. AADL [START_REF] Standards | SAE Architecture Analysis and Design Language[END_REF] and MARTE [START_REF] Omg | UML profile for Modeling and Analysis of Real-Time and Embedded systems (MARTE)[END_REF] are two such modeling formalisms, in part similar in their objectives. They both allow independent descriptions of the functional applications and the execution platforms, and the possible allocation of the former onto the latter. They also allow the description of both the structural organization of systems, and to some extent of their dynamic behaviors.

Our belief here is that AADL relies on a number of assumptions that make the definition of dynamic behaviors visibly simple, but largely implicit and informal (with the risk of ambiguity or misdesign, which various analysis tools then try to spot and identify). Conversely, MARTE explicit Time model with powerful logical time constraints allows to specify precisely and thoroughly the scheduling aspects of application elements (which induces a relevant definition apparatus). Multiform logical time supported by MARTE, is inspired from the theory of tag systems [START_REF] Lee | A framework for comparing models of computation[END_REF].

AADL applications comprise threads, often of periodic nature (with distinct periods), connected through event or data parts. Data communications can be immediate or delayed. As can be seen here, the same model provides structural information (the thread connections) together with a crude abstraction of behaviors usually needed for schedulability analysis (the relative speeds of threads). Delayed communications are needed in particular to break down cycle propagation of data. They implicitly impose a partial order on how various threads (and their containing processes) can be executed/simulated in a simultaneous step. The issues of priority inversion involved here are dealt with in [START_REF] Feiler | Embedded System Architecture Analysis using SAE AADL[END_REF]. AADL thread modeling thus requires the conjunct of two MARTE models (one behavioral and one structural), with the relevant logical clocks defining the relative ordering of dispatch events for the threads according to the desired semantics. The operational semantics is now explicit, and the various protocols (immediate/delayed) can be constructed in a formal way. This is the topic of the current paper. The hope is that such construction can then allow by analytic techniques to prevent non-determinism and pathological priority inversions to occur, in a way that is predicted and garanteed rather than monitored by non-exhaustive model simulations.

II. Background

A. Time in MARTE

The metamodel for time and time-related concepts is described in the "Time modeling" chapter of the UML profile for MARTE, soon available at the OMG site. The time chapter is briefly described in another paper [START_REF] André | Modeling time(s)[END_REF].

In MARTE, Time can be physical, and considered as continuous or discretized, but it can also be logical, and related to user-defined clocks. Time may even be multiform, allowing different times to progress in a non-uniform fashion, and possibly independently to any (direct) reference to physical time. The time structure is defined by a set of clocks and relations on these clocks. Here clock is not a device used to measure the progress of physical time. It is a mathematical object lending itself to formal processing instead. A clock that refers to physical time is called a chronometric clock. A distinguished chronometric clock called idealClk is provided in the MARTE time library. This clock represents the "ideal" physical time, used, for instance, in physical and mechanics laws. At the design level most of the clocks are logical ones.

The mathematical model for a clock is a 5-tuple (I, , D, λ, u) where I is a set of instants, is an order relation on I, D is a set of labels, λ : I → D is a labeling function, u is a symbol, standing for a unit. For a chronometric clock, the unit can be the SI time unit s (second) or one of its derived units (ms, us. . . ). The usual unit for logical clocks is tick, but clockCycle, executionStep . . . may be chosen as well. Since instants of a clock are fully ordered, (I, ≺) is an ordered set.

Clock are a priori independent. They become dependent when their instants are linked by instant relations imposing either coincidence between instants (coincidence relation ≡) or precedence (precedence relation ).

Clock relations are a convenient way to impose manyoften infinitely many-instant relations. Examples of clock relations are given in Section III-B.

A Time Structure is a 4-tuple (C, R, D, λ) where C is a set of clocks, R is a relation on a,b∈C,a =b (I a × I b ), D is a set of labels, λ : I C → D is a labeling function. I C is the set of the instants of a time structure. I C is not simply the union of the sets of instants of all the clocks; it is the quotient of this set by the coincidence relation induced by the time structure relations represented by R. A time structure specifies a poset (I C , C ).

During a design we introduce several (logical) clocks that are progressively constrained. This causes strengthenings of the ordering relation of the application time structure.

B. AADL inter-thread communications

As a demonstration of the expressiveness of MARTE, we take as an example the inter-thread data communication semantics of AADL. In AADL, the communications can be immediate (Fig. 1a) or delayed (Fig. 1b). The threads are concurrent schedulable units of sequential executions. Several properties can be assigned to threads, the one of concern here is the dispatch protocol. We actually consider only periodic threads, associated with a period and a deadline, specified as chronometric time expressions (e.g., period=50ms or frequency=20Hz). By default, when the deadline is not specified it equals the period.

III. The explicit modeling of AADL communication aspects A. Application and clock refinement

A first difference with AADL is that MARTE differentiates the algorithm, which can be represented as an activity diagram (Fig. 2, upper part), from the underlying structure, which is modeled here as a composite structure diagram (Fig. 2, lower part), and that implies a logical scheduling. Each part has its own causality constraints. MARTE refinement mechanism, and its associated clock constraints, allows for expliciting relations amongst the clocks of both parts. In MARTE, activation conditions of all application model elements are represented by clocks identified with the appropriate stereotypes, for instance TimedProcessing. As a starting point, we consider the clocks of each element as independent, then the context (dependencies and refinement) constrains these clocks. At last, a timing analysis tool may resolve the constraints to determine a (family of) possible schedules. We strive to avoid overspecification and keep the model as generic as possible, adding only required constraints. From the algorithmic point of view, the actions read data and control are CallBehaviorAction that execute a given behavior repetitively according to their activation condition (clocks d and c respectively).

B. Introducing clock constraints

From the structural point of view, the threads t1 and t2 are also associated with clocks ( t1 and t2 respectively). These clocks, purely logical, represent the dispatches of the threads. In AADL, the period of a thread is expressed as a chronometric time expression and therefore, at some point, we need to establish relations between these clocks and chronometric clocks. This aspect is addressed in section III-E, but we need to set up some causality relations first.

Deciding that a given behavior (i.e., read data) is executed by a periodic thread (i.e., t1) implies that each thread dispatch (modeled by clock t1) causes and therefore precedes a new execution of subprogram read data, and that this execution must complete before the deadline (the next dispatch by default). In MARTE, we differentiate atomic behaviors, for which the execution time is considered negligible as compared to the period, from non-atomic ones. If we consider the behaviors as atomic, the association of a behavior with a thread is simply expressed with the constraint given by Eq. 1. Note that this constraint is not symmetrical since t1 may cause d, but not the converse.

t1 alternatesWith d (1)
If the execution time is not negligible, each action can be represented by two events, the start (e.g., ds for d, cs for c ) and the finish (e.g., df for d, cf for c), and a duration. In that latter case, we need three constraints to express that the behavior read data is repetitively executed on thread t1 (Eqs. 2-4).

t1 alternatesWith ds

(2)

t1 alternatesWith df (3)
ds isFasterThan df (4)
The first two constraints express that the behavior starts and finishes between two consecutive dispatches of thread t1. The last constraint, which reads clock ds is faster than clock df , specifies that the action read data starts before it finishes; it is sufficient to impose that it finishes within the same cycle of execution.

The next constraint comes from the communication itself. We use a UML data store to mean that the action read data can overwrite the existing value (in the object node) without generating a new token and this very same value can be read several times by the action control (non depleting read). In UML, there must be at least one writing before any reading (Eq. 5).

d [START_REF] Standards | SAE Architecture Analysis and Design Language[END_REF] precedes c [START_REF] Standards | SAE Architecture Analysis and Design Language[END_REF] (5)

Let wr be the (logical) clock for significant writings in the data store. There could be several consecutive writings in the datastore before one reading. In that case, only the last one is considered significant. Let rd be the corresponding (logical) clock for significant readings from the data store. When the same value is read several times, only the first reading is considered to be significant. Furthermore, AADL assumes that communicating threads must have common dispatches. A simple way to achieve that is if all threads start their execution at the same time (they are in phase). The AADL standard considers three cases: synchronous threads with the same period, oversampling (the period of control is evenly divided by the period of read data), undersampling (the period of read data is evenly divided by the period of control). Let q1 and q2 be natural numbers such that f d /f c = q1/q2. They represent the relative periods of read data and control. Section III-F discusses how to compute q1 and q2 in the general case. When the threads are synchronous (Eq. 6), q1 = q2 = 1. When oversampling (Eq. 7), q1 = 1 and q2 > 1. When undersampling (Eq. 8), q1 > 1 and q2 = 1. max(q1, q2) is called the hyper-period. In Eq. 7 (resp. Eq. 8), the binary word [START_REF] Cohen | N-synchronous kahn networks[END_REF] following the keyword filteredBy expresses that each instant of t1 (resp. t2 ) is synchronous with every q2 th (resp. q1 th ) instant of t2 (resp. t1 ).

t1 ≡ t2 (6)
t1 ≡ t2 filteredBy (1.0 q2-1 ) (7)

t2 ≡ t1 filteredBy (1.0 q1-1 ) (8)
Selecting the significant writings and readings consists in choosing one every q1 th instant of d (Eq. 9) and one every q2 th instant of c (Eq. 10).

Additionally, Eq. 11 states that each significant writing must precede its related significant reading.

wr isPeriodicOn d period q1 (9)
rd isPeriodicOn c period q2 (10)

wr alternatesWith rd (11)
We restrict our comparison to the three cases considered by the AADL standard. However, in subsection III-F we elaborate on the general case.

We have defined all general constraints. In particular, note that contrary to Eqs. 7-8, Eqs. 9-10 do not specify which instant is chosen as a significant writing or reading. The actual instant depends on the semantics of the communication. The following two subsections study the three different cases (synchronous, oversampling, undersampling) with both an immediate and a delayed communication, each subsection gives stronger constraints compatible with Eqs. 9-11. An immediate communication means that the result of the sending thread (here read data) is immediately available to the receiving thread (here control). When threads are synchronous (Fig. 3a), this is denoted by " wr ≡ d " and " rd ≡ c ", or more precisely by " wr ≡ df "and " rd ≡ cs ". In case of oversampling (Fig. 3b), the result of the action read data must be written in the object node early enough so that the first (for each q2-long hyper-cycle) execution of the action control can use it. This is denoted by " wr ≡ d " and " rd ≡ c filteredBy 1.0 q2-1 ". The latter constraint is stronger than Eq. 10: it implies it. In case of undersampling (Fig. 3c), AADL specifies that the execution of the first (for each q1-long hyper-cycle) execution of the action read data must complete before the execution of the action control. This is stated by " rd ≡ c " and " wr ≡ d filteredBy 1.0 q1-1 ". A delayed communication means the result of the sending thread is made available only at its next dispatch while the receiving thread only reads after its own dispatch and ultimately when the data is required. The dispatches of the sending and the receiving threads are not necessarily all synchronous, even if there must be a synchronization at some point. When the thread are synchronous (Fig. 4a), the constraint is denoted by Eqs. 12-13. Note that δ4 offers the possibility to delay the actual execution of read data. The thread t1 can either be idle or be executing another action before starting to execute read data. Eq. 12 states that

C. Immediate communication

D. Delayed communication

(∃δ4 ∈ N) (∀k ∈ N ) wr[k] ≡ t1[δ4 + k] . (∃δ4 ∈ N) wr ≡ t1 filteredBy 0 δ4 (1) (12) rd ≡ c (13)
For oversampling (Fig. 4b), the result is available for the first execution of the action control of the next q2long hyper-cycle. This leaves lots of freedom to schedule the action read data anywhere within the current hypercycle. We keep the relation Eq. 12 while Eq. 13 is replaced by Eq. 14.

rd ≡ c filteredBy 1.0 q2-1 (14)
For undersampling (Fig. 4c), the result of the last execution (for each q1-long hyper-cycle) of the action read data is available for the action control at the next hyper-cycle. This is denoted by combining Eq. 15 with Eq. 13.

(∃δ4 ∈ N) wr ≡ t1 filteredBy 0 δ4 1.0 q1-1 (15)

Note that the relations are not fully symmetrical. This is due to the AADL semantics that changes the rule depending on the kind of communication.

Up to here, we have only defined logical constraints. In some cases, these constraints are strong enough to get a total order, and thus a possible schedule, on all instants belonging to the defined clocks. For instance, in the delayed synchronous case, whenever the first execution of read data occurs, the first significant writing occurs at the very next dispatch. However, in some other cases, we need additional stronger constraints to get a schedule. These constraints reflects additional choices that are mainly implicit in the AADL semantics. Depending on these choices we get different deterministic schedules. These cases are studied in the next section.

E. Getting a schedule

Figure 3 shows that for immediate communications, the constraints given define a total order between instants of d and c in both the synchronous and the oversampling cases. Combining our constraints we get the same result analytically. One question remains, it is whether or not both executions (read data and control) can be performed within the period of thread t2. If not, there is no possible schedule, otherwise, the schedule is given by Figure 5, assuming both threads are executed on the same process. For delayed communications, additional constraints are required to get a deterministic schedule. Several criteria can be considered, like for instance, the size of the buffer used for the communication, or applying a well-know scheduling policy, like Earliest Deadline First (EDF).

An apparent easy way to force a total order is to project the logical clocks onto chronometric clocks. Logical clocks only give an order amongst instants (sometimes partial), while chronometric clocks give an absolute position in time. The use of chronometric clocks is implied in AADL because of the units used to describe either the frequency (Hz) or the period (s). In MARTE, we create models of chronometric clocks by discretizing idealClk (Sec. II-A). For instance, we create three chronometric clocks c 100 , c 10 and c 30 of respective frequency 100Hz, 10Hz and 30Hz (Eqs. 16-18). Note that these are relations, whence the definition of the 30Hz-clock from c 10 . Now, we replace the three equations (Eqs. 6-8) by the three following constraints. t1 ≡ t2 ≡ c 10 (synchronous), t1 ≡ c 10 and t2 ≡ c 30 (oversampling), t1 ≡ c 30 and t2 ≡ c 10 (undersampling). The only additional information we have here is the distance (expressed in seconds) between two consecutive dispatches. This information is useful for comparing the duration of executions with the period of the threads, however it does not change in any way the causality relations expressed.

c 100 ≡ idealClk discretizedBy 0.01 (16) c 10 ≡ c 100 filteredBy (1.0 9 ) (17) c 10 ≡ c 30 filteredBy (1.0 2 ) (18)
For the immediate undersampling, we can infer from the specified constraints that, for each hyper-cycle, the first execution of read data must complete before the execution of control. However, we cannot decide when to execute control relatively to other executions of read data. We need another criterion. For instance, we choose to minimize the actual size of the buffer used for the communication. To get this buffer as small as possible (size=1), we have to schedule control before the second execution of read data. Were we to schedule according to an EDF policy we would get another schedule, see Fig. 5.

For a delayed communication, we just have partial orders and we need additionnal criteria. For synchronous threads, the use of an EDF policy is of no help. However, reducing the size of the communication buffer gives a schedule (top-most part of Fig. 6). For oversampling, both criteria are compatible and we get the second schedule on Fig. 6. For undersampling, we get two different schedules depending on whether we apply an EDF policy or we attempt to reduce the buffer size.

F. Generalization

We can generalize the constraints to get only two sets of constraints, one for the immediate communication and one for the delayed communication.

In this section we do not restrict to the three special cases addressed in the AADL standard. This generalization does not assume that the frequencies of the threads are natural numbers, it just assumes that they are rational numbers. It also assumes that in the notation of our binary words Y.x 0 = Y , for any binary word Y and any bit x.

Let

f d = n r /d r and f c = n c /d c , f d /f c = (n r * d c ) / (n c * d r ) with n r , n c , d r , d c ∈ N . Let r 1 = n r * d c and r 2 = n c * d r .
We choose q1 and q2 such as q1 = r 1 / gcd(r 1 , r 2 ) and q2 = r 2 / gcd(r 1 , r 2 ). Note, that we still have f d /f c = q1/q2 and that the constraints given by Eq. 15 and Eq. 14 are general. However, Eqs.6-8 are replaced by a single one, Eq. 19.

t1 filteredBy 1.0 q1-1 ≡ t2 filteredBy 1.0 q2-1 (19) Again, these constraints are purely logical. In the general case, these constraints are not strong enough to identify deterministically the significant writings and readings. If we take for instance, the case where q1 = 2 and q2 = 5 (Fig. 7). If we apply the AADL semantics, we can only say that, within an hyper-cycle (of period lcm(q1, q2)), the first execution of read data produces the sample for the first To get a deterministic behavior, we need to give more constraints. For instance we can project our clock to chronometric clocks and we model as an example the case where f d = 10Hz and f c = 25Hz. We proceed by using the clock c 100 defined in Eq. 16 and we add two new constraints given below.

t1 ≡ c 10 (20) t2 ≡ c 100 filteredBy (1.0 3 ) (21)
With such constraints, we get a total order (Fig. 8) and then there are two possible cases. The first case appears when duration(read data) + duration(control) ≥ 0.02s. Then, we exactly get the result presented in Fig. 8, where, within an hyper-cycle, the third execution of control uses the sample computed by the first execution of read data and the fourth execution of control uses the sample computed by the second execution of read data. In the second case, if duration(read data)+ duration(control) < 0.02s, the third execution of control should use the sample computed by the second execution of read data. However, note that such systems that very much depend on the exact duration of tasks are not very robust. If we now take a look at the situation with a delayed communication, there are several possible interpretations of a generalized AADL semantics. The simplest interpretation is that the data is made available (written in the object node) at the first dispatch (of the sending thread) following the execution of the behavior that has produced it (read data). And the data is read at the first dispatch of the receiving thread following the writing (see Fig. 9).

Fig. 9. General case with delayed communications (first interpretation).

A second interpretation could be that the data is read at the first dispatch of the receiving thread following the actual production of the data (not waiting for the following dispatch of the sending thread). This interpretation leads to make the second significant reading synchronous the third instant of control (for each hypercycle) instead of the fourth as in Figure 9. These cases are studied in detail in [START_REF] André | Modeling time(s)[END_REF]. Note these two interpretations can all be valid and deterministic. It is just a matter of making explicit the semantics. The first interpretation is very simple to implement and the second one requires to be able to control very tighly the communication times.

A UML object node has two interesting attributes: it has an upper bound, possibly unlimited, and it can order events, by default according to a FIFO policy. Thus, there is no reason to assume that the threads are in phase, the sending thread writes (and possibly overwrites) tokens in the object node, while the receiving thread reads them when required. Our definition of the significant writings and readings helps defining when the token is the samethe content must be ovewritten-and when the token is different, which implies that a new token must be created. Actually, the occurrence of wr should create a new token.

IV. Conclusion

We have briefly introduced the Time model of MARTE and we have illustrated its use on an example taken from AADL. We think that our clock constraint language could be used to make formal the semantics of UML-like graphical representations that is often partially implicit. In this language, we borrowed some notations on binary words from the N-synchronous approach but in our case we do not limit ourself to synchronous relations. We have implemented a constraint parser that has been made available with the XMI of the Time subprofile on the OMG website. This parser can be used to parse constraints extracted from UML models. Some analytic tools should reduce the constraints or compute new ones and put them back in the models. For now, all these formal computations are manual but we intend to transform our constraints into languages amenable to clock computations (time automata or synchronous languages like Signal or Esterel). Ultimately, our constraint language could be used to drive a UML simulator, in a constructive way, according to the model time semantics rather than an untimed event-driven semantics.

Fig. 1 .

 1 Fig. 1. AADL inter-thread data communication.

Fig. 2 .

 2 Fig. 2. Application/Execution platform in MARTE.

Fig. 3 .

 3 Fig. 3. Immediate communications.

Fig. 4 .

 4 Fig. 4. Delayed communications.

Fig. 5 .

 5 Fig. 5. Schedules with immediate communications.

Fig. 6 .

 6 Fig. 6. Schedules with delayed communications.

Fig. 7 .

 7 Fig. 7. General case with immediate communications and purely logical clocks.

Fig. 8 .

 8 Fig. 8. General case with immediate communications and chronometric clocks.

  control, but we cannot know what sample is used by other executions of control. In particular, there is no relation between t1[2 * n + 1] and t2[5 * n + 2].

	wr (sample)
	t1[2*n]		t1[2*n+1]
	read _data
	control
	t2[5*n]	t2[5*n+1]	t2[5*n+2]	t2[5*n+3]	t2[5*n+4]
	rd (sample)
		general (q1=2, q2=5), immediate