Dr François Wasels
email: francois.wasels@ifpen.fr

Jennifer Jean-Marie

Florent Collas

Ana M López-Contreras

Nicolas Lopes Ferreira

A two-plasmid inducible CRISPR/Cas9 genome editing tool for Clostridium acetobutylicum

Keywords: Clostridium acetobutylicum, CRISPR/Cas9, genome engineering, metabolic engineering aTc, anhydrotetracycline, CRISPR, Clustered regularly interspaced short palindromic repeats, Cas, CRISPR-associated proteins, Cas9n, Cas9 nickase, DSB, Double-strand break, gDNA, genomic DNA, gRNA, guide RNA, HR, Homologous recombination, NHEJ, Non-homologous end joining, SOE, splicing

CRISPR/Cas-based genetic engineering has revolutionised molecular biology in both eukaryotes and prokaryotes. Several tools dedicated to the genomic transformation of the Clostridium genus of Gram-positive bacteria have been described in the literature; however, the integration of large DNA fragments still remains relatively limited. In this study, a CRISPR/Cas9 genome editing tool using a two-plasmid strategy was developed for the solventogenic strain Clostridium acetobutylicum ATCC 824. Codonoptimised cas9 from Streptococcus pyogenes was placed under the control of an anhydrotetracycline-inducible promoter on one plasmid, while the gRNA expression cassettes and editing templates were located on a second plasmid. Through the sequential introduction of these vectors into the cell, we achieved highly accurate genome modifications, including nucleotide substitution, gene deletion and cassette insertion up to 3.6 kb. To demonstrate its potential, this genome editing tool was used to generate a marker-free mutant of ATCC 824 that produced an isopropanol-butanolethanol mixture. Whole-genome sequencing confirmed that no off-target modifications were present in the mutants. Such a tool is a prerequisite for efficient metabolic engineering in this solventogenic strain and provides an alternative editing strategy that might be applicable to other Clostridium strains.

Introduction

Clostridium acetobutylicum is a Gram-positive, spore-forming, anaerobic bacterium that utilises a wide range of different carbon sources (including C6 and C5 sugars and glycerol) to produce a mixture of acetone-butanol-ethanol and other compounds of interest. In recent years, several metabolic engineering tools have been developed to improve or modify the industrial capacities of this bacterium, mainly based on group IIintron retargeting or homologous recombination (HR) techniques. Group II-intron retargeting techniques such as Targetron [START_REF] Shao | Targeted gene disruption by use of a group II intron (targetron) vector in Clostridium acetobutylicum[END_REF] or ClosTron [START_REF] Heap | The ClosTron: a universal gene knock-out system for the genus Clostridium[END_REF][START_REF] Heap | The ClosTron: mutagenesis in Clostridium refined and streamlined[END_REF] are rapid but only allow insertional mutagenesis, which may result in undesired polar effects. In contrast, HR-based techniques allow a more precise modification of the genome but are time consuming and not always efficient [START_REF] Heap | Integration of DNA into bacterial chromosomes from plasmids without a counter-selection marker[END_REF].

More recently, genome editing strategies based on CRISPR (clustered regularly interspaced short palindromic repeats)/Cas (CRISPR-associated proteins) have been developed, enabling genome editing through the creation of double-strand breaks (DSBs) in the DNA [START_REF] Jinek | A programmable dual-RNA-guided DNA endonuclease in adaptive bacterial immunity[END_REF][START_REF] Cong | Multiplex genome engineering using CRISPR/Cas systems[END_REF]. Several groups have worked on the adaptation of this genome editing tool to the Clostridium genus [START_REF] Wang | Markerless chromosomal gene deletion in Clostridium beijerinckii using CRISPR/Cas9 system[END_REF][START_REF] Xu | Efficient genome editing in Clostridium cellulolyticum via CRISPR-Cas9 nickase[END_REF][START_REF] Huang | CRISPR/Cas9-based efficient genome editing in Clostridium ljungdahlii, an autotrophic gas-fermenting bacterium[END_REF][START_REF] Li | CRISPR-based genome editing and expression control systems in Clostridium acetobutylicum and Clostridium beijerinckii[END_REF][START_REF] Pyne | Harnessing heterologous and endogenous CRISPR-Cas machineries for efficient markerless genome editing in Clostridium[END_REF][START_REF] Wang | Bacterial genome editing with CRISPR-Cas9: deletion, integration, single nucleotide modification, and desirable "clean" mutant selection in Clostridium beijerinckii as an example[END_REF]; however, with the exception of [START_REF] Huang | CRISPR/Cas9-based efficient genome editing in Clostridium ljungdahlii, an autotrophic gas-fermenting bacterium[END_REF], who adapted CRISPR/Cas9 to Clostridium ljungdahlii, all groups reported difficulties when generating mutants that constitutively expressed the heterologous native Cas9 nuclease from Streptococcus pyogenes. These challenges may arise from the low transformation and HR frequencies observed when manipulating Clostridium, or from the supposed absence of non-homologous end joining (NHEJ) mechanisms in these organisms [START_REF] Xu | Efficient genome editing in Clostridium cellulolyticum via CRISPR-Cas9 nickase[END_REF]. Several strategies were successfully adopted to circumvent this problem.

The Cas9 nickase (Cas9n) catalyses a single-strand nick in the DNA [START_REF] Jinek | A programmable dual-RNA-guided DNA endonuclease in adaptive bacterial immunity[END_REF], protecting organisms from the potential detrimental effects of DSBs while inducing HR events [START_REF] Metzger | Single-strand nicks induce homologous recombination with less toxicity than double-strand breaks using an AAV vector template[END_REF]. The use of Cas9n allowed the generation of one-step deletions in the genome of several Clostridium species, including C. acetobutylicum ATCC 824 [START_REF] Xu | Efficient genome editing in Clostridium cellulolyticum via CRISPR-Cas9 nickase[END_REF][START_REF] Li | CRISPR-based genome editing and expression control systems in Clostridium acetobutylicum and Clostridium beijerinckii[END_REF]. Cas9n is a less powerful selection tool than Cas9 however, and sometimes the isolation of correctly edited cells requires serial transfers in fresh medium [START_REF] Xu | Efficient genome editing in Clostridium cellulolyticum via CRISPR-Cas9 nickase[END_REF]. Fragments of up to 1.72 kb have been inserted using this technique, but the integration of larger fragments remains unsuccessful [START_REF] Xu | Efficient genome editing in Clostridium cellulolyticum via CRISPR-Cas9 nickase[END_REF]. Until now, only short deletions of 20 bp were reported in C. acetobutylicum ATCC 824, with editing efficiencies ranging from 6.7% to 100% depending on the target and on the number of colonies analysed [START_REF] Li | CRISPR-based genome editing and expression control systems in Clostridium acetobutylicum and Clostridium beijerinckii[END_REF].

Another genome editing strategy was to exploit the endogenous CRISPR/Cas machinery found in some Clostridium strains [START_REF] Pyne | Harnessing heterologous and endogenous CRISPR-Cas machineries for efficient markerless genome editing in Clostridium[END_REF]. Observing that heterologous expression of cas9 was toxic in Clostridium pasteurianum ATCC 6013 even in the absence of associated guide RNA (gRNA), Pyne et al. exploited acetobutylicum ATCC 824. Furthermore, only deletions have been reported using this method; no other modifications, such as nucleotide substitutions or insertions, were tested.

enabling its expression to be activated in a larger bacterial population to enhance the selection of low-frequency HR events [START_REF] Wang | Bacterial genome editing with CRISPR-Cas9: deletion, integration, single nucleotide modification, and desirable "clean" mutant selection in Clostridium beijerinckii as an example[END_REF]. The researchers generated a 1.5-kb deletion, a 1.6-kb gene insertion and single-nucleotide modifications within the genome of C. beijerinckii [START_REF] Wang | Bacterial genome editing with CRISPR-Cas9: deletion, integration, single nucleotide modification, and desirable "clean" mutant selection in Clostridium beijerinckii as an example[END_REF]. A disadvantage of this strategy is that the template length is limited by the cargo capacity of the plasmid, which already harbours the 4.1-kb cas9 gene.

Here, we developed a two-plasmid inducible CRISPR/Cas9 strategy for C. acetobutylicum ATCC 824. This strategy enabled several chromosomal modifications, including the integration of a larger fragment than previously reported. Furthermore, it was also successfully applied to remove the 192-kbp pSOL megaplasmid.

Materials and methods

Bacterial strains, plasmids and culture conditions

Relevant characteristics of the bacterial strains and plasmids used in this study are listed in Table 1. C. acetobutylicum was grown anaerobically at 35°C in liquid 2YTG medium (16 g L -1 Bacto tryptone, 10 g L -1 yeast extract, 4 g L -1 NaCl and 5 g L -1 glucose) or solid 2YTG with 1.5% agar supplemented with 20 μg mL -1 erythromycin and/or 20 μg mL -1 thiamphenicol if necessary. Solid media was supplemented with 50 μg mL -1 5-fluorouracil (5-FU) where specified. Escherichia coli was grown aerobically at 37°C and 200 rpm in liquid LB medium or solid LB with 1.5% agar supplemented with erythromycin (500 μg mL -1 for solid media and 100 μg mL -1 for liquid media), chloramphenicol (25 μg mL -1 for solid media and 12.5 μg mL -1 for liquid media), or tetracycline (20 μg mL -1 ) if necessary.

