also among bacteria lacking an outer membrane (monoderms: Actinobacteria and Firmicutes). These results confirm previous studies showing that the possession of NF-T3SSs by bacterial taxa is much more restricted than flagella [79]. Some of the T3SS loci lacked core genes, but functional T3SS genes need not be in a single locus. We therefore investigated in detail the replicons with partial T3SS loci. 61 replicons had at least three of the nine NF-T3SS core genes homologs but lacked at least two of them. Only two of these systems corresponded to NF-T3SS and all others were of flagellar origin (Figure 1B). This finding suggests that NF-T3SSs are rapidly deleted when they lose function. Incomplete loci might represent NF-T3SSs encoded in multiple loci, systems with different functions or systems under- going genetic degradation. For example, a cryptic short NF-T3SS locus in E. coli (ETT2 locus) [87] often lacks sctT and genes encoding structural proteins such as sctL and sctD. ETT2 was suggested to play an important role in virulence by regulating the NF-T3SS of the locus for enterocyte effacement (often termed LEE) [88,89]. We then investigated the replicons lacking at most two of the nine core genes. Of 216 such NF-T3SSs, 21 included complete NF-T3SSs scattered in the genome and 10 corresponded to a Myxococcales system (‘‘Myxo’’) described below. As previously reported, the NF- T3SSs are spread over at least four loci in Chlamydia, three of which contain core genes [81,90]. Scattered NF-T3SS loci are present in all Chlamydiales genomes (‘‘Chlamy’’ systems), in Hamiltonella defensa [91], an intracellular Proteobacterium, and in the plasmid pYPTS01 of Yersinia pseudotuberculosis PB1/+. We note that the NF-T3SS is constitutively expressed in all development stages in Chlamydia [92]. Absence of specific regulatory elements might alleviate selection for the clustering of all NF-T3SSs genes and facilitate the fixation of rearrangements scattering the NF- T3SS into several loci. These disrupted loci are less likely to be transferred horizontally because acquisition of a complete system would require the co-transfer of different regions of a replicon. We tested the quality of the discrimination between NF-T3SSs and flagella by protein profiles with linear discriminant analysis (Figure 2, Figure S1). Our results indicate that the accuracy of assignment was .97% in gene-by-gene analyses, and .99% for combined protein profiles (see Materials and Methods), and that all mis-classified NF-T3SSs were in Myxo and Chlamy systems (see below). The accuracy of discrimination between the two types of T3SS for single proteins shows that these profiles are potentially useful for unassembled genomic data, including metagenomic data. We have therefore implemented a web server that allows detection of NF-T3SS and flagellar genes with our profiles (http://mobyle. pasteur.fr/cgi-bin/portal.py#forms::T3SSscan-FLAGscan). The NF-T3SSs described here can be queried and visualized from http://secreton.web.pasteur.fr. The origin(s) of T3SS We now turn to the evolutionary origins of the T3SS, a topic that has been extensively debated [75,82,93,94], in order to decide between three scenarios: the early split of the two systems, the flagellum-first or the NF-T3SS-first hypotheses (Figure 3A). Our analysis showed that of the T3SS proteins with clear homologs between flagella and NF-T3SSs, only the ATPase also has homologs in other cell machineries with significant sequence similarity to allow rooting the T3SS tree. A set of homologs of the T3SS ATPase and F- and V- ATPase catalytic subunits [39] (Protocol S1) were selected and aligned, resulting in sequences with an average length of 459 amino-acids. We selected 296 informative positions from the multiple alignment with BMGE [95] (Dataset S1), and chose the tree with the highest maximum Origins and Diversification of T3SS likelihood from 200 phylogenies built with RAxML [96]. This tree supports the T3SS monophyly with high support (100% bootstrap), and places the root of the T3SS tree within flagellar sequences (Figure 3B, Protocol S1). NF-T3SS sequences emerge in one clade within the flagellar T3SSs. We also counted the proportion of the 1000 bootstrap trees fitting each of the three evolutionary hypotheses (Figure 3A, Protocol S1). 84% of the trees support the flagellum-first hypothesis, arguing strongly against an early split between flagella and NF-T3SSs or that flagella were derived from an NF-T3SS. We confirmed this result by an analysis on a larger dataset including all curated systems. It is often difficult to obtain clear bootstrap supports for inner branches in very large trees spanning sequences with limited similarity and/or few sites. However, even this very large dataset clearly supported the flagellum-first scenario (.72% of the bootstrap trees, Text S1, Figure S2). The phylogeny of NF-T3SS In order to investigate early steps in the evolution of the NF- T3SS we reconstructed the phylogenies of the eight core proteins present in both NF-T3SSs and flagella for both single genes and their concatenated sequences. Initially we included the flagellar proteins to root the NF-T3SS tree. Then we restricted the analyses to the NF-T3SS proteins to obtain longer and more conserved multiple alignments allowing more accurate phylogenetic infer- ence. The individual phylogenies of the eight core proteins support a common descent of all NF-T3SSs from a single ancestor and identify the same NF-T3SS groupings (Figure S3, Table S4). These groupings extend and clarify a previous classification of NF- T3SSs [62] (Figure 4, Figure S4, Text S2). The use of the program Prunier [97] showed that any topological differences among the eight individual gene trees and the concatenate trees were supported by less than 90% of the bootstraps (Text S3). Thus, gene-wise and concatenated ‘‘rooted’’ and ‘‘unrooted’’ phyloge- netic analyses all support a similar history for the eight core NF- T3SS genes showing that they evolved together, apart from their flagellar homologs. The first NF-T3SS was probably not a contact-dependent secretion system The NF-T3SS tree places the root between one group of systems found in Delta-proteobacteria of the Myxococcales order (the ‘‘Myxo’’ group), and all remaining systems ($98% bootstrap support, Figure 4 and Figures S4, S5). The early diverging Myxo group includes both a long and a short variant of the NF-T3SS locus. These variants lack core NF-T3SS genes, resulting in their prior annotations within the genome of Myxococcus xanthus as relics of NF-T3SS undergoing degradation [98]. If this interpretation were correct, then these genes should evolve quickly and our assignment of these variants to a basal phylogenetic position might be artifactual. However, we identified six additional genomes from the same clade (Cystobacterineae) having homologous systems (Figure 5) (see [99] for the taxonomy of Myxococcales). All fully sequenced genomes of Cystobacterineae have the ‘‘short’’ locus and a monophyletic group of three of these genomes also possesses the ‘‘long’’ locus. These loci have G+C contents within the 25– 75% range of the G+C genomic content (SeqinR [100] analysis with a 1 kb sliding window), and a conserved gene order (Figure 5). The core genes that are common to these variants correspond to the secretion apparatus, the ATPase, the smaller inner ring protein and the inner rod protein (short locus). The long locus also contains the large inner ring protein. These core proteins interact with each other and also correspond to the most conserved NF- T3SS core proteins. The long and short loci each correspond to PLOS Genetics | www.plosgenetics.org 4 September 2012 | Volume 8 | Issue 9 | e1002983