Evolutionary Timeline and Genomic Plasticity Underlying the Lifestyle Diversity in Rhizobiales

Lifestyle diversification in Rhizobiales.The Rhizobiales taxa fall into four lifestyles, the nodule-associated, plant-associated, animal-associated, and free-living lifestyles. We inferred ancestral lifestyles of Rhizobiales using the maximum parsimony method implemented in Mesquite based upon the lifestyles of extant taxa (see Data Set S1 in the supplemental material for the complete list) and on their concatenated ribosomal protein phylogenies (see Materials and Methods). We did not use the maximum likelihood method in the main analysis because the short branches across the phylogeny can lead to overestimations of transition rates and thus to inaccurate ancestral lifestyle inferences (19), although we included a maximum likelihood analysis to assess the consistency of the results (see below). According to this procedure, the last common ancestor (LCA) of Rhizobiales was likely a free-living bacterium (Fig. 1), consistent with the fact that a vast majority of the branches of Rhizobiales that split early are represented by free-living members (Fig. 1). The nodule-associated lifestyle evolved multiple times, during which four major origins led to the formation of four well-known rhizobia genera, namely, Bradyrhizobium, Mesorhizobium, Rhizobium, and Sinorhizobium/Ensifer (nodes 2, 6, 5, and 4, respectively, in Fig. 1). Interestingly, none of the basal groups of these four rhizobia genera include nodule-associated bacteria: the basal members of Bradyrhizobium are free-living bacteria, those of Rhizobium are plant associates, and those of Sinorhizobium and Mesorhizobium take plant-associated or free-living lifestyles (Fig. 1). This suggests that the nodule-associated lifestyle in all of the four genera evolved relatively recently within each genus.

• Open in new tab
• Download powerpoint

FIG 1

Ancestral lifestyle reconstruction of the Rhizobiales. Ancestral lifestyles were inferred using the parsimony method in Mesquite. Branches in red, green, orange, and blue indicate nodule-associated, plant-associated, animal-associated, and free-living lifestyles, respectively. Numbered nodes represent the origins of the host-associated lifestyles (the nodule-associated, plant-associated, and animal-associated lifestyles). Zoomed-in lineages represent species that split early within the Bradyrhizobium, Mesorhizobium, Rhizobium, and Sinorhizobium. The three layers are each indicated with a distinct color surrounding the phylogeny to denote the presence/absence of key nodule-related genes (the nod, nif, and fix genes). The genes selected to represent each pathway/complex are shown in Text S1. Purple circles on the phylogeny represent nodes supported by IQ-Tree ultrafast bootstrap values of ≥95%. The outgroups are not shown.

Animal associates showed two major independent origins leading to Bartonella (node 7 in Fig. 1) and Brucella (node 8 in Fig. 1). Since some of their close relatives, Ochrobactrum, for example, are increasingly recognized as opportunistic pathogens, there is a chance that their common ancestor had already adapted to an animal-associated lifestyle. We also identified two major origins of plant-associated members: one within the Methylobacterium (node 1 in Fig. 1) and the other corresponding to the LCA of the Rhizobiaceae (node 3 in Fig. 1). Species from the Rhizobiaceae further diversified into nodulating members of Rhizobium and Sinorhizobium, while others, in particular, those from Agrobacterium, plausibly retained the ancestral plant-associated lifestyle (and evolved plant pathogens later [17]) (Fig. 1). It is possible that a few host-associated lineages have a deeper origin, including Rhizobiaceae, where nodulating members exhibited mosaic distributions in phylogeny (Fig. 1), implying a more complex evolutionary history. We therefore updated the analysis by inclusion of the recently available genomes of a large number (>300) of Rhizobiaceae isolates from the roots of several nonlegume plants (8). Our updated phylogenomic tree showed that the phylogenetic positions of the major group of the nodulating Rhizobium (see Fig. S1a in the supplemental material) and of the nodulating Sinorhizobium (Fig. S1b) remained congruent with those shown in Fig. 1, suggesting the robustness of ancestral lifestyle reconstruction in these lineages.

