A Phylogenomic Approach to Bacterial Phylogeny: Evidence of a Core of Genes Sharing a Common History

Comparison of Gene Trees

As noted above, it is difficult to study lateral transfers using phylogeny because the extent to which the rRNA tree, or any other reference, represents something more than the phylogeny of a gene is unknown. To bypass this problem, we made all of the possible comparisons between gene phylogenies by using principal coordinates analysis (PCO). If a group of genes tends to have similar phylogenies, it may be representative of a common history.

We used the Robinson-Foulds (RF) topological distance (Robinson and Foulds 1981) to compare trees with each other. It was not possible to consider every domain (Archaea, Bacteria, and Eukarya) at the same time since too many pairs of trees were not comparable due to lack of common species. We therefore computed topological distances between all 310 trees containing at least ten bacterial species. Only results based on distance-based trees are shown, because ML-based trees gave very similar results. The result of this analysis of 310 trees is particularly interesting: the representation of the two first axes of PCO (Fig. ​(Fig.3)3) shows a cloud that is very dense on the right with a tail on the left. This structure is mainly due to the first axis, the other axes displaying a distribution that is centered on the origin. The structuring on the first axis suggests that genes gathered in the densest region of the cloud share, at least partially, a common phylogenetic signal, while trees present in the tail are perturbed by lateral transfers, hidden paralogies, or reconstruction artifacts. When considering the position of informational and operational genes in the cloud, it is very striking that informational genes are almost all grouped in the densest region, while the tail is formed only by operational genes. This result is consistent with previous studies (Rivera et al. 1998; Jain et al. 1999) that present evidence of a better conservation of phylogenetic information in informational genes. However, since operational genes are also well represented in the dense region, this result suggests that, contrarily to informational genes, this definition refers to a heterogeneous group, which contain genes that may be as constrained as informational genes through evolution.

Open in a separate window

Figure 3

Plot of the two first axes of the PCO made from 310 BIONJ trees compared with RF distance. The trees chosen contained at least 10 bacterial species. The same experiment with ML-trees gave very similar results. Black dots correspond to informational genes, and gray dots correspond to operational genes. The ellipse contains the 121 trees retained for supertree reconstruction (see Table ​Table11).

Supertree Compared to Other Genome Trees

Many methods using information from complete genomes to infer phylogenetic relationships between prokaryotes have been proposed. Among them, we mention here those based on concatenation of genes and those using gene content. Regarding the former method, one of the most remarkable works is that of Brown et al. (2001). Those investigators used a set of 23 ubiquitous and well-conserved genes to infer the phylogeny of 45 organisms. Their tree supports, with high bootstrap values, the basal position of Spirochaetes and Chlamydiales. However, they found that nine of these genes (which represented about 40% of their data set) had been subject to interdomain lateral transfers. Notably, some of them were identified as transfers involving Archaea and Spirochaetes, which could be responsible for the basal position of these bacteria. After removal of those genes from the set, a phylogeny that is sensitive to reconstruction methods and with low support for several deep branches was obtained. This topology is however in general agreement with the rRNA-based topology, notably for the position of hyperthermophilic bacteria that occupy the most basal position. Although this method enables one to obtain alignments of respectable length, it remains limited by the number of genes it can take into account. Moreover, Brown et al. (2001) showed that the presence of laterally transferred genes radically changes the topology of the tree in the concatenation method. Thus, if 40% of the genes retained have undergone interdomain lateral transfers, what is the rate of lateral transfers among bacteria and what is their impact on the final phylogeny?

Another objection to the concatenation approach is the weighting accorded to a gene. For example, in the 14-protein alignment of Brown et al. (2001), only four proteins represent more than half of all sites. Thus, if a gene family has undergone a lateral transfer, it may impose its topology if the protein is long enough. A solution to these problems could be the addition of a large number of genes, since a common phylogenetic signal may emerge through discordant information due to lateral transfers (Eernisse and Kluge 1993). However, other approaches must be developed, because ubiquitous genes are rare.

The methods based on gene content may be summarized as follows: if one considers that events of gain and loss of genes are relatively rare, then the presence or absence of a gene in a genome can be considered an informative binary character. Hence, a phylogeny minimizing these events can be reconstructed and may represent the phylogeny of the genomes. Several authors have proposed schemes derived from this idea. Though these methods can give very interesting results (Snel et al. 1999), the hypothesis on which this model is based could be discussed at length, since many investigators consider gene loss and lateral transfers the main driving force of bacterial evolution. For example, Ochman et al. (2000) estimated that prokaryotic genomes may contain 0%–16.6% genes (with a mean of ∼6%) acquired recently enough to conserve an atypical nucleotide composition. Moreover, Mira et al. (2001) proposed a model of genome size maintenance in which gain and loss of genes play the most important role. Thus, gene content-based methods may encounter problems due to convergence.

