Ratio of observed to expected discordant bipartitions among proteins in major TIGR role category groupings. The expected number of discordant bipartitions in each category is equal to the total number of strongly supported bipartitions (concordant and discordant) within that category, multiplied by 0.134, the proportion of bipartitions that are discordant across all categories at PP ≥0.95. Observed numbers of discordant bipartitions range from 78 for “mobile elements” to 3,015 for “hypothetical proteins.”

Highways of obligate gene transfer within and among phyla and divisions of prokaryotes, based on analysis of the 22,348 protein trees for which a minimal edit path could be resolved. Each oval represents a prokaryotic group, with the name and number of taxa in that group indicated on the first line. Numbers below taxon names report inferred transfers within that taxon, whereas numbers on the linking edges report inferred transfers between taxa. Ovals representing groups with one or more thermophilic organisms are drawn with dashed lines. The type of line shown between each pair of taxa indicates the number of obligate edits in this analysis: >100 with thick solid lines, 10-99 with thin solid lines, and 5-9 with dashed lines. Relationships between taxonomic groups with fewer than five obligate edits are not shown. Note that transfers cannot be identified within phyla with one (e.g., Nanoarchaeota) or two (e.g., Bacteroidetes) genomes in our data set.

Reconciliation of an unrooted protein tree with a rooted reference tree. Successive subtree prune-and-regraft (edits) operations (edits) are applied to the reference tree (b), until (ideally) all topologies, or for complex comparisons at least one topology, consistent with the protein tree (a), is obtained. In this example, only a single operation is needed to generate a tree (c) with which the tree in a is topologically congruent. Four alternative edits, indicated with arrows representing the direction of gene flow, can reconcile the reference and protein trees in a single step (thus with an edit path of length 1). The tree in c is the result of the edit operation implied by the boldface arrow in the tree in b: an ancestor of taxon B donates genetic material to an ancestor of taxon C. This is implemented algorithmically by breaking the terminal edge subtending C and reannealing it along the terminal edge subtending B. The resulting rooted tree (c) contains no bipartitions that are discordant with protein tree (see supporting information for details). In this simple example there is no obligate edit path; (B,C) and (D,E) are possible (but mutually exclusive) partner pairs in the implied LGT event.