DNA manipulation, plasmid construction and transformation

All enzymes for DNA modification as well as a Gibson Assembly kit were purchased from New England Biolabs (NEB). Q5 High-Fidelity Polymerase (NEB) was used for all PCR amplifications, except for colony PCRs, which were performed using DreamTaq DNA polymerase (Thermo Fisher Scientific). Genomic DNA (gDNA) was extracted from C. acetobutylicum using the GenElute Bacterial Genomic DNA Kit (Sigma-Aldrich).

Plasmids and PCR product purification kits were purchased from Qiagen. All primers used in this study are listed in Supplementary Table S1.

The pFW01 plasmid was constructed by a StuI/XhoI ligation of the amplicon obtained using a splicing by overhang extension (SOE) PCR [START_REF] Higuchi | A general method of in vitro preparation and specific mutagenesis of DNA fragments: study of protein and DNA interactions[END_REF] Three gRNA expression cassettes, composed of the miniPthl promoter and a 20-nt guiding sequence targeting either upp, adhE1 or thl fused with the chimeric gRNA sequence [START_REF] Jinek | A programmable dual-RNA-guided DNA endonuclease in adaptive bacterial immunity[END_REF], were cloned into the pEX-A2 vector (Eurofins Genomics), amplified with primers P07 and P08, and cloned into the XhoI/SalI-doubledigested pEC750C, yielding pGRNA-upp, pGRNA-adhE1 and pGRNA-thl, respectively.

The pGRNA-upp oc plasmid was constructed by cloning the 1306-bp SOE PCR product, obtained using primer pairs P09/P10 and P11/P12 on ATCC 824 gDNA, into the EcoRI/SalI-double-digested pGRNA-upp. The pGRNA-Δ 43-348 upp plasmid was constructed by cloning the 1-kb SOE PCR product, obtained using primer pairs P09/P13 and P11/P14 on ATCC 824 gDNA, into the EcoRI/SalI-double-digested pGRNA-upp. The Δupp::ipa8 editing template was constructed using a Gibson assembly in the BamHI/EcoRI-double-digested pUC19, inserting the 1-kb upp flanking regions amplified with primer pairs P15/P16 and P17/P18 from ATCC 824 gDNA and the PCR product amplified with primers P19/P20 from plasmid pFC008. The resulting template and pGRNA-upp were digested with EcoRI and BamHI and ligated to obtain pGRNA-Δupp::ipa8.

To construct the thl-adh editing template, the adh gene was amplified from pFC008 (Collas et al., 2014) with primers P21 and P22, then assembled to the regions flanking the gRNA target site in the ATCC 824 genome using a Gibson assembly in pUC19. A 651-bp fragment corresponding to the end of thl was optimised to alter the target site (Eurofins Genomics, Supplementary Text) and amplified with primers P23 and P24.

The 600 bp located downstream of adh was amplified from gDNA of ATCC 824 using primers P25 and P26. The resulting template and pGRNA-thl were digested with SalI and EcoRI, then ligated to obtain pGRNA-thl-adh.

A diagram summarizing plasmid construction is shown in Fig. S1 andS2. The lengths of all homology arms used for the construction of editing templates are reported in the Supplementary Table S2.

Plasmids were transformed into chemically competent NEB 10-beta competent E. coli cells containing pAN2 [START_REF] Heap | The ClosTron: a universal gene knock-out system for the genus Clostridium[END_REF] for DNA methylation. The vectors were then isolated and electroporated into C. acetobutylicum ATCC 824 as previously described [START_REF] Mermelstein | In vivo methylation in Escherichia coli by the Bacillus subtilis phage Φ3T I methyltransferase to protect plasmids from restriction upon transformation of Clostridium acetobutylicum ATCC 824[END_REF].

Isolation of mutants

Independent transformants containing their respective plasmids were resuspended in liquid 2YTG, and serial dilutions were spotted onto 2YTG solid media containing erythromycin and thiamphenicol, supplemented with anhydrotetracycline (aTc) at concentrations ranging from 0 to 500 ng mL -1 . Isolated colonies were selected for subsequent analyses.

Whole-genome sequencing

Genomic DNA was sequenced on an Illumina MiSeq sequencer with a 2 × 250 pairedend sequencing kit. Reads were mapped against the corrected genome and pSOL sequences of C. acetobutylicum ATCC 824 [START_REF] Nölling | Genome sequence and comparative analysis of the solvent-producing bacterium Clostridium acetobutylicum[END_REF][START_REF] Ehsaan | Mutant generation by allelic exchange and genome resequencing of the biobutanol organism Clostridium acetobutylicum ATCC 824[END_REF] using Geneious 9.1.3 [START_REF] Kearse | Geneious Basic: an integrated and extendable desktop software platform for the organization and analysis of sequence data[END_REF].

Fermentation assays

Fermentation assays were performed in modified Gapes medium [START_REF] Gapes | Long-term continuous cultivation of Clostridium beijerinckii in a two-stage chemostat with on-line solvent removal[END_REF] containing 2.5 g L -1 yeast extract, 1 g L -1 KH 2 PO 4 , 0.6 g L -1 K 2 HPO 4 , 1 g L -1 MgSO 4 7H 2 O, 6.6 mg L -1 FeSO 4 7H 2 0, 0.1 g L -1 4-aminobenzoic acid, 2.9 g L -1 CH 3 COONH 4 and 60 g L -1 glucose,. The initial pH of the medium was around pH 6.2. Fresh colonies were used to inoculate 10 mL Gapes media. After 24 h of growth in an anaerobic chamber at 35°C without agitation, 3 mL of these precultures were inoculated into a 100-mL flask containing 30 mL Gapes liquid medium. The flasks were sealed and incubated at 3435°C with agitation at 150 rpm for 72 h. The concentrations of the solvents produced were determined by gas chromatography. The fermentation samples were centrifuged at 15,000 g for 5 min and the supernatant was diluted with an internal standard (0.5 g L -1 propanol) to enable quantification. The solvents were separated on a PoraBOND-Q column (25 m length, 0.32 mm internal diameter, 0.5 µm film thickness; Agilent Technologies) equipped with a flame ionisation detector. Helium was used as carrier gas, at a flow rate of 1.6 mL min -1 .

Results

Previous work performed using Clostridium bacteria showed that the use of a plasmid containing cas9 under the control of a constitutive promoter dramatically reduced the likelihood of obtaining transformants. In the present study, two cas9-expression plasmids, pCas9 con and pCas9 ind , were constructed using the shuttle vector pFW01, in which cas9 was placed under the control of the constitutive miniPthl promoter [START_REF] Dong | Development of an anhydrotetracycline-inducible gene expression system for solvent-producing Clostridium acetobutylicum: A useful tool for strain engineering[END_REF] or the inducible Pcm-tetO2/1 promoter [START_REF] Dong | Development of an anhydrotetracycline-inducible gene expression system for solvent-producing Clostridium acetobutylicum: A useful tool for strain engineering[END_REF], respectively.

To evaluate the robustness of this newly developed CRISPR/Cas9 tool (patent: FR15/59846; Fig. S1S3), the upp gene (ca_c2879, coding for a phosphoribosyl transferase) was targeted. The deletion of this gene enables C. acetobutylicum ATCC 824 to grow on solid media containing 5-FU [START_REF] Croux | Construction of a restriction-less, marker-less mutant useful for functional genomic and metabolic engineering of the biofuel producer Clostridium acetobutylicum[END_REF], making its inactivation easily detectable. A gRNA expression cassette consisting of a 20-nt sequence targeting upp fused with the chimeric gRNA sequence [START_REF] Mali | RNA-guided human genome engineering via Cas9[END_REF] under the control of the miniPthl promoter was cloned into the pEC750C shuttle vector. Three different templates were designed to repair the resulting DSB and concomitantly inactivate upp (Fig. 1). The editing performed using the upp oc template caused two nucleotide substitutions within the 20-bp target sequence recognised by the gRNA, which resulted in a silent mutation and a premature stop codon, TAA (ochre mutation), leading to the synthesis of a truncated 66-aa Upp protein. Editing using the Δ 43-348 upp template caused a 306-bp internal deletion within the 630-bp coding sequence of upp.