To validate the origins of the host-associated lifestyles with the parsimony-based approach described above, we applied the maximum likelihood method implemented in BayesTraits (see Materials and Methods). Some of the host associations were estimated to have a deeper origin (nodes 1, 3, and 4 in Fig. 1), but the general pattern did not change (Fig. S2a). We further assessed the impacts of taxon sampling (Fig. S2b) and the set of genes used to build phylogeny (Fig. S2c) on lifestyle reconstruction. In both cases, the reconstructed lifestyles are in good agreement with the data in Fig. 1.

To further quantify the tendency of lifestyle transitions, we calculated transition rates between lifestyles using BayesTraits (see Materials and Methods). The transition rate from nodule association to nonnodule association was about eight times the rate calculated for the opposite direction (27.62 versus 3.30; log Bayes factor [logBF] = 72.04) (Fig. 2b), indicating that the tendency for rhizobia to lose their nodulating ability is much stronger than the gain of nodulating ability for nonrhizobia. The rate of transition to nodule associations was the highest for the plant-associated lifestyle (Fig. 2a) and was significantly higher than that determined for the animal-associated lifestyle (logBF = 3.28) but not that determined for the free-living lifestyle (logBF = 0.90). The transition from the plant-associated lifestyle to the free-living lifestyle is more likely to occur than the reverse transition, as reflected by the significantly higher transition rate (logBF = 3.48) (Fig. 2a). The rate of transition from an animal-associated lifestyle to any of the other three lifestyles was significantly lower than the rates of transition in the opposite direction and was not significantly different from zero (Fig. 2a). The pattern held when we combined all of the non-animal-associated lifestyles (logBF < 2; Fig. 2b). Nodule- and animal-associated bacteria exhibited markedly distinct patterns in lifestyle transition. Animal pathogens are often subjected to strong bottlenecks, which may lead to genetic drift and to massive losses of genes that cannot confer large advantages (2), and as a result, this could make it difficult for them to evolve into other lifestyles or even to reach an evolutionary end. On the other side, rhizobia need to dwell various habitats, including nodules, bulk soils, and rhizospheres; the free-living stage in soils and rhizosphere may provide rhizobia large population sizes, acting against the tendency of the decrease of selection effectiveness observed in animal pathogens (2). Rhizobia are also equipped with genes allowing them to thrive in all these habitats. Thus, they might easily shift back to nonrhizobia by loss of symbiosis genes, in particular, when their hosts grow in nitrogen-rich soils, as the benefit of carrying these symbiosis genes becomes vanishingly low (20).

• Open in new tab
• Download powerpoint

FIG 2

Rates of transitions between lifestyles. The width of each arrow is proportional to the transition rate (log transformed). Gray dashed lines denote transition rates that are not significantly different from zero (logBF < 2). The posterior distributions of transition rates derived by the reversible-jump MCMC method are shown as histograms. The means of transition rates and Z-scores are displayed adjacent to the histogram. Expressed as percentages, Z-values represent the proportions of sampled runs in the Markov chain where the transition rate is assigned to be zero. Z-values allow examination of the contingency of evolutionary transitions, with higher values signifying lifestyle transitions that are less likely to occur in evolution. Nodule-associated, plant-associated, animal-associated, and free-living lifestyles are abbreviated as NA, PA, AA, and FL, respectively. The color that represents each lifestyle is the same as that defined for Fig. 1. (a) Pairwise comparisons of transition rates between lifestyles. (b) Comparisons of transition rates between nodule-associated lifestyles (NA) and non-nodule-associated lifestyles (AA, PA, and FL) and between animal-associated lifestyles (AA) and non-animal-associated lifestyles (NA, PA, and FL).

Coevolutionary history of the associations between Rhizobiales species and their hosts.A large proportion (76%) of Rhizobiales members sampled in the present study were isolated from a host-associated environment, making it possible to explore the coevolution between Rhizobiales and their hosts. Our strategy started by estimating the time of origin of each lifestyle by the use of careful molecular clock analyses and comparing each estimated time of origin with that of their hosts which were recorded in fossils. For computational efficiency, we selected 176 representative genomes based on the operational taxonomic unit (OTU) at the 16S rRNA gene sequence identity level of 98.7% (21) (see Materials and Methods). Molecular clock analyses showed that the LCA of the Rhizobiales occurred 1,569 million years ago (Mya) (95% highest posterior density [HPD] interval, 1,667 to 1,447 Mya), which greatly predated the origin of their hosts (Fig. 3) (22–24; also see below). This lends strong support for the idea of a free-living LCA of Rhizobiales illustrated by the ancestral lifestyle reconstruction (Fig. 1; see also Text S1 in the supplemental material).

