Mangayarkarasi Nivaskumar

Javier Santos-Moreno

Christian Malosse

Nathalie Nadeau

Julia Chamot-Rooke

Guy Tran Van Nhieu

Olivera Francetic
email: ofrancet@pasteur.fr

Pseudopilin residue E5 is essential for recruitment by the type 2 secretion system assembly platform

Keywords: type 2 secretion system, type 4 pili, pilus assembly, bacterial two-hybrid, assembly platform, protein interactions

Type II secretion systems (T2SSs) promote secretion of folded proteins playing important roles in nutrient acquisition, adaptation and virulence of Gram-negative bacteria. Protein secretion is associated with the assembly of type 4 pilus (T4P)-like fibres called pseudopili.

Initially membrane embedded, pseudopilin and T4 pilin subunits share conserved transmembrane segments containing an invariant Glu residue at the 5th position, E5.

Mutations of E5 in major T4 pilins and in PulG, the major pseudopilin of the Klebsiella T2SS abolish fibre assembly and function. Among the four minor pseudopilins, only PulH required E5 for secretion of pullulanase, the substrate of the Pul T2SS. Mass-spectrometry analysis of pili resulting from the co-assembly of PulG E5A variant and PulG WT ruled out an E5 role in pilin processing and N-methylation. A bacterial two-hybrid analysis revealed interactions of the full-length pseudopilins PulG and PulH with the PulJ-PulI-PulK priming complex and with the assembly factors PulM and PulF. Remarkably, PulG E5A and PulH E5A variants were defective in interaction with PulM, but not with PulF and co-purification experiments confirmed the E5dependent interaction between native PulM and PulG. These results reveal the role of E5 in a recruitment step critical for assembly of the functional T2SS, likely relevant to T4P assembly systems.

Introduction

Bacterial interactions with their environment involve the transport of proteins and other macromolecules across their cell envelope. In Gram-negative bacteria, several sophisticated molecular machines facilitate protein secretion across two bilayer membranes [START_REF] Costa | Secretion systems in Gram-negative bacteria: structural and mechanistic insights[END_REF]. Among these, the type II secretion system (T2SS) promotes specific transport of folded proteins across the outer membrane once they have reached the periplasmic compartment though the Sec or the Tat systems [START_REF] Voulhoux | Involvement of the twin arginine translocation system in protein secretion via the type II pathway[END_REF][START_REF] Korotkov | The type II secretion system: biogenesis, molecular archtecture and mechanism[END_REF][START_REF] Nivaskumar | Type II secretion system: a magic beanstalk or a protein escalator[END_REF]. T2SSs are structurally and functionally similar to type IV pilus (T4P) assembly systems [START_REF] Berry | Exceptionally widespread filaments composed of type IV pilins: the prokaryotic Swiss Army knives[END_REF]. Unlike type IV pili, which extend beyond the bacterial surface to promote attachment and motility, the T2SS pseudopilus fibres are thought to be restricted to the periplasm. However, plate-cultured bacteria that overexpress T2SS-encoding genes present extended pseudopili (hereafter referred to as T2SS pili) on the cell surface, a feature that has facilitated their biochemical and structural characterisation [START_REF] Sauvonnet | Pilus formation and protein secretion by the same machinery in Escherichia coli[END_REF][START_REF] Durand | Type II protein secretion in Pseudomonas aeruginosa: the pseudopilus is a multifibrillar and adhesive structure[END_REF][START_REF] Kohler | Structure and assembly of the pseudopilin PulG[END_REF]. T2SS pili are helical homo-polymers composed of one major pseudopilin subunit called PulG in K. oxytoca [START_REF] Sauvonnet | Pilus formation and protein secretion by the same machinery in Escherichia coli[END_REF][START_REF] Kohler | Structure and assembly of the pseudopilin PulG[END_REF]. Mechanistic insights gained from their structure function analysis have revealed that interactions between neighbouring pilus subunits P and P +1 tightly correlate with fibre assembly and function in protein secretion [START_REF] Campos | Detailed structural and assembly model of the type II secretion pilus from sparse data[END_REF]. The fact that these essential contacts take place in the membrane implies a one-start helix rotational assembly mode for these and other type 4 pilus-like fibres (Nivaskumar et al., 2014).

Pseudopilus biogenesis is a multistep process that begins with co-translational insertion of pseudopilins in the inner membrane (IM) via the SRP and the Sec machinery [START_REF] Arts | Export of the pseudopilin XcpT of the Pseudomonas aeruginosa type II secretion system via the signal recognition particle-Sec pathway[END_REF][START_REF] Francetic | Signal recognition particle-dependent inner membrane targeting of the PulG pseudopilin component of a type II secretion system[END_REF]. Pseudopilins are made as precursors anchored in the IM through a positively charged N-terminal peptide that is removed prior to assembly by an inner membrane protease called the prepilin peptidase [START_REF] Nunn | Product of the Pseudomonas aeruginosa gene pilD is a prepilin leader peptidase[END_REF]. Following cleavage of this peptide after a conserved Gly residue at the base of the transmembrane segment, the N-terminal domain of the prepilin peptidase transfers a methyl group to the new N-terminal residue of the mature pilin [START_REF] Strom | A single bifunctional enzyme, PilD, catalyzes cleavage and N-methylation of proteins belonging to the type IV pilin family[END_REF][START_REF] Aly | Cell-free production of integral membrane aspartic acid proteases reveals zinc-dependent methyltransferase activity of the Pseudomonas aeruginosa prepilin peptidase PilD[END_REF].

In addition to the highly abundant major pseudopilins that build the helical homopolymeric fibre, T2SSs contain four minor pseudopilins, essential for function. Purified globular domains of three of these minor subunits, GspI, GspJ and GspK from enterotoxigenic Escherichia coli form a quasi-helical complex, which is predicted to cap the pseudopilus tip [START_REF] Korotkov | Structure of the GspK-GspI-GspJ complex from the enterotoxigenic Escherichia coli type 2 secretion system[END_REF]. Functional, biochemical and molecular dynamics analysis of their full-length equivalents in the Pul T2SS showed that PulI, PulJ and PulK selfassemble in the IM in the absence of other T2SS factors (Cisneros et al., 2012a). The PulJ-PulI-PulK complex promotes initiation of pseudopilus assembly and presumably provides a template for subsequent incorporation of PulH and PulG subunits. Mutants lacking PulI, PulJ or PulK, but not PulH, assemble fewer PulG pili and are completely defective for secretion of the specific Pul T2SS substrate, pullulanase (PulA) (Cisneros et al., 2012a). Biochemical studies of the Pseudomonas aeruginosa Xcp T2SS show that the periplasmic domain of the PulH homologue XcpU forms a complex with other minor pseudopilins in vitro by binding to the PulJ homologue XcpW [START_REF] Yanez | The Crystal Structure of a Binary Complex of two Pseudopilins: EpsI and EpsJ from the Type 2 Secretion System of Vibrio vulnificus[END_REF][START_REF] Korotkov | Structure of the GspK-GspI-GspJ complex from the enterotoxigenic Escherichia coli type 2 secretion system[END_REF][START_REF] Douzi | The XcpV/GspI pseudopilin has a central role in the assembly of a quaternary complex within the T2SS pseudopilus[END_REF].

In addition, the major pseudopilin XpsG of Xanthomonas campestris T2SS and the minor subunit XpsH, a PulH homologue, interact directly in vivo [START_REF] Hu | XpsG, the major pseudopilin in Xanthomonas campestris, pv. campestris forms a pilus-like structure between cytoplasmic and the outer membranes[END_REF]. Based on these studies, PulH homologues are thought to provide a link between the priming complex and the major pseudopilins [START_REF] Yanez | The Crystal Structure of a Binary Complex of two Pseudopilins: EpsI and EpsJ from the Type 2 Secretion System of Vibrio vulnificus[END_REF][START_REF] Korotkov | Structure of the GspK-GspI-GspJ complex from the enterotoxigenic Escherichia coli type 2 secretion system[END_REF][START_REF] Douzi | The XcpV/GspI pseudopilin has a central role in the assembly of a quaternary complex within the T2SS pseudopilus[END_REF]Cisneros et al., 2012a).

Assembly of PulG fibres requires a functional complex called the assembly platform (AP) composed of the IM proteins PulC, PulF, PulL and PulM [START_REF] Py | An inner membrane platform in the type II secretion machinery of Gram-negative bacteria[END_REF][START_REF] Possot | Multiple interactions between pullulanase secreton components involved in stabilization and cytoplasmic membrane association of PulE[END_REF]. The cytoplasmic domain of PulL binds the hexameric ATPase PulE that provides energy for pseudopilus assembly [START_REF] Abendroth | The X-ray structure of the type II secretion system complex formed by the N-terminal domain of EpsE and the cytoplasmic domain of EpsL of Vibrio cholerae[END_REF][START_REF] Camberg | Synergistic stimulation of EpsE ATP hydrolysis by EpsL and acidic phospholipids[END_REF].

Biochemical and structural analyses of AP components in T2SSs have provided molecular insights into their soluble domains and hints about their interactions and organization [START_REF] Korotkov | Structural and functional studies on the interaction of GspC and GspD in the type II secretion system[END_REF]Abendroth et al., 2004b;Abendroth et al., 2004a;[START_REF] Sandkvist | Interaction between the autokinase EpsE and EpsL in the cytoplasmic membrane is required for extracellular secretion in Vibrio cholerae[END_REF][START_REF] Johnson | Mapping critical interactive sites within the periplasmic domain of the Vibrio cholerae type II secretion protein EpsM[END_REF][START_REF] Abendroth | The X-ray structure of the type II secretion system complex formed by the N-terminal domain of EpsE and the cytoplasmic domain of EpsL of Vibrio cholerae[END_REF]. This information has led to the current T2SS model, where the IM platform promotes pseudopilus assembly within a cage-like compartment delimited by the secretin channel formed by a GspD dodecamer in the outer membrane and the GspD-interacting partner GspC in the IM (Gsp being a generic term to designate T2SS components) [START_REF] Mclaughlin | Structural insights into the Type II secretion nanomachine[END_REF].