The editing performed using the Δupp::ipa8 template caused the replacement of upp by the operonic structure ipa8 from plasmid pFC008. This operon contains genes from C. acetobutylicum ATCC 824 involved in the assimilation of acids (ctfA, ctfB) and the production of acetone (adc), as well as the adh gene from C. beijerinckii DSM 6423 encoding a secondary alcohol dehydrogenase able to convert acetone into isopropanol. Similar genetic operons have previously been overexpressed in C. acetobutylicum ATCC 824, allowing the strain to efficiently produce an isopropanolbutanol-ethanol mixture [START_REF] Collas | Simultaneous production of isopropanol, butanol, ethanol and 2, 3-butanediol by Clostridium acetobutylicum ATCC 824 engineered strains[END_REF][START_REF] Lee | Metabolic engineering of Clostridium acetobutylicum ATCC 824 for isopropanol-butanol-ethanol fermentation[END_REF]. [START_REF] Nölling | Genome sequence and comparative analysis of the solvent-producing bacterium Clostridium acetobutylicum[END_REF][START_REF] Ehsaan | Mutant generation by allelic exchange and genome resequencing of the biobutanol organism Clostridium acetobutylicum ATCC 824[END_REF]. The asterisk indicates a premature stop codon, while the black triangles indicate primer binding sites. T, target site of CRISPR/Cas9; Pthl, ca_c2873 promoter; Tadc, ca_p0165 transcription terminator.

Sequential transformation experiments were performed to introduce the cas9expression plasmids (pFW01-derivatives) followed by the gRNA-expression plasmids (pEC750C-derivatives) into C. acetobutylicum ATCC 824. Cells containing the empty pFW01 were successfully transformed with all of the pEC750C derivatives. As anticipated, no transformants were obtained that contained the pCas9 con in combination with any pEC750C derivative harbouring the gRNA expression cassette, whether or not the editing template was included. This result suggests that Cas9 is functional and that the low HR frequency does not allow edited cells to be obtained when constitutively expressing the nuclease gene. Cells containing pCas9 ind were successfully transformed with all pEC750C derivatives at frequencies similar to those of cells containing pFW01, indicating that expression of cas9 is correctly repressed in the absence of the inducer, aTc. Moreover, cells containing pCas9 ind transformed with pEC750C derivatives harbouring the gRNA expression cassette did not survive on plates containing aTc, highlighting the stringent control of the inducing system. The results of the transformation experiments are summarised in Supplementary Table S3.

Transformants containing pCas9 ind and pEC750C derivatives obtained on plates without the inducer were further investigated, and induction of cas9 expression was performed by spot-plating the cells on 2YTG solid media supplemented with erythromycin, thiamphenicol and increasing concentrations of aTc (Fig. 2). Overall, a toxic effect was observed for the inducer, with aTc reducing the viability of cells, including in the transformants containing the empty pEC750C; no growth was observed for transformants containing pCas9 ind and pGRNA-upp on plates supplemented with the inducer. In contrast, colonies containing pCas9 ind and pGRNA-upp oc were isolated on plates supplemented with aTc (Fig. 2). Colonies were also obtained when transformants containing pCas9 ind and either pGRNA-Δ 43-348 upp or pGRNA-Δupp::ipa8 were grown on aTc-supplemented media (data not shown). Notably, aTc-resistant pCas9 ind colonies containing pGRNA-Δupp::ipa8 were obtained at lower frequencies (10 -4 colonies/total colonies) than those containing either pGRNA-upp oc or pGRNA-Δ 43- 348 upp (10 -2 -10 -3 colonies/total colonies; Fig. 2). supplemented with 500 ng mL -1 aTc, the inducer of cas9 expression (right plate). ND, not diluted; Em, erythromycin; Tm, thiamphenicol; aTc, anhydrotetracycline. Isolated colonies were selected from aTc-supplemented plates and streaked onto 2YTG solid media, either with or without 5-FU. All colonies containing pCas9 ind and either pGRNA-upp oc (10 colonies tested), pGRNA-Δ 43-348 upp (10 colonies tested) or pGRNA-Δupp::ipa8 (4 colonies tested) were able to grow on solid media supplemented with 5-FU, while colonies containing pCas9 ind and pEC750C were not (data not shown).

In parallel, the gDNA of four colonies for each transformation was extracted from cells that were not exposed to 5-FU. The upp locus was analysed by PCR using primers P27 and P28, which yield a 2720-bp PCR product in the wild-type strain and that do not hybridize on any of the editing templates used. Desired mutations in the upp gene were confirmed by sequencing the PCR product in all four modified strains containing pGRNA-upp oc (Fig. 3A), and the expected 306-bp deletion was detected in the four colonies transformed with pGRNA-Δ 43-348 upp (Fig. 3B). Similarly, the replacement of upp by the ipa8 operon was confirmed in the four colonies containing pGRNA-Δupp::ipa8 by the amplification of a 5705-bp PCR product (Fig. 3C).

Figure 3. Editing of the Clostridium acetobutylicum ATCC 824 genome. (A)

Sequencing of the upp gene in cells edited with the upp oc template. The genome sequence is numbered according to the revised version of the genome sequence of ATCC 824 [START_REF] Nölling | Genome sequence and comparative analysis of the solvent-producing bacterium Clostridium acetobutylicum[END_REF][START_REF] Ehsaan | Mutant generation by allelic exchange and genome resequencing of the biobutanol organism Clostridium acetobutylicum ATCC 824[END_REF]. The corresponding translation is To determine whether the gRNA-expression plasmid could be efficiently removed to permit the introduction of another pEC750C-derived plasmid targeting other genes, two colonies of each type were streaked on 2YTG supplemented with erythromycin.

Erythromycin-resistant and thiamphenicol-susceptible colonies were easily isolated (at least 50% of the colonies tested after two rounds of growth on these plates), which could be used for further rounds of modification through the introduction of new To illustrate the versatility of the tool, two other modifications were performed in the genome of C. acetobutylicum ATCC 824. Firstly, a gRNA expression cassette was designed to target the end of the thl gene (ca_c2873). An editing template was constructed that allows both the modification of the target sequence and the insertion of the adh gene from C. beijerinckii DSM 6423. The gene was inserted between the end of the thl coding sequence and its transcriptional terminator, so that both genes are present in an operon structure under the control of the thl promoter. Plasmids pGRNA-thl and pGRNA-thl-adh were introduced into cells containing pCas9 ind . The cas9 induction was then performed as described above. All three colonies obtained from the aTc-supplemented plates were found to be correctly edited, as shown by a PCR performed on their gDNA using primers P29 and P30, which yields a 1406-bp product in the WT strain and a 2477-bp product in a correctly edited cell (Fig. 3D).

Secondly, a gRNA expression cassette targeting the adhE1 gene located on the pSOL megaplasmid was designed and cloned into pEC750C to yield pGRNA-adhE1. The viability of cells containing pCas9 ind and pGRNA-adhE1 was not reduced by the induction of cas9 expression on aTc-supplemented plates (data not shown). The loss of the megaplasmid in edited colonies was confirmed by the absence of amylase activity on a plate supplemented with starch and coloured using an iodine solution (Fig. 3E), as described previously [START_REF] Sabathé | a reporter gene to study strain degeneration in Clostridium acetobutylicum ATCC 824[END_REF]. Moreover, PCR analyses of three colonies confirmed that they no longer contained the megaplasmid (data not shown).

Similarly, the introduction of pGRNA-adhE1 in ATCC 824 containing pCas9 con yielded transformants that did not contain the pSOL megaplasmid (data not shown).

Discussion

The use of CRISPR/Cas-based genome editing tools is revolutionising genetics, allowing efficient genome editing in a broad range of organisms including bacteria of the Clostridium genus, which are known to be challenging to engineer. Several groups have reported the adaptation of this tool using strategies compatible with the low transformation efficiencies and low HR frequencies that are inherent to Clostridium bacteria [START_REF] Wang | Markerless chromosomal gene deletion in Clostridium beijerinckii using CRISPR/Cas9 system[END_REF][START_REF] Xu | Efficient genome editing in Clostridium cellulolyticum via CRISPR-Cas9 nickase[END_REF][START_REF] Huang | CRISPR/Cas9-based efficient genome editing in Clostridium ljungdahlii, an autotrophic gas-fermenting bacterium[END_REF][START_REF] Li | CRISPR-based genome editing and expression control systems in Clostridium acetobutylicum and Clostridium beijerinckii[END_REF][START_REF] Pyne | Harnessing heterologous and endogenous CRISPR-Cas machineries for efficient markerless genome editing in Clostridium[END_REF][START_REF] Wang | Bacterial genome editing with CRISPR-Cas9: deletion, integration, single nucleotide modification, and desirable "clean" mutant selection in Clostridium beijerinckii as an example[END_REF]. Most of these strategies are based on the use of a single plasmid that harbours all the elements needed, i.e. the 4.1-kb cas9 gene, the gRNAexpression cassette and the editing template, in addition to the replication origins for E. coli and Clostridium and antibiotic resistance gene(s). Assembling all of these elements yields relatively large plasmids that are difficult to introduce into bacterial cells, which is particularly challenging for Clostridium strains because of their low transformation efficiency. For this reason, and because HR frequencies are also low in Clostridium strains, a constitutive CRISPR/Cas9 system is not well suited to Clostridium genomic editing.

