MultiNoC: A Multiprocessing System Enabled by a Network on Chip

Aline Mello, Leandro Möller, Ney Calazans, Fernando Moraes Faculdade de Informática -PUCRS -Av. Ipiranga, 6681, Porto Alegre, Brazil {mello, moller, calazans, moraes}@inf.pucrs.br

Abstract

The MultiNoC system implements a programmable onchip multiprocessing platform built on top of an efficient, low area overhead intra-chip interconnection scheme. The employed interconnection structure is a Network on Chip, or NoC. NoCs are emerging as a viable alternative to increasing demands on interconnection architectures, due to the following characteristics: (i) energy efficiency and reliability; (ii) scalability of bandwidth, when compared to traditional bus architectures; (iii) reusability; (iv) distributed routing decisions. An external host computer feeds MultiNoC with application instructions and data. After this initialization procedure, MultiNoC executes some algorithm. After finishing execution of the algorithm, output data can be read back by the host. Sequential or parallel algorithms conveniently adapted to the MultiNoC structure can be executed. The main motivation to propose this design is to enable the investigation of current trends to increase the number of embedded processors in SoCs, leading to the concept of "sea of processors" systems.

Design Overview

This work presents the implementation of multiprocessing systems, connected through a NoC. According to ITRS estimation, in 2012, SoCs will have hundreds of IP cores, operating at clock frequencies near 10 GHz. In this context, a Network-on-Chip (NoC) [START_REF] Benini | Networks on chips: a new SoC paradigm[END_REF] appears as a possible solution for future on-chip interconnections. A NoC is an on-chip network composed by IP cores connected to routers, which are interconnected by communication channels. Another motivation to present this design is the current trend to increase the number of embedded processors in SoCs, leading to the concept of "sea of processors" systems [START_REF] Henkel | Closing the SoC Design Gap[END_REF].

MultiNoC comprises four IP cores connected to the NoC, as illustrated in Figure 1:

• 2 R8 embedded processors. R8 is a load-store 16-bit processor architecture, containing a 16x16 bit register file, and supporting execution of 36 distinct instruc-tions. Each R8 processor has an attached local memory for program and data (1K 16-bit words), acting as a unified cache.

• 1 memory IP, implemented with 4 BlockRAMs, resulting in a capacity of 1024 16-bit words.

• 1 RS-232 serial IP, providing bi-directional communication with a host computer.

The MultiNoC system is a NUMA (non-uniform memory access) architecture, in which each processor has its own local memory, but can also have access to memory owned by other processors, or to remote memory.

The external interface of the MultiNoC system comprises 4 signals: (i) reset, responsible to initialize the Mul-tiNoC system; (ii) clock, a basic synchronization signal; (iii) tx, data from the host computer to the MultiNoC system; (iv) rx, data from the MultiNoC system to the host computer. The limitations imposed to the current version of the system arise from the employed FPGA area restrictions, as well as from the choice of using serial low cost, low performance external communication. The approach can be extended to any number of processor IPs and/or memory IPs, using the natural scalability of NoCs. It can also be adapted to faster external interface protocols, such as USB, PCI, Firewire, etc.

MultiNoC System

Serial

Detailed description

The next Sections present in detail each of the Multi-NoC IP cores.

Hermes IP core

The Hermes NoC employs packet switching, a communication mechanism which packets are individually routed between cores, with no previously established communication path [START_REF] Guerrier | A generic architecture for on-chip packet-switched interconnections[END_REF]. The wormhole packet switching mode is used to avoid the need for large buffer spaces [START_REF] Mohapatra | Wormhole routing techniques for directly connected multicomputer systems[END_REF]. The routing algorithm defines the path taken by a packet between the source and the destination. The deterministic XY routing algorithm is employed.

The Hermes NoC follows a mesh topology, justified to facilitate routing, IP cores placement and chip layout generation. The routers in MultiNoC use an 8-bit flit size, and the number of flits in a packet is fixed at 2 (flit size in bits) . The first and the second flits of a packet are header information, being respectively the address of the target router, named header flit, and the number of flits in the packet payload. An asynchronous handshake protocol is used between neighbor routers. The physical interface between routers is composed by the following signals:

• tx: control signal indicating data availability;

• data_out: data to be sent; The control logic implements the routing and arbitration algorithms. When a router receives a header flit, arbitration is performed, and if the incoming packet request is granted, an XY routing algorithm is executed to connect the input port data to the correct output port. If the chosen port is busy, the header flit, as well as all subsequent flits of this packet, will be blocked in the input buffers. The routing request for this packet will remain active until a connection is established in some future execution of the procedure in this router. When the XY routing algorithm finds a free output port to use, the connection between the input port and the output port is established. After routing all flits of the packet, connection is closed. At the operating frequency of 50MHz, with a word size (flit) of 8 bits the theoretical peak throughput of each Hermes router is 1Gbits/s.

A router can establish up to five connections simultaneously. Arbitration logic is used to grant access to an output port when one or more input ports require a connection at the same time. A round-robin arbitration scheme is used to avoid starvation.

When a flit is blocked in a given router, the performance of the network is affected, since several flits belonging to the same packet may be blocked in several intermediate routers. To lessen the performance loss, a 2-flit buffer is added to each input router port, reducing the number of routers affected by the blocked flits. Larger buffers can provide enhanced NoC performance. Multi-NoC employs small buffers to cope with FPGA area restrictions. The inserted buffers work as circular FIFOs.

The minimal latency in clock cycles to transfer a packet from source to destination is given by: ( )

2 1 × + = ¦ = P R latency n i i
where: n is the number of routers in the communication path (source and target included), R i is the time required by the routing algorithm at each router (at least 7 clock cycles), and P is the packet size. This number is multiplied by 2 because each flit requires at least 2 clock cycles to be sent, due to the handshake protocol. The Hermes NoC in the MultiNoC system internally supports nine distinct packet formats, which define a set of services offered by the communication network to the IP Cores connected to it. The packets denominations/ functions are: 1. read from memory, is used to request data from memory; 2. read return, response for a read request from memory; 3. write in memory, is used to store data into some memory of the system; 4. activate processor, initiates the processor, that then starts executing instructions from the first position of its local memory; 5. printf, is used by processors to send data to the host computer; 6. scanf, is used by processors to request user input data from the host computer; 7. scanf return, receives the requested input data from the host computer; 8. notify, is used to wake up a processor that has been blocked by a wait command; 9. wait, blocks a processor until being notified.

Serial IP core

The Serial IP Core is responsible to provide communication between the user working in a host computer the modules of the system connected through the NoC. This communication is performed by an RS-232 protocol standard serial interface. The basic function of the Serial IP is to assemble and disassemble packets. When information comes from the host computer, the Serial IP creates a valid NoC packet. When a packet is received from the NoC it must be disassembled, and sent serially to the host computer.

The Serial IP accepts seven commands. Four commands are handled by the host computer: (i) read from memory; (ii) write to memory; (iii) activate processor; (iv) scanf return. The other three commands accepted by the serial IP come from the HERMES NoC to the host computer: (i) printf; (ii) scanf; (iii) read return.

Memory IP core

The Memory IP core provides storage for data and/or instructions, and can be accessed through the processormemory bus or through the NoC. Three Memory IP cores are used in the MultiNoC system: two are internally connected to an R8 processor to form the processor IP core and one is an independently accessible remote memory.

Each Memory IP contains 4 BlockRAM modules, each organized as 1024 4-bit words, and control logic to arbitrate the access to the memory banks. Figure 4 shows the external interface of the Memory IP core and the Block-RAMs organization. The access to the memory banks is done in parallel, reading and writing 16-bit words. This access may be done by the processor interface or the NoC interface. The processor interface is not existent in the remote memory IP core.

The memory IP external interface is composed by the following signals:

• clock: system clock (not shown in Figure 4).

• reset: when asserted, initializes the control logic (not shown in Figure 4). • addressCore: system address provided to this IP (not shown in Figure 4). • tx, data_out, ack_tx, rx , data_in, ack_rx: interface with the HERMES NoC • interface with the processor:

-ceR8: enables the memory to read/write operations.

-rwR8: read or write operation selection.

-addrR8: processor address bus (16-bit).

-dinR8: processor input data bus (16-bit).

-doutR8: processor output data bus (16-bit).

- The busyNoCR8 and busyNoCMem are responsible to prevent the processor and the memory from using the same interface with the NoC simultaneously. The highest priority to access the memory banks is given to the processor.

Processor IP core

The Processor IP external interface, as well as its two main internal modules, is presented in Figure 5. The Processor IP includes the R8 soft core processor [START_REF]R8 Processor: Architecture and Organization[END_REF]; a Memory IP, acting as a unified cache; control logic responsible for interfacing these modules to the HERMES NoC. The R8 soft core processor was chosen due to its simplicity, low area footprint and flexibility to be modified.

The R8 processor is a 16-bit Von Neumann architecture (unified instruction/data memory), with a CPI (Clocks Per Instruction) between 2 and 4.. The datapath contains 16 general purpose registers, an instruction register (IR), program counter (PC), stack pointer (SP), and 4 status flags (negative, zero, carry and overflow). The Processor IP control logic commands the execution of the R8 processor, putting it in wait state each time the processor executes a load-store instruction (see waitR8 signal in Figure 5). Load-store operations can access: (i) the local memory; (ii) a remote memory; (iii) I/O devices; (iv) other processors, for synchronization purposes. The next 3 Sections detail these different access modes.