The hydrophobic segments of major (pseudo)pilins in bacterial T4P and T2SSs are highly conserved and rich in branched chain amino acid residues. In addition to the conserved Gly residue preceding the prepilin peptidase cleavage site, mature subunits contain an invariant Glu residue at position 5 (E5), which is located near the cytoplasmic side of the transmembrane segment and is essential for function [START_REF] Strom | Amino acid substitutions in pilin of Pseudomonas aeruginosa[END_REF][START_REF] Aas | Substitutions in the N-terminal alpha helical spine of Neisseria gonorrhoeae pilin affect Type IV pilus assembly, dynamics and associated functions[END_REF][START_REF] Pugsley | Processing and methylation of PuIG, a pilin-like component of the general secretory pathway of Klebsiella oxytoca[END_REF]. In the T4P systems, residue E5 has been implicated in prepilin processing [START_REF] Pasloske | The expression of mutant pilins in Pseudomonas aeruginosa: fifth position glutamate affects pilin methylation[END_REF] or N-methylation [START_REF] Strom | Amino acid substitutions in pilin of Pseudomonas aeruginosa[END_REF][START_REF] Aas | Substitutions in the N-terminal alpha helical spine of Neisseria gonorrhoeae pilin affect Type IV pilus assembly, dynamics and associated functions[END_REF]. Based on structural studies of T4P, it has also been proposed that E5 is involved in docking of pilins to the growing fibre during assembly, by forming electrostatic contacts with the N-terminal amine of the last pilin subunit incorporated in the pilus [START_REF] Parge | Structure of the fibre-forming protein pili at 2.6 A resolution[END_REF][START_REF] Craig | Type IV pilus structure by cryo-electron microscopy and crystallography: implications for pilus assembly and functions[END_REF].

In contrast, the E5V substitution in PulG from K. oxytoca T2SS did not affect processing and N-methylation [START_REF] Pugsley | Processing and methylation of PuIG, a pilin-like component of the general secretory pathway of Klebsiella oxytoca[END_REF]. Analyses of the PulG pilus structure and assembly show that E5 is not implicated in docking, but participates in fibre stabilisation.

More precisely, once the protomer P has been extracted from the membrane, its E5 residue interacts with two lysine residues (K28 and K35) of protomer P -3 [START_REF] Campos | Detailed structural and assembly model of the type II secretion pilus from sparse data[END_REF]Nivaskumar et al., 2014). However, the Ala substitutions of these Glu and Lys residues lead to strikingly different phenotypes: while pulG K28A/K35A mutants are fully functional in protein secretion, pulG E5A mutants are completely defective. This and other data suggest an additional role for E5 in a step preceding the docking step in the pilus assembly pathway (Nivaskumar et al., 2014). With the exception of the interactions between EpsG and the AP component EpsL in Vibrio cholerae T2SS that have been revealed by chemical cross-linking [START_REF] Gray | In vivo cross-linking of EpsG to EpsL suggests a role for EpsL as an ATPase-pseudopilin coupling protein in the type II secretion system of Vibrio cholerae[END_REF], little is known about the early events of the assembly process. To shed some light on these steps, we sought to characterise interactions between minor and major pseudopilins and to identify AP components that directly interact with pseudopilins using the K. oxytoca T2SS as a model system. By combining bacterial two-hybrid and co-purification approaches with mass spectrometry and functional analyses, we identified several interacting partners of the K. oxytoca major pseudopilin PulG and revealed a novel role of the conserved pseudopilin residue E5, which holds important clues to the assembly mechanism of the T4P fibre family.

Results

Mass spectrometry analysis of PulG and PulG E5A co-assembled into mixed pili

As mentioned above, earlier studies showed that residue E5 is not required for PulG processing or N-methylation [START_REF] Pugsley | Processing and methylation of PuIG, a pilin-like component of the general secretory pathway of Klebsiella oxytoca[END_REF], while studies of T4P suggest the opposite [START_REF] Strom | Amino acid substitutions in pilin of Pseudomonas aeruginosa[END_REF][START_REF] Aas | Substitutions in the N-terminal alpha helical spine of Neisseria gonorrhoeae pilin affect Type IV pilus assembly, dynamics and associated functions[END_REF]. The assembly-defective pilin variants with E5 residue substitutions have been shown to co-assemble into pili in the presence of wild type pilins [START_REF] Pasloske | Assembly of mutant pilins in Pseudomonas aeruginosa: formation of pili composed of heterologous subunits[END_REF][START_REF] Aas | Substitutions in the N-terminal alpha helical spine of Neisseria gonorrhoeae pilin affect Type IV pilus assembly, dynamics and associated functions[END_REF]. However, while N-terminal sequencing of Neisseria gonorrhoeae T4P made of PilE wild type and E5L variants revealed undermethylation of the pilins, it was not clear whether this under-methylation was specific to PilE E5L [START_REF] Aas | Substitutions in the N-terminal alpha helical spine of Neisseria gonorrhoeae pilin affect Type IV pilus assembly, dynamics and associated functions[END_REF]. To clarify the role of E5 in PulG, we used a similar approach and tested whether the assembly-defective PulG E5A variant can be co-assembled into pili with PulG WT . Therefore, we co-expressed the full set of genes encoding the Pul T2SS (on plasmid pCHAP8185, which includes PulG WT ) with the gene encoding assembly-defective PulG E5A variant (on plasmid pCHAP7790, Table 1). The surface proteins were isolated from these bacteria and analysed by SDS-PAGE and Coomassie Blue staining (Experimental Procedures and Figure 1A). A prominent band of approximately 14.5 kDa, the molecular mass of PulG, was present in the sheared fraction (Figure 1A, lane 1). This band was not present in samples from the negative control strain producing PulG E5A and the Pul T2SS lacking PulG (G, Figure 1A, lane 2). The intensity of this band was higher in the strain where both plasmids carried the wild type copy of the pulG gene (Figure 1A, lane 3), compared to the strain carrying a pulG version of T2SS complemented with wild type pulG (Figure 1A, lane 4). To test whether PulG E5A was co-assembled with PulG WT , the gel slices corresponding to the 14.5-kDa band were excised from lanes 1 (strain producing PulG WT and PulG E5A ) and 4 (producing PulG WT ) and analysed for protein content using top-down mass spectrometry (analysis of intact proteins without any digestion) [START_REF] Gault | Complete posttranslational modification mapping of pathogenic Neisseria meningitidis pilins requires top-down mass spectrometry[END_REF][START_REF] Gault | Neisseria meningitidis type IV pili composed of sequence invariable pilins are masked by multisite glycosylation[END_REF]. For PulG WT sample (Figure 1B), two major peaks were found at 14607.56 and 14621.54 Da, corresponding to the molecular mass of PulG (theoretical Mr: 14607.51 Da) and methylated PulG (theoretical Mr: 14621.53 Da). For the PulG WT + PulG E5A sample (Figure 1C), two supplementary peaks corresponding to PulG E5A (experimental: 14549.49 Da; theoretical: 14549.50 Da) and methylated PulG E5A (experimental: 14563.53 Da; theoretical: 14563.52 Da) were observed.

To confirm the N-terminal methylation and presence of an alanine residue (A) instead of a Glu (E) at the 5 th position in the sequence, we performed High Energy Collision Dissociation (HCD) fragmentation of the (14 + ) ions of both methylated PulG and methylated PulG E5A . The MS/MS spectra are shown in Figure 2. The presence of series of b-type ions in both cases confirms without any ambiguity both the methylation of the N-terminus and the identity of the 5th amino acid.

These results show that PulG E5A can assemble into pili, provided it is co-produced with PulG WT . This suggests that PulG E5A likely co-assembles with native PulG into mixed pili.

The presence of methylated and non-methylated forms of both PulG variants in the pili shows further that methylation of pseudopilins is not required for assembly.

Differential requirements of residue E5 for the major and minor pseudopilin function

With the exception of the PulK subunit, which caps the priming complex, all minor pseudopilins in T2SS have the conserved E5 residue. Given its strong conservation among (pseudo)pilins, we wondered whether E5 was also essential for minor pseudopilin function.