In this study, a two-plasmid inducible CRISPR/Cas9 genome editing tool was successfully developed. To our knowledge, the concomitant use of two plasmids has not been reported previously in Clostridium species, probably because of the lack of compatible replication origins and selection markers available. Recently, however, the increasing number of sequenced Clostridium genomes has enabled the identification of new extra-chromosomal elements, as well as compatible replicons for most of the Clostridium strains currently being studied [START_REF] Heap | A modular system for Clostridium shuttle plasmids[END_REF][START_REF] Poehlein | Microbial solvent formation revisited by comparative genome analysis[END_REF].

Since C. acetobutylicum ATCC 824 does not possess any endogenous CRISPR/Cas machinery, Cas9 from S. pyogenes was utilised. A codon-adapted cas9 gene was synthesised in order to maximise the selection of correctly edited cells. As a consequence, and as already observed by other authors [START_REF] Xu | Efficient genome editing in Clostridium cellulolyticum via CRISPR-Cas9 nickase[END_REF][START_REF] Li | CRISPR-based genome editing and expression control systems in Clostridium acetobutylicum and Clostridium beijerinckii[END_REF][START_REF] Pyne | Harnessing heterologous and endogenous CRISPR-Cas machineries for efficient markerless genome editing in Clostridium[END_REF][START_REF] Wang | Bacterial genome editing with CRISPR-Cas9: deletion, integration, single nucleotide modification, and desirable "clean" mutant selection in Clostridium beijerinckii as an example[END_REF], cas9 constitutive expression did not result in any transformants being obtained, because of the low transformation efficiency and low HR frequencies in C. acetobutylicum. This problem was solved by placing the gene under the control of the Pcm-tetO2/1 inducible promoter [START_REF] Dong | Development of an anhydrotetracycline-inducible gene expression system for solvent-producing Clostridium acetobutylicum: A useful tool for strain engineering[END_REF], and the induction of cas9 expression yielded edited cells in which HR events had occurred.

These initial results indicated that, as expected, editing frequencies are related to the type of modification attempted, with large insertions being obtained at lower frequencies than small deletions or nucleotide substitutions. As an example, colonies edited with either the upp oc or the Δ 43-348 upp templates (causing a 2-nt substitution and a 306-bp deletion, respectively) were obtained at higher frequencies than cells edited with the Δupp::ipa8 template, which causes a 3.6-kb insertion. The strategy was highly efficient, with correct modifications observed in 100% of cells tested, an improvement upon the editing frequencies using Cas9n previously reported in C. acetobutylicum ATCC 824 [START_REF] Li | CRISPR-based genome editing and expression control systems in Clostridium acetobutylicum and Clostridium beijerinckii[END_REF]. As previously reported [START_REF] Xu | Efficient genome editing in Clostridium cellulolyticum via CRISPR-Cas9 nickase[END_REF], no NHEJ mechanism was involved in repair of the DSBs, since all the analysed mutants contained the exact sequences of the editing templates used, rather than containing the errors prominent in NHEJ. Moreover, no off-target modification was detected and, among the six mutants sequenced, four contained only the desired modifications, while the two others contained supplementary mutations unrelated to the strategy used.

Overall, this method enables the rapid introduction of marker-free genomic modification of any type, from the substitution of a few nucleotides to large deletions or insertions.

Once cells containing pCas9 ind are transformed with the targeting plasmid harbouring the gRNA expression cassette, one round of growth on aTc-supplemented plates is sufficient to obtain correctly edited cells, illustrating the high efficiency of this strategy.

Moreover, in cases requiring multiple genetic modifications, an intermediate mutant harbouring only pCas9 ind can be easily obtained after a few rounds of growth on appropriate plates for the curation of the targeting plasmid, making it ready for a new round of modification (data not shown).

It is not possible to modify any non-essential genetic mobile element using this technique, as the Cas9 action results in the simple loss of the element. A CRISPR/Cas9 strategy is therefore not applicable for the modification of non-selectable extra-chromosomal elements, such as the non-essential pSOL from C. acetobutylicum ATCC 824 [START_REF] Cornillot | The genes for butanol and acetone formation in Clostridium acetobutylicum ATCC 824 reside on a large plasmid whose loss leads to degeneration of the strain[END_REF].

The absence of selection markers in the genome of the modified strains and the potential to perform sequential modifications suggest new possibilities for synthetic biology approaches in industrial biotechnology involving Clostridium solventogenic strains. As an initial example, the adh gene from C. beijerinckii DSM 6423 was inserted into the genome of ATCC 824, either alone or in combination with other genes involved in acid re-assimilation and acetone production, placed under the control of a strong constitutive promoter. To our knowledge, this is the first report of a C. acetobutylicum strain able to produce an isopropanol-butanol-ethanol mixture without any selection marker.

Future work will focus on the optimisation of this tool through the determination of the maximum fragment length that can be inserted or deleted, and of the minimal size required for the homology arms. One hint was provided by [START_REF] Xu | Efficient genome editing in Clostridium cellulolyticum via CRISPR-Cas9 nickase[END_REF], who reported a high editing efficiency using homology arms of at least 0.2 kb with their Cas9n system in C. cellulolyticum. Moreover, this two-plasmid inducible CRISPR/Cas9 genome editing tool will be employed in other strains of the Clostridium genus in the future, to demonstrate its varied possibilities.

  its native CRISPR/Cas6 machinery. Introducing only a synthetic CRISPR array and an editing template, they reduced the size of the plasmid used and quadrupled the efficiency of the transformation. Pyne et al. also generated a 750-bp deletion in the genome with a 100% editing efficiency in the transformants, using either heterologous Cas9 or endogenous Cas6. The transformation efficiency remained low however, and CRISPR/Cas systems are not naturally present in all strains of Clostridium, including C.

  of the ermB gene (primers P01 and P02) and the rep origin from pMTL500E (primers P03 and P04), with a PCR amplification of the repH origin from pMTL007S-E1 (primers P05 and P06). A cassette consisting of the miniPthl promoter and the thl terminator separated by the NcoI and SalI restriction sites was synthesised and sub-cloned into the pEX-A2 vector (Eurofins Genomics), amplified with primers P07 and P08 and cloned into XhoI/SmaI-double-digested pFW01. A codon-optimised cas9 gene from S. pyogenes flanked by NcoI and SalI was synthesised (Genscript, Supplementary Text) and cloned into a NcoI/SalI-double-digested vector, yielding pCas9 con . The sequence of the Pcm-tetO2/1 promoter was synthesised (Eurofins Genomics) and cloned into XhoI/NcoIdouble-digested pCas9 con . A cassette containing the tetR gene under the control of the miniPthl promoter was cloned into the pEX-A2 vector (Eurofins Genomics), amplified using primers P07 and P08, and cloned into the SmaI/SacI-double-digested intermediate plasmid, yielding pCas9 ind .

Figure 1 .

 1 Figure 1. Templates used to edit the upp locus. Genes are annotated according to the

Figure 2 .

 2 Figure 2. Selection of Clostridium acetobutylicum cells edited with the upp oc template on aTc-containing plates. Independent transformants containing pCas9 ind and either pEC750C, pGRNA-upp or pGRNA-upp oc were suspended in liquid 2YTG, serially diluted and spotted on plates containing the appropriate antibiotics only (left plate), or

  indicated above the nucleotide sequence. The asterisk indicates a stop codon, while modifications are indicated in bold. The same result was obtained for the four colonies tested. PAM, Protospacer adjacent motif. (B) PCR amplification of the upp locus in cells edited with the pGRNA-Δ 43-348 upp template. Amplification yields a 2720 bp product in the WT strain and a 2414 bp product in correctly edited cells. Lane M, 2-log DNA ladder (0.1 to 10 kb; New England Biolabs [NEB]); Lane P, amplification on pGRNA-Δ 43-348 upp. (C) PCR amplification of the upp locus in cells edited with the Δupp::ipa8 template. Amplification yields a 2720 bp product in the WT strain and a 5705 bp product in correctly edited cells. Lane M, 2-log DNA ladder (0.1 to 10 kb; NEB); Lane P, amplification on pGRNA-Δupp::ipa8. (D) PCR amplification performed with primers P29 and P30 of the thl locus in cells edited with the thl-adh template. Amplification yields a 1406 bp product in the WT strain and a 2477 bp product in correctly edited cells. Lane M, 2-log DNA ladder (0.1 to 10 kb; NEB); Lane P, amplification on pGRNAthl-adh. (E) Representative amylolytic activity of C. acetobutylicum ATCC 824 pCas9 ind transformed with pEC750C or pGRNA-adhE1 on a glucose + starch plate.

Figure 4 .

 4 Figure 4. Final solvent concentrations in flask fermentations of the Clostridium