• Open in new tab
• Download powerpoint

FIG 3

Time tree of the Rhizobiales with selected taxa from Proteobacteria as the outgroup. Divergence time was estimated using MCMCTree on the species phylogeny shown in Fig. 1 (performed with only the 176 representative species). Nodes marked with a gray circle represent the calibration points in Proteobacteria and cyanobacteria (see Text S1 for details). Branch colors are based on the ancestral lifestyle reconstruction shown in Fig. 1. Vertical bars in green, orange, and red indicate the origin times of the primary hosts of extant Rhizobiales, namely, land plants, mammals, and legumes, respectively. The panel in the lower left corner of the figure shows a zoomed-in view of the evolutionary timeline of Bartonella, where the hosts are also shown next to the tips of the phylogeny. Node bars denote the 95% HPD interval of posterior dates (for key nodes related to the origins of host association only).

With an origin at 116 Mya (95% HPD interval, 146 to 88 Mya), nodulating Bradyrhizobium showed the earliest origin among the aforementioned four major rhizobia lineages (Fig. 3), very close to the origin time of another nodulating clade, the Azorhizobium clade, at 134 Mya (95% HPD interval, 180 to 91 Mya). Hence, the first alphaproteobacterial rhizobium was likely associated with Bradyrhizobium or Azorhizobium. The origins of nodulating lineages of Mesorhizobium, Sinorhizobium, and Rhizobium generally postdated those of Bradyrhizobium and Azorhizobium (Fig. 1), implying that the nodulating ability of the former lineages was acquired from the latter lineages or their relatives. Notably, the divergence time of the Rhizobiales lineages should be understood as a span of the posterior age estimate (indicated by the 95% HPD interval), rather than as a time point. Recent molecular dating studies suggest that legumes (the host of alphaproteobacterial rhizobia) originated 110 to 65 Mya (25) (see also references 16, 26, and 27 and Text S1). Hence, there were considerable overlaps in the origin times of legumes and alphaproteobacterial rhizobia (e.g., Azorhizobium, Bradyrhizobium, and Mesorhizobium). The origin of leguminous nodules, assuming its first appearance in the LCA of legumes (28–30), was thus roughly contemporaneous with that of nodulating alphaproteobacterial rhizobia (Fig. 3). Alternatively, certain rhizobial lineages (Azorhizobium or Bradyrhizobium) might have originated a bit earlier than legumes and evolved the nodulating ability after the emergence of legumes in independent lineages. Additionally, the uncertainties might result from methodological limits of molecular dating in organisms with ancient origins (31), such as the Rhizobiales. Nonetheless, our result remained compatible with the general hypothesis of the coevolution of alphaproteobacterial rhizobia and their hosts (Text S1).

The plant-associated members in Rhizobiaceae and Methylobacterium originated 280 Mya (95% HPD interval, 314 to 242 Mya) and 207 Mya (95% HPD interval, 241 to 171 Mya), respectively (Fig. 3), >100 million years (My) after the terrestrialization of plants (24). In support of this idea, these lineages are found in the microbial communities at the phyllosphere or endosphere of various land plants (8, 32). Note that, due to the lack of species that split early, the LCA shared by Rhizobiaceae and its sister group Martelella was ambiguous in terms of its lifestyle, and there is a chance that it had already adapted to a plant-associated lifestyle (Fig. 3). As this LCA occurred at 417 Mya (95% HPD interval, 479 to 355 Mya) and coincided with the emergence of land plants at ∼470 Mya, when scarce nutrients and water severely limited the development of early land plants (3), the primitive interaction between these Rhizobiales lineages and the earliest land plants might have contributed to the successful terrestrialization of early plants.

Animal-associated Brucella and Bartonella displayed divergent patterns in terms of the origin time (Fig. 3). Brucella originated no earlier than 20 Mya, whereas Bartonella likely originated at 343 Mya (95% HPD interval, 393 to 293 Mya), much earlier than the emergence of mammals (22), suggestive of host shifts during Bartonella evolution. Recent efforts have revealed that basal lineages Bartonella apis and Bartonella tamiae are nutritional commensals inhabiting the guts of insects (33) whose origin (23) generally coincided with the emergence of Bartonella (Fig. 3). Further, unlike Brucella, where transmission is directly mediated by contact between mammals, Bartonella is transmitted across mammals via blood-sucking arthropod vectors. The evidence provided above suggests that ancestral lineages of Bartonella might have already lived closely with arthropods and that they became arthropod-transmitted mammalian pathogens ∼150 My later, coinciding with the emergence of mammals (22) (Fig. 3).