To address this question, we introduced E5A substitutions in minor subunits PulH, PulI and PulJ and assessed their ability to support PulA secretion in conditions of low, chromosomelike levels of pul gene expression. The results of three independent secretion assays are shown in Figures 3A andsupplementary Figure S1, and their quantification is shown in Figure 3B. Under these conditions, the PulG E5A variant was as defective for PulA secretion as the negative control strain lacking PulG (Figure 3A, lanes 1-6), as shown previously (Nivaskumar et al., 2014), The pulH deletion mutant supported a low level of PulA secretion (Figure 3A,lanes 11,12) confirming that PulH is required for efficient secretion in physiological expression conditions (Cisneros et al., 2012a). Surprisingly, PulA secretion in the presence of the PulH E5A variant was nearly abolished, suggesting a dominant negative effect of the pulH E5A allele (Figure 3A, lanes 7-12). In contrast, E5A substitutions in minor pseudopilins PulI and PulJ did not affect their function (Figure 3A,.

Replacing the Met-5 with Glu in variant PulK M5E had no effect on PulA secretion (Figure 3A, lanes 25-30), confirming previous results obtained in conditions of pul gene overexpression [START_REF] Vignon | Type IVlike pili formed by the type II secreton: specificity, composition, bundling, polar localization, and surface presentation of peptides[END_REF]. Thus, the requirement for E5 appears to be specific to PulG and PulH pseudopilins, which are not part of the priming tip complex and have been implicated in the downstream steps of pseudopilus assembly (Cisneros et al., 2012a).

Pseudopilin interaction network

The PulJ-PulI-PulK complex presumably provides a template for PulH incorporation (Cisneros et al., 2012a), as suggested by the formation of the quaternary complex comprising all minor pseudopilin periplasmic domains in the P. aeruginosa Xcp T2SS [START_REF] Yanez | The Crystal Structure of a Binary Complex of two Pseudopilins: EpsI and EpsJ from the Type 2 Secretion System of Vibrio vulnificus[END_REF][START_REF] Korotkov | Structure of the GspK-GspI-GspJ complex from the enterotoxigenic Escherichia coli type 2 secretion system[END_REF][START_REF] Douzi | The XcpV/GspI pseudopilin has a central role in the assembly of a quaternary complex within the T2SS pseudopilus[END_REF]. However, this complex did not interact with the globular domain of the major pseudopilin XcpT in vitro [START_REF] Douzi | The XcpV/GspI pseudopilin has a central role in the assembly of a quaternary complex within the T2SS pseudopilus[END_REF], leaving the question of the mechanism that couples the initiation and elongation stages of assembly open. Based on the findings of Hu and collaborators [START_REF] Hu | XpsG, the major pseudopilin in Xanthomonas campestris, pv. campestris forms a pilus-like structure between cytoplasmic and the outer membranes[END_REF], it has been proposed that the minor pseudopilin quaternary complex and the major pseudopilin interact instead though their hydrophobic segments [START_REF] Douzi | The XcpV/GspI pseudopilin has a central role in the assembly of a quaternary complex within the T2SS pseudopilus[END_REF]. To test this possibility and to characterise the pseudopilin interaction network, we employed the bacterial two-hybrid (BAC2H) approach that allows one to study interactions between full-length, membraneembedded proteins [START_REF] Karimova | A bacterial two-hybrid system based on a reconstituted signal transduction pathway[END_REF]. Using this method we had previously demonstrated interactions of PulI with PulJ and PulK (Cisneros et al., 2012a). In the present study, we fused the T18 and T25 fragments of adenylyl cyclase CyaA from Bordetella pertussis to the N-terminus of all five full-length mature pseudopilins and performed BAC2H assays (Experimental Procedures). Using T18-PulG as bait, we identified strong interactions with two minor pseudopilins, PulH and PulJ (Figure 4). When T18-PulH was used as bait, a specific interaction was observed only with T25-PulG. Although both T18-PulH and T25-PulH chimera consistently showed a tendency to interact with PulJ, these interactions were not statistically significant despite low P values (0.106 and 0.201, respectively) (Figure 4A and Supplementary Dataset 1). The T18-PulI chimera showed specific interactions with PulJ and PulK (Figure 4), in agreement with previous studies in several T2SSs (Cisneros et al., 2012a;[START_REF] Korotkov | Structure of the GspK-GspI-GspJ complex from the enterotoxigenic Escherichia coli type 2 secretion system[END_REF][START_REF] Douzi | The XcpV/GspI pseudopilin has a central role in the assembly of a quaternary complex within the T2SS pseudopilus[END_REF]. Conversely, T18-PulJ interacted with PulI (Figure 4A). In addition, T18-PulI, T18-PulJ and T18-PulK showed a weak interaction with PulG. Of note, only PulG formed homo-dimers in the BAC2H assay, consistent with the unique ability of major pseudopilins to form long homo-polymers [START_REF] Durand | XcpX controls biogenesis of the Pseudomonas aeruginosa XcpT-containing pseudopilus[END_REF]. The results of these analyses, summarised schematically in Figure 4B, reveal multiple novel contacts between PulG and minor pseudopilins. Overall, the data are compatible with the formation of complexes containing all five pseudopilin species.

Pseudopilin interactions with IM assembly platform components

Previous functional studies suggest that the minor pseudopilin complex primes fibre assembly and that it might activate the ATPase PulE that is associated with the assembly platform (AP) complex (Cisneros et al., 2012a). The AP is essential for T2SS function and contains multiple copies of IM proteins PulC, PulF, PulL and PulM [START_REF] Py | An inner membrane platform in the type II secretion machinery of Gram-negative bacteria[END_REF][START_REF] Possot | Multiple interactions between pullulanase secreton components involved in stabilization and cytoplasmic membrane association of PulE[END_REF]. To understand the physical and functional link between AP and the pseudopilin complex and to elucidate molecular details of the initiation and elongation steps of assembly, we assessed interactions between the pseudopilins and membrane-embedded AP components by using the BAC2H system. Therefore, we fused the T18-and T25-CyaA fragments to the N-terminal ends of full-length AP components PulC, PulF, PulL and PulM (Experimental Procedures). In the BAC2H assays, both T18-PulG and T25-PulG interacted specifically with the corresponding PulM-and PulF-CyaA chimera, but not with PulCchimera. T18-PulG interacted very weakly with the T25-PulL, but the reciprocal pair did not interact (Figure 5A), which was surprising, given that their homologues in V. cholerae, EpsL and EpsG, interact in a cross-linking study [START_REF] Gray | In vivo cross-linking of EpsG to EpsL suggests a role for EpsL as an ATPase-pseudopilin coupling protein in the type II secretion system of Vibrio cholerae[END_REF]. We confirmed that this was not due to non-functional PulL chimera, since the latter did interact with corresponding PulM hybrids (Figure 5A, black bars on the right), as expected based on previous studies [START_REF] Possot | Multiple interactions between pullulanase secreton components involved in stabilization and cytoplasmic membrane association of PulE[END_REF][START_REF] Buddelmeijer | Green fluorescent chimeras indicate nonpolar localization of pullulanase secreton components PulL and PulM[END_REF]. The results, summarized in Figure 5B, revealed strong and specific interactions of PulG with the PulM and PulF components of the assembly platform, suggesting their direct role in pseudopilus elongation.

Among the minor pseudopilins, PulH also interacted with PulF and PulM, although these interactions seem weaker than those observed between PulG and PulF or PulM, based on beta-galactosidase activity levels (Figure 5A). A weak "one-way" interaction was also detected between T18-PulK and T25-PulM chimera. In addition, PulF interacted weakly but significantly with PulI, PulJ and PulK in one out of two protein hybrid pairs. The high betagalactosidase activity of strains producing T18-PulF and T25-PulF chimera in the BAC2H system (Figure 5A) shows a strong propensity of PulF for dimer formation.

The PulG E5A and PulH E5A variants are specifically defective in the interaction with PulM Given the suggested role of E5A in an early step of the assembly process [START_REF] Campos | Detailed structural and assembly model of the type II secretion pilus from sparse data[END_REF]Nivaskumar et al., 2014), we asked whether the E5A mutation affects interactions of PulG with one of the assembly factors. In BAC2H assay the PulG E5A variant showed equal or stronger interaction signal with PulF, compared to native PulG, as indicated by the high beta-galactosidase activities of T18-PulG E5A or T25-PulG E5A hybrids (Figure 6A). In contrast, the same PulG E5A hybrids showed a significantly decreased interaction with PulM (Figure 6A). These results suggest that mutation E5A specifically alters the interface between PulG and PulM. Likewise, while the E5A substitution in PulH did not affect the PulH-PulF interaction, it reduced the interaction with PulM, supporting a role of E5 in PulM binding (Figure 6B).

The PulG-PulM interaction data were further validated with native, full-length proteins.

We analysed PulG interactions with PulM and the effect of the PulG E5A substitution using a co-purification approach. PulG-His 6 , PulG E5A -His 6 or PulG WT were co-produced with PulM in the absence of other T2SS components (Experimental Procedures). Membrane proteins were extracted from these strains with Triton-X-100 and separated on the Ni-NTA columns.

PulM was co-eluted with PulG-His 6 (Figure 7A, lanes 6-11). Despite the higher levels of the PulG E5A -His 6 variant produced and retained on the column, the quantity of co-purified PulM was significantly reduced (Figure 7A,. Quantification of the relative amounts of PulG and PulM shows that the amount of co-eluted PulM was reduced nearly ten-fold, relative to PulG-His 6 (Figure 7B). As shown in Figure 7A, PulG and PulM were present in very low amounts in the elution fractions when membrane proteins were extracted from the control strain producing untagged PulG (lanes 28-33), indicating very low nonspecific binding to the Ni-NTA resin.

The results of these affinity co-purification experiments were in good agreement with those of the BAC2H analysis, revealing specific binding of PulM to PulG in vivo. They confirm that the E5A substitution in PulG, which abolishes pseudopilus assembly and protein secretion, specifically affected the interaction between PulG and PulM.

Discussion

Archaeal pili and flagella, as well as bacterial T2SS, T4P and competence systems use similar machineries to assemble helical fibres from membrane-anchored (pseudo)pilin subunits, suggesting a common mechanism. The globular (pseudo)pilin domains, exposed on the fibre surface, show variability in size and sequence, presumably optimized to promote specific functions [START_REF] Berry | Exceptionally widespread filaments composed of type IV pilins: the prokaryotic Swiss Army knives[END_REF][START_REF] Nivaskumar | Type II secretion system: a magic beanstalk or a protein escalator[END_REF][START_REF] Shahapure | The archaellum: a rotating type IV pilus[END_REF]. In contrast, their hydrophobic segments are highly conserved, which might reflect constraints imposed by their biogenesis and assembly pathway [START_REF] Campos | The type II secretion system -a dynamic fiber assembly nanomachine[END_REF]. For example, high hydrophobicity is key for efficient targeting to the SRP and Sec pathways during integral membrane protein biogenesis [START_REF] Francetic | Signal recognition particle-dependent inner membrane targeting of the PulG pseudopilin component of a type II secretion system[END_REF][START_REF] Arts | Export of the pseudopilin XcpT of the Pseudomonas aeruginosa type II secretion system via the signal recognition particle-Sec pathway[END_REF] and additional constraints might be linked to specific interactions with the prepilin peptidase or with fibre assembly factors. Here we used the Klebsiella T2SS as a model to study pseudopilus assembly, focusing on the most conserved (pseudo)pilin residue E5 playing an essential role in this process.

Although the E5 residue is involved in pseudopilus stabilisation via long-range interactions, genetic data suggest it plays a critical role at a step preceding pseudopilin docking. Using two complementary mass spectrometry methods we demonstrated unambiguously that PulG E5A co-assembles with PulG WT into mixed PulG pili containing the methylated and non-methylated forms of PulG and PulG E5A . This confirms previous findings that E5A substitution does not prevent N-methylation of PulG [START_REF] Pugsley | Processing and methylation of PuIG, a pilin-like component of the general secretory pathway of Klebsiella oxytoca[END_REF] and shows that methylation is not essential for pseudopilus assembly. This is in agreement with assembly of T4P in the methylase-deficient pilD mutants of P. aeruginosa (Pepe and Lory, 1998) and with the small amount of non-methylated PulG detected in T2SS pilus preparations (Köhler et al., 2004). Compared to PulG WT , the degree of N-methylated PulG E5A was lower, which might be a consequence of pulG overexpression increasing the load on the methyl-transferase function of the prepilin peptidase PulO. Of note, the proportion of PulG E5A in the mixed pili was substantially lower than 50%, which could be explained by the dependence on PuG WT for assembly, as well as by the predicted impact of the E5A substitution on fibre stability, due to the loss of long-range interactions with K28 P-3 and K35 P-3 (Nivaskumar et al., 2014). We propose that co-assembly of PulG E5A relies on its ability to form heterodimers with PulG WT via the previously characterised electrostatic contacts of conserved residues E44 and D48 of the incoming subunit (P -1 ) with R87 and R88 of the P subunit incorporated in the PulG pilus [START_REF] Campos | Detailed structural and assembly model of the type II secretion pilus from sparse data[END_REF]Nivaskumar et al., 2014). This association with PulG WT in the membrane would bypass the defect of PulG E5A possibly related to its targeting to the assembly site, as discussed below.

Pseudopilus assembly requires the formation of the PulJ-PulI-PulK priming complex, essential for protein secretion by the T2SS (Cisneros et al., 2012a). While our previous studies demonstrated the correlation between the formation of this complex and pseudopilus assembly activation (Cisneros et al., 2012a;Cisneros et al., 2012b), the molecular events linking the two processes have not been identified. To understand this link, we employed the BAC2H approach and characterised the network of interactions between full-length membrane-embedded pseudopilins and between individual pseudopilins and the AP components. The results confirmed the PulI-PulJ and PulI-PulK interactions observed in vitro in T2SSs from Vibrio [START_REF] Yanez | The Crystal Structure of a Binary Complex of two Pseudopilins: EpsI and EpsJ from the Type 2 Secretion System of Vibrio vulnificus[END_REF], E. coli [START_REF] Korotkov | Structure of the GspK-GspI-GspJ complex from the enterotoxigenic Escherichia coli type 2 secretion system[END_REF] and P. aeruginosa [START_REF] Douzi | The XcpV/GspI pseudopilin has a central role in the assembly of a quaternary complex within the T2SS pseudopilus[END_REF]. In the BAC2H assay, the full-length PulH showed only a weak tendency to interact with PulJ, although the periplasmic domains of their Pseudomonas homologues interacted in vitro [START_REF] Douzi | The XcpV/GspI pseudopilin has a central role in the assembly of a quaternary complex within the T2SS pseudopilus[END_REF]. In addition, contrary to the latter study, we identified direct contacts of PulG with PulH, which are in agreement with the results obtained in Xanthomonas T2SS studies [START_REF] Hu | XpsG, the major pseudopilin in Xanthomonas campestris, pv. campestris forms a pilus-like structure between cytoplasmic and the outer membranes[END_REF]. In the P. aeruginosa T4P, the BAC2H analysis revealed very similar interactions between FimU, the PulH structural homologue, and the major pilin PilA, showing that these contacts are conserved in both systems [START_REF] Nguyen | Pseudomonas aeruginosa minor pilins prime type IVa pilus assembly and promote surface display of the PilY1adhesin[END_REF]. Morover, in the same study, FimU also failed to interact with FimW, the PulJ equivalent in this T4P system. Finally, we also identified novel direct contacts of PulG with PulJ that are in good agreement with the proposed structural models wherein GspH, but also GspG, could be docked directly to GspJ at the base of the tip complex [START_REF] Korotkov | Structure of the GspK-GspI-GspJ complex from the enterotoxigenic Escherichia coli type 2 secretion system[END_REF]). An interaction between PulG and PulJ might bypass the requirement for PulH, explaining the minor effect of pulH deletion on PulG pilus assembly (Cisneros et al., 2012a) and on PulA secretion [START_REF] Sauvonnet | Pilus formation and protein secretion by the same machinery in Escherichia coli[END_REF] in conditions of pul gene overexpression.