The strength of the supertree method is that it allows a large amount of data to be considered. As discussed above, this property should allow the recovery of a phylogenetic signal in the presence of lateral transfers. Moreover, each gene tree brings a comparable amount of information, whatever its length. However, the topology of the supertree based on 730 genes, and particularly its bacterial part, suggests that it is necessary to remove trees containing long branch artifacts, lateral transfers, or hidden paralogy. It is worth noting that the ML trees seem to be more subject to reconstruction problems, because the grouping of ɛ-Proteobacteria, hyperthermophilic bacteria, and Spirochaetes is clearly artefactual. The PCO analysis made of trees containing comparable sets of species (see Methods) revealed that a group of genes possess similar topologies for the bacterial part of the tree. This group contains almost all informational genes contained in the data set. This result is in agreement with the vision of a core of genes that remains associated for long periods in prokaryotes. As proposed earlier, informational genes seem to be an essential component of this core, but it appears that this is also the case for several operational genes. However, operational genes undoubtedly display a larger range of topology, which highlights the fact that this functional class regroups genes having very different evolutionary patterns. Though it may be due to lateral transfers, it is worth noting that the genes present in the tail of the cloud shown in Figure ​Figure33 tend to contain fewer species. Hence, they may also be subject to reconstruction problems due to low number of taxa (Lecointre et al. 1993) or may contain hidden paralogies, which are more difficult to detect in gene families containing few species (Salzberg et al. 2001).

Horizontal Transfers: “Genome Space” or Core of Genes?

Although some deep nodes have low bootstrap support, the level of resolution of the supertree reported here is in strong disagreement with the “genome space” (Bellgard et al. 1999) vision of the prokaryotic world predicting a “star phylogeny.” One could argue that grouping of species in the supertree would only reflect the frequency of gene exchanges between these species. This interpretation can be excluded because the supertree method would then not be expected to give a tree topology radically different from gene content-based trees (Snel et al. 1999; Tekaia et al. 1999; Lin and Gerstein 2000), which are predicted to be very sensitive to this problem. It is worth noting that a particularly stringent selection of protein families was exercised for building the supertree. In particular, a phylogenetic definition of orthology rather than a definition based on reciprocal best BLAST hits was used (Eisen 2000a; Koski and Golding 2001), as is often the case for practical reasons. Thus, all gene trees where a species was represented more than once were excluded from analysis. This selection allowed us to make absolutely no a priori assumptions about the topology of the trees, except for the monophyly of Bacteria, and to reduce the probability of taking hidden paralogies into account. Although the PCO analysis led to a strong reduction of the length of the supermatrix (e.g., from 5382 sites in Fig. ​Fig.2A2A to 1891 sites in Fig. ​Fig.4A),4A), bootstrap values increased for most bacterial nodes. This increase of bootstrap values in supertrees reveals that the group of genes selected after the PCO analysis contains congruent information on the phylogeny of Bacteria. This suggests a vision of bacterial evolution where a “core” of genes tends to remain stable through evolution (Snel et al. 1999; Eisen 2000b).

The HOBACGEN-CG annotations of the gene families present in the dense region of the PCO data with BIONJ trees are shown in Table ​Table1.1. As noted above, this set of genes is strongly enriched in informational genes compared to the complete data set. However, about half of the genes have operational functions. A substantial fraction of these genes have no known function. Their presence in the inferred core of genes suggests that they may have an important function.

Which Artifacts May Affect the Supertree?

The sample of completely sequenced bacterial genomes is currently strongly biased toward species of medical interest. Thus, the supertree contains many parasites that display peculiar evolutionary patterns. Based only on topology and statistical support, our supertree method is expected to be sensitive to systematic artifacts of reconstruction. Nevertheless, although systematic bias exists, artifacts are not likely to systematically gather the same species, depending on the species sampling, which may differ between gene families in a supertree approach. In this case, even weak congruent information due to phylogenetic signal would be stronger than conflicting artefactual information. For instance, Mycoplasma species have a very low genomic G+C content (25% for Ureaplasma parvum and 32% for Mycoplasma pneumoniae), and are known to have a very reduced genome and fast evolutionary rate (Ochman et al. 1999). This is probably why these species tend to have a very basal position in several single (Gupta 1998; Klenk et al. 1999) and multiple gene phylogenies (Teichmann and Mitchison 1999; Hansmann and Martin 2000; Lin and Gerstein 2000). Therefore, the fact that Mycoplasma species are unambiguously grouped with Bacillus in the supertrees suggests that our approach is robust against biases related to G+C content and evolutionary rates. The same remarks can be made for Helicobacter pylori, which shows a high level of genetic variation between strains (Wang et al. 1999) and tends to have an aberrant position in many phylogenies (Gupta 2000), probably due to its high evolutionary rate.