To accommodate potential biases in the time constraints used here, we performed additional analyses with various combinations of time constraints derived from fossil records and estimates from previous studies (Fig. S3; see Text S1 for details). In general, the patterns obtained from these new analyses remained unchanged (Fig. S3). For example, the 95% HPD interval of the estimates for the origins of both nodulating Bradyrhizobium and Azorhizobium generally overlapped that of nodulating plants across all combinations of calibrations (Fig. S3c), strengthening the idea that the first rhizobial lineages in Alphaproteobacteria lay in Bradyrhizobium or Azorhizobium. In addition, note the uncertainties inherent in time estimates, which can arise from the lack of fossils from close relatives, data partitioning, and lack of gene sets (Fig. S3). In general, removal of secondary calibrations within the Proteobacteria (sets 5 to 8), decreasing the number of partitions (set 11), or using the single-copy genes identified by OrthoFinder (set 12) led to more-ancient posterior times being estimated (Fig. S3). The largest posterior age value was observed in Set 11, where the sequence data were partitioned according to the scheme recommended by ModelFinder instead of being fully partitioned as performed for the other 11 calibration sets (Fig. S3c). This is consistent with previous findings revealing that estimated ages increase as more partitions come to be used (34). Different lineages also showed different extents of variation in the posterior age across calibration sets (Fig. S3c). Considering these uncertainties, one should be cautious in offering any conclusive arguments based on the time estimates. We think that the lack of fossils in most major bacterial lineages, the ambiguity in the data used to estimate the age of cyanobacteria fossils, and the large phylogenetic distance between cyanobacteria and other bacteria are the biggest challenges in bacterial divergence time estimation. Future studies may consider using the recently developed strategy based on horizontal gene transfer (HGT) (35, 36) to better resolve the evolutionary timeline for Rhizobiales and other bacteria.

Genome-wide identification of genes associated with nodulating members.Gene families conserved across diverse bacterial lineages of the same lifestyle show strong signals for convergent evolution and are therefore potentially important to bacterial adaptation in their common habitats (15, 16, 37). We integrated different protein family annotations, performed BayesTraits-based analysis to search for genes significantly associated with their lifestyles using the full set of the Rhizobiales genomes (see Materials and Methods), and elaborated on their putative roles in lifestyle adaptation of a few examples of particular interest, starting from those correlated with nodule-associated Rhizobiales (Data Set S1b; see also Data Set S1c for the full list).

Rhizobia-legume symbiosis is initiated by nodule formation and invasion (38, 39). As expected, genes participating in the biosynthesis of Nod factors (nod genes), which play key roles in inducing the host plant to form infection threads (38), were among the top-ranking significantly correlated genes (Fig. 1; see also Data Set S1). Genes encoding a type III secretion system (T3SS), T4SS, and T6SS, as well as bacterial effector proteins exported through them, were also detected. Distinct from other secretion systems which simply transport proteins/compounds out of cells, T3SS, T4SS, and T6SS can transport bacterial effectors to enable them to have direct communication with the eukaryotic cytosol (40). The roles of the T4SS and T6SS in symbiosis are less well studied than those of the T3SS. Our results suggest that those secretion systems, though not universally present at the strain level, may contribute to Rhizobia-legume symbiosis potentially by affecting host specificity and/or nodule growth (40). Genes involved in hopanoid lipid synthesis and modification were also identified, supporting the view of hopanoid as a molecule promoting bacterial mobility and attachment to root surfaces (41). Moreover, we detected several Rhizobia-associated genes that may help manipulate the level of plant hormones by rhizobia, such as the 1-aminocyclopropane-1-carboxylate deaminase (acds) which facilitates nodulation by degrading the precursor of the nodule inhibitor ethylene (42), and halimadienyl-diphosphate synthase which presumably participates in biosynthesis of gibberellin (42).