However, when the T2SS components are not overproduced, this requirement becomes more critical, consistent with the strongly defective PulA secretion in the absence of PulH (Figure 3). In addition, all minor pseudopilin subunits showed a weak tendency to interact with PulG in the BAC2H assay, which might explain the capacity of PulI-PulJ and PulI-PulK minor pseudopilin pairs to partially restore initiation of PulG assembly in pulHIJK mutants (Cisneros et al., 2012a).

How do pseudopilins connect to the AP and with the associated ATPase, essential for fibre elongation? The results of our BAC2H analysis show that PulH and PulG, but not the other minor pseudopilins, interact specifically with two AP components, PulM and PulF, which might provide a basis for the recruitment of the initiation complex to the assembly site.

We demonstrated that PulG and PulH interact with the conserved AP component PulF, presumably via TM segments of the two partners, given the absence of prominent periplasmic segments in PulF. In view of their high conservation, PulF and its equivalents in T4P assembly systems might be the main factors imposing restraints on the pilin primary sequence. The sequence conservation of pseudopilin TM segments is consistent with weak but significant binding of all minor pseudopilins to PulF in the BAC2H assay (Figure 5).

Although we cannot exclude the possibility that these weak interactions anchor the PulJ-I-K priming complex to PulF, we favour the model wherein the quaternary minor pseudopilin complex binds to PulF via PulH. In addition, PulF showed a strong tendency to form dimers in this assay, consistent with the crystallography data [START_REF] Abendroth | The three-dimensional structure of the cytoplasmic domains of EpsF from the type 2 secretion system of Vibrio cholerae[END_REF] and with the observed oligomerisation of its homologue PilC from Thermus thermophilus [START_REF] Karuppiah | Structure and oligomerization of the PilC type IV pilus biogenesis protein from Thermus thermophilus[END_REF]. In the recent study of the Myxococcus xanthus T4P architecture by cryo-electron tomography, the PulF homologue PilC also appears to form a dimer [START_REF] Chang | Architecture of the type IVa pilus machine[END_REF].

During fibre elongation, PulF dimers could act as membrane scaffolds or docking sites for the minor pseudopilin complex (or the nascent pilus) on one hand, and the incoming PulG subunits on the other, to facilitate assembly. In the large-scale BAC2H interaction study of T4P from Neisseria meningitidis, the major pilin PilE interacted with the PulF homologue PilG, and both PilE and PilG formed homodimers, much like PulG and PulF [START_REF] Georgiadou | Large-scale study of the interactions between proteins involved in type IV pilus biology in Neisseria meningitidis: characterization of a subcomplex involved in pilus assembly[END_REF]. In the P. aeruginosa and Myxococcus xanthus T4P, the PulF homologue called PilC interacts with the ATPase PilB [START_REF] Takhar | The platform protein is essential for Type IV Pilus Biogenesis[END_REF][START_REF] Bischof | The type IV pilus assembly ATPase PilB of Myxococcus xanthus interacts with the inner membrane platform protein PilC and the nucleotide binding protein PilM[END_REF], consistent with its role in transduction of mechanical energy generated by the ATPase. In the E. coli bundleforming pili (Bfp) the ATPase activity of BfpD is stimulated by specific regions of the PulF homologue BpfE [START_REF] Crowther | The ATPase activity of BfpD is greatly enhanced by zinc and allosteric interactions with other Bfp proteins[END_REF].

Importantly, the BAC2H results revealed interactions of PulG and PulH with the PulM component of the AP. Moreover, the direct interaction of native PulG and PulM was confirmed by a complementary co-purification approach. So far, PulM has been implicated in stabilization of PulL within the AP complex [START_REF] Possot | Multiple interactions between pullulanase secreton components involved in stabilization and cytoplasmic membrane association of PulE[END_REF]. While the results of the BAC2H analysis confirm PulM interaction with PulL, widely observed and well-studied in other T2SSs [START_REF] Py | An inner membrane platform in the type II secretion machinery of Gram-negative bacteria[END_REF][START_REF] Johnson | Mapping critical interactive sites within the periplasmic domain of the Vibrio cholerae type II secretion protein EpsM[END_REF][START_REF] Lallemand | Dynamic Interplay between the periplasmic and transmembrane domains of GspL and GspM in the type II secretion system[END_REF], the strong and specific interactions with PulG and PulH reveal a novel role for PulM, possibly in pseudopilin recruitment to the assembly complex. Furthermore, we have shown that E5A substitutions in PulG and PulH interfere with their interactions with PulM in the absence of any other Pul factors, which implies that, in both cases, the E5 residue is a key feature of the PulG-PulM and PulH-PulM interfaces. These interaction defects caused by the E5A substitution likely account for the dramatic assembly defect of PulG E5A variant. The trans-dominant effect of the pulH E5A allele might be due to the reduced ability of PulH E5A to target the priming complex to PulM, as discussed below. In contrast, residue E5 is dispensable for function of PulI and PulJ subunits, although it might provide optimal packing with the N-termini of the distal neighbouring pseudopilins in the complex, as proposed previously [START_REF] Craig | Type IV pilin structure and assembly: X-ray and EM analyses of Vibrio cholerae toxin-coregulated pilus and Pseudomonas aeruginosa PAK pilin[END_REF].

Our results show that PulG interacts strongly and specifically with PulM, but only very weakly with PulL, which apparently contradicts the studies in Vibrio, showing that EpsG could be cross-linked with EpsL [START_REF] Gray | In vivo cross-linking of EpsG to EpsL suggests a role for EpsL as an ATPase-pseudopilin coupling protein in the type II secretion system of Vibrio cholerae[END_REF]. This difference in interaction might reflect differences between the Vibrio and Klebsiella T2SSs, or could be due to a difference in the techniques used to detect G-L interactions. The interaction of EpsG with EpsL was observed using chemical cross-linking, which might enhance and stabilize a weak or indirect association [START_REF] Gray | In vivo cross-linking of EpsG to EpsL suggests a role for EpsL as an ATPase-pseudopilin coupling protein in the type II secretion system of Vibrio cholerae[END_REF]. Here, we identified direct associations of PulG with PulM and PulF in the absence of other T2SS components using BAC2H, and also, in the case of PulG and PulM, by co-purification in the presence of nondenaturing detergents. Nevertheless, both studies support a similar model wherein interactions of major pseudopilin with the L-M complex result in pilin recruitment to the assembly site.

The architecture of the T2SS, proposed based on partial high-and low-resolution structural data of individual components [START_REF] Mclaughlin | Structural insights into the Type II secretion nanomachine[END_REF] is very similar to that of the Thermus thermophilus or Myxococcus xanthus T4P determined by cryo-electron tomography [START_REF] Gold | Structure of a type IV pilus machinery in the open and closed state[END_REF][START_REF] Chang | Architecture of the type IVa pilus machine[END_REF]. In all models, the secretin and the AP components homologous to PulC, PulL and PulM delimit a cage-like compartment that encloses PulF within and connects directly with the ATPase PulE at its base. While cryoEM tomography shows that the pilus occupies the interior of this compartment, PilO (a PulM homologue) and its interacting partner PilN (corresponding to the transmembrane and periplasmic domains of PulL) were placed in the lower periplasmic ring surrounding the cavity [START_REF] Chang | Architecture of the type IVa pilus machine[END_REF].

Integrated with the previous data, the results of this study allow us to propose a schematic working model of pseudopilus assembly initiation and elongation (Figure 8). In this model, one of the initial steps, following pseudopilin maturation by the prepilin peptidase, would be the assembly of the priming complex PulJ-PulI-PulK and its binding to PulH and PulG (step 1). Consistent with the direct binding of PulH and PulG to PulF, and with PulF self-interaction, this complex would associate with a dimer of PulF (step 2). In step 3, the pseudopilins and PulF would bind to PulM, outside or within the pre-assembled complex that includes the secretin PulD channel in the OM bound to the IM components PulC and PulL.

An independent assembly of this latter complex is consistent with the results of cellular localisation studies of T2SS components fused to fluorescent protein tags [START_REF] Buddelmeijer | Type II secretion system secretin PulD localizes in clusters in the Escherichia coli outer membrane[END_REF][START_REF] Lybarger | Docking and assembly of the type II secretion complex of Vibrio cholerae[END_REF], as well as with the T4P cryo-electron tomography data [START_REF] Chang | Architecture of the type IVa pilus machine[END_REF]. Importantly, association of PulM with PulF-pseudopilin complex requires residue E5 of PulG and PulH (Figure 8, step 3). Results of the T4P study by cryotomography suggest that the ATPase is recruited to the assembly site in the final step of the T4P complex biogenesis [START_REF] Chang | Architecture of the type IVa pilus machine[END_REF]. A similar order of assembly, in which the incorporation of the PulF-pseudopilin complex into the incomplete T2S machine would precede the recruitment of the ATPase PulE, is possible in T2SS (steps 4 and 5). However, there is an important difference between the two systems at the level of PulL, which corresponds to a fusion between PilM and PilN of T4P, leaving open a possibility that ATPase recruitment occurs independently of PulF.

During pseudopilus elongation, PulG, possibly in the form of dimers, would be recruited to the assembly site via interaction with PulM, through the critical residue E5 (step 6). PulG would dock to the available PulF "acceptor" site and bind to the membraneembedded PulG P+1 subunit incorporated in the pseudopilus. ATP hydrolysis could drive rotation of the pilus via PulF to spool the protomer P into the growing fibre (step 7), following the one-start helix assembly model that we proposed and described earlier [START_REF] Campos | Detailed structural and assembly model of the type II secretion pilus from sparse data[END_REF]Nivaskumar et al., 2014). Fibre elongation would comprise cycles of targeting, docking and spooling events (steps 6 to 9).