Memory Accesses

To determine which device of the MultiNoC system the R8 processor is accessing by load-store instructions, address ranges were defined to each memory. The address ranges for the MultiNoC system are presented in Figure 6.

I/O Operations

The I/O operations are mapped to the FFFFh memory address. Thus, when the ST instruction is executed the printf is performed and when the LD instruction is executed the scanf is performed.

Synchronization Operations

Multiprocessor systems require synchronization mechanisms among processors to implement distributed applications. The synchronization among processors can be done through shared memory or explicit message exchange. The second mechanism was chosen due to the use of NoCs,.

The Processor IP control logic implements the wait and notify commands, both memory-mapped. The wait command is responsible to block the execution of the proces-sor until the reception of a notify command. The wait command is identified through the execution of a store instruction (ST) at address FFFEH with the number of the processor that will restart the processor executing ST with a notify command. The notify command is identified through the execution of ST at address FFFDH with the number of the processor that will be restarted.

For example, when the R8 processor with address 1 executes the instruction "ST R3, R1, R2" (R3=2, R1=0, R2=FFFEH), the Processor IP control logic pauses the R8 processor until receiving a packet with a notify command from the IP with address 2. The R8 processor with address 2 should execute "ST R3, R1, R2" (R3=1, R1=0, R2=FFFDH) to create the notify command.

System prototyping

The target device is a Spartan-IIe XC2S200E [11]. The MultiNoC system uses 98% of the available slices and 78% of the LUTs. It is important to stress the value of floorplanning in designs using most of the FPGA surface. This generates a complex optimization problem that had to be solved. The use of synthesis and implementation options alone was not sufficient to make the design fit in the restricted area of the XC2S200E device. Even multiple choices of alternate synthesis parameters could not handle the 98% occupation of the design adequately. Figure 7 illustrates the MultiNoC system floorplan design that enabled physical synthesis to be successful. The original clock of the prototyping board, 50MHz, was divided by two, using a clkdll component. The frequency was reduced, due to the delay estimated by the timing analysis tool, 21.23 MHz. Despite the fact that the employed frequency is higher (25 MHz), the circuit worked correctly.

The NoC area can be seen to be an important part of the design when compared to the other IPs. In fact, NoCs trade increased bandwidth (and performance) for increased area. However, NoCs are in principle designed for much bigger systems than this prototype. It is not uncommon to consider that NoCs are a feasible communication medium for systems containing more than a hundred IPs (e.g. 10x10 NoCs) [START_REF] Kumar | A Network on Chip Architecture and Design Methodology[END_REF]. When more area is available, the IPs connected to the NoC can increase in area and functionality. The router surface will remain constant and the NoC dimensions will scale less than the IPs, becoming a very small fraction of the whole system, typically less than 10 or 5%. • Simulate the Assembly Code. The R8 Simulator environment [START_REF]GAPH -Hardware Design Support Group. R8Simulator[END_REF] allows writing, simulating and debugging assembly code, generating automatically the object code that must be opened in the current version of the Serial software to send it to the R8 processor. Unfortunately, the R8 Simulator is not able to simulate a multiprocessed application. • Start the Serial Software. The Serial software [START_REF]GAPH -Hardware Design Support Group[END_REF] enables the host computer to communicate with the Spartan-IIe device. • Synchronize SW/HW. The MultiNoc system must receive from the Serial software the host computer baud rate, to correctly receive/send data. This is achieved transmitting the value 55H to the MultiNoc system. • Send Generated Object Code. The text file obtained after the application simulation is sent to the MultiNoc system using the Serial software. • Fill Memory Contents. Optionally, data may be also sent to the remote memory or the local memories of the MultiNoC. This process of sending data to the memory is similar to sending the object code to the instruction memory. • Activate Processors. The system is now ready to execute the application, since program and data are stored. This action is achieved by sending a specific command through the Serial software (activate processor command). • I/O Operations. In order to execute I/O operations, the Serial software has interaction monitors for each processor. Figure 9(2) presents a monitor with input/output operations indicating the result of an application execution. • Debug. There are two ways of verifying the prototype correct functionality. One is directly reading memory values (step 1 in Figure 9) and the other is using printf instructions executed by some processor (step 2 in Figure 9). Printf instructions are part of the application code and can help verifying intermediate values.

System execution

Memory reads can be used to verify the memory contents at the end of the execution. In the example presented in Figure 9, the user has typed "00 01 01 00 20", meaning a read operation (00) from P1 processor local memory (01), reading just one memory position (01) and starting at address 0020H.

The software of Figure 9 is used for basic communication with MultiNoC system. More complex applications have been developed. One example is a parallel edge detection which uses basic functions of the Serial software to construct more powerful user interfaces. For demonstration purposes, consider the GUI presented in Figure 10. In this application the host computer sends an image line, after what each embedded processor computes one gradient (gx and gy). Next, that embedded processor adds gx and gy and notifies the host, which receives the processed line, and sends a new line to the MultiNoC system.

Conclusions and future work

The MultiNoC system is in fact an exercise of implementing and making available a design platform on top of which applications can be effectively and rapidly prototyped. This is indeed a recently proposed new design paradigm called platform based design, as opposed to existing paradigms, system level design and component based design [START_REF] Keutzer | System-level design: orthogonalization of concerns and platform-based design[END_REF].

Future research with the MultiNoC system includes the development of a multiprocessor simulator. This tool is important to detect distributed application errors and to synchronize software running on different processors. Another important tool is a C compiler to automatically generate R8 assembly code, allowing faster software implementation.

Mapping the MultiNoC system in a larger FPGA device would allow increasing the NoC dimension and the number of IPs connected to it. This new system can be composed by more instances of the presented predesigned and pre-verified IP cores, adopting the concept of design reuse, or by implementing new IP cores. Increasing the number of identical IPs enhances the parallelism degree. On the other hand, increasing the amount of different IPs contributes with new functionalities to the MultiNoC system.

One of the current research foci is on partial and dynamic reconfiguration applied to the MultiNoC system. Partial and dynamic reconfiguration allows, for example, that the IP cores position be modified in execution at runtime, favoring the IPs communication with improved throughput. Reconfiguration can also be used to reduce system area consumption through insertion and removal of IP cores on demand.

The MultiNoC system can be very useful to undergraduate/graduate students for learning concepts arising in hardware description languages, distributed systems, parallel processing hardware development environments, prototyping designs and applying digital systems concepts to related disciplines. Additionally, the MultiNoC system has a low area overhead, being able to be prototyped in small devices, decreasing the cost to be acquired in large numbers for academic laboratories.

Figure 1 :

 1 Figure 1: MultiNoC system block diagram.

Figure 2 :

 2 Figure 2: Hermes router architecture. B indicates input buffers.

Figure 3 Figure 3 :

 33 Figure 3: Serial IP external interface.

Figure 4 :

 4 Figure 4: Memory IP block diagram.

Figure 5 :

 5 Figure 5: Processor IP block diagram.

Figure 6 :

 6 Figure 6: C code illustrating the access to local/remote memories. The Processor IP control logic arbitrates which memory block is accessed.

Figure 7 :

 7 Figure 7: MultiNoC design floorplan. The reasoning behind the placement design of the IPs is justified as follows: • the NoC IP is placed in the middle of the FPGA, offering easy access to it from all IPs in the system; • the Serial IP is placed next to the I/O pins responsible for the data transmission/reception to reduce global wire length and routing congestion; • the Processor IPs are placed in the left/right side of the FPGA, near to the corresponding BlockRAMs for the same reason of the previous item; • the Memory IP (the smallest IP) is placed in the remaining area.

Figure 8

 8 Figure 8 illustrates the data flow to execute the Multi-NoC system. The main steps of this flow are detailed below.• Simulate the Assembly Code. The R8 Simulator environment[START_REF]GAPH -Hardware Design Support Group. R8Simulator[END_REF] allows writing, simulating and debugging assembly code, generating automatically the object code that must be opened in the current version of the Serial software to send it to the R8 processor. Unfortunately, the R8 Simulator is not able to simulate a multiprocessed application. • Start the Serial Software. The Serial software[START_REF]GAPH -Hardware Design Support Group[END_REF] enables the host computer to communicate with the Spartan-IIe device. • Synchronize SW/HW. The MultiNoc system must receive from the Serial software the host computer baud rate, to correctly receive/send data. This is achieved transmitting the value 55H to the MultiNoc system. • Send Generated Object Code. The text file obtained after the application simulation is sent to the MultiNoc system using the Serial software. • Fill Memory Contents. Optionally, data may be also sent to the remote memory or the local memories of the MultiNoC. This process of sending data to the memory is similar to sending the object code to the instruction memory. • Activate Processors. The system is now ready to execute the application, since program and data are stored. This action is achieved by sending a specific command through the Serial software (activate processor command).

Figure 8 :

 8 Figure 8: MultiNoC system flow diagram.

1 2 Figure 9 :

 129 Figure 9: Two ways of debugging the MultiNoC system: 1) read operation; 2) printf operation.