To supply legumes with N in nodular environments, rhizobia are equipped with the nitrogenase-encoding nif genes, which, as expected, were identified as genes enriched in nodulating bacteria (Fig. 1; Data Set S1b). A high rate of O₂ respiration is needed to fulfill the energy requirement during N₂ fixation (43). However, O₂ can irreversibly inactivate nitrogenase. The microaerobic environment of nodules sets up a conflict of interest between N₂ fixation and other biological processes in terms of O₂ concentration (39). To cope with this issue, some rhizobia recycle the H₂ released from N₂ fixation via hydrogenase to reduce energy loss by regenerating chemical energy and removing H₂ and O₂, the reversible and irreversible inhibitors of nitrogen fixation, respectively (44). Accordingly, the hyd and hup genes encoding this H₂ recycling system were significantly associated with nodule-associated taxa. In addition, many O₂-high-affinity cytochromes and genes involved in their synthesis or regulation were significantly correlated. The best example is the Fix system (Fig. 1), including fixABCX participating in electron transfer to nitrogenase, fixJLKT responsible for nif regulation, and fixNOQP encoding high-affinity cytochrome oxidases, which collectively ensures high efficiency of aerobic biological processes under micro-oxic environment (39). Also significantly correlated were denitrifying enzymes, which are hypothesized to participate in detoxification of the signaling module nitric oxide in Bradyrhizobium and Sinorhizobium (45). In bacteroids, N₂ fixation is driven by oxidation of host-supplied C4-dicarboxylic acids (43). Accordingly, the dct genes encoding the C4-dicarboxylate transporter were enriched in rhizobia. Note, however, that the low O₂ level in bacteroids may inhibit the TCA cycle due to imbalanced redox state of NADH/NAD⁺, thereby disrupting N₂ fixation (43). Rhizobia use the storage of polyhydroxybutyrate (PHB), which could account for half of the dry weight of rhizobial cells, as a way to stabilize cellular redox conditions, deposit redundant energy, and release the inhibition of the TCA cycle at low O₂ conditions (43). Accordingly, several genes (e.g., phaZ, phbB, and phbC) responsible for the synthesis and degradation of PHB were found to be significantly associated.

Rhizobia need to not only persist in nodules but also thrive in soils where they compete with other bacteria for limited resources such as iron (Fe) and phosphorus (P). To overcome the low concentrations of soluble Fe available in soils, rhizobia use siderophores to import Fe by binding it in tight complexes (46). Indeed, several genes involved in siderophore biosynthesis and transport were significantly correlated with nodule-associated bacteria. Likewise, genes comprising the phn operon encoding a C-P lyase for utilization of phosphonate, which is commonly found in soils (47), were also among Rhizobia-associated genes. In addition, several genes involved in the biosynthesis of ectoine, a protectant against osmotic stress described in many soil bacteria (48), were significantly correlated with rhizobia, implying their role in adaptation to distinct osmotic pressures across various habitats.

Genes associated with animal-associated, plant-associated, and free-living lifestyles.Using the same procedure, we identified genes significantly correlated with each of the other three lifestyles. Fewer genes were significantly correlated with animal-associated than with nodulating bacteria (Data Set S1d), likely because of the limited taxonomic distribution of the animal-associated lifestyle within the Rhizobiales. Of most interest were the VirB genes encoding the type IV secretion system (Fig. 1), known as the essential virulence factors contributing to the success of infection by Bartonella and Brucella (49). Also significantly correlated with the animal-associated bacteria were the genes encoding adhesins, which are necessary for attaching Bartonella to host cells (49). Likewise, many genes that encode transporters of amino acids and metals (e.g., Fe³⁺ and Mg²⁺) showed significant correlation, consistent with their demonstrated essentiality in the survival of Bartonella and Brucella in mammalian bloodstream (50, 51) (Data Set S1b). Genes coding for multidrug efflux systems, which may help pathogens develop antimicrobial resistance during infection (52), were also enriched in animal-associated bacteria (Data Set S1b).

In addition, genes encoding the class Ib ribonucleotide reductase (RNR), a key enzyme in synthesis of the precursors of DNA in its replication (53), were among significantly associated genes in animal pathogens. Compared with other types of RNRs, class Ib RNR is special because it uses manganese instead of iron as the cofactor and is found only in bacteria and bacteriophages (53). The use of class Ib RNR in DNA replication thus likely helps Bartonella and Brucella survive in mammalian cells where iron is rare and facilitates escape from host defense via iron limitation, making the class Ib RNR a promising target for antibacterial and antiviral drug design, particularly given its absence in eukaryotes (thereby exerting less influence on host cells) (54).