Based on this model, we propose that co-assembly of PulG E5A relies on its ability to form heterodimers with PulG WT , which would promote targeting to the assembly site [START_REF] Campos | Detailed structural and assembly model of the type II secretion pilus from sparse data[END_REF]Nivaskumar et al., 2014). The trans-dominant effect of PulH E5A variant would be due to its association to pseudopilin-PulF complex but not to PulM. While providing testable hypotheses, this model raises numerous questions, notably those related to the mechanism of exoprotein substrate recruitment and transport. Whether a recruitment step accompanies uptake of exoprotein substrate molecules, or whether there are mechanisms that control substrate entry to the preformed assembly site, are only some of the questions that need to be addressed by further investigation.

The interaction network of pseudopilin subunits and assembly platform proteins in the inner membrane described here will provide the basis for further biochemical and structure function analysis of pseudopilus biogenesis and its mechanistic link with T2SS-mediated protein secretion.

Experimental Procedures

Bacterial strains and plasmids

The Escherichia coli strain DH5 [F' lacI Q ∆lacZM15 pro+ Tn10)] was used for recombinant DNA experiments. Strains PAP7460 [∆(lac-argF)U169 araD139 relA1 rpsL150 ∆malE444 malG501] and PAP5207 [∆(lac-argF)U169 araD139 relA1 rpsL150 pcnB::Tn10 (F' lacI Q ∆lacZM15 pro+)] were used for pul gene expression studies. The cya strain DHT1 [START_REF] Dautin | Sensitive genetic screen for protease activity based on a cyclic AMP signaling cascade in Escherichia coli[END_REF] was used for bacterial two-hybrid experiments. The bacteria were grown in LB medium supplemented with antibiotics, as required: chloramphenicol (Cm) (25 g ml -1 ), ampicillin (Ap) (100 g ml -1 ) or kanamycin (Km) (15 or 25 g ml -1 ). The expression of the pul genes was induced by addition of 0.4 % maltose. Isopropyl--D-thiogalactoside was added to induce lacZ promoter-controlled gene expression in strain PAP5207.

Plasmid construction

Plasmids used in this study are listed in Table 1. Plasmid DNA purification, gel extraction and PCR product purification were performed using appropriate Qiagen kits. Restriction enzymes, DNA ligase and other molecular biology reagents were purchased from Fermentas or New England Biolabs. The high-fidelity Pwo polymerase (Roche) was used for PCR amplification and site directed mutagenesis using the modified Quick-change method. The list of oligonucleotides (synthesized by Sigma Genosys) used for cloning or site-directed mutagenesis is provided in Supplementary Table 1. To construct the BAC2H chimera, the pul genes were PCR-amplified using corresponding primers, treated with DpnI and cloned into pKT25 and pUT18c vectors using KpnI and EcoRI enzymes. All plasmids were sequenced by GATC.

Bacterial two-hybrid and statistical analysis

Competent cells of strain DHT1 were co-transformed with pUT18C and pKT25 derivatives and bacteria were grown for 48 h at 30°C on LB plates containing Ap and Km. Colonies were picked at random and inoculated into 5 ml cultures in LB containing Km and Ap, grown overnight and inoculated the next day into fresh medium containing 1 mM IPTG. Bacteria were cultured to mid-log phase and -galactosidase activity was measured as described [START_REF] Miller | Experiments in molecular genetics[END_REF]. At least 2 independent experiments were performed with 3 randomly picked transformants. Mean values were presented by bar graphs, and error bars indicate standard deviation. Microsoft Excel software was used for data processing and presentation. The statistical analysis was performed using the non-parametric Kruskal-Wallis test, followed by Dunn's post-test for multiple comparisons, using the Prism software.

Purification of PulG pili

PAP7460 bacteria were transformed with pCHAP8185 plasmid containing all pul T2SS genes including pulG WT , or its derivative pCHAP8184 lacking pulG, and with pSU18 or its derivatives pCHAP1205 (PulG WT ) or pCHAP7790 (PulG E5A ) carrying different pulG alleles under control of the lacZ promoter. Bacteria were cultured on LB agar containing Ap, Cm and 0.4 % maltose. After incubating for 48 h at 30°C, bacteria were harvested and resuspended in LB medium. Pili were sheared by vortex treatment and 20 passages through a 26-Gauge needle. Two consecutive centrifugation steps at 16 000 g for 20 min were used to separate bacteria and pili. The pilus fractions were further collected by ultracentrifugation in rotor Ti60 at 150 000 g and pili were resuspended in 20 mM HEPES for further analysis by SDS-PAGE and mass spectrometry.

Mass spectrometry

All samples were desalted by C 4 ZipTip® (Millipore) and eluted directly into a 10 µL spray solution of methanol:water:formic acid (75:25:3). Between 2 and 6 µL were introduced into an Orbitrap Velos mass spectrometer, equipped with ETD module (Thermo Fisher Scientific, Bremen, Germany) using a TriVersa NanoMate® (Advion) in positive ion mode. The spray voltage was set to 1.2-1.6 kV and back-pressure to 0.3-0.4 psi. A full set of automated positive ion calibrations was performed immediately prior to mass measurement. The transfer capillary temperature was lowered to 100°C, sheath and auxiliary gasses switched off and source transfer parameters optimised using the auto tune feature. Helium was used as the collision gas in the linear ion trap. The FT automatic gain control was set at 1x10 6 for MS experiments. Spectra were acquired in the FTMS in full profile mode with between 10 microscans over several minutes, with averaging on and set to max, and a resolution of 60,000 at 400 m/z. The final few spectra were then averaged using Qualbrowser in Thermo Xcalibur 2.1 and deconvoluted using Xtract to produce zero charge mass spectra.

For MS/MS experiments, the FT automatic gain control was set at 2x10 5 . Ions corresponding to the isotopic distribution of a single charge state (14 + ) were selected with the largest possible window to avoid overlap with neighbouring species but minimize signal loss. HCD was performed at 27 eV and spectra were acquired in the FTMS in full profile mode at a resolution of 60,000 at 400 m/z, with 10 microscans and with averaging on and set to the maximum value. The final few spectra were then averaged using Qualbrowser in Thermo Xcalibur 2.1 and deconvoluted using Xtract to produce singly charged MS/MS spectra. MS/MS spectra were interpreted manually.

SDS-PAGE and immuno-detection

Proteins from bacterial extracts were separated by electrophoresis on 9 % or 10 % polyacrylamide gels and transferred onto nitrocellulose membranes (ECL, Amersham) using a semi-dry blotting apparatus. Membranes were blocked with 5% milk in TBST (10 mM Tris, 150 mM NaCl, 0.05% Tween 20) and incubated with polyclonal antisera raised against purified PulA, PulG and MalE-PulM (diluted 1:1000 in TBST-5% milk), followed by four 10min washes and incubation in horseradish peroxidase-coupled anti-rabbit antibody (1:40,000; Amersham). Membranes were developed by enhanced chemiluminescence ECL2 (Thermo) or Western Lightning Plus ECL (PerkinElmer) and recorded using the Typhoon phosphorimager (GE) or LAS 4000 imager (Fujifilm). ImageJ software [START_REF] Abramoff | Image Processing with ImageJ[END_REF] was used to quantify the density of bands.

PulA secretion assay

PAP5207 bacteria were transformed with pCHAP8185 plasmid derivatives containing pul genes with corresponding pseudopilin gene knockouts, and a pSU18 empty vector or its derivatives containing the missing wild type or mutant pseudopilin gene (Table 1). Bacteria were grown in LB containing Ap and Cm in the presence of 0.4% maltose, 1/10 volume of M9 salts and 1 mM IPTG to early stationary phase (OD 600nm >2). Cultures were normalized to OD 600nm = 1 and bacteria were pelleted by centrifugation for 10 min at 16000 g at 4°C.

Bacteria were resuspended in SDS-sample buffer at final concentration of 1 OD 600nm per ml. Supernatant fractions were centrifuged again for 10 min and mixed with equal volume of 2x SDS-sample buffer. Samples corresponding to 0.05 OD 600nm from each fraction were separated by SDS-PAGE on 9% Tris-Tricine gels. Proteins were transferred to nitrocellulose membranes (ECL Amersham) by semi-dry electro-transfer. Polyclonal antisera were used for immuno-detection of PulA.

Co-purification of PulG-bound proteins

Bacteria of strain PAP7460 producing PulG-His 6 , PulG E5A -His 6 or PulG WT variants encoded by pCHAP1362, pCHAP7785 and pCHAP8658, respectively and PulM (from plasmid pCHAP2393) were cultured at 30°C in LB medium containing Cm and Ap to OD 600nm = 1. Bacteria were collected by centrifugation and broken by sonication in cold TBS (20 mM Tris-HCl, pH 7.4, 150 mM NaCl) with 100 µg.ml -1 of lysozyme. The lysate was cleared by centrifugation to remove unbroken debris. Membranes were collected by ultracentrifugation at 186000 x g and resuspended in cold TBS, followed by solubilisation with 2% Triton X-100.

Ultracentrifugation was repeated at 150000 g to remove non-solubilised membranes. Ni-NTA resin beads were washed with 10 volumes of TBS and the solubilised membrane fraction was incubated with Ni-NTA resin at 4°C. The flow-through was collected, followed by seven washes with two column volumes of TBS supplemented with 20 mM imidazole. Proteins were eluted with TBS containing 300 mM imidazole.

Table 1. Plasmids used in this study

Figure 1 .

 1 Figure 1. PulG E5A is N-methylated and co-assembled into pili with PulG WT . A. SDS-PAGE and Coomassie Blue stained sheared fractions from equivalent amounts of bacteria of strain PAP7460 carrying two compatible plasmids (Table 1), as indicated: lane 1, pCHAP8185 (encoding the complete Pul T2SS) and pCHAP7790 (encoding PulG E5A ); lane 2, pCHAP8184 (encoding Pul T2SS lacking PulG) and pCHAP7790; lane 3, pCHAP8185 and pCHAP1205 (encoding PulG WT ); and lane 4, pCHAP8184 and pCHAP1205. Only the relevant portions of the gel are shown, with the molecular mass markers indicated on the left. The expected molecular mass of PulG is around 14.6 kDa. The squares and arrowheads indicate samples that were further analysed by mass spectrometry. B. Deconvoluted high-resolution mass spectrum (in Mr) obtained for the sample in lane 4 (PAP7460 carrying pulG WT allele) indicating the presence of a minor peak at 14607.56 Da corresponding to PulG WT and a major peak at 14621.54 Da corresponding to methylated PulG WT ; C. Deconvoluted high resolution mass spectrum (in Mr) obtained for the sample in lane 1 (PulG WT + PulG E5A ) indicating the presence of supplementary peaks corresponding to PulG E5A (14549.49 Da) and methylated PulG E5A (14563.53 Da).