Figure 10 :

 10 Figure 10: Parallel edge detection GUI.

  busyNoCR8: signals to the memory banks that an operation of the processor with the Hermes NoC is under way (e.g. I/O, read/write).-busyNoCMem: signals to the processor that an operation of the memory with the Hermes NoC is under way (e.g. return read).

	Processor Interface	ceR8 rwR8 addrR8 dinR8 doutR8 busyNoCR8 busyNoCMem	we en addr di do din(15:12) RAM3	we en addr di RAM2 do din(11:8)	we en addr di RAM1 do din(7:4)	RAM0 we en addr do din(3:0) di
				dout(15:12)	dout(11:8)	dout(7:4)	dout(3:0)
					MEMORY IP
			tx	data_out ack_tx	rx	data_in ack_rx
					NoC Interface

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgements

This research has been partially funded by CNPq through grants 550009/2003-5 and 307665/2003-2.


Gerlind Sulzenbacher

Véronique Roig-Zamboni

Régine Lebrun

Yann Guérardel

Dorothée Murat

Pascal Mansuelle

Nao Yamakawa

Xin-Xin Quian

Renaud Vincentelli

Yves Bourne

Long-Fei Wu

François Alberto
email: falberto@imm.cnrs.fr

Francois Alberto

Glycosylate and move! The glycosyltransferase Maf is involved in bacterial flagella formation

Originality-Significance Statement

Flagellin glycosylation with a nonulosonic sugar is required for the formation of the flagellum on the cell surface of Magnetospirillum magneticum AMB-1. This work describes the structural and functional characterization of the bacterial glycosyltranferase Maf. Because flagellin glycosylation is primordial for the motility and the virulence of many pathogens, and since many nonulosonic acid derivatives and the glycosyltransferases responsible for their transfer onto flagellins are unique to bacteria, we believe that these glycosyltransferases represent attractive targets for the development of new antimicrobial agents.

Introduction

Over the last few decades bacterial glycosylation has received considerable attention, since it had been well established that bacteria, like eukaryotes, possess both N-linked and Olinked glycosylation pathways [START_REF] Nothaft | Protein glycosylation in bacteria: sweeter than ever[END_REF]. The O-glycosylation pathway has mainly been described for flagellin (the individual subunits of the flagellar filament) and pilin monomers [START_REF] Logan | Flagellar glycosylation -a new component of the motility repertoire?[END_REF][START_REF] Ng | Archaeal flagella, bacterial flagella and type IV pili: A comparison of genes and posttranslational modifications[END_REF][START_REF] Nothaft | Protein glycosylation in bacteria: sweeter than ever[END_REF]. Bacterial flagellin glycosylation is now well-documented for pathogenic bacteria, including Campylobacter jejuni, Helicobacter pylori, Pseudomonas aeruginosa, Legionella pneumophila, Aeromonas caviae, Clostridium difficile, or Listeria monocytogenes [START_REF] Schirm | Structural, genetic and functional characterization of the flagellin glycosylation process in Helicobacter pylori[END_REF]Schirm et al., 2004b;Schirm et al., 2004a;[START_REF] Logan | Flagellar glycosylation -a new component of the motility repertoire?[END_REF][START_REF] Twine | Motility and Flagellar Glycosylation in Clostridium difficile[END_REF][START_REF] Hopf | Protein Glycosylation in Helicobacter pylori: Beyond the Flagellins?[END_REF][START_REF] Parker | Identification of a putative glycosyltransferase responsible for the transfer of pseudaminic acid onto the polar flagellin of Aeromonas caviae Sch3N[END_REF][START_REF] Iwashkiw | Pour some sugar on it: the expanding world of bacterial protein O-linked glycosylation[END_REF]. Flagellin O-glycosylation takes place on serine and/or threonine residues, often near a hydrophobic region, but so far a general consensus amino acid sequence has not been identified. The glycosylated amino acids reside in the central and variable region of the flagellin monomer, the region that is located at the surface of the flagellar filament [START_REF] Bubendorfer | Analyzing the Modification of the Shewanella oneidensis MR-1 Flagellar Filament[END_REF][START_REF] Poweleit | CryoEM structure of the Methanospirillum hungatei archaellum reveals structural features distinct from the bacterial flagellum and type IV pili[END_REF]. Bacterial flagellin glycosylation features a remarkable variety in the number of acceptor sites, the type and size of glycan structures and in some cases even strain-to-strain glycan heterogeneity [START_REF] Thibault | Identification of the carbohydrate moieties and glycosylation motifs in Campylobacter jejuni flagellin[END_REF][START_REF] Schirm | Identification of unusual bacterial glycosylation by tandem mass spectrometry analyses of intact proteins[END_REF].

Among the flagellin sugar modifications, pseudaminic acid (Pse5Ac7Ac) has been identified as a specific bacterial sialic acid related nonulosonic acid sugar [START_REF] Zunk | The occurrence and biological significance of the alpha-keto-sugars pseudaminic acid and legionaminic acid within pathogenic bacteria[END_REF], essential for flagellar assembly in Campylobacter spp., A. caviae, or H. pylori [START_REF] Goon | Pseudaminic acid, the major modification on Campylobacter flagellin, is synthesized via the Cj1293 gene[END_REF]. Since motility is required for colonization and the glycosylated extremities of the flagellins mediate host interactions [START_REF] Zunk | The occurrence and biological significance of the alpha-keto-sugars pseudaminic acid and legionaminic acid within pathogenic bacteria[END_REF], the presence of the Pse5Ac7Ac has been related to the virulence capacities of these bacteria. The complete biosynthesis of Pse5Ac7Ac has been characterized in C. jejuni and H. pylori [START_REF] Mcnally | Functional characterization of the flagellar glycosylation locus in Campylobacter jejuni 81-176 using a focused metabolomics approach[END_REF][START_REF] Schoenhofen | Elucidation of the CMPpseudaminic acid pathway in Helicobacter pylori: synthesis from UDP-N-acetylglucosamine by a single enzymatic reaction[END_REF]. Within these two bacteria CMP-activated Pse5Ac7Ac is generated from UDP-N-acetylglucosamine in a six-step pathway involving six different enzymes [START_REF] Morrison | The Renaissance of Bacillosamine and Its Derivatives: Pathway Characterization and Implications in Pathogenicity[END_REF].

Despite the thorough characterizations of the biosynthetic pathway of Pse5Ac7Ac, very little is known about the glycosyltransferases that transfer the sugar onto the flagellin. When the genome of C. jejuni was published, authors described a number of putative flagella-related genes similar to genes of Escherichia coli and other bacteria [START_REF] Parkhill | The genome sequence of the food-borne pathogen Campylobacter jejuni reveals hypervariable sequences[END_REF]. The genes involved in flagellin glycosylation are part of a large cluster containing genes involved in sugar biosynthesis and seven closely related genes of unknown function. These genes with unknown function were termed as the motility accessory factor (maf) family of flagellin associated genes [START_REF] Karlyshev | A novel paralogous gene family involved in phase-variable flagella-mediated motility in Campylobacter jejuni[END_REF]. In H. pylori two of these genes code for HP0114 and HP0465, respectively [START_REF] Parkhill | The genome sequence of the food-borne pathogen Campylobacter jejuni reveals hypervariable sequences[END_REF]. Inactivation of the gene coding for HP0114 displayed a non-motile phenotype. As HP0114 does not appear to be involved in the biosynthesis of CMP-Pse5Ac7Ac but clearly plays a role in flagellar assembly, it was suggested that HP0114 is involved in the transfer of Pse5Ac7Ac from CMP-Pse5Ac7Ac to the flagellin monomer [START_REF] Schirm | Structural, genetic and functional characterization of the flagellin glycosylation process in Helicobacter pylori[END_REF]. Following deletion of the maf genes found in Aeromonas hydrophila AH-3, maf1 and maf2, and A. caviae, maf1, the flagellin monomers were still produced within the cell, along with CMP-Pse5Ac7Ac [START_REF] Canals | Polar flagellum biogenesis in Aeromonas hydrophila[END_REF][START_REF] Canals | Non-structural flagella genes affecting both polar and lateral flagella-mediated motility in Aeromonas hydrophila[END_REF][START_REF] Parker | Identification of a putative glycosyltransferase responsible for the transfer of pseudaminic acid onto the polar flagellin of Aeromonas caviae Sch3N[END_REF], but were no longer glycosylated, suggesting that Maf proteins are glycosyltransferases targeting flagellins [START_REF] Parker | Mafdependent bacterial flagellin glycosylation occurs before chaperone binding and flagellar T3SS export[END_REF]. Furthermore, the authors of this work showed that the Maf-dependent glycosylation takes place before interaction of the unfolded flagellin with its specific chaperone and subsequent export via the T3SS secretion system [START_REF] Parker | Mafdependent bacterial flagellin glycosylation occurs before chaperone binding and flagellar T3SS export[END_REF].

We have performed genomic, genetic, biochemical, proteomic, and structural analyses to understand the structure and function of Maf in our magnetotactic model strain Magnetospirillum magneticum AMB-1 (AMB-1). We found that deletion of the maf gene affected glycosylation and assembly of Fla, the sole AMB-1 flagellin, into functional flagellar filaments. Glycan and proteomic analyses showed that the flagellin monomers are decorated with Pse5Ac7Ac or a close derivative -but only in the presence of Maf. Finally, we solved the 3D structure of Maf, which provides a structural template for the Maf family and the framework for the development of novel antibiotic agents specifically targeting this family.

Results

The AMB-1 flagellin is produced as a glycosylated protein.