Table 1 .

 1 Bacterial strains and plasmids used in this study

	Bacterial strain or plasmid	Relevant characteristics	a	Source or reference
	Strains
		C. acetobutylicum ATCC 824	Wild-type	ATCC
		E. coli NEB 10-beta				NEB
	Derivatives and plasmids
						Heap et al.,
		pAN2	Tet r , Φ3T I gene, p15A origin	2007; Mermelstein et
						al., 1993
		pMTL500E	Ap r , Em	r , ColE1 origin, pAMβ1 origin	Oultram et al., 1988
		pMTL007S-E1	Sp r , ColE1 origin, pCB102 origin, ermB RAM	Heap et al., 2010
		pEC750C	Cm	r , ColE1 origin, pIP404 origin	Collas, unpublished
		pFC008	pMTL500E derivative with adh ctfA ctfB (constitutive thl promoter) and adc (natural promoter) insertions	Collas et al., 2014
		pFW01	Em	r , ColE1 origin, pCB102 origin	This study
		pCas9 con	pFW01 derivative with cas9 (constitutive miniPthl promoter) insertion	This study
			pFW01 derivative with cas9 (inducible Pcm-
		pCas9 ind	tetO2/1 promoter) and tetR (miniPthl	This study
			promoter) insertions
		pGRNA-upp	pEC750C derivative with gRNA_upp cassette insertion	This study
		pGRNA-upp oc	pGRNA-upp derivative with upp oc template insertion	This study
		pGRNA-Δ 43-348 upp	pGRNA-upp derivative with Δ 43-348 upp template insertion	This study
		pGRNA-Δupp::ipa8	pGRNA-upp derivative with Δupp::ipa8 template insertion	This study
		pGRNA-adhE1	pEC750C derivative with gRNA_adhE1 cassette insertion	This study
		pGRNA-thl	pEC750C derivative with gRNA_thl cassette insertion	This study
		pGRNA-thl-adh	pGRNA-thl derivative with thl-adh template insertion	This study
	a Tet	r , tetracycline resistant; Sp	r , spectinomycin resistant; Cm	r , chloramphenicol resistant; Em	r ,
	erythromycin resistant.

Acknowledgements

This work has benefited from the High-Throughput Sequencing Platform facilities and expertise of the Institute for Integrative Biology of the Cell (I2BC), France.

Funding

Work at Wageningen Food and Biobased Research was supported by European

Union's Horizon 2020 Macrofuels project (contract number 654010).

targeting plasmids. An additional round of growth on 2YTG without any antibiotics was performed to curate pCas9 ind in 100% of the tested colonies.

To validate the efficiency and detect putative off-target events that could have been caused by the use of this tool, the genome of six independent mutants (two of each type) were sequenced. In all of them, the same modifications were detected when compared to the re-sequenced ATCC 824 wild-type strain [START_REF] Nölling | Genome sequence and comparative analysis of the solvent-producing bacterium Clostridium acetobutylicum[END_REF][START_REF] Ehsaan | Mutant generation by allelic exchange and genome resequencing of the biobutanol organism Clostridium acetobutylicum ATCC 824[END_REF]; six single nucleotide variations, one single nucleotide deletion and one four-nucleotide insertion. Of the six mutants analysed, four contained only the desired modifications to the upp gene, i.e. either the 306-bp internal deletion, two single nucleotide variations or the replacement of the whole gene by the ipa8 operon. The two remaining mutants contained undesired modifications elsewhere in their genome; however, these mutations appeared to be unrelated to the activity of CRISPR/Cas9, since none of them were associated with sequences that would have been targeted by the gRNA. All the modifications detected in the mutants are listed in Supplementary Table S4.

To investigate the fermentation profiles of the CRISPR/Cas9-modified strains, the solvent production of the two sequenced Δupp::ipa8 mutants and the two sequenced Δ 43-348 upp mutants were compared to the wild-type ATCC 824 strains, using glucose as a carbon source. After 72 h of fermentation, the wild-type strain and the Δ 43-348 upp mutants yielded 4.32 ± 0.03 and 3.62 ± 0.08 g L -1 acetone, respectively, and no isopropanol was detected in the medium (Fig. 4). The two Δupp::ipa8 mutants produced 4.45 ± 0.34 g L -1 of isopropanol and a residual 0.21 ± 0.08 g L -1 of acetone, confirming that the adh gene from the ipa8 operon was correctly expressed and functional.

Conflict of interest

The authors declare no financial or commercial conflict of interest.


Vashti Galpin
email: vashti.galpin@ed.ac.uk

Modelling ambulance deployment with CARMA

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Creating formal dynamic models of systems that can be simulated and subjected to other forms of quantitative analysis is one way in which formal methods can be used in the development and evaluation of these systems. Frequently, it is not possible to experiment with the system itself, because of the cost or disruption involved. Hence development of models that can be used for experimentation is important. This paper applies a language that has been developed to model collective adaptive systems (CAS) to an existing ambulance deployment scenario.

CAS feature frequently in modern information systems. Multiple components interact (and sometimes compete) to achieve various outcomes. The components can be individual pieces of software or different physical devices, and such systems are often characterised by local information and local action which therefore, requires a notion of space. Coordination and collaboration are features of these models because of the components communicate to achieve their aims. The language CARMA and its associated software tool the Eclipse CARMA Plug-in have been developed for the quantitative modelling of CAS allowing for an understanding of both functional and nonfunctional properties of models [START_REF] Bortolussi | CARMA: collective adaptive resource-sharing markovian agents[END_REF][START_REF] Ciancia | CAS-SCEL semantics and implementation[END_REF]. Important aspects of CARMA include attribute-based communication, in the sense that the possibility of a component taking part in an interaction depends on the current values in the store of the component, thus allowing for a rich representation of state. Both unicast and broadcast modes of communication are supported. Furthermore, CARMA allows the environment within which the model components interact to be defined separately from the components. The development of CARMA has been influenced by a number of previous process algebra including the Markovian process algebra PEPA [START_REF] Hillston | A compositional approach to performance modelling[END_REF], the location-focussed PALOMA [START_REF] Feng | PALOMA: A process algebra for located Markovian agents[END_REF] and SCEL [START_REF] De Nicola | A formal approach to autonomic systems programming: The SCEL language[END_REF] which uses attribute-based communication. Attribute-based communcation is explored further in the process calculus AbC [START_REF] Alrahman | A calculus for attribute-based communication[END_REF].

In this paper, the modelling and analysis of a particular system using CARMA is considered. Jagtenberg et al have proposed a new approach to ambulance deployment [START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF]. The general goal of such systems is to minimise the time it takes to respond to medical incidents by ensuring good base locations for ambulances together with a distribution of ambulances over bases that leads to fast response. Traditionally, deciding how to deploy ambulances across a region has been done statically, in the sense that once an ambulance has completed its current task, it returns to a predefined base, and moreover determining the best bases is done in advance of deployment. In the dynamic approach, depending on the locations of the other ambulances, an ambulance that is no longer busy can be requested to go to a specific location in a set of base locations to wait for its next task, thus allowing the system to adapt to the current circumstances. The ambulance system is modelled as a graph of locations with edges representing roads, annotated with information about how long it takes to traverse the edge, as shown in Figure 5. Locations may be cities, towns, road junctions or other points of interest. Each location has an incident probability, and some locations have ambulances bases or hospitals. There has been much research into different aspects of ambulance response time that use a graph to represent the road network. These have considered how many ambulances to use, the best locations for bases and how to distribute vehicles over bases [START_REF] Alanis | A Markov chain model for an EMS system with repositioning[END_REF][START_REF] Church | The maximal covering location problem[END_REF][START_REF] Daskin | A maximum expected covering location model: Formulation, properties and heuristic solution[END_REF][START_REF] Gendreau | A dynamic model and parallel tabu search heuristic for real-time ambulance relocation[END_REF][START_REF] Maxwell | Tuning approximate dynamic programming policies for ambulance redeployment via direct search[END_REF][START_REF] Toregas | The location of emergency service facilities[END_REF]. The specific system modelled here has been chosen because of its time-based performance evaluation aspects and straightforward heuristic function. The developed model could be modified to investigate other aspects of ambulance deployment.

This paper presents a CARMA model of such an ambulance system. As CARMA is a new modelling language, it is necessary to evaluate it by developing interesting and complex models, and the ambulance deployment system fulfils these requirements. First, the ambulance scenario is introduced after which details of CARMA are presented, followed by the ambulance model expressed in CARMA. Finally results of simulation of the model are presented and a discussion of further research relating to the model discussed.

An ambulance deployment scenario

This section describes the mathematical model that Jagtenberg et al [START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF] propose, together with their heuristic for best real-time redeployment of ambulances. This model considers a scenario where there is a fairly sparse network of roads between cities and towns (as shown in Figure 5), and hence is slightly more appropriate for a non-urban situation, where there are not many routes between each point of interest. An urban map can be transformed into a similar sparse network by focussing on major routes.

Let N = (V, E) be a graph where E ⊆ V ×V . Four functions are associated with this graph.