Figure 2 .

 2 Figure 2. High-energy Collision Dissociation (HCD) analysis of methylated PulG WT and PulG E5A variants co-assembled into pili. HCD fragmentation spectra of the (14+) ion of methylated PulG WT at 1046.05 (top) and methylated PulG E5A at 1041.83 (bottom). Methylation of the N-terminal residue is indicated with an asterisk. The series of N-terminal btype ions obtained in both cases and marked with a star unambiguously delineates the presence of an E at the 5 th position in PulG WT and an A in PulG E5A . C-terminal y-type ions are depicted with a circle.

Figure 3 .

 3 Figure 3. Effect of 5 th residue substitutions on pseudopilin function. Pullulanase (PulA) secretion was assayed in E. coli strain PAP5207 containing pCHAP8185 derivatives with single deletions of pseudopilin genes was complemented with pSU18 plasmid (-) or its derivatives expressing the wild type (WT) or the mutant (E5A or M5E) allele of the missing pseudopilin gene as indicated above the lanes. A. A representative of three independent experiments is shown. Equivalents of 0.05 OD 600nm of cell (C) or supernatant (S) fractions were analysed on 9% Tris-Tricin SDS-PAGE and detected using anti-PulA antibodies. B. Quantification of the fraction of secreted PulA in the three independent experiments shown in panel A and in Figure S1. Bar graphs represent the mean values and the error bars indicate standard deviation.

Figure 4 .

 4 Figure 4. Pseudopilin interaction network determined by the bacterial two-hybrid analysis. A. Beta-galactosidase activities of DHT1 bacteria co-producing indicated T18 and T25 chimera determined as described in Experimental Procedures and expressed in Miller units. NC, activity of bacteria producing T18 and T25 as negative control; PC, activity of positive control strain producing T18-Zip and T25-Zip chimera. Each bar represents mean betagalactosidase activity value from at least 3 independent colonies obtained by cotransformation of pKT25 and pUT18c derivatives encoding pseudopilin chimera (T25 or T18 fused to the N-terminus of mature pseudopilins) indicated by the colour code in the inset: PulG, red; PulH, purple; PulI, orange; PulJ, blue; and PulK, green. The colours of the bars correspond to the T25-fused proteins. The red horizontal line indicates the background mean beta-galactosidase activity measured in the negative control. Error bars indicate standard deviation. Statistical significance relative to the negative controls is indicated above graphs as follows: **** = p<0.001; *** = P< 0.01; * = P < 0.1; ns= non-significant. The inset above the main graph shows the part of the same graph with the scale of beta-galactosidase activities expanded in the low range (from 0 to 500 Miller units). B. The results are summarised schematically in a pentagram depicting pseudopilin arrangement in a putative right-handed helical complex. Arrows are oriented from T18-to T25-chimera and their line thickness indicates the strengths of significant interactions, in the range of beta-galactosidase activities (in Miller units) defined as shown in the legend: weak (50>mean>500), strong (500>mean>1500) and very strong (mean>1500).

Figure 5 .

 5 Figure 5. Interactions of pseudopilins with assembly platform components identified using bacterial two-hybrid analysis. A. Beta-galactosidase activities of DHT1 bacteria producing indicated T18-Pul or T25-Pul hybrids as bait in the presence of AP component chimera. The Pul components analysed are indicated by the single letter and colour code in the inset. NC, negative control strain co-producing T18 and T25 fragments; PC, positive control coproducing T18-Zip and T25-Zip chimera. The bars represent mean values from at least 3 independent colonies resulting from co-transformation of strain DHT1 with indicated pKT25 and pUT18c derivatives. The colours of the bars correspond to the AP proteins tested. The red line indicates the background beta-galactosidase activity measured in the NC. Error bars indicate standard deviation. Statistically significant mean values relative to the negative control (Experimental Procedures and Supplementary Dataset 1) are indicated above bars. The inset above the main graph shows the part of the same graph with the expanded scale of beta-galactosidase activities in the low range (from 0 to 500 Miller units). B. Summary of the interaction data, with the arrows oriented from T18-to T25-chimera and with line thickness corresponding to arbitrary range of interaction strengths indicated in the legend, as in Figure 4.

Figure 6 .

 6 Figure 6. The effect of E5A substitution on PulG and PulH interactions with PulF and PulM. A. Bacterial two-hybrid analysis of PulG and PulG E5A interactions with PulF and PulM. B. Bacterial two-hybrid analysis of PulH and PulH E5A interactions with PulF and PulM. Each bar represents the mean value from at least 3 independent colonies obtained by transformation of pKT25 and pUT18c derivatives containing indicated inserts. The colours of the bars correspond to the AP proteins. Error bars indicate standard deviation. NC, negative control and PC, positive control as indicated in the legend of Figure 4. The red line indicates the background beta-galactosidase activity of the NC. Statistical significance of multiple pairwise comparisons is indicated by stars, as in Figure 4.

Figure 7 .

 7 Figure 7. Co-purification of PulM with PulG-His 6 , PulG E5A -His 6 and PulG. Triton X-100 soluble extracts of total membranes from E. coli strains PAP7460 producing PulM and the indicated PulG variants were subject to affinity chromatography on Ni-NTA matrix (Experimental Procedures). A. SDS-PAGE and immuno-detection of PulG and PulM in fractions of the co-purification. S, solubilised membrane fractions; FT, flow-through; W1, W3 and W7, wash fractions; E1-E6, elution fractions. B. Quantification of the relative amount of eluted PulG and PulM relative to wild type levels, according to the densitometric analysis of the bands in (A).

Acknowledgments

We thank Evelyne Richet for insightful comments and for the critical reading of the manuscript, Jenny-Lee Thomassin for the help with statistical analysis, Alexandra East and Peter J. Bond for helpful suggestions. We are grateful to all members of the Laboratory of Macromolecular Systems and Signaling and of the Laboratory of Intercellular Communication and Microbial Infections for helpful discussions and friendly support. We thank Gouzel Karimova and Daniel Ladant for strains, plasmids and advice concerning the BAC2H analysis. This work was funded by the ANR FiberSpace grant N°ANR-14-CE09-0004. MN was a scholar of the Pasteur-Paris University (PPU) International PhD Program. JSM is funded by a fellowship from the Basque Government. JCR and CM acknowledge the DIM MALINF from the Ile de France Region for funding the LTQ Orbitrap Velos. The authors declare that they have no conflict of interest.

Name

Origin/resistance Relevant markers Source/reference pUT18c ColE1/Ap R placZ-T18 (Karimova et al., 1998) pKT25 p15A/Km R placZ-T25 [START_REF] Karimova | A bacterial two-hybrid system based on a reconstituted signal transduction pathway[END_REF] pUT18c-Zip ColE1/Ap R GCN4 (Leu zipper region) fused to T18 (Karimova et al., 1998) pKT25-Zip p15A/Km R GCN4 (Leu zipper region) fused to T25 (Karimova et al., 1998) pSU18 p15A/Cm R placZ, lacZ' (Bartolomé et al., 1991) pCHAP1205 p15A/Cm R pSU18 pulG (Possot et al., 2000) pCHAP1329 p15A/Cm R pSU18 pulJ (Possot et al., 2000) pCHAP1331 p15A/Cm R pSU18 pulH (Possot et al., 2000) pCHAP1351 p15A/Cm R pSU18 pulI (Cisneros et al., 2012) pCHAP1362 p15A/Cm R pSU18 pulG-His 6 (Kohler et al., 2004) pCHAP2393 ColE1/Ap R pUC18 pulM (Possot et al., 2000) pCHAP6117 p15A/Cm R pSU18 pulJ E5A This study pCHAP7330 ColE1/Ap R pUT18c pulG (Nivaskumar et al., 2014) pCHAP7332 p15A/Km R pKT25 pulG (Nivaskumar et al., 2014) pCHAP7785 p15A/Cm R pSU18 pulG E5A -His 6 This study pCHAP7790 p15A/Cm R pSU18 pulG E5A This study pCHAP8113 ColE1/Ap R pUT18c pulC This study pCHAP8119 p15A/Km R pKT25 pulC This study pCHAP8154 ColE1/Ap R pUT18c pulM This study pCHAP8155 p15A/Km R pKT25 pulM This study pCHAP8184 ColE1/Ap R pCHAP8185 pulG (Campos et al., 2010) pCHAP8185 ColE1/Ap R pulS, pulA NA pulB pulCDEFGHIJKLMNO (Cisneros et al., 2012) pCHAP8201 ColE1/Ap R pCHAP8185 pulH::kan (Cisneros et al., 2012) pCHAP8209 ColE1/Ap R pCHAP8185 pulJ::kan (Cisneros et al., 2012) pCHAP8212 ColE1/Ap R pCHAP8185 pulK::kan (Cisneros et al., 2012) pCHAP8218 ColE1/Ap R pCHAP8185 pulI::kan (Cisneros et al., 2012) pCHAP8245 ColE1/Ap R pUT18c-pulI (Cisneros et al., 2012) pCHAP8246 ColE1/Ap R pUT18c pulJ This study pCHAP8247 ColE1/Ap R pUT18c pulK This study pCHAP8248 p15A/Km R pKT25 pulI (Cisneros et al., 2012) pCHAP8249 p15A/Km R pKT25 pulJ (Cisneros et al., 2012) pCHAP8250 p15A/Km R pKT25 pulK (Cisneros et al., 2012) pCHAP8256 ColE1/Ap R pUT18c pulH This study pCHAP8257 p15A/Km R pKT25 pulH (Cisneros et al., 2012) pCHAP8364 ColE1/Ap R pUT18c pulF This study pCHAP8365 p15A/Km R pKT25 pulF This study pCHAP8418 p15A/Cm R pSU18 pulH E5A This study pCHAP8420 p15A/Km R pKT25 pulG E5A (Nivaskumar et al., 2014) pCHAP8434 p15A/Km R pKT25 pulH E5A This study pCHAP8446 ColE1/Ap R pUT18c pulH E5A This study pCHAP8472 ColE1/Ap R pUT18c pulL This study pCHAP8484 p15A/Km R pKT25 pulL This study pCHAP8568 p15A/Cm R pSU18 pulG This study pCHAP8639 p15A/Cm R pSU18 pulK M5E

This study pCHAP8670

ColE1/Ap R pUT18c pulG E5A (Nivaskumar et al., 2014)

Fibre elongation begins with the recruitment of PulG subunits, likely in the form of dimers, by PulM (6). As in step 3, this recruitment requires a direct contact between the E5 residue of PulG and PulM (6). PulG enters the assembly platform, docks to PulF via its TM segments and associates with PulG P+1 protomer of the proto-pseudopilus via their globular domains (7), through electrostatic contacts described previously (Nivaskumar et al., 2014). ATP hydrolysis causes conformational changes in PulE that are transmitted to PulF through direct contact, driving the rotation of the proto-fibre (7). The incoming PulG protomer is spooled into the fibre, which results in an overall extension of the pseudopilus (7 and 8). Fibre growth comprises multiple cycles of PulG recruitment, docking and extraction (steps 6 to 9).