A considerable number of genes significantly correlated with plant-associated strains encoded transporters covering diverse substrates, including sugars, amino acids, and oligopeptides (Data Set S1e). Many of them participate in the transport of rhamnose, a key component of lipopolysaccharide important to bacterial attachment to plants (55). Also included were those involved in cellulose synthesis and its activation, consistent with their roles in mediating plant-bacterium interaction (56). Free-living Rhizobiales species were derived from diverse isolation sites (Data Set S1). Hence, there were few “characteristic” genes shared by free-living Rhizobiales (Data Set S1f). Of most interest was the arc3 gene encoding a protein pumping arsenite from the cell, which showed the lowest P value among all genes correlated with this lifestyle, suggesting its role in adaptation to arsenite compounds, the most prevalent environmental toxic substances (57).

Genome expansion in the origin of nodulating lineages.Lifestyle-associated genes could be acquired before (i.e., preexisting traits), during, or after a lifestyle transition. These scenarios were differentiated using ancestral genome reconstruction of 176 representative Rhizobiales genomes with BadiRate (see Materials and Methods). Overall, this analysis predicted that Rhizobiales started with ∼2,100 genes at its LCA and gradually expanded to the current genome sizes (Fig. 4a). It also predicted repeated genome expansion based on the origin of the nodule-associated lifestyle and repeated genome reduction based on the origin of the animal-associated lifestyle (Fig. 4a), consistent with an early study that analyzed only nine genomes (12).

• Open in new tab
• Download powerpoint

FIG 4

Ancestral genome reconstruction and gene gains/losses during the evolution of Rhizobiales. (a) Genome size evolution in the Rhizobiales. The colors of the branches in the phylogeny represent the changes of gene numbers in the genomes. Ancestral genomes were inferred with BadiRate based on gene family clustering using OrthoFinder. (b and c) The phyletic pattern and inferred gain/loss of lifestyle-correlated genes in the evolution of nodule-associated lineages (b) and animal-associated lineages (c). Branches in red and orange indicate nodulating and animal-associated lineages, respectively. Selected pathways/complexes important to the host-associated lifestyle are shown next to the trees. Genes were selected based on the criteria detailed in Text S1. Solid and open circles denote the presence and absence of the corresponding genes, respectively. Presence/absence at ancestral nodes inferred by BadiRate is indicated adjacent to the node. Pathways or complexes with ≥50% or <50% of genes present are indicated by a solid or open square adjacent to the ancestral nodes, respectively, based on the reconstruction of ancestral genome content.

The nod and nif genes appeared to be the only ones that were repeatedly gained during the lifestyle transitions to the four major nodulating lineages, possibly via HGT from rhizobial lineages that had evolved early (14), consistent with their determining role in nodulation and nitrogen fixation by rhizobia. In contrast, genes constituting the Fix system, Dct transporter system, and phn operon and those involved in PHB metabolism were already present in their nonnodulating ancestors (Fig. 4b).