Shearing-prepared AMB-1 flagellin fractions were resolved on SDS-PAGE gels and Coomassie staining revealed major bands around 70, 55, and 40 kDa (Fig. 1A). Polyclonal antibodies raised against the AMB-1 flagellin Fla, of expected theoretical mass of 54137 Da, [START_REF] Murat | Opposite and Coordinated Rotation of Amphitrichous Flagella Governs Oriented Swimming and Reversals in a Magnetotactic Spirillum[END_REF] hybridized with both the 70 and the 55 kDa bands (Fig. 1B). The two bands were analyzed in a bottom-up proteomics workflow and showed the presence of Fla.

The coverage obtained for the sequence of the 70 and the 55 kDa bands was 80% and 65%, respectively. Among the other polypeptides identified in the 55 kDa band, many have a cytoplasmic location, thus the presence of Fla in this band is most likely due to cytoplasmic protein contamination. Indeed, immunoblot analysis with the anti-flagellin antibody of a concentrated fraction of AMB-1 culture supernatant revealed only the presence of the 70 kDa band (Fig. S1A). Analysis of protein glycosylation by the periodate/biotin hydrazine method revealed the presence of a glycoprotein in the 70 kDa band (Fig. 1C).

Deletion of maf prevents the glycosylation of the flagellin of AMB-1.