Kevin Dalleau
email: kevin.dalleau@loria.fr

Miguel Couceiro
email: miguel.couceiro@loria.fr

Malika Smaïl
email: malika.smail@loria.fr

Malika Smail-Tabbone

Clustering graphs using random trees

published or not. The documents may come

Introduction

Identifying community structure in graphs is a challenging task in many applications: computer networks, social networks, etc. In this paper, we propose a decision tree based method to compute pairwise distances between vertices that we call GraphTrees (GT). These dissimilarities between vertices in a graph can be used for clustering, but also for other purposes such as filtering or information retrieval.

While many graph clustering algorithms have been proposed, all of them fall into the three following categories:

-Top-down approaches, where the set of vertices is split into partitions in a iterative fashion, -Bottom-up approaches, where each vertex is first assigned to its own cluster and then merged with other vertices according to a specific measure, -Local optimization approaches, where a random clustering is first performed and vertices are then migrated.

A thorough review of the methods already available has been performed by Schaeffer et al. in [START_REF] Schaeffer | Graph clustering[END_REF]. Other interesting approaches have been proposed since, such as the Louvain clustering approach [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], based on modularity optimisation.

In this paper, we present a novel tree-based method enabling the computation of vertex-vertex similarities in graphs 1 and that we call GraphTrees (GT).

Using random trees on graphs leverages the use of decades of research on the subject, opening a wide array of possible improvements. Moreover, using different types of trees, the approach could be extended to vertex-attributed graph clustering.

The paper is organized as follows. In Section 2, we present our method. We then discuss its performance in Section 3 through an empirical study on real and synthetic datasets. In the last section of the paper, we present a brief discussion of our results and state some perspectives for future research.

Method

In this section, we begin by describing our proposed method. We then compare two different approaches to compute a (dis)similarity matrix. The first one is inspired by the approach of unsupervised extra-trees (UET) [START_REF] Dalleau | Unsupervised extremely randomized trees[END_REF], while the second one uses the mass-based distance proposed by [START_REF] Ting | Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure[END_REF].

The intuition behind GT is to leverage a recursive partition of the vertices to compute (dis)similarities. This partition is performed using random trees. This approach has already been studied in the case of data represented as feature vectors [START_REF] Dalleau | Unsupervised extremely randomized trees[END_REF], [START_REF] Ting | Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure[END_REF] but not to graphs.

UET is a tree-based method extending random trees to compute the similarities between instances. The idea is that all instances ending up in the same leaves are more similar to each other than to other instances. The pairwise similarities s(i, j) are hence obtained by increasing s(i, j) for each leaf where both i and j appear. A normalisation is finally performed when all trees have been constructed, to have values in the interval [0, 1].

Leaves, and, more generally, nodes of the trees can be viewed as partitions of the original space. Enumerating the number of co-occurrences in the leaves is then the same as enumerating the number of co-occurrence of instances in the smallest regions of a specific partitioning.

While the method has been applied to feature vectors, we show in this paper that the same approach can be applied to graphs, with a simple change to the splitting method. In UET, the split is performed by selecting a random cut-point on one attribute, sampled from the attribute set without replacement. When applied to graphs, the split can be performed in a similar fashion by choosing randomly one vertex v s from the graph. Let N (v) be the set of neighbours of a vertex v in a graph. When a split is done, the resulting left node contains all vertices v ∈ N (v s ) and v s , while the right node contains the other vertices.

The algorithm of GT is presented Algorithm 1. Algorithm 2 presents how to obtain a similarity matrix from the forest of random trees. This method of computing a similarity matrix from the trees is the same as the one proposed in [START_REF] Dalleau | Unsupervised extremely randomized trees[END_REF], the trees being GraphTrees.

Algorithm 1: Graph tree algorithm

Data: A graph G(V, E), an uninitialized stack S Parameter: Minimum node size to split nmin Result: A list of leaves L root node = V ; vs = a vertex sampled without replacement from V ; This approach has some limitations. First, when a dissimilarity is needed, it is necessary to apply a transformation to the similarity matrix. The choice of transformation can have a great impact on the subsequent clustering. Moreover, this adds up to the time complexity of the method, as a transformation of an n × n similarity matrix is at least in O(n 2 ), and can become an issue in large graphs.

V lef t = N (vs) ∪ {vs} ; //N (v) returns the set of neighbours of v V right = V \ V lef t ; Push V lef
In [START_REF] Ting | Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure[END_REF], Ting et al. presents a probability mass-based dissimilarity measure, obtained using random trees. The key property of their proposed measure is that the dissimilarity between two instances in a dense region is higher than the same interpoint dissimilarity between two instances in a sparse region of the same space. This mass-based dissimilarity between two instances depends on the mass probability of the smallest region that covers these two instances.

Let H ∈ H(D) be a hierarchical partitioning of the original space of a dataset D into non-overlapping and non-empty regions, and let R(x, y|H) be the smallest local region covering x and y with respect to H. The mass-based dissimilarity estimated by a finite number t of models is given by the following equation:

m e (x, y|D) = 1 t t i=1 P (R(x, y|H i )) (1)
where

