Phylogenetic inference MrBayes. The same parameters were used with each alignment block in MrBayes, except for the longest alignments, which required 2X–3X more generations to run. Most runs had 500,000 generations with printing every 100 generations. 0.25% generations were removed as burnin before consensus tree building. The General Time Reversible model with gamma distributed evolutionary rates, including a proportion of sites that are invariant, was chosen as the most appropriate model of nucleotide substitution in ModelTest [41]. BUCKy. For each dataset BUCKy [32]was run using default parameters and a burnin identical to that for MrBayes. The a priori level of discordance between input trees (a) was varied from its default value of 1 up to 10; this did not significantly change the results. SplitsTree. Concatenated alignment blocks from each dataset were imported into SplitsTree [27,28]. The NeighborNet method with uncorrected distances was used to create the networks shown in Figure 5. Network structure was insensitive to different models of nucleotide substitution and numbers of bootstrap replicates. ClonalFrame. Three replicate runs were done in ClonalFrame [33]; these had 56105 iterations of burn-in and 56106 iterations after burn-in; output was recorded for the posterior sample at 1,000 iteration intervals. An 85% consensus topology from the three replicate runs was estimated in CONSENSE. Tests for recombination Each aligned block was used as input for the PhiTest [26], as implemented in SplitsTree [27,28] and the analyses were run using default parameters. RDP [42], Chimaera & MaxChi [43,44], Bootscan [45], SiScan [46], and 3Seq [47] were also used in the Recombination Detection Program [29]; only those recombination events that were agreed upon by all six programs were retained. References 1. Johnsborg O, Eldholm V, Havarstein LS (2007) Natural genetic transformation: prevalence, mechanisms and function. Res Microbiol 158: 767–778. 2. Lorenz MG, Wackernagel W (1994) Bacterial gene transfer by natural genetic transformation in the environment. Microbiol Rev 58: 563–602. 3. Chen I, Christie PJ, Dubnau D (2005) The ins and outs of DNA transfer in bacteria. Science 310: 1456–1460. 4. Chen I, Dubnau D (2004) DNA uptake during bacterial transformation. Nat Rev Microbiol 2: 241–249. 5. Burrows LL (2005) Weapons of mass retraction. Mol Microbiol 57: 878– 888. 6. Mattick JS (2002) Type IV pili and twitching motility. Annu Rev Microbiol 56: 289–314. 7. Pelicic V (2008) Type IV pili: e pluribus unum? Mol Microbiol 68: 827–837. 8. Coupat B, Chaumeille-Dole F, Fall S, Prior P, Simonet P, et al. (2008) Natural transformation in the Ralstonia solanacearum species complex: number and size of DNA that can be transferred. FEMS Microbiol Ecol 66: 14–24. 9. Fujise O, Lakio L, Wang Y, Asikainen S, Chen C (2004) Clonal distribution of natural competence in Actinobacillus actinomycetemcomitans. Oral Microbiol Immunol 19: 340–342. 10. Gromkova RC, Mottalini TC, Dove MG (1998) Genetic transformation in Haemophilus parainfluenzae clinical isolates. Curr Microbiol 37: 123–126. 11. Ramirez M, Morrison DA, Tomasz A (1997) Ubiquitous distribution of the competence related genes comA and comC among isolates of Streptococcus pneumoniae. Microb Drug Resist 3: 39–52. 12. Rowji P, Gromkova R, Koornhof H (1989) Genetic transformation in encapsulated clinical isolates of Haemophilus influenzae type b. J Gen Microbiol 135: 2775–2782. 13. Sikorski J, Teschner N, Wackernagel W (2002) Highly different levels of natural transformation are associated with genomic subgroups within a local population of Pseudomonas stutzeri from soil. Appl Environ Microbiol 68: 865–873. 14. Zawadzki P, Roberts MS, Cohan FM (1995) The log-linear relationship between sexual isolation and sequence divergence in Bacillus transformation is robust. Genetics 140: 917–932. Phylogeny of Competence DNA uptake and transformation phenotypes DNA uptake and transformation were measured as previously described [16]. Briefly, DNA uptake was measured by counting the amount of radio-labeled DNA retained by competent cells after 15 minutes of incubation. Raw measurements were corrected for cell number using optical density readings. Transformation was measured by providing competent cells with a cloned allele conferring resistance to the antibiotic novobiocin (nov). Transfor- mation frequencies were obtained by dividing the number of nov resistant colonies (corrected for spontaneous novR mutants) by the total number of colonies. Transformation frequencies were not dependent on divergence between donor and recipient alleles [16]. Taxon instability Taxon instabilities were calculated in Mesquite [34]. For each strain, the distance between it and all other strains was calculated for each tree pair, and the sum of all distances is the measure of instability. Mapping of DNA uptake and transformation phenotypes DNA uptake and transformation values were mapped onto each of the four trees using Parsimony in the Trace Character History function in Mesquite [34]. Raw data values were log10- transformed before mapping to normalize their distribution. Acknowledgments The authors wish to thank members of the Redfield lab for discussions of this work and three anonymous reviewers for helpful suggestions. Author Contributions Conceived and designed the experiments: HM. Performed the experi- ments: HM. Analyzed the data: HM RJR. Contributed reagents/ materials/analysis tools: HM RJR. Wrote the paper: HM RJR. 15. Singh AH, Wolf DM, Wang P, Arkin AP (2008) Modularity of stress response evolution. Proc Natl Acad Sci U S A 105: 7500–7505. 16. Maughan H, Redfield RJ (2009) Extensive variation in natural competence in Haemophilus influenzae. Evolution, in press. 17. Erwin AL, Sandstedt SA, Bonthuis PJ, Geelhood JL, Nelson KL, et al. (2008) Analysis of genetic relatedness of Haemophilus influenzae isolates by multilocus sequence typing. J Bacteriol 190: 1473–1483. 18. Meats E, Feil EJ, Stringer S, Cody AJ, Goldstein R, et al. (2003) Characterization of encapsulated and noncapsulated Haemophilus influenzae and determination of phylogenetic relationships by multilocus sequence typing. J Clin Microbiol 41: 1623–1636. 19. Harpending HC, Batzer MA, Gurven M, Jorde LB, Rogers AR, et al. (1998) Genetic traces of ancient demography. Proc Natl Acad Sci U S A 95: 1961–1967. 20. Schierup MH, Hein J (2000) Consequences of recombination on traditional phylogenetic analysis. Genetics 156: 879–891. 21. Slatkin M, Hudson RR (1991) Pairwise comparisons of mitochondrial DNA sequences in stable and exponentially growing populations. Genetics 129: 555–562. 22. Hogg JS, Hu FZ, Janto B, Boissy R, Hayes J, et al. (2007) Characterization and modeling of the Haemophilus influenzae core and supragenomes based on the complete genomic sequences of Rd and 12 clinical nontypeable strains. Genome Biol 8: R103. 23. Yazdankhah SP, Kriz P, Tzanakaki G, Kremastinou J, Kalmusova J, et al. (2004) Distribution of serogroups and genotypes among disease-associated and carried isolates of Neisseria meningitidis from the Czech Republic, Greece, and Norway. J Clin Microbiol 42: 5146–5153. 24. Cody AJ, Field D, Feil EJ, Stringer S, Deadman ME, et al. (2003) High rates of recombination in otitis media isolates of non-typeable Haemophilus influenzae. Infect Genet Evol 3: 57–66. 25. Perez-Losada M, Browne EB, Madsen A, Wirth T, Viscidi RP, et al. (2006) Population genetics of microbial pathogens estimated from multilocus sequence typing (MLST) data. Infect Genet Evol 6: 97–112. PLoS ONE | www.plosone.org 12 June 2009 | Volume 4 | Issue 6 | e5854