The Supertree of Life: Questions About Bacterial History

The topology of the supertrees (Fig. ​(Fig.4)4) strongly supports the monophyly of each of the three domains of life (Bacteria, Archaea, and Eukarya). The phylogeny of Proteobacteria appears to be relatively well resolved at this level and is in agreement with the rRNA phylogeny and protein-based works (for review, see Gupta 2000). Their monophyly (including H. pylori and Campilobacter jejunii) is well supported, and this last result is particularly valuable because it has rarely been found with genome tree methods (Teichmann and Mitchison 1999; Tekaia et al. 1999; Lin and Gerstein 2000). Equally interesting is the position of the thermophilic bacteria, Aquifex aeolicus and Thermotoga maritima, which are strongly grouped. First, the monophyly of these bacteria contradicts small subunit ribosomal RNA analysis, which branch them successively at the base of the Bacteria and thus supports a thermophilic origin of Bacteria (Woese 1987; Barns et al. 1996, Bocchetta et al. 2000). If thermophilic bacteria are shown to be monophyletic, even with a basal position, the hypotheses of a thermophilic or mesophilic bacterial ancestor become at least equally parsimonious. However, since proteins of thermophilic bacteria and Archaea have been shown to possess a very peculiar amino acid composition (Kreil and Ouzounis 2001), it remains possible that the grouping of Thermotoga and Aquifex rests on a systematic artifact present in the majority of the trees. Second, Aquifex and Thermotoga are significantly excluded from the basal position in the gamma distance-based supertree. Thus, the genomic supertree brings no evidence for an early divergence of thermophilic lineages and is more consistent with a mesophilic last universal common ancestor (LUCA; Forterre 1996; Galtier et al. 1999). This view interprets the early emergence of these lineages in rRNA trees as a reconstruction artifact (Forterre 1996; Klenk et al. 1999) due to a bias of rRNA toward high-G+C content in hyperthermophiles (Galtier et al. 1999). Our result rather confirms that Thermotoga and Aquifex were secondarily adapted to high temperature (Miller and Lazcano 1995; Forterre 1996). Several studies have already reported a clustering of Aquifex with Proteobacteria (Klenk et al. 1999; Gupta 2000) or of Thermotoga with Gram-positives (Tiboni et al. 1993; Gribaldo et al. 1999). Thus, though our results cast a shadow on the basal position of thermophilic bacteria, their exact position remains an open question.

The basal position of Spirochaetes and Chlamydiales seems to have some level of support. The deep nodes of the supertree based on gamma-corrected distances are indeed supported by bootstrap values over 70%. The fact that these bacteria are vertebrate parasites does not preclude their basal position, because they possess close free-living relatives (Paster and Dewhirst 2000). Remarkably, Brown et al. (2001) using a set of 23 concatenated proteins found a very similar topology and interpreted this result as an artifact due to lateral transfers between Bacteria and Archaea in some of these proteins. However, such an explanation could not be proposed in the present case, since only families compatible with monophyletic Bacteria were selected. Noticeably, among the 121 trees retained to build the supertree, only 35 contain information for the position of the root of Bacteria by spanning two or more domains (see Table ​Table1).1). Few studies have inferred the position of the root of Bacteria with so much data, but this number is still relatively low. Thus, this result must be confirmed by adding species, and particularly species close to Spirochaetes and Chlamydiales.

The monophyly of low G+C Gram-positives (including Bacillus and Mycoplasma) on one side and of high G+C Gram-positives on the other side appears to be very robust, but the significant support for the position of Deinococcus radiodurans suggests polyphyly of the Gram-positives. This position is very striking because Deinococcus is usually considered to have a much more basal position among bacteria (Woese 1987). Huang and Ito (1999) noted such a position, close to Gram-positives, with a DNA polymerase C phylogeny. The Brown et al. (2001) study also gives strong support to this position. These results suggest that two independent losses of the external membrane occurred in high-G+C and low-G+C Gram-positive bacteria. Nevertheless, it is interesting to note that the bootstrap value supporting this grouping is the only one that decreases after the PCO analysis. Thus, it remains possible that this position is due to the high G+C content of the genome of Deinococcus. Indeed, Deinococcus is a close relative of Thermus aquaticus, which is a Gram-negative thermophilic bacterium. Though Deinococcus is positive to the Gram coloration, it has been shown to possess an external membrane, unlike Gram-positives (Murray 1986). Thus, though this position of Deinococcus seems to have some degree of support in several studies (including our present work), it still needs to be confirmed, in particular by the addition of Thermus in the supertree.

