Christopher T Lefèvre

Claire-Lise Santini

Alain Bernadac

Wei-Jia Zhang

Ying Li

Long-Fei Wu
email: wu@ibsm.cnrs-mrs.fr

Christopher ; Lefèvre

-Jia

Christopher T Lefèvre

Calcium-ion mediated assembly and function of glycosylated flagellar sheath of marine magnetotactic bacterium

Keywords: flagella, Sheath, Calcium ions, Glycoprotein, Magnetotaxis

Flagella of some pathogens or marine microbes are sheathed by an apparent extension of the outer cell membrane. Although flagellar sheath has been reported for almost 60 years, little is known about its function and the mechanism of its assembly. Recently, we have observed a novel type of sheath that encloses a flagellar bundle, instead of a single flagellum, in a marine magnetotactic bacterium MO-1. Here, we reported isolation and characterization of the sheath which can be described as a six-start, right-handed helical tubular structure with a diameter of about 100 nm, and a pitch of helix of about 260 nm. By proteomic, microscopic and immunolabelling analyses, we showed that the sheath of MO-1 consists of glycoprotein with an apparent molecular mass >350 kDa. This protein, named sheath associated protein (Sap), shows homology with bacterial adhesins and eukaryotic calcium-dependent adherent proteins (cadherin). Most importantly, we showed that calcium ions mediate the assembly of the tubular-shaped sheath and disintegration of the sheath was deleterious for smooth-swimming of MO-1 cells. The disintegrated sheath was efficiently reconstituted in vitro by adding calcium ions. Altogether, these results demonstrate a novel bacterial Ca 2+ -dependent surface architecture, which is essential for bacterial swimming.

Introduction

Flagella provide bacteria with a highly efficient means of locomotion and also play a central role in adhesion, biofilm formation, and host invasion [START_REF] Mccarter | Polar flagellar motility of the Vibrionaceae[END_REF][START_REF] Terashima | Flagellar motility in bacteria structure and function of flagellar motor[END_REF]. The flagella are powered by reversible rotary motors embedded in the cell membrane. Beside the function of locomotion they also act as a protein export-assembly apparatus [START_REF] Macnab | How bacteria assemble flagella[END_REF].

Tens of thousands copies of a single flagellin protein or of several closely related flagellins are self-assembled to form a hollow concentric double-tubular structures, called simple or complex flagellum, respectively. Flagellins and other exported substrates diffuse down the narrow channel in the growing filament structure and assembly at the distal ends. Recently, it has been shown that glycosylation of flagellins is an important component of numerous flagellar systems in both archaea and bacteria [START_REF] Logan | Flagellar glycosylation -a new component of the motility repertoire?[END_REF]. The glycosylation plays either an integral role in assembly or for a number of pathogenic bacteria a role in virulence.

