Taxon selection by collapse of a preliminary tree. Collapse was a sequential process of identifying the shortest leaf pair and replacing it with a single representative leaf. This maximized diversity between clusters of the available genomes. The number of genomes selected this way was 104, since this preceded a phase in the collapse process with an especially high loss of diversity.

Family conflict. The conflict scores for each set of protein families identified those with egregious phylogenetic signals. Families scoring above the 90th percentile were rejected.

Gammaproteobacterial phylogeny. Four subgroups of the taxa (excepting Ca. Carsonella, which is omitted here) were found not to mingle, by protein-jackknife subsampling of an all-taxon concatenation of 356 protein alignments. Longer concatenations were prepared for each taxon subgroup (Table 1), and tree topologies were built for each; small black geometric symbols link each subgroup to the outgroups used in building its subtree. The four regional trees were merged back into the topology for the all-taxon data set. Branch lengths for the merged topology were computed based on the all-taxon data set, and the four of its bifurcations that had less than 25% protein-jackknife support were collapsed, leaving three multifurcating nodes (dotted lines). Support values are shown (in the following order: all-taxon protein 50% jackknifing, taxon-subgroup protein 50% jackknifing, and taxon-subgroup single-taxon jackknifing) when any of these are <100%; cases marked NA (not applicable) were for nodes not included in taxon subgroup studies. The Entero region subtree was prepared by a two-step procedure described in the text that makes the usual support values inapplicable; however, for the first-step subtree prepared for the core Enterobacteriales taxa whose topology persists in this figure, protein and taxon jackknifing gave 100% support at each node. Taxon names are given in parentheses for incomplete genomes and are color coded according to the taxonomic order designation at NCBI. Taxonomic families represented by more than one taxon, except in cases in which the lone family represents the order, are bracketed, extending brackets to include unassigned taxa as necessary; only two of these nine families are split in our tree. Two nodes of interest are marked: the X indicates a node supported by a rare indel (10), and the star indicates a fully supported node that groups members of Pseudomonadales, Alteromonadales, and Oceanospirillales while excluding other members of each order. All known members of the latter clade, and no other known bacteria, autoregulate a ribosomal protein operon through strong mimicry of a 23S rRNA domain (38).

Compositional bias. Amino acid bias was measured according to the method of Karlin (15) for the set of 61 all-taxon protein families that contain Ca. Carsonella and plotted against nucleotide composition, producing a horn of A+T-rich endosymbionts with Ca. Carsonella at its tip.

Positions of the root and endosymbionts among the Enterobacteriales. (A) Two root positions (Plu and Eco) were obtained in our study; positions taken by A+T-rich endosymbionts (O and S) and two tested intermediate root positions (Int1 and Int2) are marked. Esch., Escherichia; Salm., Salmonella; Enter., Enterobacter; lum., luminescens; outgp, outgroup. (B) Positions taken by endosymbionts and their effect on rooting. The full Enterobacteriales taxon set was reduced to a core by removing all eight A+T-rich genomes (retaining the two outgroups), then each alone, or in groups of four, was added back to the data set. The compositionally unbiased endosymbiont Sodalis was excluded or not, and either the full set of Entero protein families (Fams) (part i) or subsets with at least one outgroup and favoring either the Plu-root (part ii) or the Eco-root (part iii) were used. The resulting root position and the position taken by the tested endosymbiont is reported. *, bootstrap analysis was performed for these trees, with support measuring 100% for every node. Bau., Ca. Baumannia; Blo. or Bloch., Ca. Blochmannia; Wig., Wigglesworthia; florid., floridanus; penn., pennsylvanicus. (C) Intermediate root positions disfavored. Each of the 696 protein families containing all core taxa and both outgroups were tested for preference of four hypothetical root positions using the P value of the Approximately Unbiased test (pAU), and pAU is reported for the supermatrix (Supermtx) that combined these 696 protein families. A pAU of <0.05 is typically taken as a rejection. (D) Identifying Photorhabdus as a disruptive taxon. For each of the 696 Entero families used in panel C, the indicated core taxa were singly omitted and pAU was taken for either the Plu-Root or Eco-Root topology, to determine the topology favored by the family; pAU was also taken for the two topologies based on the corresponding supermatrix.