The evolutionary histories of most Rhizobia-associated genes were actually a mix of these scenarios where they preexisted in some rhizobia but were not recruited until lifestyle transition in others. Examples are T3SS, T4SS, T6SS, and denitrification genes (Fig. 4b). Such distinct patterns across lineages were closely related to the ancestral lifestyle from which the corresponding rhizobial lineage evolved, implying that these genes contributed to lifestyle adaptation in a lineage-specific manner (13). For instance, the nodulating Bradyrhizobium species likely arose from a free-living ancestor (Fig. 1). Accordingly, most genes involved in bacterium-host interactions, such as T3SS, T4SS, and T6SS genes, were predicted to be absent in the nonnodulating ancestor of Bradyrhizobium (Fig. 4b). T3SS was inferred to be acquired by the ancestor of nodulating Bradyrhizobium. This is interesting because photosynthetic Bradyrhizobium lineages that split early can use T3SS to nodulate legumes in the absence of nod (58). Considering its reported roles in symbiosis and conservation in Bradyrhizobium (40), our results imply that a gain of T3SS might have contributed to the ancestral transition of Bradyrhizobium from the free-living to the nodulating lifestyle (Fig. 4b). Distinct from Bradyrhizobium, nodulating Rhizobium and Sinorhizobium likely evolved from a plant-associated ancestor (8) (Fig. 1). Plant-associated bacteria produce various cell surface polysaccharides, among which EPS (exopolysaccharide) attracts the most attention because of its high abundance in the surrounding environment of bacteria (59). EPS has been shown to contribute to both symbiosis for Rhizobium and Sinorhizobium and plant pathogenesis for Agrobacterium (60). Our results suggest the presence of EPS I (succinoglycan) synthesis genes in the LCA of Rhizobiaceae and in the shared ancestors of Rhizobium, Sinorhizobium, and Agrobacterium (Fig. 4b). We hypothesize that the role of EPS in early Rhizobiaceae lineages may be simply the attachment to the plant surface and a protective barrier (as in the case of Agrobacterium) (60) and that it was coopted later in evolution by some rhizobia as a signaling molecule during invasion and infection thread formation. Note that, in addition to EPS I, rhizobia secrete other types of EPSs. However, given their low abundance and that their synthesis genes are less well characterized in rhizobia (59), those genes were not analyzed here. The case for Mesorhizobium was similar to those for Rhizobium and Sinorhizobium, where the genes participating in EPS synthesis and T6SS were inherited from their nonnodulating ancestor (Fig. 4b). This implies a plant-associated ancestor of Mesorhizobium, although the ancestral lifestyle of Mesorhizobium could not be fully resolved (Fig. 1). The conservation of T6SS in nodulating Mesorhizobium hints at its role in symbiosis, despite there being little knowledge about it (40). Further, we employed AnGST, a method fundamentally different from BadiRate (see Materials and Methods), to repeat the ancestral reconstruction analysis and obtained a similar pattern (Fig. S4).

Despite significant genome expansion in the origins of nodulating lineages (Fig. 4a), genes encoding the gene transfer agent (GTA), a small tailed phage-like element that consists of ∼15 genes and mediates HGT of short genomic DNA segments (61), were possibly independently lost in all of the four major nodulating lineages (Fig. S5). A previous study showed that, while GTA was retained in Azorhizobium, its expression is suppressed when members of this rhizobial lineage form bacteroids (62). Also, despite the importance of HGT via plasmids or mobile islands to the Rhizobia-legume symbiosis (12), GTAs may not play a role in this process, because they preferentially mediate transfer of chromosomal DNA (63, 64) and can pack DNA segments of ∼4 kb (61), which are much smaller than those needed for rhizobial symbiosis. It is likely that GTAs became dispensable and thus were lost during the evolution toward the rhizobial lineages. This hypothesis can be tested by introducing the full set of GTA genes into rhizobia and assessing the effects on the growth of the bacteria.

Exchange of genetic materials by HGT between bacteria inhabiting the same niches is very frequent (65). Given the coexistence of nonnodulating bacteria with rhizobia in both nodular and soil environments, it is likely that key genes involved in rhizobial symbiosis (e.g., the nod, nif, and fix genes) have frequently been transferred across bacteria over time (14). Paradoxically, until now, the hundreds of known rhizobial species were discovered in some 12 genera within only the Rhizobiales and Burkholderiales (14, 66). This suggests that HGT of these symbiosis genes is insufficient for the conversion from nonrhizobia to rhizobia. A recent study revealed that genome modifications of the recipient lineages are required for newly acquired symbiosis traits to function (67). In the present study, we found that preexisting traits and gene losses might have also contributed to the origin of rhizobia. Possibly, it is a combination of different mechanisms that make diverse lineages within the Rhizobiales independently evolve to be successful symbionts of legumes, which, however, needs to be further explored.