Downstream of the fla gene coding for the AMB-1 flagellin is located maf (amb0685), coding for a 75 kDa protein of unknown function. The Maf protein displays sequence identity with hypothetical proteins from other Gram negative bacteria like Magnetospira QH2 (33%), Alteromonas australica (30%), and numerous Aeromonas species: A. schubertii (32%), A. piscicola (32%), A. hydrophila (31%), A. caviae (29%), or C. jejuni PseE (22%). The homologue from A. caviae, Maf1, had been shown to transfer Pse5Ac7Ac onto the flagellins FlaA/B [START_REF] Parker | Mafdependent bacterial flagellin glycosylation occurs before chaperone binding and flagellar T3SS export[END_REF] and the same role was attributed to PseE in C. jejuni (McNally et al., 2006). The central part of all the above homologous proteins bears a MAF_flag10 domain (accession number: pfam01973) of unknown function. HHpred analysis [START_REF] Meier | Automatic Prediction of Protein 3D Structures by Probabilistic Multitemplate Homology Modeling[END_REF] pointed to a structural similarity between this central domain of Maf and C. jejuni sialyltransferases Cst-I and Cst-II. These enzymes, members of the CAZy (http://www.cazy.org/) glycosyltransferase family GT42 [START_REF] Lombard | The carbohydrateactive enzymes database (CAZy) in 2013[END_REF], use CMP-Nacetylneuraminic acid (CMP-Neu5Ac) as the universal donor sugar and transfer a sialic acid moiety onto cell surface lipo-oligosaccharides (Chiu et al., 2004a;[START_REF] Chiu | Structural analysis of the alpha-2,3-sialyltransferase cst-i from Campylobacter jejuni in apo and substrate-analogue bound forms[END_REF]. The sequence similarities with A. caviae Maf1 and the predicted structural similarity to the wellcharacterized sialyltransferases Cst-I and Cst-II advocated for a possible involvement of Maf in the transfer of a nonulosonic acid onto Fla.

To test this hypothesis, we prepared a Δmaf deletion mutant in which the genetic regions flanking maf where cloned into an AMB-1 non-replicative vector (pAK31), where maf was replaced by a short linker in order to avoid the deletion from having a polar effect. The Δmaf mutant cells were non-motile and electron microscopy confirmed the absence of flagella (Fig. 1E) as compared to the wild-type strain (Fig. 1D). Expression of maf in trans in the Δmaf mutant restored the wild type phenotype, that is to say, cell motility and the presence of a functional flagellar filament outside the cell (Fig. 1F). To verify whether the deletion of maf had a deleterious effect on flagellin production, we hybridized the anti-flagellin antibody against total protein extracts of wild type AMB-1, the Δmaf mutant and the complemented Δmaf mutant. As expected, the Western blot showed that hybridizations occurred at 70 and 55 kDa for the wild-type total protein extract (Fig. 1G), but only the 55 kDa band could be revealed in total protein extract of the deletion mutant, indicating that the flagellin was still produced in Δmaf, but not glycosylated (Fig. 1H). Immunoblotting of the complemented Δmaf mutant protein extract revealed the 70 kDa band, indicating that flagellin glycosylation was restored by the complementation (Fig. 1I). Immunoblotting of a concentrated fraction of the supernatant of the Δmaf mutant culture revealed no band at all (Fig. S1B), indicating that the non-glycosylated protein is not exported.

The flagellin of AMB-1 is glycosylated by pseudaminic acid or a close derivative.

In a first approach, we tried to identify flagellin-associated glycans by purifying potential nonulosonic acids from flagellins. To accomplish that, we released nonulosonic acids from purified flagellin by mild acid hydrolysis. Free potential nonulosonic acids were then derivatized by 1,2-diamino-4,5-methylenedioxybenzene (DMB), a fluorogenic reagent for 2keto-acids that shows high specificity for all derivatives of nonulosonic acids, and analyzed by reverse phase HPLC coupled to mass spectrometry (LC-MS n ) . The analysis of the hydrolysis product of flagellin by LC-MS showed a MS signal at m/z 451.25 corresponding to the [M+H] + adduct of a compound with a molecular mass of 450.25 Da. This value could correspond to the expected mass of DMB-derivatized Pse5Ac7Ac or DMB-derivatized Leg5Ac7Ac (legionaminic acid) that both exhibit a [M+H] + value at m/z 451 [START_REF] Lewis | Innovations in host and microbial sialic acid biosynthesis revealed by phylogenomic prediction of nonulosonic acid structure[END_REF][START_REF] Ricaldi | Expression of sialic acids and other nonulosonic acids in Leptospira[END_REF]. The attribution to Pse5Ac7Ac or Leg5Ac7Ac was further confirmed by MS 2 analysis of the parent ion at m/z 451. Indeed, recurrent losses of H 2 O and N-acetyl groups at m/z 433.24 and 415.23, respectively, show similarities with the fragmentation pattern of standard Neu5Ac sialic acid (Fig. 2A and2B), in accordance with a previous study [START_REF] Lewis | Innovations in host and microbial sialic acid biosynthesis revealed by phylogenomic prediction of nonulosonic acid structure[END_REF].

A BLAST search [START_REF] Altschul | Basic Local Alignment Search Tool[END_REF] using the sequences of the enzymes involved in nonulosonic acid biosynthesis pathways in various bacterial species (C. jejuni, H. pylori, or A. caviae) against the AMB-1 protein database identified hits for all of the enzymes involved in the pseudaminic acid biosynthesis pathway and the corresponding cluster from genes amb0713 to amb0718. Thus, PseB of H. pylori is homologous to Amb0716 (77% sequence similarity), PseC to Amb0717 (55%), PseG to Amb0714 (45%), PseH to Amb0715 (43%), PseI to Amb0713 (68%), and PseF to Amb0718 (42%). Transcriptomic analysis showed that all these genes are expressed in the wild-type AMB-1 strain (Fig. S2B). Genetic deletion of amb0715 led to the same phenotype as the Δmaf mutant, that is to say the absence of flagellum and the disappearance of the 70 kDa band as revealed by Western blotting (Fig. S3A andS3C). Complementation of the Δamb0715 mutant by a plasmid carrying amb0715 restored flagellum assembly and the presence of the glycosylated form of Fla (Fig. S3B andS3D). A BLAST search [START_REF] Altschul | Basic Local Alignment Search Tool[END_REF] for the biosynthetic pathway of legionaminic acid in the AMB-1 protein database gave no conclusive result. In other bacterial species the number of maf homologues is correlated with the number of nonulosonic acids decorating the flagellin [START_REF] Merino | Gram-negative flagella glycosylation[END_REF]. Amb0685 presents no other homologue in the AMB-1 genome, suggesting that Pse5Ac7Ac (or a close Pse5Ac7Ac derivative) is the only nonulosonic sugar synthesized and transferred onto the flagellin.

Tandem mass spectrometry data from enzymatically digested Fla were analysed searching for Pse5Ac7Ac (316.13 Da) as a variable modification on serine and threonine residues. The sequence of Fla was covered at 80% by unique peptides and four among them displayed one or two modifications by Pse5Ac7Ac (Fig. S4A). For example, the parent ion at [M+H] + 3192.624 Da corresponding to the sequence -GLALNAQSASSSQIGSLVQQFNALR-, fitted with a mass accommodating two groups of Pse5Ac7Ac on serine residues (Fig. S4B). MS/MS fragmentation of this modified peptide in the HCD (Higher-energy Collisional Dissociation) cell displayed the nonulosonic acid specific signature as described previously [START_REF] Thibault | Identification of the carbohydrate moieties and glycosylation motifs in Campylobacter jejuni flagellin[END_REF], in the lowest m/z range: 299, 281, 257, 239, 221, 180, and 134 (Fig. S4C). Conversely, tandem mass spectrometry analysis of digested flagellin produced by the Δmaf mutant did not reveal any Pse5Ac7Ac modification on any peptide (Fig. S4D). Altogether these data strongly suggest that the nonulosonic acid found on the AMB-1 flagellin is Pse5Ac7Ac or a Pse5Ac7Ac derivative.

Overall structure of full-length Maf.

In order to gain insight into structure/function relationships, the crystal structure of Maf was determined taking advantage of multiple wavelength anomalous diffraction (MAD) data recorded at the Yb edge and refined at a resolution of 2.3 Å to R work of 18.94% and R free of 22.20% (Table S1). The final model of good stereo-chemical quality encompasses residues 7-664, but two peptide regions, spanning from Ser86 to His89 and from Lys422 to Gly443, respectively, could not be modelled because of lacking electron density.

In cristallo, Maf adopts a helical shape and is organized into three domains (Fig. 3). At the Nterminus (Ile7-Ser81 and Ser119-Ile237) a degenerated Rossmann-like domain, consisting of a four-stranded parallel -sheet, flanked by five -helices, is preceded by three additional helices and a -hairpin. A structural homology search with the DALI server [START_REF] Holm | Protein structure comparison by alignment of distance matrices[END_REF] did not identify significant structural resemblance with coordinates from the Protein Data Bank, except for weak similarities limited to the Rossmann-like motifs as found in nucleotide-and dinucleotide-binding enzymes and S-adenosyl-L-methionine (AdoMet)-dependent methyltransferases. A Gly-rich motif is located in a position structurally corresponding to the Gly-rich motif I in Mtases [START_REF] Malone | Structure-guided analysis reveals nine sequence motifs conserved among DNA amino-methyltransferases, and suggests a catalytic mechanism for these enzymes[END_REF], but where class I Mtases present a cavity accommodating the methyl donor, bulky side-chains occupy the equivalent space in Maf.

A long loop with an -helical insert connects the N-terminal domain to the central MAF_flag10 domain (Thr273-Arg530), displaying a modified glycosyltransferase GT-A topology as found in family GT29 and GT42 sialyltransferases (Chiu et al., 2004b;[START_REF] Chiu | Structural analysis of the alpha-2,3-sialyltransferase cst-i from Campylobacter jejuni in apo and substrate-analogue bound forms[END_REF]. Briefly, a central parallel seven-stranded twisted -sheet (topology 8, 7, 1, 2, 3, 4, 5) is bordered by four (A, B, C, D) and three (E, F, G) -helices on either sides and capped by a last -helix (αH) at the N-terminal end of the -strands. Between strand6 and helix G a long loop, comprising the disordered region Lys422-Gly443, projects away from the  domain and packs against the N-terminal domain of a symmetryrelated molecule.

A long loop comprising an -helix connects the  domain to the C-terminal domain (Trp546-Asp664), composed of a mostly antiparallel six-helix bundle. One of the -helices making up this helical bundle originates from the N-terminal part of Maf (Leu92-Asp107).

Structural homology searches with DALI [START_REF] Holm | Protein structure comparison by alignment of distance matrices[END_REF] and PDBeFold [START_REF] Krissinel | Secondary-structure matching (SSM), a new tool for fast protein structure alignment in three dimensions[END_REF], taking into account the connectivity of the peptide chain of the C-terminal domain, pointed to weak structural similarity to the N-terminal domain of a fungal translation initiation factor (PDB 5DBO, Z-score of 8.0) and the E. coli histidine kinase NarX sensor domain (PDB 3EZH, Z-score of 7.6). Interestingly, weaker structural similarities (Z-scores in the range of 5 to 6) can be found between the Maf C-terminal domain and flagellin export chaperones and flagellins, like Aquifex aeolicus FliS (PDB 1ORJ) and FliC from Burkholderia pseudomallei (PDB 4CFI).

In the crystal, Maf appears to form a dimer, generated by a crystallographic two-fold axis, with a buried surface of 8420 Å 2 per monomer as calculated by the PISA server [START_REF] Krissinel | Inference of macromolecular assemblies from crystalline state[END_REF] (Fig. S5). However, this is undoubtedly a crystallization artefact, as size-exclusion chromatography coupled with multi-angle laser light scattering (SEC-MALLS) (Fig. S6) clearly showed that Maf is a monomer in solution.

Comparison of the central MAF_flag10 domain with sialyltransferases and identification of functional residues.

The closest structural homologue of the central domain of Maf is C. jejuni sialyltransferase Cst-II (PDB 1RO7) belonging to CAZy [START_REF] Lombard | The carbohydrateactive enzymes database (CAZy) in 2013[END_REF] family GT42, with a DALI Zscore of 9.8 and an rmsd of 3.6 Å for 158 equivalent Cα-atoms (this similarities is comparable with that to Cst-I, but for simplicity only Cst-II will be discussed). More distant similarities can be found to members of glycosyltransferase family GT29 and of the thiamine pyrophosphokinase family. The central -sheet and -helices A, F, and G are structurally well conserved between Maf and Cst-II (Fig. 4), but larger structural divergence can be observed for the remaining -helices and especially for the last -helix of the domain, αH, which in Cst-II lies on the opposite end of the -sheet when compared to Maf. Family GT42 sialyltransferases catalyze the transfer of a sialic acid moiety from CMP-Neu5Ac onto the terminal position of glycoconjugates with overall inversion of configuration of the anomeric carbon. Their active site is located between the edge of the central -sheet and a small lid-like structure, which undergoes a conformational change, becomes ordered and folds over the active site upon substrate binding. The general base has been identified as being His188 in Cst-II [START_REF] Chan | NMR spectroscopic characterization of the sialyltransferase CstII from Campylobacter jejuni: histidine 188 is the general base[END_REF]. A superposition of the Maf coordinates with the structures of GT42 members in complex with glycosyl donors permitted identification of a putative active site for Maf. Interestingly, the disordered loop region of Maf has its boundaries in positions equivalent to the boundaries of the lid-like domain in the GT42 members. Maf has no residue with a functional group that could act as reaction catalyst in a position corresponding to His188 in Cst-II. By docking we produced a model of CMP-Pse5Ac7Ac bound to Maf, where the ligand adopted a position very similar to that occupied by CMP-3FNeu5Ac in the Cst-II sugar donor complex (PDB 1RO7) (Fig. S7). Intriguingly the phosphate group of the modelled CMP-Pse5Ac7Ac overlaps precisely with a sulfate ion present in the crystal structure of Maf, indicating that the sulfate might mimic binding of a genuine phosphate group present in sugar donors and corroborating the validity of the docking result. In the model of Maf with docked CMP-Pse5Ac7Ac Glu324 is located on the C-terminal end of βstrand β3 in a position equivalent to Asn51 in Cst-II, a residue shown to be crucial for acceptor binding and catalysis. Other features in the substrate binding region common to Cst-II and Maf are conserved residues located in the loop regions following β-strands β1 (Gly279, Gly281, Pro282, Ser283) and β6 (Gly413, Asp415) as well as a Thr preceding helix αF (Fig. 4). In the model of the Maf/CMP-Pse5Ac7Ac complex this latter Thr392 is at hydrogenbonding distance from the ribosyl O3 hydroxyl group.

A sequence alignment of the MAF_flag10 domain of AMB-1 with the corresponding domains of closest Maf homologues, displaying around 70% of sequence identity, and of more distant homologues (~35% of sequence identity), representing different genera (Fig. 5A) highlighted fully conserved residues with functional groups that could potentially steer catalysis: Ser283, Asp318, Glu324, Asp415, and Asn491. Point mutations S283A, D318A, and N491A on the pAK22-maf plasmid we used to complement the Δmaf strain did not affect AMB-1 motility and the synthesis of the 70 kDa band, as verified under an optical microscope and revealed by immunoblotting, respectively. Conversely, point mutations E324A and D415A on the complementation plasmid affected directly Maf activity, as bacterial motility was not restored and the glycosylated form of the flagellin could not be detected (Fig. 5B). As mentioned before, Glu324 is located in proximity of the putative reaction center (Fig. 4), and could thus be directly involved in catalysis. Asp415 corresponds to Asp154 in Cst-II, where this residue structures a loop forming the binding pocket of the nucleotide portion of the sugar-donor and Asp415 might exercise the same role in Maf.

Discussion

In this work we show that the deletion of the gene amb0685 (maf) in AMB-1 prevents the glycosylation of the flagellin with pseudaminic acid or a close derivative. The flagellin is still produced but the individual monomers are not exported outside the cell to form a functional flagellum, suggesting that flagellin glycosylation by the nonulosonic acid is an essential prerequisite for flagellum export and assembly. By sequence threading we found that the central MAF_flag10 domain common to all Maf proteins is distantly related to family GT42 sialyltransferases and this prediction has been corroborated with the X-ray structure of Maf.

The -strand core of the MAF_flag10 domain is structurally well conserved between Maf and GT42 members, although more variability can be found for the position of the surrounding helices. Furthermore, the boundaries of the disordered segment between strand 6 and helix G of the MAF_flag10 domain overlap with the boundaries of the lid-like domain, which is present in all bacterial (GT42) and mammalian (GT29) sialyltransferases and participates in the structuring of the active site. It is not surprising that the highest structural conservation between the  domain of Maf and GT42 members can be found in the donor binding site, accommodating in both cases activated nonulosonic acids sugars, whereas more structural divergence occurs in the acceptor binding site, which in the case of the sialyltransferases accommodates a saccharide, galactose or sialic acid, as opposed to Maf, which accommodates a polypeptide chain. It should be noted that in C. jejuni the role of Cst-I and Cst-II is to transfer Neu5Ac onto cell wall lipo-oligosaccharide outer core structures, whereas Pse5Ac7Ac is predicted to be transferred onto the C. jejuni flagellin by the gene product of pseE (maf 5) [START_REF] Merino | Gram-negative flagella glycosylation[END_REF].

In the artificial dimeric arrangement within the crystal the active site of Maf is shielded from the solvent and consequently we were not able to obtain structures of complexes with a donor substrate by soaking experiments. All attempts to obtain by cocrystallization a complex of Maf with a carbohydrate donor related to pseudaminic acid, CMP-Neu5Ac failed, indicating that ligand binding is governed by a fine substrate recognition mechanism. Unquestionably, further biochemical and structural studies are warranted to dissect the precise mechanism by which Maf transfers pseudaminic acid or a close derivative onto the flagellin and to ascertain the identity of the catalytic residue, which at the time being we can only hypothetically assign to Glu324.

Even though we provide strong evidence that the Maf-10 domain of Maf is a catalytic module responsible for the transfer of a nonulosonic acid onto the flagellin, the function of the N-and C-terminal modules remains elusive. Degenerated Rossmann-like motifs are found in a large number of proteins of diverse function and the similarity with methyltransferases is too distant to allow assignment of a precise function to the N-terminal domain. Six methylated lysine were observed by mass spectrometry analysis of the flagellin. Since there is a gene (amb0693) encoding for a putative methyltranferase in close vicinity of the flagellin gene, further work would be needed to determine whether Maf or Amb0693 is responsible for flagellin methylation. Concerning the C-terminal -helical bundle, its intriguing resemblance to flagellar chaperones and flagellins points towards a putative role in flagellin recognition or export.

Maf proteins have been most extensively studied in gram-negative pathogens like C. jejuni [START_REF] Thibault | Identification of the carbohydrate moieties and glycosylation motifs in Campylobacter jejuni flagellin[END_REF][START_REF] Karlyshev | A novel paralogous gene family involved in phase-variable flagella-mediated motility in Campylobacter jejuni[END_REF][START_REF] Logan | Structural heterogeneity of carbohydrate modifications affects serospecificity of Campylobacter flagellins[END_REF][START_REF] Schirm | Identification of unusual bacterial glycosylation by tandem mass spectrometry analyses of intact proteins[END_REF][START_REF] Mcnally | Targeted metabolomics analysis of Campylobacter coli VC167 reveals legionaminic acid derivatives as novel flagellar glycans[END_REF], H. pylori [START_REF] Schirm | Structural, genetic and functional characterization of the flagellin glycosylation process in Helicobacter pylori[END_REF], A. hydrophila [START_REF] Gavin | Lateral flagella of Aeromonas species are essential for epithelial cell adherence and biofilm formation[END_REF], and A. caviae [START_REF] Rabaan | Motility and the polar flagellum are required for Aeromonas caviae adherence to HEp-2 cells[END_REF], where the maf genes are often, though not systematically, associated with genes coding for the flagellins and the enzymes involved in nonulosonic acid biosynthesis. The genes encoding other structural flagella elements, like the hook and the basal body, are found elsewhere on the genome. The number of maf genes can vary from one organism or strain to another. In AMB-1 the only maf gene (amb0685) and the adjacent flagellin are distant from the gene cluster comprising Pse5Ac7Ac biosynthesis genes.

It has been shown by others and within this work that flagellin glycosylation can be essential for export and assembly of the bacterial flagellum, but glycosylation appears also to be involved in adhesion and regulation of the host immune response [START_REF] Chaban | The flagellum in bacterial pathogens: For motility and a whole lot more[END_REF]. The highly modified prokaryote-specific nonulosonic acid sugars can be considered as a virulence factor [START_REF] Thibault | Identification of the carbohydrate moieties and glycosylation motifs in Campylobacter jejuni flagellin[END_REF][START_REF] Logan | Structural heterogeneity of carbohydrate modifications affects serospecificity of Campylobacter flagellins[END_REF][START_REF] Goon | Pseudaminic acid, the major modification on Campylobacter flagellin, is synthesized via the Cj1293 gene[END_REF], and the biosynthetic pathways underlying their synthesis and transfer onto the flagellin may thus represent appealing targets for the development of new antibiotics. With the first three-dimensional structure of a Maf glycosyltransferases family member, we deliver the structural framework that should enable screening for novel compounds to address the growing challenge associated to antibiotic resistance.

Experimental Procedures

Bacterial strains and growth conditions.

Magnetospirillum magneticum AMB-1 was grown in MG (Magnetospirillum Growth) media as previously described [START_REF] Murat | Comprehensive genetic dissection of the magnetosome gene island reveals the step-wise assembly of a prokaryotic organelle[END_REF] and E. coli in LB media. E. coli DH5αλpir strain was used for cloning. The E. coli WM3064 strain was used as donor strain for conjugation.

For E. coli strains antibiotics were used as follows: 50 µg/ml for kanamycine and 100 µg/ml for ampicilline. For AMB-1, kanamycine was used at 15 µg/ml on plates and 10 µg/ml in liquid.

Construction of the maf deletion mutant and complementation experiments.

The AMB-1 maf deletion mutant (Δmaf) was created as described previously [START_REF] Murat | Comprehensive genetic dissection of the magnetosome gene island reveals the step-wise assembly of a prokaryotic organelle[END_REF]. PCR runs were performed using GoTaq green mix (Promega). Briefly, the flanking regions of maf were amplified using AMAF2/BMAF and CMAF3/DMAF2 primers (Table S2). Then the two fragments were fused by PCR using AMAF2/DMAF2 primers. PCR cycles were : 95°C for 2 min, 30 cycles of as follows : 95°C for 10 s, 55°C for 30 s, 72°C for 90 s or 200 s (for the PCR fusion), and 72°C for 10 min. The resulting fragment of PCR fusion was cloned into the pAK31 vector [START_REF] Komeili | Magnetosome vesicles are present before magnetite formation, and MamA is required for their activation[END_REF] using the In-Fusion HD Cloning Kit method (Clontech) to create the pAK31-DELMAF plasmid. This plasmid was transformed in donor strain E. coli WM3064, and conjugation was done in AMB-1 as previously described [START_REF] Murat | Comprehensive genetic dissection of the magnetosome gene island reveals the step-wise assembly of a prokaryotic organelle[END_REF]. Transformed AMB-1 cells were plated on MG agar supplemented with kanamycine and let grow for six days at 30°C in a jar to maintain microaerophilic conditions (0.4% oxygen). Some of the hereby obtained colonies were grown in 1.5 ml of MG supplemented with kanamycine for 48 h at 30°C. Then, 10 ml of MG were inoculated at 1/100 with one transconjugant and let grow at 30°C for 48 h. One, two, and six hundred microliters of this culture were used to inoculate MG plates containing sucrose (2%). The plates were incubated 8 days at 30°C in a jar under microaerophilic conditions. Colonies obtained were screened by PCR using AMAF2/DMAF2 primers to check the deletion of the maf gene.

For complementation experiments, the maf gene was amplified by PCR using GoTaq green mix (PROMEGA) and the MAFINFPAK22F/MAFINFPAK22R primer couples (Table S2).

The PCR cycle consisted of 98°C for 2 min and 35 cycles as follows: 98°C for 30 s, 55°C for 30 s, 72°C for 120 s, and 72°C for 10 min. Then the fragment generated was cloned in the AMB-1 replicative pAK22 plasmid [START_REF] Murat | Comprehensive genetic dissection of the magnetosome gene island reveals the step-wise assembly of a prokaryotic organelle[END_REF] using the In-Fusion HD Cloning Kit method (Clontech). The plasmid was transferred by conjugation into the Δmaf AMB-1 strain using E. coli WM3064 strain as donor. Transconjugants were plated on MG supplemented with kanamycine and incubated in a jar at 30°C for 6 days under microaerophilic conditions.

Colonies were picked and grown in 1.5 ml MG supplemented with kanamycine at 30°C for 48 h. The same protocol was used to generate the AMB-1 amb0715 deletion mutant (Δamb0715). Primers 0715A/0715B and 0715C/0715D were used to generate the amplicon cloned into the deletion plasmid and primers 0715PAK22F/0715PAK22R were used to generate the amplicon cloned into the complementation plasmid (Table S2).

Complementation of the Δmaf strain with mutated maf was obtained by generating point mutations in the pAK22-maf complementation plasmid by PCR. 100 ng of plasmid were amplified with 0.4 µM of each primer couple (S283AF2/S83AR2, D318AF/D318AR, E324AF/E324AR, D415AF/D415AR, and N491AF/N491AR) (Table S2), 0.3 mM of dNTP, 2 U of PfuTurbo DNA polymerase (Agilent Technologies) in 1X Buffer. PCR was carried out as follows: 60 sec at 92°C, 16 x (30 sec at 92°C, 60 sec at 55°C, 1200 sec at 68°C). Then 40 U of DpnI (New English Biolabs) were added to 50 µl of PCR volume and incubated at 37°C for 16 h. Five microliters of the total digestion volume were used to transform competent E. coli DH5α cells. Some colonies, which were able to grow on LB agar plates supplemented with 50 µg/ml of kanamycine were sequenced to confirm the point mutation (Genewiz).

RNA preparation and Reverse Transcription for transcriptional analyses.

RNAs were prepared from AMB-1 cultures (50 ml) in late exponential growth phase (OD 600 ∼0.2). Cells were harvested and frozen at -80°C. Total RNAs were isolated from the pellet using the Maxwell® 16 LEV simplyRNA Blood Kit (Promega) according to the manufacturer's instructions and an extra TURBO DNase digestion step was performed to eliminate the contaminating DNA. RNA quality was assessed by an Experion chip (Bio-Rad), and the absence of DNA contamination was confirmed by PCR (Fig. 2SA). RNA was quantified spectrophotometrically at 260 nm (NanoDrop 1000, Thermo Fisher Scientific). For cDNA synthesis, 1 μg of total RNA and 0.5 μg of random primers (Promega) were used with the GoScript™ Reverse transcriptase (Promega) according to the manufacturer instruction.

Templates for the amplifications were cDNA, diluted at 1/20 (Fig. 2SB) and water (as a negative control of the PCR, Fig. 2SC). PCR runs were performed using Platinum SuperFi DNA Polymerase (Invitrogen) and primers 0713RTF/0713RTR, 0714RTF/0714RTR, 0715RTF/0715RTR, 0716RTF/0716RTR, 0717RTF/0717RTR, 0718RTF/0718RTR (Table S2). The PCR cycle consisted of 98°C for 30 s and 25 cycles as follows: 98°C for 10 s, 64°C for 10 s, 72°C for 10 s, and 72°C for 5 min.

Detection of protein glycosylation.

Proteins were transferred from the SDS-PAGE gel to a nitrocellulose membrane. The membrane was incubated 30 min in 15 mM sodium periodate and 50 mM sodium acetate, then washed 4 times in PBS (Phosphate Buffer Saline) and incubated 1 h in 5 mM biotin hydrazine. The membrane was blocked overnight in TBS (Tris Buffer Saline) containing 5% BSA (Bovine Serum Albumin), and then incubated 1 h in alkaline phosphate buffer. After washing in TBS, sugar revelation was performed using the ECL Western Blotting Substrate (Thermo Scientific).

Characterization of flagellin and its glycosylation sites by tandem mass spectrometry.

Flagellins were isolated from cells using the shearing method [START_REF] Murat | Opposite and Coordinated Rotation of Amphitrichous Flagella Governs Oriented Swimming and Reversals in a Magnetotactic Spirillum[END_REF]. Samples were resuspended in a minimal volume of running buffer and submitted to SDS-PAGE analyses. The protein-containing bands were cut out from SDS-PAGE gels and treated as follows: washed with 100 mM acetonitrile/ammonium bicarbonate pH 7.5, reduced by 10 mM dithiothreitol in 100 mM ammonium bicarbonate pH 7.5, alkylated by 55 mM iodoacetamide in 100 mM ammonium bicarbonate pH 7.5, digested in a single or two steps by trypsin from porcine pancreas (Promega) followed or not by -chymotrypsin (Promega). Each protease was used at 10 ng/µL and incubations were performed overnight at 37°C in 100 mM ammonium bicarbonate pH 7.5. Digested peptide solutions were dried and then solubilized in 8 µL of 0.05% TFA and 2% acetonitrile in water. Aliquots of 2 µl were analyzed on a ESI-Q-Exactive Plus (ThermoFisher) mass spectrometer coupled to nanoliquid chromatography (Ultimate 3000, Dionex). Peptides were first desalted on a nano-trap (Acclaim PepMap100, 300 µm i.d.x 5 mm, 5 µm, 100 Ǻ, Dionex), mounted in a 6-port valve, before elution onto a C18 column (Acclaim PepMap RSLC, 75 µm i.d. x 150 mm, 2 µm, 100 Ǻ, Dionex). Peptides were eluted with a linear gradient from 6% to 40% of mobile phase B (80% acetonitrile and 0.1% formic acid in water) in mobile phase A (0.1% formic acid in water) for 52 min. The peptides were detected in the mass spectrometer in a positive ion mode using a Top 10 data dependent workflow. One scan event full MS in the Orbitrap (resolution 70 000 at m/z 400), in a 350-1900 range (Auto Gain Control target at 3 x 10 6 ), was followed by fragmentation MS/MS of the top 10 ions, in the Higher Energy Collisional Dissociation cell (HCD) set at a normalized value of 27. Analysis of the MS/MS fragments in the Orbitrap was performed at resolution 17 500 at m/z 400 and "no fixed first mass" set (Auto Gain Control target at 1 x 10 5 ). The spectra were analyzed with the Proteome Discoverer software (ThermoFisherScientific, version: 1.4.0.288) using the following parameters: (1) AMB-1 proteins database (4561 entries); (2) enzymes used: trypsin/-chymotrypsin (5 missed cleavages); (3) fixed modification: carbamidomethyl (Cys) (4) variable modifications including: oxidation (Met), methylation (Lys) and pseudaminic acid (Ser, Thr); (5) mass values specific for monoisotopic; (6) precursor mass tolerance: ± 10 ppm; (7) fragment mass tolerance: ± 0.02 Da. A high confidence filter was applied with validation on q-Value (Strict Target FDR: 0.01) and Maximum Delta Cn: 0.05.

Secretion assays.

Five hundred mL of a log-phase culture of wild-type AMB-1 and Δmaf mutant were filtered onto a 0.22 µm membrane (Millipore) to remove the cells. Secreted fractions were generated by precipitating culture supernatant in ten volumes of ice-cold ethanol and incubated overnight at -20°C. Samples were centrifuged at 24,610 g for 30 min and protein pellet was washed in 70% ice-cold ethanol, dried, resuspended in 8 M urea, 50 mM Tris-HCl pH 7.5 and incubated 1 h at 30°C in loading buffer. Samples were analyzed by Western blotting as described previously [START_REF] Murat | Opposite and Coordinated Rotation of Amphitrichous Flagella Governs Oriented Swimming and Reversals in a Magnetotactic Spirillum[END_REF].

Expression and purification of Maf.

The coding region of Maf was amplified from Magnetospirillum magneticum AMB-1 DNA using Pfu polymerase (Invitrogen) and the following PCR reaction primers: AMB0685FW/AMB0685RV (Table S2). The amplified PCR product was inserted into a pGEX20 vector, enabling fusion of a thioredoxin/polyhistidine-tag, using the Gateway cloning technology (Invitrogen). The recombinant vectors were checked by double-stranded DNA sequencing. Constructs were synthesized from E. coli Rosetta pLys cells, grown in ZYP5052 medium [START_REF] Studier | Protein production by auto-induction in high-density shaking cultures[END_REF] at 37°C, until exponential growth phase was reached, and then transferred to 17°C for overnight protein production. Cells were harvested by centrifugation at 5,000 g and stored at -80°C. Dry cell pellet was resuspended in lysis buffer (50 mM Tris-HCl pH 8.0, 300 mM NaCl, 5 mM DTT, 1% (w/v) Triton X-100, 1 mM PMSF, 0.25 mg/ml DNase, 10 mM MgCl 2 , 0.25 mg/ml lysozyme) and sonicated at 4°C. After centrifugation at 16,000 g, the soluble fraction was loaded onto a HisTrap™ 5 ml column (GE Healthcare) and eluted with a 10-500 mM gradient of imidazole in 50 mM Tris-HCL pH 8.0 and 300 mM NaCl. Eluted fractions were pooled and desalted in a buffer containing 50 mM Tris-HCL pH 8.0, 300 mM NaCl and 10 mM imidazole. The thioredoxin/6xHis-tag was removed by overnight incubation with tobacco etch virus protease at 4°C. The reaction mixture was loaded onto a HisTrap™ 5 ml column and the flow-through was concentrated using a Vivaspin 30 kDa cutoff centrifugal filter unit (GE Healthcare). A final purification Crystallization and structure solution.

Crystals were grown at room temperature by the vapour diffusion method in sitting drops consisting of equal volumes (100 + 100 nl) of Maf solution at 7 mg/ml and a crystallization solution composed of 1.5-1.7 M (NH 4 ) 2 SO 4 , 5% (v/v) polyethylene glycol 400 and 0.1 M MES buffer, pH 6.5-7.0. Crystals belong to space group P2 1 2 1 2 with unit cell dimensions of 117x127x65 Å and one molecule per asymmetric unit. Because crystals were extremely fragile, a heavy atom derivative was prepared by adding with a cryo-loop step-wise infinitely small amounts of a 100 mM YbCl 3 solution to a drop containing the crystals. Crystals were flash-cooled in liquid nitrogen without prior addition of a cryo-protectant. A 3-wavelength multiple anomalous dispersion data set for an Yb-derivatized crystal and a dataset for a crystal of native Maf were collected on the ESRF beamlines (Grenoble, France) ID29 [START_REF] De Sanctis | ID29: a highintensity highly automated ESRF beamline for macromolecular crystallography experiments exploiting anomalous scattering[END_REF] and ID30A-1 [START_REF] Svensson | Fully automatic characterization and data collection from crystals of biological macromolecules[END_REF], respectively. Diffraction data were indexed with XDS [START_REF] Kabsch | XDS[END_REF] and scaled with the program AIMLESS [START_REF] Evans | How good are my data and what is the resolution?[END_REF]. The structure of Maf was solved with the CRANK software suite [START_REF] Pannu | Recent advances in the CRANK software suite for experimental phasing[END_REF], which delivered an almost complete (95%) structural model. Model completion and adjustment, using the native data set, were carried out with the programs Refmac [START_REF] Murshudov | Refinement of macromolecular structures by the maximum-likelihood method[END_REF] and Coot [START_REF] Emsley | Features and development of Coot[END_REF], respectively. A random set of 5% of reflections was set aside for cross-validation purposes. The model quality was assessed using the Molprobity server [START_REF] Chen | MolProbity: all-atom structure validation for macromolecular crystallography[END_REF]. The coordinates for CMP-Pse5Ac7Ac and its library used for docking where prepared with UCSF Chimera [START_REF] Pettersen | UCSF Chimera--a visualization system for exploratory research and analysis[END_REF]. Docking was performed with the SwissDock web service [START_REF] Grosdidier | SwissDock, a protein-small molecule docking web service based on EADock DSS[END_REF]. Figures representing structural renderings

where generated with the PyMOL Molecular Graphics System (DeLano, W.L. The PyMOL Molecular Graphics on http://www.pymol.org/). Atomic coordinates and structure factors have been deposited within the Protein Data Bank http://www.rcsb.org [START_REF] Berman | The Protein Data Bank[END_REF].

Identification of sialic acids.

Intact sialic acids were liberated by mild hydrolysis in 0.1 N TFA at 80°C and coupled to 1,2diamino-4,5-methylenedioxybenzene dihydrochloride (DMB). For DMB derivatization, sialic acids reacted with a volume of DMB reagent at 50°C for 2h30 min. Sialic acid derivatives were first observed by fluorescence detection after HPLC separation. To do that, compounds were separated isocratically on a C18 reverse phase HPLC column (250 x 4.6 mm, 5 micron, Vydac) by a solvent mixture of acetonitrile:methanol:water (7:9:84, v/v) and identified by referring to the elution positions of standard Neu5Ac, Neu5Gc, and Kdn derivatives [START_REF] Hara | Fluorometric highperformance liquid chromatography of N-acetyl-and N-glycolylneuraminic acids and its application to their microdetermination in human and animal sera, glycoproteins, and glycolipids[END_REF]. The sialic acid derivatives were then identified by LC/MS n analysis in positive ion mode on an amaZon speed ETD ion trap mass spectrometer equipped with the standard electrospray ionization (ESI) ion source and controlled by Hystar (ver. 3.2) software (Bruker Daltonics). DMB-coupled sialic acid separation was achieved on a micro LC system (Prominence LC-20AB, Shimadzu). Samples were diluted 5-fold with 0.1% formic acid and 5 µL of dilution were applied to the analytical column (luna 3u C18 (2) 100 Å 150 x 1.00 mm, 2.9 (2.9) 2.9 (2.9) 2.9 (2.9) Completeness (%) 99.7 (99.5) 99.9 (99.9) 99.9 (100) 99.9 (100)

  step was carried out by size exclusion chromatography using a HiLoad™ 26/60 Superdex™ 200 column (GE Healthcare) with 20 mM Hepes buffer pH 7.0 and fractions containing the desired protein were pooled and concentrated as above. The oligomerization state of Maf was investigated by Size-Exclusion Chromatography coupled with Multi-Angle Laser Light Scattering (SEC-MALLS, Wyatt technology).

Fig. 1 .

 1 Fig. 1. Shearing-prepared surface fractions containing flagellin from wild-type AMB-1. The

Fig. 2 .

 2 Fig. 2. Analysis of DMB-coupled sialic acids by LC-MS n . (A) MS 3 fragmentation pattern of [M-18+H] + ion at m/z 408 of standard DMB-Neu5Ac (Inset Neu5Ac); (B) MS 2 fragmentation pattern of [M+H] + ion at m/z 451 of a nonulosonic acid purified from AMB-1 flagellin (Inset

Fig. 3 .

 3 Fig. 3. Overall structure of Maf. Ribbon view of Maf colored by domains: the N-terminal

Fig. 4 .

 4 Fig. 4. Comparison of Maf and C. jejuni Cst-II. Superposition of the central  domain of

Fig. 5 .

 5 Fig. 5. (A). Sequence alignment of the MAF_flag10 domain (from amino acids T273 to

Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Fig. S5 .

 12345S5 Figure 1

Fig. S6 .

 S6 Fig. S6. Light scattering (SEC-MALLS) analysis of Maf. The chromatogram from the sizeexclusion experiment (solid line) and the calculated molar mass of the protein (dotted line) are shown.

Fig. S7 .

 S7 Fig. S7. Donor sugar binding to Maf and C. jejuni Cst-II. Superposition of the central  domain of Maf, color-coded as in Fig. 3, and C. jejuni Cst-II (PDB 1RO7), colored in lightblue. A model of CMP-Pse5Ac7Ac obtained by docking is represented in sticks, with carbon atoms colored in pink, and oxygen and nitrogen atoms colored in red and blue, respectively. A sulphate ion present in the crystal structure of Maf and overlapping with the phosphate group of modelled CMP-Pse5Ac7Ac is shown in orange sticks. CMP-3FNeu5Ac bound to Cst-II is shown in yellow sticks. Conserved residues, the catalytic base His188 of Cst-II and the putative catalytic base Glu324 of Maf are shown in sticks, with carbon atoms of Maf colored in green and carbon atoms of Cst-II shown in light-blue, whereas oxygen and nitrogen atoms of both Maf and Cst-II are shown in red and blue, respectively. Maf residues Thr305 and Ser280 might have a role in binding of the activated sugar-donor.

Table S1 :

 S1 Crystallographic data collection and refinement statistics

		Supplemental Tables
		Native	Yb-derivative
			Peak	Inflection	Remote
	Data collection
	Wavelength	0.9650	1.38519	1.38578	1.38056
	Resolution range a	45.26-2.30 (2.42-	45.23-2.80	45.27-2.80	45.34-2.80
		2.30)	(2.95-2.80)	(2.95-2.80)	(2.95-2.80)
	Redundancy	5.1 (5.2)	5.7 (5.7)	5.7 (5.7)	5.6 (5.7)
	Anomalous redundancy	2.7 (2.7)

  Throughout the table the values in parentheses apply for the outermost resolution shell b R merge = ∑ hkl ∑ i ( I i(hkl) -<I hkl > ) / ∑ hkl ∑ i I i(hkl) , where I is an individual reflection measurement and <I> is the mean intensity for symmetry related reflection. d R cryst = ∑ hkl | | F o | -|F c | | / ∑ hkl | F o |, where F o and F c are observed and calculated structure factors, respectively.

	Anomalous completeness (%)	99.8 (99.2)	99.1 (99.3)	99.2 (99.3)	99.2 (99.3)
	No. of unique reflections	43504	24525	24620	24689
	Rmerge b	0.085 (0.790)	0.077 (1.035)	0.057 (0.575)	0.080 (1.502)
	CC1/2	0.998 (0.769)	0.996 (0.719)	0.998 (0.885)	0.998 (0.546)
		12.8 (2.4)	13.9 (1.4)	16.6 (2.7)	12.6 (1.0)
	B-factor from Wilson plot (Å 2 )	40.93	72.77	69.46	82.78
	Refinement
	Rcryst (%) d	18.67 (28.0)
	Rfree (%)	22.02 (31.30)
	No. of free reflections	2224
	Protein atoms	5014
	Ligand atoms	46
	Solvent atoms	98
	r.m.s. deviations from target values
	Bond lengths (Å)	0.009
	Bond angles (°)	1.389
	Chiral volumes (Å 3 )	0.079
	Average B-factors (Å 2 )
	Main/side chains	47.80/53.59
	Ligands/solvent	67.50/47.81
	r.m.s. deviations on B-factors (A 2 )
	Main chain	1.663
	Side chain	2.660
	Ramachandran plot statistics (%) e
	Residues in favoured regions	98.56
	Residues in allowed regions	1.44

a e There are no Ramachandran outliers

Acknowledgments

We thank the European Synchrotron Radiation Facility (ESRF) and Synchrotron Soleil for beam time allocation, and the staff of beam lines Proxima1, Proxiam2, ID29, and ID30A-1 for assistance with data collection. We are grateful to Artemis Kosta and Yann Denis (IMM, CNRS, Marseille) for electron micrographs and transcriptomic experiments, respectively, and Bernard Henrissat for helpful discussion. We also thank the Plateforme d'Analyse des Glycoconjugués (PAGés, http://plateforme-pages.univ-lille1.fr/) and Frabio FR 3688 CNRS for providing access to the instrumental facilities for carbohydrate analysis.

Funding Information

This work was supported by l'Agence Nationale de la Recherche (ANR-2010-BLAN-1320-01 to L.-F.W.) and the French Infrastructure for Integrated Structural Biology (FRISBI) ANR-10-INSB-05-01.

ACCESSION NUMBERS: Coordinates and structure factors have been deposited in the Protein Data Bank with accession number 5MU5.

The authors declare no conflict of interest.

Supplemental Figures

Fig. S1. Western blotting of secreted fractions from cultures of (A) wild-type AMB-1 and (B) the Δmaf mutant. Hybridization was done with a polyclonal antibody raised against the AMB-1 flagellin. Fig. S2. Expression of genes from the cluster putatively involved in Pse5Ac7Ac cluster biosynthesis. The agarose gels presented in the figure show the result of PCR using primers for the expression of amb0713 (lane 1), amb0714 (lane 2), amb0715 (lane 3), amb0716 (lane 4), amb0717 (lane 5), and amb0718 (lane 6) utilizing (A) total extracted RNA, (B) cDNA, and (C) water as templates.