The number and organization of bacterial flagella vary from species to species. The most extensively studied are polar and peritrichous flagella. Interestingly, the polar flagella are surrounded by sheaths in several bacteria including marine Vibrio species (Furuno et al., 2000;[START_REF] Mccarter | Polar flagellar motility of the Vibrionaceae[END_REF], Vibrio cholera (Fuerst and Perry, 1988;[START_REF] Hranitzky | Characterization of a flagellar sheath protein of Vibrio cholerae[END_REF], Bdellovibrio bacteriovorus [START_REF] Thomashow | Isolation and composition of sheathed flagella from Bdellovibrio bacteriovorus 109[END_REF], Pseudomonas stizolobii (Fuerst and Hayward, 1969), Helicobacter pylori (Geis et al., 1993;[START_REF] Luke | Identification of a 29 kDa flagellar sheath protein in Helicobacter pylori using a murine monoclonal antibody[END_REF][START_REF] O'toole | The putative neuraminyllactose-binding hemagglutinin HpaA of Helicobacter pylori CCUG 17874 is a lipoprotein[END_REF], and Azospirillum brasilense [START_REF] Burygin | Detection of a sheath on Azospirillum brasilense polar flagellum[END_REF]. Each sheath encloses one flagellar filament. How a sheathed flagellum rotates has not been elucidated, and little is known about the composition, formation, or function of flagellar sheaths. Evidence from these organisms suggests that the sheath contains both lipopolysaccharide and proteins with molecular weight ranging from 18 to (Furuno et al., 2000;[START_REF] Hranitzky | Characterization of a flagellar sheath protein of Vibrio cholerae[END_REF][START_REF] Jones | A flagellar sheath protein of Helicobacter pylori is identical to HpaA, a putative Nacetylneuraminyllactose-binding hemagglutinin, but is not an adhesin for AGS cells[END_REF]. The sheath protein HpaA of H. pylori has been localized in the cytoplasm [START_REF] O'toole | The putative neuraminyllactose-binding hemagglutinin HpaA of Helicobacter pylori CCUG 17874 is a lipoprotein[END_REF] or on the flagellar sheath [START_REF] Jones | A flagellar sheath protein of Helicobacter pylori is identical to HpaA, a putative Nacetylneuraminyllactose-binding hemagglutinin, but is not an adhesin for AGS cells[END_REF]. The mechanism of its secretion and assembly remains unknown. The procedure of sheath formation is suggested to be independent of filament polymerization, since empty flagellar sheaths have been observed as tubule projections originating from the cell surface [START_REF] Allen | Structure and arrangement of flagella in species of the genus Beneckea and Photobacterium fischeri[END_REF]. Moreover, the sheath in Vibrio parahaemolyticus seems to act on retaining flagellin monomers and allowing subunit assembly [START_REF] Mccarter | Genetic and molecular characterization of the polar flagellum of Vibrio parahaemolyticus[END_REF]. Despite the extensive microscopic and molecular studies, the requirement of the sheath for bacterial motility has not been reported.

Recently, we reported a peculiar architecture of the flagellar apparatus of marine magnetotactic bacteria MO-1 [START_REF] Lefèvre | Isolation and characterization of a magnetotactic bacterial culture from the Mediterranean Sea[END_REF]. Magnetotactic bacteria (MTB) consist of a heterogeneous group of gram negative bacteria that synthesize intracellular crystals of magnetic iron oxide and/or iron sulfide minerals [START_REF] Bazylinski | Magnetosome formation in prokaryotes[END_REF]. These membrane-bounded crystals, called magnetosomes, align forming an intracellular magnetic dipole moment and allow the bacteria to orient and migrate along geomagnetic field lines. This behavior, called magnetoaerotaxis, increases the efficiency of cells to find and maintain at a preferred position at the oxicanoxic transition zone (OATZ) [START_REF] Bazylinski | Magnetosome formation in prokaryotes[END_REF]. Like most magnetotactic coccoid cells studied, MO-1 cells are bilophotrichously flagellated, having two flagellar bundles on one hemisphere of the cells [START_REF] Lefèvre | Isolation and characterization of a magnetotactic bacterial culture from the Mediterranean Sea[END_REF]. We have reported for the first time that these flagellar bundles are enclosed within sheaths. In this study, we identified the major sheath associated protein (Sap) as a large glycosylated polypeptide. Most importantly, we showed that calcium ions play an essential role in the assembly of tubular-shaped sheath, and that the sheath is required for smooth swimming of MO-1 cells.

Results

Biochemical characterization of MO-1 surface appendages

To investigate their biochemical composition, surface appendages of MO-1 were detached from cell by shearing and centrifugation. The final fractions named C2 contained flagella, sheaths and membrane vesicles as revealed by transmission electron microscopy (TEM) analysis (Fig. 1A).

In the C2 fraction, sheaths were separated from the flagella, indicating a loose connection between the internal core of flagella bundle and external sheath. Although detached from the flagella bundle, the sheath remained as nanotube, but broken into shorter fragments due to the shearing. Image analysis suggests that the sheath can be described as a six-start (composed of six protofilaments), right-handed helical tubular structure with a diameter of about 100 nm, and a pitch of helix of about 260 nm (Fig. 1, panels C to E).

The protein composition of the C2 fraction was analyzed by SDS-PAGE and Coomassie Blue staining. The C2 fraction was apparently composed of 7 polypeptide bands (IN and M1 to M6, Fig. 1F, lane 2). IN was located in the stacking gel and not further studied. Periodic acid Schiff staining showed that M1, M2, M5 and M6 were glycoproteins (Fig. 1F, lane 2s). In addition, Azur blue staining revealed a polyanionic nature of the glycans on these polypeptides (Supporting Information, Fig. S1). N-terminal sequencing and ion-trap MS-MS mass spectroscopy analyses revealed that the polypeptides M4, M5 and M6 were homologous to flagellin proteins from various bacteria, including the closely related Candidatus Magnetococcus marinus strain MC-1 [START_REF] Schubbe | Complete genome sequence of the chemolithoautotrophic marine magnetotactic coccus strain MC-1[END_REF]. Intriguingly, MC-1 genome contains 15 flagellin encoding genes and the predicted flagellins exhibit similar molecular sizes and pI values [START_REF] Schubbe | Complete genome sequence of the chemolithoautotrophic marine magnetotactic coccus strain MC-1[END_REF]. It is likely that the genome of MO-1 contains multiple copies of flagellins. Recently, it has been reported that inactivation of the flagellin gene flaA in [START_REF] Schultheiss | Inactivation of the flagellin gene flaA in Magnetospirillum gryphiswaldense results in nonmagnetotactic mutants lacking flagellar filaments[END_REF]. The N-terminus of the polypeptide M3 was homologous to the hypothetical protein Mmc1_3749 of Cand. M. marinus MC-1 [START_REF] Schubbe | Complete genome sequence of the chemolithoautotrophic marine magnetotactic coccus strain MC-1[END_REF]. The Nterminal sequence of M2 (PTITASNLT) did not possess 100% sequence identity with any protein in the NCBI database. The identity of this polypeptide remains to be determined.

The polypeptide M1 particularly drew our attention. Autolysis of C2 fractions at 37 °C for 4 days led to the concomitant disappearance of M1 polypeptide and the sheaths (Fig. 1B, Fig. 1F, lane 3 compared to lane 2), whereas the other five polypeptides and flagella and vesicles remained intact. To further analyze the relationship between the M1 protein and the sheath structure, we excised the polypeptide band of M1 and used it to raise polyclonal antibodies. Immunoblot analyses confirmed the specificity of the polyclonal antibody obtained; only M1 was detected in the crude extracts or the C2 fractions of MO-1 by this antiserum (Fig. 2, inset panel). Using anti-M1 antibody-based immuno-gold staining, we found that the gold-particles specifically localized on the sheath (Fig. 2). These results strongly suggest that the M1 protein is a component of the sheath.

To identify the M1 polypeptide, protein samples in the M1 band were digested with trypsin and then analyzed by Microflex MALDI-ToF, ESI-Q-ToF and nLC-ESI-MS/MS mass spectrometry.

Searching in the MO-1 genomic contig database unambiguously identified M1 as product of a gene encompassing 10068 bp (accession HM015774) and encoding 3356 amino acids with a predicated molecular weight of 344502.6 Da and a pI of 3.29 (see Supporting Information, Fig S2). In addition, the N-terminal sequence (AATPTATD) of M1 perfectly matched with the residues 226 to 233 of the gene product, suggesting a posttranslational processing of the precursor. We designate the gene as sap for its product sheath-associated protein. Cadherins represent a major superfamily of transmembrane glycoproteins that mediate calciumdependent cell-cell adhesion in both vertebrates and invertebrates [START_REF] Takeichi | Cadherin cell adhesion receptors as a morphogenetic regulator[END_REF]. Canonical cadherins have an extracellular domain in the N-terminal part of the molecule, which typically is composed of five cadherin repeats. Proteins are designated as members of the broadly defined cadherin family if they have one or more cadherin repeats. As it contains 2 predicated cadherin repeats, Sap can be considered as a novel member of the cadherin family.

Calcium-ions are crucial for the sheath structure

As implied in the name, cadherins (for calcium-dependent adherent proteins) require calcium ions for assembly of protein domains and subunit into highly organized functional structures.

Calcium ions bind to specific residues (Asp, Asn, Glu and Gln) in cadherin repeats to ensure its proper folding and to confer rigidity upon the extracellular domain. Therefore, calcium ions are essential for cadherin adhesive function and for protection against protease digestion [START_REF] Takeichi | Cadherin cell adhesion receptors as a morphogenetic regulator[END_REF]. The Sap protein of MO-1 contains cadherin-repeat-domains and is rich in residues Asp (12.7%), Asn (5.8%) and Glu (5.2%). Hence, we sought to assess the involvement of calcium ions in establishing the structure of the sheaths. The solutions used in C2 fractions preparation appeared to be important for the sheath structure.

The synthetic seawater seemed to have beneficial effect on the stability of the sheath. Addition of divalent ion chelators led to the disappearance of the sheaths from the C2 fractions, whereas the flagella and vesicles remained intact (Fig. 3A). Interestingly, the chelate treatment did not modify protein patterns of the C2 fractions on SDS-PAGE gels (data not shown). These results suggest that chelators disintegrate the structure of the sheaths, implying a crucial role of calcium ions for the structure.

To corroborate this hypothesis, we assessed the possibility to reconstitute the sheaths from disintegrated components. The citrate-treated sheath-free C2 fractions were incubated with addition of CaCl 2 or MgCl 2 , or both. As shown in Fig. 3, only calcium ions allowed reconstitution of the sheath structure. The same results were obtained when the sheaths were disintegrated with EGTA (ethylene glycol tetraacetic acid chelating specifically calcium ions) (see Supporting Information,Fig S3) or EDTA (ethylene diamine tetraacetic acid). Therefore, calcium ions seem to specifically mediate the reconstitution of the sheath structure.

Requirement of the flagellar sheath for the smooth swimming of MO-1 cells

Although it has been over sixty years since the first report of flagellar sheath, its function in bacterial motility remain undemonstrated. The disintegration of the flagellar sheath by citrate provides an effective means to analyze sheath function. Figure 4 than the circumgyrating cells (Fig. 4B). We quantified the helical trajectories and the spots using Image J software. Without citrate treatment, about half of MO-1 cells (43.3±7.9%, average ± standard deviation, n=618 cells analyzed) swam smoothly with swimming velocity of 126 ± 10 µm s -1 . The percentage and the velocity of smooth swimming bacteria decreased in direct proportion with the increase of citrate concentration (Fig. 4C1 and4C2, respectively). When sodium citrate was added at 50 mM, less than 1% cells swam smoothly with velocity of 49 ± 11 µm s -1 (n=312). Moreover, addition of magnesium or calcium ions relieved the deleterious effect of citrate on bacterial motility (Fig. 4D). Under these conditions, the sheath structure remained intact. Statistic analysis confirms that harmful effect of citrate on the smooth swimming is significant compared to the untreated cells or cells protected by divalent ions (Table 1). Together these results reveal that the sheath of the flagellar bundle is crucial for the smooth swimming of MO-1 cells.

Discussion

Since the first observation in Vibrio metchnikovii in 1947 (Van Iterson, 1947), single flagellar sheath that cover only one polar flagellum has been reported for several bacterial species.

Microscopic studies together with immunolabeling analyses revealed that the single flagellum sheath is a continuation of the cell wall [START_REF] Burygin | Detection of a sheath on Azospirillum brasilense polar flagellum[END_REF]Fuerst and Perry, 1988;Glauert, 1968). Interestingly, Hranitzky et al. have reported that although the sheath protein was detected 11 on the flagellum as well as on the outer membrane of the V. cholera cells, antibody specific for lipopolysaccharide labeled the cell but not the sheathed flagellum [START_REF] Hranitzky | Characterization of a flagellar sheath protein of Vibrio cholerae[END_REF].

Therefore, they proposed that the sheath is not a simple extension of the outer membrane. In this study, immuno-fluorescence analysis revealed that Sap also locate on the surface of the MO-1 cells (Supporting information, Fig S4). However, immune-gold labeled only sheath disconnected from the cells or the isolated sheath, but not the cell surface (data not shown). The discrepancy of the results might be due to the difference between the two immune-detection procedures used.

Fluorescein is a small molecule with a mass of about 332 Dalton (<1 nm). In contrast the gold particle has a big size of about 7 nm. Therefore, fluorescein marker has a better accessibility than gold particles. In addition, MO-1 cells are rich in phosphor and lipid granules, which considerably reduced the contrast between cells and the gold particles and made the observation difficult. It is unknown how the Sap protein is secreted to the cellular surface and how they assemble at precise position to form the sheath. N-terminal sequencing revealed that the first 225 residues are absent from the mature Sap, implying a processing of the precursor during Sap secretion. As the potentially processed segment does not carry any known protein targeting signal sequence, a novel protein targeting and secretion mechanism might be involved in sheath assembly.

Calcium ions impact nearly every aspect of cellular life. Ca 2+ -binding triggers changes in protein shape and charge, participates in a variety of cellular processes in both eukaryotic and prokaryotic organisms [START_REF] Clapham | Calcium signaling. Cell 131: 1047-1058. process that requires HMW1C and phosphoglucomutase, an enzyme involved in lipooligosaccharide biosynthesis[END_REF]Dominguez, 2004). Eukaryotic extracellular matrix hosts a large variety of Ca 2+ -binding proteins (Maurer et al., 1996). For example, human fibrillin-1 is a 350 kDa calcium binding glycoprotein, which assembles to form 10-12 nm microfibrils in extracellular matrix [START_REF] Handford | Fibrillin-1, a calcium binding protein of extracellular matrix[END_REF]. MO-1 Sap protein shares similarity with fibrillin-1 in that F o r P e e r R e v i e w 12 both are exported large glycoproteins and assemble into higher order structures in a calcium iondependent manner. To our knowledge, the MO-1 sheath is the only known bacterial extracellular calcium dependent architecture assembled from glycoprotein. Sequence similarity between Sap and cadherins would suggest that calcium ions bind to residues Asp, Asn, Glu and Gln rather than directly to glycans of Sap as that occurs in cadherins. Autolysis or treatment of flagella with hydrochloric acid or urea resulted in loss of the sheaths of V. metchnikovii and P. stizolobii flagella (Follett and Gordon, 1963;Fuerst and Hayward, 1969), implying a fragile structure of the single flagellum sheath. Here we showed that removing calcium ions by chelators disintegrates the MO-1 sheaths. It is unknown whether the assembly of the single flagellum sheath is mediated by the calcium ions and if the same mechanism is involved in the assembly of both single flagellum and multiple flagella sheath.

Once thought to be restricted to eukaryotes, glycosylation is now being increasingly reported in prokaryotes [START_REF] Spiro | Protein glycosylation: nature, distribution, enzymatic formation, and disease implications of glycopeptide bonds[END_REF]. Examples of bacterial glycoproteins include, among others, the flagellins of Pseudomonas aeruginosa [START_REF] Takeuchi | Flagellin glycosylation island in Pseudomonas syringae pv. glycinea and its role in host specificity[END_REF] and Campylobacter spp. (Doig et al., 1996), the type IV pili of P. aeruginosa [START_REF] Castric | pilO, a gene required for glycosylation of Pseudomonas aeruginosa 1244 pilin[END_REF] and Neisseria meningitides [START_REF] Power | Genetic characterization of pilin glycosylation and phase variation in Neisseria meningitidis[END_REF], the Fap1 fimbrial adhesin of Streptococcus parasanguinis [START_REF] Stephenson | The Fap1 fimbrial adhesin is a glycoprotein: antibodies specific for the glycan moiety block the adhesion of Streptococcus parasanguis in an in vitro tooth model[END_REF], the high-molecular-weight protein (HmwA) of Haemophilus influenzae (Grass et al., 2003), and the autotransporter protein Ag43 of Escherichia coli (Sherlock et al., 2006). It is evident that glycosylation plays a vital role in pathogenicity and host invasion [START_REF] Szymanski | Protein glycosylation in bacterial mucosal pathogens[END_REF].

Interestingly, impairment of flagellin glycosylation in Pseudomonas syringae pv. tabaci decreases bacterial swimming activity in a highly viscous medium and affects polymorphic transitions and the bundle formation of peritrichous flagella [START_REF] Taguchi | Effects of glycosylation on swimming ability and flagellar polymorphic transformation in Pseudomonas syringae pv. tabaci 6605[END_REF]. It has been proposed that glycosylation stabilizes the filament structure and lubricates the rotation of the [START_REF] Hills | Boundary lubrication in vivo[END_REF].

In this study we found that both the major sheath protein Sap and flagellins are glycosylated.

Considering that seven flagella rotate within the sheath, probably at very high frequency, it seems reasonable to propose that, apart from other functions, the glycans on the sheath and flagella of MO-1 cells might serve as lubricants to reduce the mechanical friction. At present, we don't know if the same system is involved in the glycosylation of the flagellin and the sheath proteins. In addition, whether the glycosylation is essential for the export, assembly and/or function of sheath and flagellins remains an open question.

Little is known about the function of the bacterial flagellar sheath. It has been suggested that the sheath may serve as a protective covering since sheathed polar flagella appear to be more resistant to protease hydrolysis and mechanical treatment than unsheathed peritrichous flagella do. In addition, flagellum sheaths of V. cholerae and H. pylori have been proposed to serve as a carrier of adhesins (Evans et al., 1993;Fuerst and Perry, 1988), being important for specific interactions with the environment. However, the functional significance of the sheath in bacterial motility is unknown. The feature of the Ca 2+ -dependent assembly of MO-1 flagellar sheath allowed us to address this question. Disintegration of the sheath apparently has a deleterious effect on the smooth swimming of the MO-1 cells. It is expectable that rotation of seven individual flagella at high frequency within a bundle must be mechanically and structurally coordinated. We have observed the same sheath structure in uncultivated coccoid-ovoid Mediterranean magnetotactic bacteria collected at Ile des Embiez [START_REF] Lefèvre | Isolation and characterization of a magnetotactic bacterial culture from the Mediterranean Sea[END_REF]. In addition, the Cand. M. marinus MC-1 strain isolated from the Pettaquamscutt Estuary in USA and Mediterranean Sea (N. Pradel, personal communication) seem to contain the same bilophotrichous flagella and sheath structure as the MO-1 cells. Evolution might have selected the Ca 2+ -mediated sheath structure to ensure harmonious rotation of the flagella within the bundles to achieve an efficient magneto-aerotaxis of marine cocci. Elucidation of the mechanism of flagellar sheath synthesis challenges current knowledge of secretion and assembly of glycoproteins into the remarkable extracellular locomotion apparatus.

Experimental procedures

Extraction and analysis of the flagellar apparatus

Magneto-ovoid strain MO-1 was incubated in the EMS2 medium at 24°C to exponential phase [START_REF] Lefèvre | Isolation and characterization of a magnetotactic bacterial culture from the Mediterranean Sea[END_REF]. Cells were collected by centrifugation at 14 000 g for 10 min, resuspended with synthetic seawater (332 mM NaCl, 29 mM MgCl 2 , 23 mM Na 2 SO 4, 16 mM CaCl 2 , 7 mM KCl in 12.5 mM pH7.2 HEPES buffer), and cell suspension was pushed through syringe needles (0.8x40 mm) 20 times to shear the flagellar propellers. Sheared cells were centrifuged at 20 000 g for 5 min to separate cells and cellular debris from the flagellar propellers. The supernatants were further centrifuged at 200 000 g for 50 min, and the pellets (C2) were resuspended with the synthetic seawater if not mentioned specially. In general, protein samples are maintained at low temperature (on ice or at 4°C) to prevent the proteolysis. Autolysis of C2 fraction was thus performed by incubating at 37°C for 4 days. Analysis of microscopes and SDS-PAGE were made as previously described [START_REF] Pradel | Biogenesis of actinlike bacterial cytoskeletal filaments destined for positioning prokaryotic magnetic organelles[END_REF]. Glycosylated proteins were visualized by Periodic acid-Schiff staining according to Zacharius et al. (Zacharius et al., 1969). To study the disintegration of the sheath, the pellets C2 were resuspended with synthetic seawater or HEPES buffer (12.5 mM, pH=7.2), supplemented with generally used calcium chelator such as EDTA, EGTA or sodium citrate at the final concentrations as indicated in the text. After incubation in ice for 45 min, C2 fractions were ultracentrifuged and the pellets were resuspended with modified synthetic seawater without divalent ions, or supplemented with 16 mM CaCl 2 or 29 mM MgCl 2 , or both and incubated at room temperature for 45 min. The presence of sheath was examined under electron microscope.

Measurement of swimming velocities

MO-1 cells at exponential growth phase were collected and distributed into microtubes. HEPES buffer (25 mM, pH 7.2 supplemented with 328 mM NaCl, 22.8 mM Na 2 SO 4 , and 7.4 mM KCl) was added at 1/10 volume to the cell suspensions. When required, sodium citrate (at final concentrations as indicated in text), CaCl 2 (added at 1/10 volume from supernatant of saturated solution in the HEPES buffer), or MgCl 2 (50 mM in the HEPES buffer) were added at time zero.

After one to six hours of treatment, seven microliter aliquots of cell suspensions were dropped onto microscope slides and covered with 22 x 22 mm cover slips, and observed using a 40x objective on a ZEISS Photomicroscope III microscope under dark field. Swimming tracks were recorded with a Photonic Scientific CCD camera controlled by Image-Pro program with exposure time of 100 ms, and the images were analyzed using Image J. Statistics were done with Origin 8 software.

Electron microscopy

Transmission electron microscopic analysis was as described previously [START_REF] Pradel | Biogenesis of actinlike bacterial cytoskeletal filaments destined for positioning prokaryotic magnetic organelles[END_REF].

Image-Pro plus was used for inverse Fourier transform analysis of the TEM images. For image enhancement the major peaks in the Fourier Transform were amplified. Polypeptides M1 were 16 excised from the polyacrylamid gels and used to generate rabbit polyclonal antibodies by using conventional protocol [START_REF] Harlow | Antibodies: A laboratory manual[END_REF]. Immuno-gold staining using polyclonal rabbit anti-M1 at dilution of 1/1500 and 7 nm gold-conjugated protein A was performed as described by [START_REF] Pradel | Biogenesis of actinlike bacterial cytoskeletal filaments destined for positioning prokaryotic magnetic organelles[END_REF].

7

  Magnetospirillum gryphiswaldense results in nonmagnetotactic mutants lacking flagellar filaments

  NCBI database revealed that Sap is homologous primarily with outer membrane adhesin like proteins from various bacteria, and the most closely related is that from Cand. M. marinus strain MC-1 (42% identity with putative outer membrane adhesin like protein, accession YP_865069.1). COGnitor analysis showed that Sap contains three segments belonging to the cluster of orthologous group of large exoproteins involved in heme utilization or adhesion (COG3210) and three segments belonging to COG5292 (autotransporter adhesion). InterProScan analysis showed that C-terminus of Sap possesses one Cadherin_2 domain (IPR002126, at position 2257-2331) and one Cadherin-like domain (IPR015919, at position 2441-2535).

  shows a typical TEM image of MO-1 cell after treatment with sodium citrate, flagella are dispersed resulting from disintegration of sheath (Fig.4A2 versus 4A1). The extent of disintegration augmented with increased concentration of citrate and prolonged incubation time. The impact of citrate treatment on cell motility was analyzed using dark field optical microscopy. Typically, MO-1 cells exhibit two patterns of motility; forward smooth-swimming and circumgyrating. Whereas smooth-swimming helical trajectory (Fig.4B, 's' symbol), circumgyrating cells appeared as bright spots, or rosette (Fig.4B, 'c' symbols and inset) when observed at high amplification. The circumgyrating swimming might result from either disordered flagellar rotation or adhesion of flagella to the slides. Non motile bacteria also appeared as spots, generally sharper and smaller

  function of glycoproteins in human body has been demonstrate

(

  D. A.Bazylinski, personal communication), an axenic magnetotactic coccus culture isolated from a hypersaline sea, the Salton Sea, California (C. T.Lefèvre, and D. A. Bazylinski, uncultivated magnetotactic cocci collected from the China Sea (Zhou et al., 2010)

  .,Kinsella, N., Guerry, P., and Trust, T.J. (1996) Characterization of a post-translational modification of Campylobacter flagellin: identification of a sero-specific glycosyl moiety. Mol. Microbiol. 19: 379-387. Dominguez, D.C. (2004) Calcium signalling in bacteria. Mol Microbiol 54: 291-297. Evans, D.G., Karjalainen, T.K., Evans, D.J., Jr., Graham, D.Y., and Lee, C.H. (1993) Cloning, nucleotide sequence, and expression of a gene encoding an adhesin subunit protein of Helicobacter pylori. J. Bacteriol. 175: 674-683. Follett, E.A., and Gordon, J. (1963) An electron microscope study of Vibrio flagella. J Gen Microbiol 32: 235-239. Fuerst, J.A., and Hayward, A.C. (1969) The sheathed flagellum of Pseudomonas stizolobii. J. Gen. Microbiol. 58: 239-245. Fuerst, J.A., and Perry, J.W. (1988) Demonstration of lipopolysaccharide on sheathed flagella of Vibrio cholerae O:1 by protein A-gold immunoelectron microscopy. J Bacteriol 170: 1488-1494. Furuno, M., Sato, K., Kawagishi, I., and Homma, M. (2000) Characterization of a flagellar sheath component, PF60, and its structural gene in marine Vibrio. J Biochem 127: 29-36. Geis, G., Suerbaum, S., Forsthoff, B., Leying, H., and Opferkuch, W. (1993) Ultrastructure and biochemical studies of the flagellar sheath of Helicobacter pylori. J Med Microbiol 38: 371-377. Glauert, A.M. (1968) Electron microscopy of lipids and membranes. J. R. Microsc. Soc. 88: 49-70. Grass, S., Buscher, A.Z., Swords, W.E., Apicella, M.A., Barenkamp, S.J., Ozchlewski, N., and III, J.W.S.G. (2003) The Haemophilus influenza HMW1 adhesin is glycosylated in a W. (1947) Some electron-microscopical observations on bacterial cytology. Biochim. Biophys. Acta 1: 527-548. Zacharius, R.M., Zell, T.E., Morrison, J.H., and Woodlock, J.J. (1969) Glycoprotein staining following electrophoresis on acrylamide gels. Anal. Biochem. 30: 148-152. Zhou, K., Pan, H., Yue, H., Xiao, T., and Wu, L.-F. (2010) Architecture of flagellar apparatus of marine magnetotactic cocci from Qingdao. Marine Sciences (Chinese) Accepted.

Figure 1 .

 1 Figure 1. Composition of extracted surface appendages of MO-1 cells .

Figure 2 .

 2 Figure 2. Localization of M1 protein. Specificity of polyclonal anti-M1 antibodies was

Figure 3 .

 3 Figure 3. Reconstitution of the sheath structure.

Figure 4

 4 Figure 4

Table 1 .

 1 Significance of the effect of citrate treatment on smooth swimming of MO-1 cells.

	Treatment 1	Percentage of	Average speed	P value 2
		mobile cells	(µm/s)
	HEPES buffer	(27.3±7.3) %	114±13	3.8891E-11
	HEPES	(7.1±5.5)%	72±16	-
	buffer+Citrate
	F r buffer+Citrate+Mg 2+ o HEPES (25.7±10.8)%	108±13	1.7231E-9
	HEPES	P (25.6±7.0)%	100±12	1.3825E-8
	buffer+Citrate+Ca 2+	r e e
	R 1. Composition of the HEPES buffer and concentration of ions used are described in text. e 2. Two sample t-test of average speed was analyzed by OriginPro 8 software. Each sample was v i w e compared with HEPES buffer+Citrate.
				22

Molecular Microbiology

Acknowledgment

We thank N. Philippe and C. Nicoletti for helpful discussion and suggestion, S. Lignon and R.

Lebrun for proteomic analysis. This work was supported by the grants HFSP RGP0035/2004-C, FRM FDT20080913879 and 'The Project for Extramural Scientists of SKLAB No.

2009SKLAB06-1'.


Thibaud Monteiro
email: thibaud.monteiro@univ-st-etienne.fr

Marie-Claude Portmann
email: marie-claude.portmann@loria.fr

Smaïl Khouider

Evaluation model framework based on simulation for enterprise network negotiation mechanisms

Keywords: performance evaluation, multi-agent system, distributed decision system, supply chain, cooperation, co-decision, negotiation

Currently enterprises are organizing themselves in "new" structures, alternatively called enterprise networks, Virtual Enterprises, Supply Chains. We are interested in enterprise networks in which decision and information systems are distributed. We are searching for a global performance while controlling the architecture with local bilaterally negotiated co-decisions. We propose an architecture based on multi-agent system and the associated protocols, described by statecharts, to ensure as much as possible a global coherence and the convergence of the decision process. We propose models and tools in order to validate our approach by simulation of the multi-agent system. We employ our model on a particular problem in which enterprises are searching complementary resources (stocks, production capacities, components and/or transport capacities) in order to deal with unexpected orders different from the planned forecasting. The simulation considers parameters of the architecture systems in order to define how many unexpected orders must be treated in parallel the goal is to find a good equilibrium between minimization of answer delay and maximization of efficiency.

Introduction

Currently the enterprise environment is characterized by globalisation of commercial exchange and diversification of constituent actors. To survive in this environment, enterprises organize themselves in "new" structures, called enterprise networks or supply chains.

The interest in Supply Chain Management (SCM) or enterprise network management is increasing more and more. This is due to new information technologies as well as powerful communication networks such as internet. These technologies speed up the evolution of information and decision systems. This induces a greater diversification in the usual partner choices (suppliers and/or customers). To obtain sustainable development, the possession of competitive and robust partners is a strategic stake. In enterprise networks, global performance comes from good coordination between all partners as well as from individual partner performance. As a consequence, techniques and methods to model decision making and coordination mechanisms are very useful. The pertinence and the behaviour of such decision models can be evaluated either by analytical or by simulation approaches. Furthermore it will be necessary to design evaluation methods to measure local and global performance.

In this paper, our goal is to propose a generic architecture for the decision system of such enterprise networks. Information and decision systems are distributed. We assume that the decision system is distributed with only local communication between the decision centres, while maintaining a global coherence of the whole decision system. In order to get a first validation of our model by simulation, we consider a particular application: preparing the answer associated to an unexpected order: by "unexpected" we mean very different from the forecasting plans, which had been previously designed by the partners.

The paper is structured as follows. The first Section presents previous works on enterprise relationships analysis in supply chain structures and justifies the contribution of our work. The second Section presents the industrial context and stakes. The third Section proposes the distributed decision architecture and its protocols, in a very generic environment. The last Section focuses on the validation of the simulation. It contains the particular problem description, the instances generation with several scenarios and the simulation results. We end with some conclusions and perspectives.

Previous Works

Many studies focus essentially on enterprise relationships in supply chain structures.

Several works are dedicated coordination of two business units [START_REF] Lavikka | Coordinating the service process of two business units towards a joint customer[END_REF].

Their goal is to increase financial and operational performance while minimising the global cost and size of the inventories (Turkay et al. 2004) [START_REF] Camarinha-Matos | Performance indicators for collaborative networks based on collaboration benefits[END_REF]. In these organisations, the decision making is naturally distributed.

Complex processes are then necessary to get an efficiency level similar to centralised decision mechanisms. This is due to myopic and partial view of each enterprise, who cannot evaluate the global impact of its local decisions. Procedures and coordination rules need to be designed to ensure, as much as possible, an efficient management.

Another difficulty is to control the large increase of information flow exchanges.

Even if it is not easy to measure, global efficiency must be evaluated for distributed supply chains. Performance evaluation must be the main core of any application developed in such distributed systems. [START_REF] Teti | Emergent synthesis in supply network tool management[END_REF] propose a software tool, based on multi-agent, to control a network of enterprises, associated with a flexible tool for management strategies. They develop an economical evaluation. [START_REF] Sarkara | Evaluation of supplier capability and performance: A method for supply base reduction[END_REF] develop a local performance evaluation method for suppliers of a given enterprise. Their aim is to optimise supplier selection, but this optimisation is local only. [START_REF] Reiner | Customer-oriented improvement and evaluation of supply chain processes supported by simulation models[END_REF] illustrates the interest of customer integration in global process in order to maximise the global performance in the supply chain. They propose a dynamic performance evaluation based on simulation where only centralized architectures are considered. [START_REF] Schmitz | Supplier logistics performance measurement: Indications from astudy in the automotive industry[END_REF] present performance measures for concrete supply chains.

They propose an identification method of conceptual frameworks for various configurations of supply chains. Youngui et al. (2004) present a performance evaluation approach which is essentially oriented on the collaboration with suppliers based on stock levels. This collaboration is defined between a supplier and a distributor in a two-level supply chain. [START_REF] Zhejun | An economic evaluation model of supply chain flexibility[END_REF] proposes an economical performance evaluation model in the context of a flexible supply chain.

As illustrated in this rapid review, performance evaluation becomes more and more important for supply chains, when making dimension choices and relationship designs. Nevertheless, literature concerning performance evaluation of cooperative control in distributed decision systems is very poor.

In this paper, we propose a generic distributed decision architecture model based on multi-agent systems. This decision system uses co-decision controlled by negotiation protocols. The proposition is valuated by simulation on a particular decision problem:

we must find a solution quickly enough to handle to unexpected orders. The solution is obtained by bilateral negotiation and requires to find: inventory quantities, production capacities, component availability and transport capacities.

Negotiation issue in enterprise network

In a distributed decision making structure, each entity is considered as an independent decision centre which is capable of modifying the details of its internal processes (i.e.

elected to be included in its activity). Those modifications can, with propagation, impact the others entities of the system. Therefore, in a distributed decision context, it is important to formalize coordination mechanisms able to control this impact. In a global supply chain evaluation, the member-company's internal decisions have to be considered and analysed. This coordination is made by a group of co-decisions based on cooperative behaviours.

Cooperation can be described as a will to act collectively towards a common goal or several compatible goals. In the case of inter-firm industrial flow control, cooperation can be considered as the coordination of means of each company composing the network of the supply chain, to produce goods with the final goal of getting equilibrium between cost, quality and delay conflicts. This coordination must create consistent individual decisions and assume their synchronisation.

Decision making becomes necessary after any change of the environment. A change can be either external to the member-company (direct decision maker's environment), as receiving an unexpected order from a client or occurrence of a problem with a direct provider; or internal, when a new event appears in the company. Here, cooperation includes both collective and distributed decision making, aiming to synchronize actions shared among the different entities. We are in a co-decision context, which intends to coordinate individual actions. [START_REF] Monteiro | Multi-criteria negotiation for a distributed control of a client/provider relationship[END_REF]).

The Petri net (Figure 1) illustrates the mechanism of the decision making. When a demand is initially detected, the Rest token, which indicates there is no negotiation, is consumed. The negotiation phase creates three possibilities of firing. Depending on a feasibility study, decision makers can either continue with negotiation by replying with a proposal, or stop it by replying with an agreement or a refusal. If he receives a proposal, the second partner will determine his possibility of firing.

Coordination quality is related directly to negotiation quality. Those two points must be studied jointly. The first point is related to the internal decision behaviour. Its efficiency is related to mechanisms used to analysed request feasibility. Efficient Customer Response (ECR) tools are dedicated to this analysis. Presentation of this problem is largely treated in (Pujo and Kieffer 2002). In Figure 1, the new demand analysis allows to choose to fire between the three transitions in conflict (grey zone in Figure 1).

Internal decision performance depends also on negotiation cycle control (grey cycle in

Figure 1). As shown by the "answer wait" place of the Petri net, negotiation cycle performance depends also on internal efficiency of the other partners. The second point to be studied is related to interactions induced by inter-firm industrial flow and to network structure. Indeed, when an internal decision cannot be taken, a propagation related to this decision is done. This phenomenon is recursive, and several co-decision cycles could appear.

Figure 2, illustrates this phenomenon of a propagation of one initial co-decision (black arrow, co-decision 1). This propagation has two dimensions. First, it can be in depth when it follows product's macro-bill of material (dotted arrows, co-decision 2 and co-decision 3). Second, it can be in width when it represents multi-supplier strategy or when product's macro-bill of material includes complementary components (dash arrows, co-decision 2'). This propagation phenomenon can be controlled using specific coordination and/or collaboration mechanisms between entities. In this field, [START_REF] Despotin-Monsarrat | Aide à la décision pour une coopération interentreprise dans le cadre de la production à la commande[END_REF] proposes a negotiation model dedicated to coordinate activities between two enterprises. This model is based on a constraint propagation method aiming at harmonizing the decisions of two enterprises of supply chain.

Those two points have to be jointly analysed to evaluate negotiation performance completely. It is important that performance indicators of supply chains are dedicated both to internal decision process (local behaviours) and to the enterprise network (global behaviour). The specificity of our approach is to analyse jointly those points in order to measure simultaneously local and global performances of a supply chain.

This approach provides an enterprise with a larger view of the impact of its local decision on the rest of supply chain.

Proposed Approach

Industrial architecture choice

In this work, the considered enterprise network is composed by several enterprises which are autonomous in their decision making.

Virtual Enterprise (VE) concept has been developed as an improvement of extended enterprise concept. The extended enterprise is presented in [START_REF] Perrin | A model to support collaborative work in virtual enterprises[END_REF].

VE is an ad hoc organisation that joins core competencies and shares its resources to respond to unexpected business opportunities [START_REF] Aerts | A flexible, agent-based ICT architecture for virtual enterprises[END_REF]. A comprehensive review of VE concept is given in [START_REF] Wu | Selection of partners in virtual enterprise paradigm[END_REF]. Contrary to the extended corporation, the VE characterizes a consortium where each member is totally free for local decision making.

Companies, which compose the supply chain are modelled by decision nodes, such as Virtual Enterprise Nodes (VEN) see [START_REF] Ouzizi | A model for cooperative planning within a virtual enterprise[END_REF]. The enterprise network (Figure 3) is represented as a set of tiers (according to the manufacturing bill of materials and to the propagation of component need), in which each partner, defined as a VEN, is in relation with customers and suppliers on the adjacent tiers. A supplier is in an upper tier than its client. It is assumed that each VEN is only in communication with its adjacent VENs (which induces no circuit in the VENs graph).

As a result, each VEN belongs to one tier. This VEN could be as well as a manufacturer, a distribution centre or a carrier. We decide that the upper tier is constituted by carriers (Figure 3). Transport is considered here as service which can be used to move any products between any couples of supply chain partners. Carrier tier is the upper one because it could be called in by all the other network entities.

In order to coordinate those decision centres, negotiation and data exchange mechanisms are integrated in the architecture. The relationship, which controls two direct partners of the network is based on a win-win collaboration policy [START_REF] Ouzizi | A model for cooperative planning using a virtual enterprise[END_REF]. That policy aims at maximising individual partners' benefits in a global agreement.

This enterprise network is modelled as a multi-agent system, in which the agents use cooperative negotiation to establish a global consistent coordination.

VEN 0,1 VEN 0,2 VEN 1,1 VEN 1,2 VEN 1,10 VEN 2,1 VEN 2,3 VEN 2,2 VEN 3,1 VEN 3,2 VEN T,1 VEN T,2 VEN 3,3 VEN 3,4 Tier 0 Tier 1 Tier 2 Tier 3 Carrier Tier VEN 0,1 VEN 0,2 VEN 1,1 VEN 1,2 VEN 1,10 VEN 2,1 VEN 2,3 VEN 2,2 VEN 3,1 VEN 3,2 VEN T,1 VEN T,2 VEN 3,3 VEN 3,4
Figure 3. Model of a network of enterprises.

Generic multi-agent architecture for supply chain management and evaluation

The VEN is the basic component of our architecture. Relationships between two chain partners (suppliers and customers) are located in adjacent tiers. Each company is able to take its own decision without external manager control of the other company. Thus, the architecture is totally distributed.

In our approach, we model VENs using multi-agent architecture. An agent is a combination of reactive software entity and human decision actor, with its own environment and decision making tools. To improve its performance, an agent collaborates with the other entities existing in its environment [START_REF] Luck | A Manifesto for Agent Technology: Towards Next Generation Computing[END_REF]). The VEN is a meta-agent, which is composed with three types of software agents. They collaborate with each other to achieve the company goals (Figure 4):

• The Negotiation Seller Agent manages and negotiates sales;

• The Negotiation Buyer Agent manages and negotiates purchases operation;

• The Negotiation Planner Agent manages production plans.

Each of these agents is a simple reflex agent [START_REF] Luck | A Manifesto for Agent Technology: Towards Next Generation Computing[END_REF] NSA is activated by a message, which comes from an external or an internal agent.

When activated, NSA manages all required specific actions. Decision making is based on its own databases and its own sale tools. Activation messages, called a in Figure 5, are:

• New product request from client (external NBA);

• Modification request of a previous agreement. Modifications could come from a client or from an internal NPA; • New product proposal from an internal NPA.

The Negotiation Planner Agent (NPA)

The Negotiation Planner Agent provides forecasted planning and finished product availability. The main function of this agent pattern is to manage and negotiate VEN production planning. If necessary, it contacts directly the two other VEN agents. It uses either planning software pre-existing in the company or imposes the design of planning rules. This agent is activated in the same way as NSA. Activation messages, also called a in Figure 5, are:

• New production planning request from a NSA; • Modification request of a previous planning agreement. Modifications could come from an internal NSA or NBA.

The Negotiation Buyer Agent (NBA)

The Negotiation Buyer Agent manages and negotiates purchase operations. NBA contacts negotiation planning agents and several external sale agents directly (its suppliers). The main function of this agent pattern is to manage VEN external resource acquisition. Resources could be components (example: raw materials) or services (example: transport or subcontracting). Messages that activate those agents are (also called a in Figure 5):

• New resource request from a NPA;

• Modification request of a previous supply agreement. Modifications could come from an internal NPA or an external NSA.

For the decision making NBA can use its own data bases and several supply tools. For example, some authors have designed mathematical linear models and proposed tools for decision making in various NBA problems such as, supplier selection [START_REF] Khouider | Suppliers searching tool in cooperative supply-chain management[END_REF], carrier selection (Khouider et al. 2006a), palliative supplier research (Khouider et al. 2006b) or consistent supply chain plans negotiation [START_REF] Ouzizi | Planification de la production par co-décision et négociation de l'entreprise virtuelle[END_REF])

VEN internal treatment

As we said previously, the three negotiator agents, buyer (NBA), planner (NPA) and seller (NSA), have a similar internal behaviour. Statechart modelling helps understanding the negotiation process within agents. The agent behaviour is illustrated with a generic statechart (Figure 5) where only events and internal processes differ between each other.

External flows for a cooperative decision

An example of treatment of a new command is presented Figure 6. We consider a company VEN 2.1 with its client VEN 1.1 and its two providers VEN 3.1 and 3.2 (see Figure 3). 5) A_NSA2 (6') A_NBA1 (5,1) A_NPA1 (5,2) A_NBA1 (5,3) A_NSA1 (5,4) A_NSA1 ( 6) A_NPA ( 7) A_NSA ( 8)

NBA NSA NPA NBA NSA VEN1,1 VEN2,1 VEN3,1 VEN3,2 NBA NSA NPA NBA NSA VEN1,1 VEN2,1 VEN3,1 VEN3,2 R_NBA (1) R_NSA (2) R_NPA1 (3) R_NPA2 (3') R_NBA1 (4) R_NBA2 (4') A_NSA2 (5') A_NSA1 (
OK OK OK OK OK PROP1 PROP1 PROP2 PROP2
Agent is waked up and placed on hold Agent is waked up and killed Awake agent is kept on hold Awake agent is killed NSA sends a request to its Negotiator Planner Agent (message 2). This message wakes NPA up and NSA start waiting. Thus, the first co-decision initiated with message 1 is propagated in depth with messages 2, 3 and 4, and is propagated in width with message 3'. Performance of this cooperative decision is related to those propagations. For example, NPA (VEN2,1) waken by message 2 has to obtain two agreement messages (6 and 6') before local decision making. In this example, the first co-decision generates five other co-decisions and requires fourteen messages.

Illustration on some co-decision problems linking to supply chain control

In many networks, each business unit or entity plans its operation locally. Several reasons support this approach. Demand and supply of information is widely spread within the network. This information is continually changing as the business environment is stressed by many internal and external factors. The quantity of information to deal with is still too large in some instances to make a feasible centralized planning process. However, this decentralisation raises some interesting questions. They emerge from the difficulty to synchronize the planning and coordinating decisions without an extensive share of information that would be found in a centralized approach. This section addresses this issue though the proposed distributed approach, based on multi-agent paradigm.

The first part deals with cooperative tactical planning by proposing a method to consider contingency in supply chain. This is a middle term problem.

The second part of this section describes a short term problem with an approach to manage unexpected orders. Even if it is a short term problem, its design is a strategic problem that could be solved with a simulation approach.

Unexpected order satisfaction is our main contribution in this paper. So, cooperative tactical planning is presented in this paper in order to illustrate its connection with unexpected order satisfaction problem. Cooperative tactical planning is more detailed in [START_REF] Ouzizi | Planification de la production par co-décision et négociation de l'entreprise virtuelle[END_REF].

Cooperative tactical planning

Each VEN of the first tier collects information about future sales from the customers, generally with an estimation of uncertainty. The forecasts are transmitted to all the VENs of the supply chain. It is assumed on one hand that agreements are signed between VENs of the first tier and customers, and on other hand between partners of the SC. Thus, it is assumed that information is always shared truthfully (trusted relationships) (Gavirneni et al. 1999, Cachon and[START_REF] Cachon | Contracting to assure supply: how to share demand forecasts in a supply chain[END_REF]. On the basis of forecasting data and contracts established, each VEN makes its planning. In the event of unforeseen production problems of a VEN, or of forecasting change, it must commit with its current customer and supplier VENs, so that they try to overcome the problem collectively, which ensures the continuity of the production and global nonstop of the manufacturing chains.

Using a rolling horizon [START_REF] Ouzizi | A model for cooperative planning using a virtual enterprise[END_REF], the VENs do the planning with new forecasting (Figure 7). It is assumed that, (1) in the last unit of time, planning over the supply chain are negotiated and coherent, (2) at the beginning of the next period of planning, each VEN of the first level must readjust its planning according to the demands variation for finished product, or of possible risks that can occur during the period.

Thus, the consequences are:

• To correct forecasts of finished products from the period 1 to T-1 (these forecasts are the same corresponding to periods 2 to T with corrections) • To add a new forecast for the period T • To update inventories of all upstream and downstream components of the supply chain. The problem for each VEN is to determine if it is sufficient to add one period for the planning in order to cope with variations or if it is necessary to increase or decrease the previous planning so as to find coherent and negotiable planning [START_REF] Roy | Multi-agent architecture for supply chain management[END_REF].

In theory, each VEN is faced with internal constraints which relate to its capacity limits, and with external constraints which relate to both:

• The customer VENs. These require products that have for example, minimal delays or low costs, • The supplier VENs. With similar constraints of lead times, costs, etc.

Two VEN scenarios are possible in relationship to the VEN capability to make or not a request. The first scenario is when there is no problem of consistency. In this case, the VEN is only used to propagate the needs of the client to supplier requests. The second scenario is when a local problem occurs. In this case, it is necessary to initiate a negotiation process. To cope with those issues and in the case of unexpected orders, the following section presents the problem and details a method to solve it. The following section presents the issues related to these two scenarios, as well as a solution method. It focuses on the case of unexpected orders.

The problem of unexpected order satisfaction

Description of the decision problem

Unexpected orders (Kouider 2008) are linked to firm orders which differ by the plans that were established by the process of middle-term decision. The difference in firm order could result from two factors. First, the firm order does not respect the established plan in relation to quantities or delays. Second, an urgent non-planned order occurs. Even if those situations are singular, unexpected orders are still the principal cause of supply chain performance deterioration. The bullwhip effect is one of the most known consequences of these situations [START_REF] Moyaux | Multi-Agent Coordination Based on Tokens: Reduction of the Bullwhip Effect in a Forest Supply Chain[END_REF].

In case of a new order arrival, i.e. a customer sends a planed (or not) product order to the company, the company needs to perform some operations before introducing the new order in the production planning such as transportation, product and purchase plans (Figure 8). To satisfy the order, ones need to verify with existing inventories of finished products. If more production is required the planning must be modified and the company has to reconsider two of its capacity aspects. First, the company needs to verify the availability of inside capacities, such as product, reception and loading capacities. Second, the company needs to verify the availability of outside capacities, such as component and transportation capacities.

To manage all these capacities constraints, we use the modelled VEN presented in

Integration of unexpected order

We present typical examples of decision problem. For decision making, it is possible to analyse the integration of unexpected order with only internal process or, if it is necessary, with external propagation requests (Figure 9).

We present here two categories of external problems: a component supply problem and a problem that relates to find and organize supply or distribution transport (transport problem). In the component problem case, an arrival of new order induces new production and insufficient quantities of components are in inventories. In the transport problem case, the company has to deliver or transport products to the customers.

We take the example where the company needs some components and transports in order to deliver the order. Therefore, the ordered quantity is insufficient in the product inventories, even though there is enough production capacity (component problem).

The internal transportation capacities are insufficient (transport problem).

The company contacts its suppliers and transportation capacity suppliers (carriers) to provide the missing components and to carry, totally or partially, the ordered quantity to the customer (Figure 9).

Design of cooperation mechanism

In order to efficiently manage those co-decisions, it is important to set up specific parameters that are related to cooperation mechanisms. Many approaches exist to deal with the supply chain management. Those approaches aim to ensure decision coherence among the network and to allow an efficient collaboration to guaranty the supply chain survival and stability. In order to analyze the negotiation performance in such a system [START_REF] Khouider | Cadre de modélisation pour évaluation par simulation des mécanismes de négociation dans les entreprises en réseau[END_REF], we propose to use the modelling framework as a simulation tool. Some specific parameters need to be defined to be able to evaluate the supply chain performance. Those parameters can be classified in two different fields: the network architecture and the negotiation process. From the point of view of the architecture, the network nature (number and size of tiers) or the supply strategy (mono or multi sourcing) are relevant. From the point of view of the negotiation process, the maximum number of exchange flows for a negotiation, or the number of proposition and scenario which are simultaneously treated, are analysed.

The expected measures are linked to generated information flows and to the success of cooperation and coordination. Finally, the allocated time to achieve decision is also taken into account (Figure 10). Indeed, it is important to have decisional parameter for an agile supply chain.

Example of simulation for multi-negotiation parameter

In order to illustrate the cooperation design based on simulation, we specifically look at the negotiation setting. In this example, we search to define negotiation parameter of the VEN 2.1 (greyed in Figure 11) for its Negotiator Seller Agents. We assume in this simulation that the product used is bought by ten different clients (VEN 1.1 to VEN 1.10). Therefore, a maximum of ten unexpected orders could occur for the same period. The product is composed by two different components, and each component is supplied by two suppliers (VEN 3.1 to VEN 3.4). Face to clients' requests, we compare two possible strategies that depend on how the orders are treated. First, orders are considered sequentially and separately. This way allows us to avoid resource reservation conflicts. This strategy guaranties no refusal errors. Indeed, in case of rejection due to incompatibility of a production plan, raw material or component supply, we are sure that this analysis is always well-founded.

However, separately analysis could cause the loss of some orders due to the increase in delay of the last orders. Moreover, the results (acceptations or refusals) depend on the sequence analysis of the orders. The second strategy is to treat some orders at the same time. This allows us to take simultaneously into account N numbers of orders.

The propagations that correspond to each order are independent and are treated by distinct agents. To prevent simultaneous use of the same resources, the information system includes both definitive and temporal reservations (as it is the case for classical "online" reservation systems).When one negotiation ends, another one can start to be analyzed. An acceptation or refusal sending ends the negotiation. This second strategy allows parallel analysis of orders and therefore provides smaller waiting times than the first strategy. In the second strategy, the response time creates thus less order lost. However, this strategy has a bigger risk with refusing an order, due to parallel temporal resource reservations. This same order could be accepted with a valid analysis as in the first strategy. In this second strategy, it is important to analyze the relations between the maximum number (N) of simultaneous treated orders, the response time and the decision pertinence.

Instances generation and simulation [START_REF] Khouider | Outils d'aide à la décision pour la prise de commandes imprévues[END_REF] presents a complete simulation project on both strategies, realized on the unexpected order problem. Here, we look at the enterprise network problem (figure 11). We consider the case where the bill of material for the product requires all the partners of the supply chain and where associated needs of capacities have already been generated. An initial state has also been generated for the resource availability with various scenarios which depend on the importance of idle capacities. Orders are also randomly generated with identical values among all simulations. A set of experiments have been realized with N=1 (first strategy) and N varying from 2 to 6 (second strategy). In the simulations, the decisions of VEN2.1, our studied node, are made using linear programming tools, while answers of other nodes are randomly generated.

From the point of view of response time (Figure 12), the simulation results show a direct relation between negotiation parallelization (N) and treatment quickness. It results that negotiation parallelization is a crucial parameter for negotiation agility.

There is, nevertheless, a limit on this parallelization impact on the response time reduction (asymptote at around N = 4, Figure 12). From the point of view of lost orders, as shown in Figure 13, a relation also exists, between the negotiation parallelization and loss of orders. This loss is due to two factors. First, a loss of order can result from an over delay response (response time in Figure 13). The impact of this factor decreases with parallelization growing. Second, the lost order could be caused by an over temporal reservation (false lack of resources in Figure 13). In this case, the impact of this factor increases with parallelization growing. It exists an equilibrium between those two factors which defines an optimal set of parameters. In the example presented in Figure 12, four parallel co-decisions give the best performance. To efficiently manage negotiation in the supply chain, a maximum of four negotiator agents should be set up in VEN 2.1.

Conclusion

The evaluation of the negotiation performance inside a supply chain is becoming more and more complex and requires better strategy of management. In this paper, we propose a co-decision distributed architecture system based on multi-agents. The system can be effectively used by supply chain managers. We employed this architecture on a particular negotiation problem in order to simulate negotiation protocols and to consider corresponding parameters in the case of parallel negotiation.

We illustrated how we can consider in parallel several demands in order to improve negotiation performance and how to limit the number of adequate negotiators in order to assume the negotiation convergence. Our aim is to give performance indicators, by analyzing the behaviour of this decision architecture, in order to help the enterprises to collaborate efficiently using this negotiation model. The obtained results show clearly that the use of parallel negotiations improves convergence and reduces the negotiation volumes in a given configuration of a distributed supply chain.

In the near future, negotiation mechanism analysis would be extended to consider other parameters. For example, in order to increase the chance to find a solution, different planning scenarios could be analysed for one demand. All those scenarios are treated in parallel, probably inducing similar problems to those found in parallel negotiations. Another way to reduce refusals in a parallel strategy is overbooking policy, however with this policy, negotiators could accept a demand that they are not able to satisfy. This policy has to be configured with care. All these new negotiation mechanisms and associated parameters aim to find a good equilibrium between the quality of the co-decisions and the allocated time to keep agility in enterprise networks.

Figure 2 .

 2 Figure 2. Recursive propagation of negotiation.

Figure 5 .

 5 Figure 5. Statechart of the generic behaviour of an agent.

Figure 6 .

 6 Figure 6. Swimlane illustrating a global view of cooperative decision.

Figure 7 .

 7 Figure 7. Rolling horizon for planning.

Figure 4 .Figure 8 .

 48 Figure 4.

  The first co-decision, identified by message 1 (Customer order) and 12 (Confirmation of order) in Figure9, requires five other co-decisions. The first induced co-decision concerns an internal negotiation between NSA and NPA with message 2 (NSA production demand) and message 11 (NPA confirmation of demand). This codecision generates, by propagation in width, two other co-decisions. One propagation concerns the component search (message 3 and 6). The other propagations concern the search for finish products transport (message 7 and 10). Those two last internal negotiations between NPA and NBA are propagated in depth with two external negotiations between NBA and suppliers' NSA (message 4/5 and 8/9). Example of a resolution mechanism.

  Figure 10. Allocated time in order generation based on negotiation.

Figure 11 .

 11 Figure 11. Network of enterprises used in the simulation.

Figure 12 .

 12 Figure 12. Time to reply analysis.

Figure 13 .

 13 Figure 13. Lost of orders analysis.

  When several requests came in the same time VEN will initiate, for example, as many Negotiation Seller Agents as necessary to take into account those requests. All those agents work simultaneously. In that situation, we are in presence of It is used also to describe internal behaviours of NPA and NBA. Indeed, even if main function and goal are different, internal behaviours are similar.

	parallel demand processing. Those meta-agents are connected in our multi-agent
	architecture. Each agent is equipped with environment communication abilities
	regrouped in a communication platform.
		Rules and tools
		for coordination
	Negotiation Buyer Agents	Negotiation Planner Agents		Negotiation Seller Agents
	Tools for optimization	Rules and tools for planification	Planification tools ERP..	Tools for sale
	and negotiation			supervision
		Communication platforms
		Communication platforms	Human actor
		Information flow	Connection with rules
	Figure 4. Internal VEN structure.

. Even if agents use decision making tools based on operational research models and tools, induced actions are predetermined. Agent activation results from a change in its direct environment. The Negotiation Seller Agent (NSA) The Negotiation Seller Agent manages and negotiates sales. NSA contacts directly internal Negotiation Planner Agents and several external Negotiation Buyer Agents (its customers). The main function of this agent pattern is the management of VEN sale processes. When a request occurs, one specific NSA is activated. It can reply directly with a proposal, with an agreement or with a refusal. If necessary, it can propagate this request to other agents before making a decision. If two requests occur during the same time period, two specific NSA are activated. Those agents share enterprise resources. Conflicts can appear between those two decision processes.

Figure 5 illustrate, with a statechart, the internal behaviour of NSA. This behaviour is voluntarily generic.

Table 1 .

 1 Messages correspond to different state of negotiation with downstream or upstream agents. The first line (table head) identifies agents that receive messages. R_NPA denotes a request coming from a NPA. A_NSA denotes an answer coming from a NSA. Two local decision situations exist. If NPA has all the information needed to make decision, then a local decision is possible. If not, then a local decision is not possible and the agent has to propagate the request. The following is a set of events and messages which can modify agent state

	(Table1):
	message NBA	NPA	NSA	comments
	a -	R_NPA	R_NSA	R_NBA	Request which makes agent to wake
		R_NSA	R_NBA	R_NPA	up
	b	R_NPA R_NSA R_NBA Upstream request
	c	R_NSA R_NBA R_NPA Downstream request
	d	Local decision possible
	e	Local decision impossible
	f -	A_NBA A_NPA A_NSA Proposal to upstream
	g -	R_NBA R_NPA R_NSA Request propagation to downstream
	h	Local decision impossible
	i	Local decision possible
	j -	R_NBA R_NPA R_NSA Request propagation to upstream
	k -	A_NBA A_NPA A_NSA Proposal to downstream
	l -	A_NSA A_NBA A_NPA Downstream answer
	m -	A_NPA A_NSA A_NBA Upstream answer
	n -	A_NBA A_NPA A_NSA Answer (ok, /ok) to upstream
	o -	A_NBA A_NPA A_NSA Answer (ok, /ok) to downstream

Table 1 .

 1 Messages and internal events.

Acknowledgements: A part of this paper has been presented at the conference MOSIM'08 organized by S. Lamouri and A. Thomas, held in Marsh 2008 at Paris, France.