Genome reduction and gene gain/losses in animal pathogens.The origins of animal pathogens were characterized by significant genome reductions (Fig. 4a). In particular, many genes involved in amino acid metabolism were lost during the evolution of Bartonella, leading to the incompleteness of most amino acid biosynthesis pathways in this lineage (33). To compensate for these losses, Bartonella recruited several amino acid uptake genes during and after the lifestyle transition to make use of the available resources in the host (Fig. 4c; see also Fig. S4b). In contrast, most genes gained by Brucella are involved in the uptake of metals, including nickel and cobalt (Fig. 4c; see also Fig. S4b). These genes have been proven critical to the virulence of other Gram-negative bacteria (reviewed in reference 68) and might be similarly important to Brucella (18). Other genes, e.g., those encoding T4SS, class Ib RNR (ribonucleotide reductase), and multidrug exporters, were likely present at the LCA shared by Bartonella and Brucella (Fig. 4c; see also Fig. S4b). These genes might make related lineages “preadapted” to animal association and pathogenesis. Of note, some strains belonging to Ochrobactrum, representing the closest relatives of Brucella, have evolved as opportunistic pathogens. People with an indwelling medical device are most susceptible to the bloodstream infection by Ochrobactrum (69). This could result from its ability to resist antibiotics and adhere to synthetic materials (70), consistent with the idea that the LCA of Ochrobactrum and Brucella might have already harbored relevant genes (Fig. 4c; see also Fig. S4b). We speculate that these preexisting genes might have been involved in different but related pathways in the free-living ancestors and might evolved new functions in pathogenesis during evolutionary transition to the host-associated lifestyle. For example, the T4SS in Bartonella, which exclusively functions to modulate the bacterium-eukaryotic host cell interaction, likely evolved from an ancestral conjugation system involved in the formation of stable mating junctions (71). The findings described above also suggest that to limit the risk of emergence of pathogenic bacteria, it is important to watch for (i) those with genes that potentially facilitate adaptation or conversion to a pathogenic lifestyle in genomes and (ii) those that infect related hosts or that have already been adapted to the host (72). Such examples include the aforementioned Ochrobactrum. In addition, several members of the Afipia are associated with the blood of patients (Data Set S1), highlighting its potential as a reservoir for emerging diseases (73).

Caveats and concluding remarks.Like a recent study (37), we classified host-associated Rhizobiales based on their isolation sites. However, different lifestyles could represent dynamic alternatives available to the organism at different time points (7). In our data sets, three non-nodule-associated strains (Mesorhizobium sp. strain LCM 4577, Rhizobium phaseoli Ch24-10, and Rhizobium sp. strain NXC14) possess a complete set of nodABC genes, thus likely representing strains that are capable of nodulating legumes but that happened to be isolated elsewhere. Thirteen of the 244 nodule-associated strains do not carry any nodABC genes. While some of them belong to the photosynthetic Bradyrhizobium lineage which utilizes a Nod-independent strategy for nodulation (58), others may represent nonnodulating bacteria living in nodules. Moreover, although our computational identification of lifestyle-correlated genes provides useful insights into the development of microbe-based strategies for sustainable agriculture and for prevention of plant/animal diseases, it is based purely on bioinformatics analyses. The detailed functions of many of identified genes still await exploration. The overrepresentation of agriculturally and medically important strains in sequenced genomes (8), although accounted for by BayesTraits, should also be noted.

Given the prevalence of plant-associated members, a recent study hypothesized that the LCA of Rhizobiales was already capable of colonizing the root of plants (8). Here, we revisited this idea by showing that the highly diversified lifestyles in Rhizobiales likely originated from a free-living ancestor. We also estimated the emergence of Rhizobiales some 1,500 Mya, far predating the origins of their hosts, including land plants (∼470 Mya) (24), insects (∼480 Mya), (23) and mammals (∼180 Mya) (22). Such an ancient origin of Rhizobiales indicates that the free-living lifestyle was adopted by Rhizobiales over the first half of their evolutionary trajectory. Rhizobiales evolved to live in association with early terrestrial animals and plants that emerged during the Cambrian explosion in their middle age, and at a later stage, when nodulating plants emerged, they established the legume-rhizobium symbiosis which is among the best-known symbiosis relationships.

Our results also indicate that genomic plasticity is an important feature driving the evolution of diverse lifestyles in Rhizobiales. Both the recurrent gains of genes that determine lifestyle transition and the losses of genes that do not have big advantages underlie the evolutionary adaptations of Rhizobiales to different lifestyles. Some of these lifestyle-important genes, if acquired by ancestral lineages, might make their descendants preadapted to the development of certain lifestyles. In addition, HGTs of genes important for and common to Rhizobiales of different lifestyles (e.g., T4SS genes) across rhizobia, plant associates, and animal pathogens might facilitate lifestyle diversification across the entire order (6, 13).