r : E → R >0 describes the time it takes to traverse an edge (when using sirens and lights -this figure increases for travel without lights and sirens). h : V → {0, 1} defines the presence of a hospital at a vertex.

b : V → {0, 1} defines whether a vertex is an ambulance base.

-d : V → [0, 1] with ∑ v∈V d(v) = 1,

defines the distribution of incidences over the vertices of the graph.

There is also a set of ambulances A labelled {1, . . . , n} and two functions l : A → V describing the current location of an ambulance and w : A → {0, 1} describing whether an ambulance is currently allocated to an incident. Furthermore, a function s : A → V which describes the home station of an ambulance in the static case. There are three rates that describe how long it takes for an ambulance to treat a patient at the scene, λ p , how long it takes for an ambulance to load up a patient at the scene for transportation to hospital, λ t and how long it takes to offload a patient at hospital, λ d . It is assumed that patients are either treated at the scene or uploaded to be taken to hospital but not both. Furthermore, there is a probability m that determines whether an incident is severe, requiring the patient to be transported to hospital, or minor, meaning that the patient only needs to be treated at the scene. The operation of the system is now described.

1. An incident occurs at a vertex based on the distribution defined by d and its level of severity is determined using the probability m. 2. An ambulance is identified to go to the incident location based on distance from the incident. 3. The ambulance uses the shortest route to get to the scene. Since distances are deterministic and unchanging, shortest routes can be determined in advance from the network, and hence are static in the model. 4. The ambulance treats the patient at the scene and then proceeds with item 7, or the ambulance uploads the patient to take them to hospital. 5. The ambulance uses the shortest route to the hospital using sirens and lights. 6. The ambulance drops the patient off at the hospital. 7. The ambulances uses the shortest route to go to a base but taking longer as it is not using sirens and lights. In the static case, this is the base defined by s. In the dynamic case, the base is determined by the heuristic.

Once an ambulance has been allocated to an incident, it must complete the journey to the incident, and to the hospital, if necessary, and cannot be diverted. However, once an ambulance has started to return to base, it can be immediately allocated to a new incident. An ambulance that is involved in items 2 to 6 is considered to be busy, otherwise it is idle. When it is idle, it is associated either with the base it has reached or the base to which it is travelling.

Evaluation of base heuristic

The reason to model such systems is to investigate the performance of different deployment approaches. The proportion of ambulances that do not reach the incident within a fixed time period (denoted T ) after being allocated to that incident, is often used [START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF] and will be used here.

In the case of static deployment where each ambulance has a fixed base, simulation can be used to assess the best distribution of ambulances, in the planning stages of a system. Different variants of the maximum expected covering location problem (MEX-CLP) [START_REF] Daskin | A maximum expected covering location model: Formulation, properties and heuristic solution[END_REF] have been used to tackle this task. The disadvantage of the static approach is that it ignores real-time information that can be used to provide better coverage [START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF].

Coverage describes the number of ambulances that can provide service at a specific location within the time limit. Increasing coverage means that there is a higher probability that an ambulance will be available if one is needed.

Dynamic deployment approaches can be divided into two main techniques. The first, based on lookup tables, requires dispatchers to steer the system to these optimal configurations. A better approach is based on real-time approximation. However, even using approximate dynamic programming and post-decision state is time-consuming and requires an expert to implement and choose base functions [START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF]. By contrast, the approach taken in [START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF] is moderately coarse-grained and needs little real-time information, and takes a marginal cover approach based on MEXCLP.

Consider a set of ambulances A with behaviour as described above. Also let B = {u ∈ V |b(u) = 1} be the set of vertices that are bases. It is assumed that there is a probability q which is the same for all ambulances and represents the fraction of time that the ambulance is busy. It can be determined by dividing the load of the system by the number of ambulances [START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF]. The expected coverage at vertex

v when v is in the range of k ambulances is E k (v) = d(v)(1 -q k )
and as shown in [START_REF] Daskin | A maximum expected covering location model: Formulation, properties and heuristic solution[END_REF], the marginal coverage is

E k (v) -E k-1 (v) = d(v)(1 -q)q k-1
. This figure can be used to determine to which base to send an ambulance once it has completed its task, by finding u ∈ B such that the increase in coverage is maximised, and hence the maximum coverage overall is obtained. Let ρ(v, w) be the time taken for the shortest route between vertices v and w, calculated from the values of individual hops given by the function r. Let n u represent the number of ambulances at u ∈ B, or moving towards u ∈ B after completing their allocated task, and let N = {n u | u ∈ B} represent the current number of idle ambulances for each possible base location. The function p captures the heuristic for determining ambulance base and is defined by1

p(N) = arg max w∈B ∑ v∈V d(v)(1 -q)q k(v,w,N)-1 • 1(ρ(w, v) ≤ T )
where

k(v, w, N) = ∑ u∈B n u • 1(ρ(u, v) ≤ T ) + 1(ρ(w, v) ≤ T ).
Here 1 is the indicator function. This function can also be simplified to

p(N) = arg max w∈B ∑ v∈V d(v)(1 -q)q c(v,N) • 1(ρ(w, v) ≤ T ) where c(v, N) = ∑ u∈B n u • 1(ρ(u, v) ≤ T )
For each possible base of the ambulance that has just completed its task, the increased coverage is calculated for every location in the graph whenever addition of the base would increase coverage at that location, and summed. The function c counts the number of ambulances that are already in the range of each base (reachable within the limit of T time units) as defined by the set N. If it is the case that both |A|, the number of idle ambulances, and |B|, the number of bases, are small compared to the number of vertices |V |, then the algorithm is linear in |V | [START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF].

It is important to note that some aspects of the model are generic such as the ambulance behaviour but others are specific to the system under consideration such as the graph of locations, the functions relating to these locations, and the heuristic function p. This distinction will be used when deciding how to build the CARMA model. The next section introduces CARMA, after which the CARMA model of the system is presented.

CARMA

CARMA is a powerful language, influenced by process algebra, for describing systems consisting of different interacting components which allows for an explicit definition of environment. Its semantics are time-inhomogeneous continuous-time Markov chains [START_REF] Ciancia | CAS-SCEL semantics and implementation[END_REF] thus permitting both simulation and other analysis techniques. It is embodied in software in the CARMA Eclipse Plug-in tool which implements the basic language and supports features such as function definition, enumerated types, and measures which enable quantitative behaviour of a model to be calculated and recorded.

A CARMA model consists of a number of different elements. At the highest level, there is a collective that consists of different components that interact, together with an environment that contains information about the global state, as well as information about how components interact. Thus SYS is the set of CARMA systems S defined by

S ::= N in E
where N is a collective and E is an environment. The set of collectives COL is defined by

N ::= C N N A collective N is either a component C or the parallel composition of two collectives (N N).
The syntax of components is

C ::= 0 (P, γ)
where 0 is the null component, P is a process that describes the behaviour of the component and γ is the store for the component. COMP is defined to be the set of components.

A store maps from attribute names to basic values where -ATTR is the set of attribute names a, a , a 1 ,. . . , b, b , b 1 ,. . . ; -VAL is the set of basic values v, v , v 1 ,. . . ; and -Γ is the set of stores γ, γ 1 , γ , . . ., are functions from ATTR to VAL.

PROC is the set of processes that define the behaviour of components and they are specified by

P, Q ::= nil | kill | act.P | P + Q | P | Q | [π]P | A (A = P) act ::= α [π] - → e σ | α [π] - → e σ | α [π]( - → x )σ | α [π]( - → x )σ e ::= a | my.a | x | v | now | • • • π ::= | ⊥ | e 1 e 2 | ¬π | π ∧ π | • • •
In CARMA processes can have different prefixes relating to four types of actions which are broadcast output

(α [π] - → e σ ), broadcast input (α [π]( - → x )σ ), output (α [π] - → e σ ),
and input (α A unicast communication involves two components where the sender and receiver attributes must satisfy any predicates in the prefixes, the expressions in the output prefix are assigned to the variables in the input prefix (and hence successful communication requires the two sequences are the same length), and updates are applied to both components to complete the interaction. Furthermore, there can be a probability describing whether the receiver does actually receive the communication. Unicast is blocking in that a sender cannot proceed until a receiver takes part in the interaction. By contrast, broadcast is not blocking and the sender can proceed regardless of whether there are many, one or no suitable receivers. Again, the sender and potential receivers must satisfy the predicates in the prefixes, and additionally there is a probability that the receiver although suitable to take part in the interaction, does not receive it. Expressions from the output prefix are passed to variables in the input prefix and updates are applied to all participants on completion of their roles, in the same manner as unicast. For both unicast and broadcast, rates of actions and probabilities of receiving are defined in the environment part of the model. Specific expressions of interest are now for the current simulation time and my.a which refers to the value of the attribute a in the current component.

[π]( - → x )σ ),
Apart from the four different prefix types, there is choice between two processes, the parallel composition of two processes, a guarded process which requires satisfaction of its predicate before it can perform an action and definition of constant processes. There are two distinct operators for termination. The operator nil represents the process that can perform no further actions and it can be placed in parallel with other processes. The operator kill, on the other hand, indicates termination of the whole component so that all processes in the component stop, and the component is transformed into 0, the null component which can do nothing and has no store.

