clusters contained no secretin and had hits for at least 10 flagellar genes (core genes+flagellum-specific genes). Scattered flagella had hits for at least 10 flagellar genes, and had at least one cluster containing flagellum-specific genes with one core gene. All detected NF-T3SSs, plus other clusters close to the definition above (i.e. having fewer of the core genes clustered) were manually curated and checked according to the available literature. Thus, the Myxo systems were retrieved even if they lacked a secretin and flagellum-specific genes. We did not include in our analysis the system of Lawsonia intracellularis because its flagellar genes and NF- T3SS genes were intermingled in different positions of its genome, rendering the reconstruction of the two systems more hazardous (Table S2). Discriminant analysis with hits for both NF-T3SS/flagellar genes We attributed two types of Hmmer scores to genes with homologs in both systems: one score corresponding to the NF- T3SS profile and the other to the flagellar profile. We made a learning dataset including a third of the T3SS genes and their predicted role (NF-T3SS or flagellum). This subset was randomly drawn from the set of all T3SS. Using linear discriminant analysis [135], we predicted the type of system for the remaining two thirds of the dataset. We performed such an analysis with the combined dataset (all eight genes common to the flagellum and NF-T3SS together) as described above, and also in a gene-by-gene analysis. Accuracy is defined as the number of true predictions over the total number of predictions. Individual phylogenetic analyses We extracted from the genomes the genes encoding proteins homologous to T3SS core genes that were detected as part of a NF-T3SS or flagellum system. In a given system, when multiple Hmmer hits were available for a single gene, we kept the one displaying the lower Evalue and the maximal length. Many flagellar systems had multiple hits for the same genes scattered in the genome. We manually curated a subset of these flagella (357 out of 699 detected, the list of strains is in Dataset S2). We aligned sequences with Muscle (default parameters, [133]) and selected informative sites with BMGE (BLOSUM30 similarity matrix, gap rate cut-off = 0.20, sliding window size = 3, entropy score cut- off = 0.5 [95]). We built phylogenetic trees with RAxML ([96], Le and Gascuel [136] matrix + 4-categories-discretized Gamma distribution for rate variation among sites + empirical frequencies of amino-acids): we selected the best maximum likelihood tree among 200 different starting tree inferences, and computed 1000 bootstrap trees (i.e. trees based on bootstrap alignments, consisting of randomized sites drawn with replacement from the original alignment, and of the same size of the original alignment). In the case of the ATPase SctN, we built an extra dataset that we extended with previously described outgroup sequences [39] (see Text S1) and built a tree as described above. We also ran an extra phylogenetic analysis in a similar way on a subset of these sequences (see Protocol S1, Text S1). We built a tree as indicated above with a secretin dataset that included i) sequences identified in a previously described dataset [102] that were retrieved using their accession numbers; ii) SctC of detected NF-T3SSs; iii) all the secretins we found in Myxo and Chlamy genomes. Sequences displaying branch lengths longer than 1 substitution per site were excluded from phylogenetic analyses, and the phylogenetic reconstruction was run again with the cleansed dataset. This led to the exclusion of several flagellar systems and of five potential NF-T3SSs. Some of these systems are probably undergoing degradation (Table S2). Origins and Diversification of T3SS Concatenated phylogenetic analyses The protein alignments of the genes were concatenated and phylogenetic trees were built with RAxML [96] (Le and Gascuel matrix [136] + 4-categories-discretized Gamma distribution for rate variation among sites + empirical frequencies of amino-acids) with 100 rapid bootstraps [96] for the rooted tree. We made a more thorough phylogenetic search for the unrooted dataset: we performed 100 bootstrap replicates, and mapped them on the best (i.e. with the highest likelihood) among 100 phylogenies obtained from distinct start trees. We attributed families to predicted NF- T3SSs according to previously defined families ([62]; list of genomes in [6]). We searched a posteriori for putative significant inconsistencies between phylogenies of individual unrooted trees and the concatenate tree using the program Prunier [97] (bootstrap threshold = 80% and 90% in both gene trees and in the reference tree, see Text S3). Building families of neighboring genes We extended the cluster of NF-T3SS core genes by 10 genes upstream and downstream in the replicon sequence. All these protein sequences were extracted, and a similarity search (Blast ‘‘all against all’’) was performed between them. Pairs of sequences having hits with e-value lower than 1023 were clustered based on Blast alignments using the Silix program ([137], parameters used: minimal percentage identity = 20, minimal percentage of sequence overlap = 50, and minimal accepted length for sequences = 50). The most abundant protein families, considering both replicons and NF-T3SS families, were extracted and Hmmer profiles were built from them to extend the search in NF-T3SS neighboring genes. Programs used for graphics We used the Scriptree program [138] to draw annotated trees (Figure 4; Figures S3, S4, S5) and Figtree (http://tree.bio.ed.ac. uk/software/figtree) to draw trees (Figure 3B, Figure 5, Figure 6). Graphics on Figure 1B, Figure 2, and Figure S1 were drawn with R (http://www.r-project.org). All figures were modified with Inkscape (http://www.inkscape.org). Supporting Information Dataset S1 The filtered alignment of the ATPase family used for phylogenetic analyses and the tree in Figure 3B (Fasta format). Sequence names correspond to codes described in Dataset S2 for flagella and NF-T3SS, and to Genbank accession numbers for F-/ V- ATPases. (TXT) Dataset S2 List of systems analyzed along with taxonomic information, and equivalence for system codes found in Figure S5 and Dataset S1. (XLS) Figure S1 Learning dataset for discrimination between NF- T3SS and flagellar proteins based on Hmmer profile scores. For the subset of T3SS proteins used as a training dataset for the linear discriminant analysis shown in Figure 2 we show their protein profile scores using the NF-T3SS-specific profiles (X axis) and the flagellum-specific profiles (Y axis). Color codes indicate the different gene families. Filled circles indicate flagellar system proteins whereas open squares indicate NF-T3SS proteins. (PDF) Figure S2 Representation of each scenario for T3SS evolution in the phylogenetic analysis of the F-/V- ATPase family. The number of bootstrap trees in agreement with each scenario is PLOS Genetics | www.plosgenetics.org 11 September 2012 | Volume 8 | Issue 9 | e1002983