P (R) = 1 |D| z∈D 1(z ∈ R).
Fig. 1 presents an example of hierarchical partition H of a dataset D containing 8 instances. For the sake of the example, let us compute m e [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Dongen | A cluster algorithm for graphs[END_REF] and m e [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Maaten | Visualizing data using t-SNE[END_REF].

We have m e (1, 4) = 1 8 (2) = 0.25, as the smallest region where instances 1 and 4 co-appear contains 2 instances. However, m e (1, 8) = 1 8 (8) = 1, since instances 1 and 8 only appear in one region of size 8, the original space. These instances are vertices in our case.

Similarly to the first approach to obtain a dissimilarity matrix, mass-based dissimilarity can be applied to graphs. The method is based on two steps: (i) partition the vertices using random trees, (ii) compute pairwise dissimilarities between vertices using 1.

This approach has multiple advantages over the first one. First, as many clustering algorithms require a distance matrix as an input, a similarity matrix requires a transformation to be used. Using the mass-based approach, this transformation is no longer needed, as a dissimilarity matrix is obtained. Secondly, a mass-based pairwise distance between vertices might be more effective to find communities of varying densities.

The computation of pairwise vertex-vertex dissimilarities using Graph Trees and the mass-based dissimilarity we just described has a time complexity of O(tΨ log(Ψ ) + n 2 tlog(Ψ )) [START_REF] Ting | Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure[END_REF], where t is the number of trees, Ψ the maximum height of the trees, and n is the number of vertices. When Ψ << n, this time complexity becomes O(n 2 ). In the next section, we evaluate GT on both real-world and synthetic datasets.

Evaluation

This section is divided into 3 subsections. In Subsection 3.1 we present some preliminary work, where we assess the different methods to compute dissimilarities between vertices. We then perform an assessment of the discrUsing random trees on graphs leverages the use of decades of research on the subject, opening a wide array of possible improvements. Moreover, using different types of trees, the approach could be extended to vertex-attributed graph clustering. iminative power of our proposed method 3.2. Finally in 3.3, we present its clustering performance.

Comparison of GT using UET and graph trees using mass-based dissimilarities

Even though the mass-based approach is more appealing than the UET approach complexity-wise, we empirically assess here how the two differ on various graphs. The graphs used in this subsection are described in Table 1. The stochastic bloc models (SBM) graphs are composed of k blocks of a user-defined size, connected by edges depending on a specific probability which is a parameter. In this paper, we carried out an empirical study on two SBM, denoted SBM 1 and SBM 2 that differ by the probabilities of intra-and intercluster edge creation. The Email-Eu-Core graph [12] [7] represents relations between members of a research institution, where edges represents communication between those members. The dataset also contains ground-truth community memberships of the vertices. Each individual belongs to exactly one of 42 departments at the research institute. Finally, the random graph is an Erdos-Renyi random graph [START_REF] Erdds | On random graphs I[END_REF], where edges are created with a probability p = 0.7 in our case. This graph does not exhibit any cluster structure, and is used as a negative control.

We applied our proposed mass-based approach and naive approach to compute vertex dissimilarities on these graphs. We then used t-SNE [START_REF] Maaten | Visualizing data using t-SNE[END_REF] to obtain a 2D projection of these vertices. We finally plotted the distance distribution. All results are presented in Fig. 2, 3, 4 and 5 . We observe that in both SBM models, the density-based approach leads to 3 clearly separated clusters, whereas the approach using UET leads to a sparser cluster. The difference between both methods is even greater in SBM2 here the density of edges between different clusters is higher. In that case, we observe that using GT with UET we effectively lose one cluster in the projection. In the case of the Email-Eu-Core graph, the projection shows that the mass-based approach better separates clusters than the naive one, where all clusters tend to gather. Finally, using both approaches on the random graph gives an expected result. Indeed, no clear cluster structure can be observed in the projection using both approaches. Fig. 3. SBM1 graph: the computed dissimilarities shows that the density-based approach leads to clearly separated clusters, with a dense core cluster, while the naive one tends to a sparser core cluster. Left graphs corresponds to distances using GT-Mass-based, and right graphs to distances using GT-Classic. Fig. 4. SBM2 graph: the computed dissimilarities shows that the density-based approach leads to clearly separated clusters, unlike the naive approach. Moreover, the distribution of pairwise distance between vertices is more spread out when the massbased approach is used. Left graphs corresponds to distances using GT-Mass-based, and right graphs to distances using GT-Classic. Fig. 5. Email-Eu-Core: the mass-based approach better separates clusters than the naive approach, where all clusters are close. Left graphs corresponds to distances using GT-Mass-based, and right graphs to distances using GT-Classic. The mass-based approach better separates clusters than the naive one, where all clusters tend to gather.

In the following section, we will assess the performance of GT. This evaluation will be performed using the mass-based method, as we observed its versatility in this subsection.

Assessment of the dissimilarities

All the experiments presented in this subsection are based on the comparison of the mean intracluster dissimilarities and the mean intercluster dissimilarities, as well as their differences, taking values in the interval [0, 1]. These metrics enable a comparison that is agnostic to a subsequent clustering method.

The mean difference is computed as follows. First, the arithmetic mean of the pairwise dissimilarities between all samples having the same label is computed, corresponding to the mean intracluster dissimilarity µ intra . Then the same process is done for samples with a different label, giving the mean intercluster dissimilarity µ inter . We finally compute the difference ∆ = |µ intra -µ inter |. In our experiments, this difference ∆ is computed 10 times. In the following section, ∆ denotes the mean of differences between runs, and σ its standard deviation.

The datasets used in this subsection are described in Table 2. We compare the values obtained using GT and two other methods, SimRank [START_REF] Jeh | SimRank: a measure of structural-context similarity[END_REF] and ASCOS [START_REF] Chen | ASCOS: an asymmetric network structure context similarity measure[END_REF]. Since these approaches compute similarities between vertices, we used the relation d(v i , v j ) = 1 -s(v i , v j ) to obtain pairwise dissimilarities. The results are presented Table 3. We also computed the running time for each computation, that are presented in Table 4.

Table 3. Comparison of the mean difference between mean intracluster dissimilarities and mean intercluster dissimilarities on benchmark graph datasets. Best results are in boldface.

Dataset GT -∆ (σ) SimRank -∆ (σ) ASCOS -∆ (σ) Karate 0.131 (0.008) 0.112 (0.000) 0.113 (0.000) PolBooks 0.062 (0.002) 0.080 (0.000) 0.053 (0.000) Football 0.215 (0.002) 0.139 (0.000) 0.054 (0.000) WebKB 0.050 (0.002) 0.106 (0.000) 0.023 (0.000) ASCOS outperform the other distances in terms of ∆, as it is lower in most cases. However, values of ∆ are similar and remain small for all methods and for all datasets but Football. In terms of running time, GT outperforms both methods, except in the case of the Karate graph. This is explained by the fact that this graph is the smallest, with 34 vertices. We notice than for more complex graph however, GT is competitive.

It is also interesting to compare the distribution of distance for each method according to the choice of algorithm (GT, SimRank or ASCOS). Fig. 6 and 7 display these distribution for the Football and WebKB graphs (respectively). When GT is used, the variance of the distribution is higher than its counterparts, and multiple peaks can be observed. This is also observed for all other datasets in this empirical evaluation, but not presented here.

Evaluation using a clustering algorithms

Using the NMI We then evaluated our approach on simple graphs against two other methods, in order to assess if our proposed method is competitive in such graphs. This evaluation is performed on both synthetic and real-world graphs. We compare the NMI obtained using GT with the NMI obtained using two state-of-the-art clustering method on simple graphs, MCL [START_REF] Dongen | A cluster algorithm for graphs[END_REF] and Louvain [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. N M I is a clustering quality metric. Its values lie in the range [0, 1], with a value of 1 being a perfect assignment.

To perform this evaluation, we used commonly used benchmark datasets, presented Table 5. We first computed the distance matrices using GT, with a total number of trees n trees = 200. We then applied k-means on the points obtained using t-SNE on the distance matrix. We repeated this procedure 20 times and computed means and standard deviations of the NMI.

During our experiments, we found out that preprocessing the distances prior to the clustering phase may lead to better results, in particular with Scikit learn's [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] QuantileTransformer. This transformation tends to spread out the most frequent values and to reduce the impact of outliers.

Fig. 8 shows the distribution of vertex-vertex distance for PolBooks with and without prior preprocessing using this approach. We observe that the distribution of the pairwise distance is spread out, with visible peaks. In our evaluations, we performed this quantile transformation prior to every clustering, with n quantile = 10.

The results are presented Table 6. We compared the mean NMI using the t-test, and checked that the differences between the obtained values are statistically significant.

We observe that our approach is competitive with state of the art methods in the case of non-attributed graphs on the benchmark datasets. In one specific case, we even observe that Graph trees significantly outperforms state of the art results, on the SBM graphs. This seems to confirm that our method performs particularly well in the case of clusters of different size. Using the modularity of the partitions Another way to assess the performance of GT is to use the modularity. Modularity measures the strength of a specific partition, and is obtained by [START_REF] Chen | ASCOS: an asymmetric network structure context similarity measure[END_REF].

modularity(V 1 , . . . , V k ) = K k=1 |E kk | 2|E| -( K l=1 |E kl | 2|E| ) 2 (2)
The intuition is that the higher the modularity, the lower the proportion of edges between vertices in different clusters.

Our approach here is to compare the modularities obtained using partitions obtained with GT, and the ones obtained using the ground truth values as partitions.

We performed this evaluation on the datasets presented Table 7. WebKB represents relations between web pages of four universities, where each vertex label corresponds to the university and the attributes represent the words that appear in the page. The Parliament dataset is a graph where the vertices represent french parliament members, linked by an edge if they cosigned a bill together. The vertex attributes indicate their constituency, and each vertex has a label that corresponds to their political party. The lawyers dataset represents relations between attorneys, that are described with categorical attributes for each of them. Finally, the HVR graph represent relations between malaria genes. The procedure is the following. We first compute the vertex-vertex distances using GT. We then apply t-SNE and use the k-means algorithm on the points in the embedded space. We set k to the number of clusters, since we have the ground truths. We computed the modularity of the clusterings obtained in 2 settings: (i) using a distance only on the structures using GT and (ii) using the ground truth values. We repeat these steps 5 times and report the means and standard deviations. The results are presented Table 8. We notice that the structural distance using GT leads to good results, even higher than the modularities obtained using the ground truths. This can be explained by the fact that ground truth labels do not always constitute an absolute truth, especially in terms of network structure.

Overall, GT seems to be a good candidate to compute dissimilarities between vertices of a graph.

Discussion and future work

In this paper, we presented a method based on the construction of random trees to compute similarities between graph vertices, called GT. The method works by recursively splitting the set of vertices. Each split is performed by randomly sampling a new vertex from the vertex set of the previous node. Direct neighbours of this vertex then create a new node in the tree, while the other vertices create another node in the tree. A distance between the vertices can then be defined, as the leaves correspond to a partition of the vertex space, and where each region contains similar vertices. In this work, we propose to use a mass-based approach to compute this distance.

We show that the method we propose is competitive with state of the art methods in terms of quality of clustering on graphs. In our benchmark datasets, the mean differences ∆ between the mean intracluster similarities and the mean intercluster similarities tends to be higher when GT is used. However, it should be noted that although this result is not promising, our proposed method has a lower running time. Moreover, our assessment performing an actual clustering on our data showed that the method we propose is competitive in terms of NMI against to state-of-the-art methods, i.e Louvain and MCL. This is particularly true in the case on the stochastic block model graph, where GT outperforms Louvain and MCL by 45% and 22%, respectively. This result might be a strong hint that the mass-based approach we use is particularly efficient in the case of graphs with clusters of variable size and density.

Comparing the modularities of partitions obtained using GT versus the ground truth partitions also shows that GT exhibits a good performance.

One of the appealing aspects of GT is that by computing forests of graph trees and other trees that specialize in other types of input data, e.g, feature vectors, it is then possible to compute pairwise dissimilarities between vertices in vertexattributed graphs. While many existing methods that tackle this problem are limited to categorical attributes and/or require a costly transformation of the graph, a tree-based approach would not suffer from these shortcomings. Indeed, the trees being built on the vertex attributes can take as an input both numeric and symbolic data. We already performed some experiments in the attributed graph settings that we didn't present in this paper. While the approach seems promising, our first results showed that the quality of the clusterings varies greatly between different datasets. This observation may be due to multiple factors, such as the aggregation method chosen to aggregate the graph trees and the attribute trees.

It should be noted that most of our empirical results depend on the choice of a specific clustering algorithm. Indeed, GT is not a clustering method per se, but a method to compute pairwise distances between nodes. As other distance-based methods, this is a strength of the method we propose in this paper. Indeed, the clustering task can be performed using many algorithms, leveraging their respective strengths and weaknesses.

One of the shortcomings of our proposed approach is that in graphs where the average degree is low, the splitting method leads to large unbalanced trees. Other approaches can be used, such as a splitting based on a specific criterion. As this approach merges the fields of graph clustering and decision trees, interesting research directions can be pursued.

8 Fig. 1 .

 81 Fig.1. Example of partitioning of 8 instances in non-overlapping non-empty regions using a random tree structure. The blue and red circles denote the smallest nodes (i.e, regions) containing vertices 1 and 4 and vertices 1 and 8, respectively.

Fig. 2 .

 2 Fig. 2. Random graph: the computed dissimilarities effectively shows an absence of separated clusters. The lowermost part presents the distribution of pairwise distance between vertices.

Fig. 6 .

 6 Fig. 6. Distribution of distances in Footbal obtained using GT (upper left), SimRank (upper right) and ASCOS (bottom). The different colours correspond to the data from different clusters, according to the provided ground truth.

Fig. 7 .

 7 Fig. 7. Distribution of distances in WebKB obtained using GT (upper left), SimRank (upper right) and ASCOS (bottom). The different colours correspond to the data from different clusters, according to the provided ground truth.

Fig. 8 .

 8 Fig. 8. Distribution of pairwise vertex distances without preprocessing (blue) and after quantile transformation (green).

Table 1 .

 1 Graphs used in Subsection 3.1

	Graph	# vertices # edges
	Stochastic Block Model 1 115	1226
	Stochastic Block Model 2 1005	25571
	Email-Eu-Core	2708	5429
	Random graph	200	12928

Table 2 .

 2 Datasets used for the evaluation of GT without any subsequent clustering

	Dataset # vertices # edges # clusters
	Karate 34	78	2
	Polbooks 105	441	3
	Football 115	1226	10
	WebKB 877	1480	4

Table 4 .

 4 Comparison of the mean durations on benchmark graph datasets. Best results are in boldface.

	Dataset GT -Time (s) (σ) SimRank -Time (s) (σ) ASCOS -Time (s) (σ)
	Karate 0.130 (0.0163)	0.296 (0.01)	0.094 (0.002)
	PolBooks 0.454 (0.001)	6.876 (0.105)	1.238 (0.030)
	Football 0.477 (0.012)	11.538 (0.151)	1.663 (0.003)
	WebKB 45.798 (1.417) 139.590 (1.922)	53.439 (2.036)

Table 5 .

 5 Datasets used for the evaluation of clustering on simple graphs using Graphtrees

	Dataset	# vertices # edges Average degree # clusters
	Football	115	1226	10.66	10
	Email-Eu-Core 1005	25571 33.24	42
	Polbooks	105	441	8.40	3
	SBM3	450	65994 293.307	3

Table 6 .

 6 Comparison of NMI on benchmark graph datasets. Best results are in boldface.

	Dataset	Graph-trees	Louvain	MCL
	Football	0.923 (0.007) 0.924 (0.000) 0.879 (0.015)
	Email-Eu-Core 0.649 (0.008) 0.428 (0.000)	0.589 (0.012)
	Polbooks	0.524 (0.012) 0.521 (0.000)	0.544 (0.02)
	SBM3	0.998 (0.005) 0.684 (0.000)	0.846 (0.000)

Table 7 .

 7 Datasets used for the evaluation of clustering using the modularity

	Dataset	# vertices # edges # clusters
	WebKB	877	1480	4
	Parliament 451	11646 7
	HVR	307	6526	2
	Lawyers	71	575	2

Table 8 .

 8 Modularities using GT or the ground truth labels. Best results are indicated in boldface.

	Dataset	GT Ground truth
	WebKB	0.74 0.74
	HVR	0.15 0.15
	Parliament 0.46 0.20
	Lawyers	0.27 0.26