might be critical for successful acquisitions of secretins from other systems. Flagellum assembly resembles the inside-out model of NF- T3SS assembly [128,129]. The ancestral NF-T3SS probably also assembled inside-out because it lacked a secretin. The inside-out assembly of the secretion apparatus and especially of the newly acquired SctD protein at the inner membrane might have led to interactions with secretins from other systems that stabilized an outer membrane channel in the NF-T3SS complex. Indeed, extant NF-T3SS secretins are inserted in membranes independently of the assembly of the inner ring. The inner ring assembles, and then stabilizes the secretin multimer [53]. These interactions presum- ably evolved towards a stable genetic linkage of the secretin with the NF-T3SS. Outside-in assembly modes, e.g. as proposed for Yersinia NF-T3SS, might have evolved after the acquisition of the secretin. Studies on the assembly of Myxo systems might therefore elucidate the mechanisms of assembly of the ancestral NF-T3SS and also of the evolution of the assembly process of the other NF- T3SSs. Rapid adaptation of NF-T3SSs to diverse eukaryotic cell envelopes Acquisition of the secretin and of the translocon proteins allowed bacteria to deliver effectors to eukaryotic cells. This was followed by very rapid diversification of NF-T3SSs into groups with different characteristics and tropisms (Figure 7). Such rapid radiation hinders robust phylogenetic inference after the split of the Chlamy systems at the base of the remaining NF-T3SSs (Figure 4), even though we were able to infer older splits with strong confidence. Needle/pilus, tip and translocon proteins, all of which promote intimate interactions with the host, evolved quickly and were probably key determinants of NF-T3SSs radiation. The original NF-T3SS included a needle (SctF) resembling the flagellum homolog. The replacement of the needle by a pilus was a key late adaptation in NF-T3SSs that specifically interact with the cell walls of plants and fungi. Sequence evolution of the NF-T3SS pilus of some plant-associated bacteria is driven by strong positive/diversifying selection in response to host defenses [130,131]. It might be expected that vertebrate immune systems would have had similar effects on the evolution of animal- associated NF-T3SSs. Hence, diversifying selection on plant- associated NF-T3SSs is probably not the cause of the differences between pili and needles. Instead, the pilus probably reflects adaptation to the thick cell walls of plants and fungi. More genomic, functional and structural data on NF-T3SSs involved in plant interactions will be necessary to understand whether all these plant-associated NF-T3SSs arose independently or derived from the same ancestral NF-T3SS. This work shows how a key protein secretion system arose from the recruitment of a structure that evolved for another purpose. The T3SS was initially adapted to the transport of flagellar components through the membrane and was probably exapted on multiple occasions to transport other proteins. One of those exaptations resulted in the ancestral NF-T3SS. This system adapted to its new function by a series of gene losses and acquisitions. Strikingly, it acquired secretins multiple times. Thereafter, the system was able to deliver effectors directly to eukaryotic cells, which dramatically increased its rapid diversifi- cation due to the adaptive value of NF-T3SS for mutualistic and antagonistic interactions with eukaryotes. This evolutionary reconstruction represents a remarkable example of how successive losses and recruitments of components from a series of existing molecular machines can lead to the evolution of a new complex system. Origins and Diversification of T3SS Materials and Methods Genome data Genomes were extracted from GenBank Refseq. To extend the taxon sampling, we added to the dataset some draft genomes of interest. We analyzed 1385 genomes with 2575 replicons (1483 chromosomes and 1092 plasmids). Data availability The NF-T3SS clusters identified in this study can be queried using different criteria (including taxonomy and NF-T3SS family name), and visualized along with the results of our Hmmer profiles searches at http://secreton.web.pasteur.fr. The profiles of NF- T3SS and flagellum proteins can be queried at http://mobyle. pasteur.fr/cgi-bin/portal.py#forms::T3SSscan-FLAGscan. The list of NF-T3SSs and flagella included in phylogenetic analyses can be found in Dataset S2. Construction of sequence profiles for NF-T3SSs and flagella We selected one sequenced model organism from each described NF-T3SS family (genomes marked in red on Figure S4, list in Table S5 [6]). We extracted NF-T3SS protein sequences according to their genome sequence annotations and the literature. We performed similarity searches between these sequences with a Blast ‘‘all against all’’ search and applied a clustering algorithm with stringent parameters on the transformed e-value (-log(e-value), MCL [132] inflation parameter I = 1.5) to sequences showing hits with an e-value lower than 1023. We obtained nine families that were found in all model systems, which corresponded to the nine previously described NF-T3SS core proteins: SctC, SctJ, SctN, SctQ, SctR, SctS, SctT, SctU, SctV. We aligned these nine protein families with Muscle [133], manually edited the alignments with Seaview [134], and built sequence profiles with Hmmer [86]. A similar approach was conducted for flagella from phylogenetically distinct model organisms (MCL clustering, I = 1.8) (List in Table S3). Out of 14 protein families widely conserved in flagella, eight were homolo- gous to NF-T3SS core proteins (Table S1, protein clustering of protein families obtained from NF-T3SS and flagellar model systems, MCL parameter I = 2.5), and were extracted to build Hmmer sequence profiles. We also selected three widely conserved flagellar families with no NF-T3SS homolog (confirmed by the clustering above and Hmmer profile searches): FliE, FlgB, FlgC (rod proteins), and built sequence profiles to identify other occurrences of these proteins. Additional profiles were also built for FlgDEKL, FliG, MotA and MotB (MCL parameter I = 1.5) that are essential flagellar-specific genes [71]. NF-T3SSs/flagella identification To discriminate between homologous genes in flagella and NF- T3SSs, we performed a Hmmer search with the profiles of the eight proteins shared between them (‘‘core proteins’’), the secretin (the NF-T3SS-specific core proteins), and the three selected flagellum-specific proteins. Hmmer hits with Evalue and best-1- domain Evalue (or i-evalue) lower than 1023 were selected. Two hits were said to be contiguous when separated by less than 35 genes (average size of a flagellum cluster). We searched for clusters of contiguous hits to separate NF-T3SSs and flagellar systems. Clusters of genes showing positive hits for at least seven of the eight core genes, including a secretin, and lacking all three flagellum- specific genes were classed as NF-T3SSs. Sets of clusters of NF- T3SS core genes (core genes+sctC) not containing flagellum- specific genes were inferred as scattered NF-T3SSs. Flagellum PLOS Genetics | www.plosgenetics.org 10 September 2012 | Volume 8 | Issue 9 | e1002983