The Archaeal part of the tree shows rather low bootstrap values in Figure ​Figure4.4. This may be due to the fact that all genes present only in Archaea were removed from the PCO analysis. This part of the tree appears to be rather well resolved when considering the 730 trees, especially with ML-based trees (Fig. ​(Fig.2B).2B). This supertree shows strong support for both Archaea monophyly and their division in two groups, that is, Crenarchaeota and Euryarchaeota. ML-based trees and gamma distance-based trees support a different position for the species Thermoplasma acidophilum. Hence, the topology of the Archaeal part of the tree should be considered with caution. Our experience of supertrees suggests that such problems will be resolved when more Archaeal genome sequences become available.

The eukaryotic part of the tree supports a clade gathering plants and animals, which is in contradiction with more precise studies (Baldauf et al. 2000). However, since this work was not aimed at eukaryotic phylogeny, genes that were specific to eukaryotes were not retained. Thus, the topology of this part of the tree is based on only a few of the available genes. Moreover, it is difficult to infer relations of orthology when considering so few species (Salzberg et al. 2001), especially among eukaryotes, where the frequency of multigene families is high. Indeed, it is well known that reconstruction methods often fail to find the true phylogeny with small taxa samples (Lecointre et al. 1993). A supertree study of relationships among eukaryotes should use a completely different method of selecting gene families than the one proposed here.

Alignments and Tree Construction

The sequences of each family were aligned using CLUSTAL W (Higgins et al. 1996), with all default parameters. To select parts of the alignments for which homology between sites can be assumed with good confidence, we used the GBLOCKS program (Castresana 2000). This program identifies blocks in an alignment for which homology of sites can be assumed with good confidence and regions that contain reliable phylogenetic information. It has been shown to give alignments that are almost independent of the different options of CLUSTAL W. We retained for tree construction only the alignments having conserved at least twice more sites than species.

An ML tree was computed for each family with the protML program (Kishino et al. 1990) (options: JTT model of substitution, quick add OTUs search, 300 trees retained) which gives an approximate bootstrap probability for each node. For each family, a BIONJ (Gascuel 1997) tree was also constructed using the distance matrix provided by PUZZLE (Strimmer and von Haeseler 1996) under a gamma law-based model of substitution (alpha parameter estimated by PUZZLE, eight gamma rate categories) and bootstrapped using SEQBOOT and CONSENSE from the PHYLIP package (Felsenstein 1989). To reduce the impact of interdomain lateral transfers, we applied the same criteria used by Brown et al. (2001); that is, we screened the trees where bacteria were not monophyletic and we removed these families from the data set or corrected them by removing the transferred sequences from the alignment when it was evident. We made no assumption about the monophyly of the Archaeal domain, as this problem has already been discussed (Martin and Muller 1998). Thus, 730 families containing at least seven of the 45 species available in HOBACGEN-CG were selected. Informational and operational genes were identified using annotations from HOBACGEN-CG.

Comparisons Between Trees

Trees were compared using a C program performing the following steps: (1) For each pair of trees, trees are reduced to the species they have in common. (2) The Robinson-Foulds (RF) topological distance (Robinson and Foulds 1981) is then computed for the pair. (3) On the n × n distance matrix obtained (n is the number of trees), a PCO is computed using ADE-4 (Thioulouse et al. 1997). PCO is a multivariate ordination method based on distance matrices, and it allowed us to embed our n trees in a space of up to n − 1 dimensions (Gower 1966). By taking the most significant two first dimensions and plotting the objects (the trees) along these, the major trends and groupings in the data can be determined by visual inspection.

Processing of the complete data set was difficult because several pairs of trees have nonoverlapping sets of species, producing a matrix with many holes. To reduce this problem, we performed the PCO analysis on trees containing at least ten bacterial species. This reduced the number of holes present in the matrix to less than 10% of the total, which allowed us to substitute remaining holes by the mean of the distances present in the matrix (D. Chessel, pers. comm.).

We thank G. Marais and E. Lerat for daily discussions, D. Chessel for advice in PCO computation, and L. Duret for critical reading of the paper. This work was supported by Centre National de la Recherche Scientifique and Ministére de la Recherche.The publication costs of this article were defrayed in part by payment of page charges. This article must therefore be hereby marked “advertisement” in accordance with 18 USC section 1734 solely to indicate this fact.