CARMA collectives interact within an environment E . The environment describes the rules that regulate the system such as rates of interaction and probabilities that interaction may occur. It also contains global information. The environment has two elements: a global store γ g , that records the value of global attributes, and an evolution rule ρ. This is a function which, depending on the current time (using now), on the global store and on the current state of the collective returns a tuple of functions ε = µ p , µ r , µ u known as the evaluation context where ACT = ACTTYPE ∪ {α |α ∈ ACTTYPE} and µ p : Γ × Γ × ACT → [0, 1], µ p (γ s , γ r , α) determines is the probability that a component with store γ r can receive a message from a component with store γ s when α is executed; µ r : Γ × ACT → R ≥0 , µ r (γ, α) determines the execution rate of action α executed at a component with store γ; µ u : Γ × ACT → Σ × COL, µ u (γ, α) determines the updates on the environment (global store and collective) induced by the execution of action α at a component with store γ. The execution of an action can modify the values of global variables and also add new components to the collective.

In each of the rules, the notation sender.a is used to refer to the value of the attribute a in the store of the acting or sending component, and receiver.a refers to the value of the attribute in the store of the receiving component. Operational semantics of CARMA specifications are defined in three stages using the following transition relations. For reasons of space, the rules are not presented here, but can be found in [START_REF] Ciancia | CAS-SCEL semantics and implementation[END_REF]. All relations are defined in the FUTS style [START_REF] De Nicola | A uniform definition of stochastic process calculi[END_REF] and are described using a triple (N, , N ) where the first element is a component, or a collective, or a system. The second element is a transition label. The third element is a function associating each component, collective, or system with a non-negative number. A non-zero value represents the rate of the exponential distribution characterising the time needed for the execution of the action represented by . The zero value is associated with unreachable terms. FUTS style semantics are used because it makes explicit an underlying (time-inhomogeneous) Action Labelled Markov Chain, which can be simulated with standard algorithms [START_REF] Gillespie | A general method for numerically simulating the stochastic time evolution of coupled chemical reactions[END_REF].

Ambulance model

The CARMA model is presented in Figures 1,2, 3 and 4. Each component consists of the attributes that form its local store, its behaviour defined by processes and its initial state. Additionally, the attributes of the global store are defined in Figure 4 together with the evolution rule functions over actions (one function for the rates, one for the probabilities and one for the updates of global attributes and additions to the collective). There are four actions with non-negligible rates, and the remainder are zero or fast (since CARMA does not currently support instantaneous actions). Figure 4 also includes the initial collective definition as the last item.

Th symbols and ⊥ as used for true and false, respectively. A broadcast action of the form α [⊥] is an action that cannot be received (because no component can satisfy the predicate false) and hence is local to the component that executes it, although it may also update the global store or add components to the collective.

As mentioned previously, some aspects of the model are generic and some are specific to the network of roads and places. These two concerns have been separated in The CARMA Eclipse Plug-in supports function definitions, hence this separation is both possible and sensible, and also supports the design of a tool for ambulance modelling, as discussed in the further work section.

These functions comprise of one to provide the distributions over location and type of incidents respectively, IncidentLocation(), IncidentType(); information about routes in the network, RouteLength(., .), NextHop(., ., .) and MoveTime(., ., .); location of the closest hospital to an incident, HospitalLocation(.); location of the closest idle ambulances to an incident location, ClosestIdleLoc(., N); and the base to which an ambulance should go, GetBase(., ., N) which can be defined statically or dynamically. Note that both ClosestIdleLoc and GetBase take N, the set of the counts of idle ambulances at each base or on their way to each base as an argument. For the former, N is used to find the closest location to the incident where there are idle ambulances, so that a request can be sent to ambulances in that location. For the latter, the counts of idle ambulances are required to calculate p.

There are seven generic components in the model. The Incident Queue generates Incident Queue Items using the action incident which has the side-effect of adding a new

= [i < h]start move [⊥] {i ← i + 1,t ← now}.RC + [i = h ∧ (my.dest == ToSevere ∨ my.dest == ToMinor)] arrive [ ] anum .RS + [i = h ∧ my.dest == ToHosp]dropoff [ ] anum .kill + [i = h ∧ my.dest == ToBase]atbase [ ] anum .kill + RS def = [i = h ∧ my.dest == ToSevere]pickup [ ] anum .kill + [i = h ∧ my.dest == ToMinor]treat [ ] anum .kill RC def = end move[ ] anum, nexte,t, MoveTime(nexts, nexte, dest)
{nexts ← my.nexte, nexte ← NextHop(i, my.start, my.end)}.R KR = kill route[my.anum == an](an).kill Fig. 3. Ambulance and route components Incident Queue Item to the collective (as specified by the function µ u appearing in the environment in Figure 4). Each item has a unique number, and in turn generates an Incident Handler using the action new handler . The first action of the Incident Handler is to request an ambulance from another component Closest Idle Ambulance. This is a separate component for clarity of structure. On receiving a request for a specific location, it calls the function to find the location with idle ambulances that is closest to that location, and take note of the current time. It then tries to communicate (via unicast) with any ambulance in that location. If that succeeds, then it, the Incident Handler and the Incident Queue receive a confirm message from the ambulance that has responded. If there is no response, which is possible because there may be no idle ambulances, a timeout occurs. The timeout is defined by the rate for pause in the environment in Figure 4 where if insufficient time has passed the rate is zero (otherwise, it is λ fast ). If the timeout happens, it calls the function again and send out another request to the location that the function returns.

The Incident Queue interacts with each Incident Queue Item and its associated Incident Handler to ensure that at most one Incident Handler at a time is contacting the closest idle ambulance (because two incidents may have the same closest idle ambulance). The use of queue numbers ensures fairness in the sense that an Incident Handler cannot be starved of access to an Ambulance by later incidents and their associated Incident Handlers. A queue item cannot be released and hence cannot execute new handler , until the Incident Handler associated with the previous Incident Queue Item and its interaction with Closest Idle Ambulance has successfully concluded negotiations with the closest idle ambulance via communication on the confirm action.

Each Incident Handler has an assigned ambulance and interacts with the ambulance and generates Routes to move the ambulance to the location of the incident and then to the nearest hospital, if required. After this a Return Handler is created using tobase . The two handlers are separate components because an ambulance cannot be diverted once it has been assigned to an incident but once it is returning to a base position, it can be called to a new incident, so Return Handler has behaviour to allow it to remove itself from the collective if this happens, and it is no longer needed in the collective.

Once an Incident Handler and an Ambulance have been matched, the ambulance number is used in all communication between the Incident Handler, Ambulance and Route components to limit broadcast communication to these three components. The queue number could also have been used for these purposes but ambulance number is sufficient. Since broadcast is not blocking, the model must be constructed so that Incident Handler and Ambulance are in a state to receive the message from Route.

The Route component works through the route hops. It is initialised with the start and end of the route, and after obtaining the length of route from RouteLength, it works through each hop of the route3 using the function NextHop until the end of the route when the appropriate action occurs depending on the destination type. For pickup and treatment at the scene, an arrive action is required followed by a timecheck action for the global count of late and on-time ambulances to be updated, based on the time the timecheck action happens and the time the incident was generated. The Ambulance and Route components assume that travel times are deterministic rather than stochastic (although it is straightforward to modify the model to use stochastic durations). The Route component performs a local start move action and notes the time of the action. The ambulance component responds to an end move action once sufficient time has elapsed. Since Route components can also be generated by Return Handlers, they can remove themselves from the collective on receipt of a kill command from the associated Ambulance when it receives an incident request during going to a base location.

After a simulation completes, the performance measure of the proportion of late ambulances can be calculated from the two global variables ontime and late. The model describes a system where ambulances behave in the manner described by the seven points in Section 2. The next section considers results of experiments with this model.

Results

To explore the behaviour of the model and the heuristic, the network shown in Figure 5 is used (which by contrast with [START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF] is a compact network rather than long and narrow). and is somewhat simpler than a real scenario. The number annotating the edges of the network gives the time in minutes that it takes to traverse the edge at the faster speed (with sirens and lights on). Locations with hospitals are indicated by double circles at vertices. The number annotating a vertex is the proportion of incidents at that location.

The parameters chosen for the model are given in Table 1. The parameter T which is used as the limit in the calculation of the late rate varies across experiments. The busy fraction q which is used in the calculation of the heuristic function π is estimated by simulation, for the given network with three ambulances to be 0.65. The experiments explore how the late rate varies for different values of the time limit, and furthermore, they consider how the hospital location can affect the late rate, and are illustrated in Figure 6. The square nodes indicate the hospital locations in each case. Each combination of time limit and hospital location was simulated for 500 runs over 20 hours of simulated time. The shaded circles indicate at which locations the idle ambulances were based, and all locations were considered as possible base locations. The area of the circle represents the proportion of simulations that idle ambulances are at a location (or on their way to that location as a base) at the time point of 1200 minutes (20 hours). Since there are three ambulances, fewer than three circles indicate that multiple ambulances are idle at a location.

The results show that the heuristic does not appear to have monotonic behaviour since an increased time limit can lead to a different location with a worse late rate, and this requires further investigation. The heuristic does not use the hospital location but obviously distance from hospital back to base will impact availability, and hence late rate. The lowest late rates occur when there are two hospitals at the two cities, and an ambulance goes to the closest hospital. This experiment shows how the late rates would be affected if it was necessary to close one of the hospitals. However, for some time limits, the presence of two hospitals has little effect on the late rate when compared with just one hospital at the second city, where for others it makes a significant difference. The fact that hospital location can affect the proportion of late arrivals suggests a role for the hospital location in the heuristic function.

Conclusions and further work

This paper has demonstrated how the language CARMA can be successfully used to model a system involving coordination where communication is often complex and multiway, and various components interaction to achieve goals. In this case, this is identification of an ambulance to go to an incident, movement of the ambulance to the incident using a generic component that draws on functions to give the specifics of a route, movement to hospital where required, then choice of a base to return to on completion and movement to that base. Because of the use of generic functions together with generic components, the model can be made applicable to any road network simply by substituting the appropriate functions.

Further research relating to this case study include further exploration of the parameter state space, in particular to understand the nature of the heuristic function as mean time between incidents change, as well as modifying the heuristic to take into account the current location of idle ambulances as well as their bases. Different performance measures could also be investigated that consider not just a single deadline but how late the ambulance is, in the case of late arrival at the scence. Clearly, many variations can be made to the ambulance model, including for example, switching to an ambulance closer to the incident if one becomes available when another is already on the way; investigating movement between bases as an incident occurs; and the use of different time limits depending on the severity of the incident. At the modelling level, comparison of the use of CARMA with other formalisms and an assessment of its strengths and weaknesses is important.

As often is the case in modelling for performance assessment, the users who are interested in the measure often do not have the skills to work with the modelling language directly. A ongoing project is to develop a graphical front-end for general modelling of this ambulance scenario. The final goal is software which allows a user to graphically create a road network as shown in Figure 5 with appropriate annotations, after which it will automatically generate a CARMA model consisting of the seven generic components, the model parameters and the functions to implement the network. The model can then be simulated in the CARMA Eclipse Plug-in. An additional step would be to take the output of a single simulation and use it to create an animation over the network, to give users an insight to what is happening during the simulation. This gives more information about the model over and above the performance measure.

1 .

 1 The relation -describes the behaviour of a single component. 2. The relation --→ builds on the first relation to describe the behaviour of collectives. 3. The relation --→ describes how CARMA systems evolve.

Fig. 2 .

 2 Fig. 2. Return handler and idle ambulance components

T = 7 Fig. 6 .

 76 Fig. 6. Idle ambulances and proportions of late arrivals for time limits and hospital locations

  σ is an update, i.e. a function from Γ to Dist(Γ ) in the set of updates Σ ; where Dist(Γ ) is the set of probability distributions over Γ .

	where
	-α is an action type in the set of action type ACTTYPE;
	-π is a predicate;
	-x is a variable in the set of variables VAR;
	-e is an expression in the set of expressions EXP; --→ • indicates a sequence of elements;

  confirm [ ](an, al){rnum ← rnum + 1}.RN Initial state of Incident Queue component: IG | RN Store of Incident Queue Item component: qnum number of incident itime time of incident Behaviour of Incident Queue Item component: IQI ToHosp}.IH H + treat [an == my.anum](an){aloc ← my.loc, dest ← ToBase}.IH F IH H an == my.anum](an){aloc ← my.loc, dest ← ToBase}.IH F IH F Initial state of Incident Handler component: IH Fig. 1. Incident queue, incident queue item and incident handler components .RH + kill handler [my.anum == an](an).kill RH def = atbase [my.anum == an](an).kill + kill handler [my.anum == an](an).kill Initial state of Return Handler component: RH Store of Closest Idle Ambulance component: iloc location of incident dloc location of idle ambulances t timer variable for timeout Behaviour of Closest Idle Ambulance component: CIA

	Store of Return Handler component:
	anum id of ambulance assigned
	aloc current location of ambulance
	Store of Incident Queue component: dest current destination and incident type
	inum number of incidents generated loc location of base of ambulance
	rnum next incident to be dealt with Behaviour of Return Handler component:
	Behaviour of Incident Queue component: RH
	IG
		IH I
	IH I	def = makeroute [⊥] .IH S
	IH S	def = arrive [an == my.anum](an).IH T
	IH T	def = timecheck [⊥] {atime ← now}.IH P
	IH P
		def = makeroute [⊥] .IH D
	IH D

def = incident [⊥] {inum ← inum + 1}.IG RN def = release[ ] rnum .RN RN def = def = release[my.qnum == n](n).IQI IQI def = new handler [⊥] .kill Initial state of Incident Queue Item component: IQI Store of Incident Handler component: loc location of incident or hospital anum id of ambulance assigned to incident aloc current location of ambulance assigned to incident dest current destination type and incident type itime time of incident atime arrival time at incident Behaviour of Incident Handler component: IH def = request ambulance [ ] loc .IH C IH C def = confirm [an, al]({anum ← an, aloc ← al}).def = pickup [an == my.anum](an){aloc ← my.loc, loc ← HospitalLocation(my.loc), dest ← def = dropoff [def = tobase [⊥] .kill def = tell base[ ] loc .RH RH def = makeroute [⊥] def = request ambulance[ ](l){iloc ← l, dloc ← ClosestIdleLoc(iloc, N),t ← now}.CIA CIA def = request[ ] dloc .CIA + pause [⊥] {dloc ← ClosestIdleLoc(iloc, N),t ← now}.CIA CIA def = confirm [ ](an, al).CIA Initial state of Return Handler component: CIA

  end move[an == my.anum ∧ now >= t + d](an, al,t, d){aloc ← al}.Busy + arrive [an == my.anum](an).AtScene + drop off [an == my.anum](an){idle ← }.AskBase AtScene def = pickup [an == my.anum](an).Busy + treat [an == my.anum](an){idle ← }.AskBase AskBase def = tell base[an == my.anum](an, ab){abase ← ab}.GoToBase GoToBase def = end move[an == my.anum ∧ now >= t + d](an, al,t, d){aloc ← al}.GoToBase + atbase [an == my.anum](an).Idle + request[an == my.anum](an).CleanUp1 CleanUp1

	Store of Ambulance component:
	anum ambulance id
	aloc current location of ambulance
	abase current base of ambulance
	idle whether ambulance is idle or not
	Behaviour of Ambulance component:
	Idle	def = request[al == my.aloc](al){idle ← ⊥}.Respond
	Respond	def = confirm [ ] anum, aloc .Busy
	Busy
	Store of Route component:
	anum number of ambulance
	dest current destination type and incident type
	start start of route
	end end of route
	nexts start of next hop
	nexte end of next hop
	h number of hops in route
	i hop counter
	t timer variable for deterministic movement
	Behaviour of Route component:
	R	def

def = def = kill handler [ ] anum .CleanUp2 CleanUp2 def = kill route [ ] anum .Respond Initial state of Ambulance component: Idle

Table 1 .

 1 Parameters for model

	λ p 1/12 rate of pickup action q	0.45 busy fraction
	λ t 1/12 rate of treat action	m		1 proportion of serious incidents
	λ d 1/15 rate of dropoff action r		25 mean time between incidents
	λ fast 100 rate of fast actions	timeout	1 timeout period in minutes
			0.08		0.3
			T1	7.6	C1
			6.5		5.6	8.5
	T2	5.2	J1	4.3	J2	T3
	0.06					0.16
			3.7	4.2		9.2
				C2
				0.4
		Fig. 5. Network configuration for experiments

This function differs from that in[START_REF] Jagtenberg | An efficient heuristic for real-time ambulance redeployment[END_REF] due to the additional term 1(ρ(u, v) ≤ T in the first part of the definition. It does, however, match the algorithm that was used in that paper[13].

A different approach is to use components to embody the knowledge of the network and for the generic components to communicate with these components to obtain this information, but this leads to increase complexity of interaction. Alternatively, the environment could contain this knowledge.

For the calculation of the performance measure, this detailed level of movement is not necessary but if one wanted to create an animation from a simulation then this detail is required.

Acknowledgements This work is supported by the EU project QUANTICOL, 600708. The author thanks Jane Hillston and Yehia Abd Alrahman for their useful comments.

Constants:

T limit for response time timeout time to wait for a response for a request Measures: N set containing the number of idle ambulances at each possible base Global store: ontime number of ontime ambulances late number of late ambulances Evolution rule functions:

1/r α = incident (where r is the mean time between incidents)