INTRODUCTION

TOP ABSTRACT INTRODUCTION RESULTS AND DISCUSSION CONCLUSION REFERENCES

Introduction: Traditional Single-gene Phylogeny

The sequencing of whole genomes of microbial organisms allows us to reassess how we place organisms into groups and relate them to each other in phylogenetic trees. Traditionally, microorganisms have been grouped together into trees based on the sequence similarity of small subunit ribosomal RNA (SSU rRNA) (Woese et al. 1990; Woese 1987). This approach uses a single important and highly conserved gene, which has complex interactions with many other RNAs and proteins, as a basis of phylogeny. Despite its popularity, there are a number of long-standing difficulties with this approachfor example, long-branch attraction, unresolved tree differences, rate variation among sites, and mutational saturation (Lopez et al. 1999; Doolittle 1999; Lawrence 1999; Jain et al. 1999; Gogarten and Olendzenski 1999). Some researchers have even proposed that rRNA itself can be horizontally transferred between organisms (Nomura 1999; Yap 1999).

Many researchers have also tried building trees based on sequence similarity of individual protein families, such as the cytochromes, ATPases, elongation factors, aminoacyl tRNA synthases, beta-tubulins, or RNA polymerases (Makarova et al. 1999; Teichmann and Mitchison 1999a; Tumbula t al. 1999; Lake et al. 1999; Doolittle 1998; Rivera et al. 1998; Ibba et al. 1999, 1997; Edlind et al. 1996; Baldauf et al. 1996; Brown and Doolittle 1995; Andersson et al. 1998; Tomb et al. 1997; Bult et al. 1996; Lake 1994). These studies have often resulted in a wide range of implied phylogenies. The differences from the accepted ribosomal phylogeny are usually attributed to such factors as horizontal transfer or the existence of ambiguous paralogs. However, sometimes they have been used to argue that the rRNA tree is not representative of the true phylogeny. This has been particularly effective when the protein tree is based on a complex and fundamental protein such as RNA polymerase, or when the protein tree is backed up by extensive natural history evidence (Hirt et al. 1999; Edlind et al. 1996).

Whole-genome Trees and the Current Controversy

Because SSU rRNA and other individual gene families each correspond to only a tiny fraction of the genomic material in most microorganisms, focusing exclusively on them ignores the bulk of the genetic information in constructing phylogenetic trees. (In particular, the ~1.8 kb of SSU rRNA makes up less than 0.2% of most microbial genomes, which are 1 Mb.) Now with the advent of completely sequenced genomes, it is possible to build trees that encompass much more of the genetic information in an organism. This has led to a profusion of new approaches toward phylogenetic estimation and a heated controversy about the structure of the fundamental tree of life, which has even been featured in the popular press (Pennisi 1998, 1999; Stevens 1999). On one extreme, some prefer traditional ribosomal trees. On the other extreme, some argue that trees are not really meaningful given the widespread evidence of horizontal transfer in microorganisms and that nets or more general graph structures should be used instead (Hilario and Gogarten 1993). In between, a third perspective maintains that most microorganisms can be arranged into meaningful trees; however, these trees might not always reflect the branching pattern suggested by rRNA.

To contribute to this debate, we build trees considering progressively more and more of the information in a genome and compare them with the traditionally proposed phylogeny. In particular, we are proposing a number of novel trees based on the occurrence of specific features, either folds or orthologs, throughout the whole genome. We call these genomic trees or whole-genome trees. Our approach toward genomic trees, which is schematized in Table 1, is similar to the practice in traditional phylogenetic analysis using the presence or absence of morphologic characteristics or heritable traits such as hair or vertebrae to group organisms(Hennig 1965; Maisey 1986).

Our first set of genomic trees is based on the occurrence of orthologous proteins. This work builds upon recent work done by other researchers clustering genomes based on the occurrence of protein families (Tekaia et al. 1999; Snel et al. 1999; Teichmann and Mitchison 1999a). In particular, Tekaia et al. (1999) developed a methodology for comparing the whole proteome content of one genome against another and using the loss or acquisition of genes to build trees. We add to this work by dividing the proteome into various classes, building trees based on these, and looking at their consistency.

Our second set of genomic trees is based on protein folds. Folds group together a number of protein families that may not share sequence similarity but do share the same essential molecular shape. As each protein fold represents a unique three-dimensional shape used by an organism, folds are ideal characteristics for building phylogenetic trees. To build our fold trees, we used a similar approach to that for the ortholog trees, in this case using the presence or absence of folds in particular genomes for tree construction. Our fold tree work is an extension of our previous investigations (Gerstein 1998a). Related work comparing genomes in terms of the occurrence of protein folds has been done by Wolf et al. (1999), who used somewhat different definitions to cluster organisms based on folds.

In a strict sense, our fold occurrence and ortholog occurrence trees are partial proteomes rather than whole-genome trees, because they are based on considering simultaneously a large, but not complete, portion of the protein-coding regions of genomes. The entire genome cannot be used, because not all of the proteins can be classified as part of orthologous groups or can be assigned to fold families. In the last part of our analysis, we look at trees that are based on information from the entire genome, using amino acid and dinucleotide composition. Although these trees represent an unbiased consideration of all the information in the genome, they condense everything to a simple composition vector, discarding much important detail. Our composition tree analysis follows up on our previous work (Gerstein, 1998b) and extensive work done by Karlin and co-workers (Karlin and Burge 1995; Karlin and Mrazek 1997; Campbell et al. 1999). Finally, it is worth pointing out that a number of additional approaches toward whole-genome trees have been advanced beyond those discussed here. In particular, Gupta (1998) used insertions and deletions along with cell-membrane structures for tree reconstruction.

Note that, whereas the occurrence and composition trees have the advantage over the single-gene trees in that they incorporate more genome information, they are not as clearly associated with an evolutionary mechanism. That is, underlying the ribosomal tree there is a specific biologic mechanism, internal to each organism, generating sequence diversity: the mutation of single base pairs, which happens at a rate roughly proportional to time. However, the way a single organism expands or contracts its repertoire of folds or orthologs cannot be explained simply in terms of individual molecular events. If one explains the acquisition of folds with horizontal transfer, the tree is no longer based on ancestral characteristics evolving internally but on the interaction with other organisms. Therefore, as opposed to true evolutionary phylogenies, whole-genome trees would then more appropriately be described as clusterings.

	RESULTS AND DISCUSSION

TOP ABSTRACT INTRODUCTION RESULTS AND DISCUSSION CONCLUSION REFERENCES

Genomes Analyzed and Tree Techniques Used

We focus on the first eight microbial genomes to be sequenced, which include representatives from all three domains of life (Table 2). All our trees were built with the standard programs using both maximum-parsimony and distance-based methods (Felsenstein 1993, 1996; Swofford 1998). In general, we found that distance-based methods gave more reasonable results, probably because of the great divergence of the taxa, which has been remarked upon in other contexts (Swofford et al. 1996). Additional information (clickable trees, plots, etc.) is available on the Internet at http://bioinfo.mbb.yale.edu/genome/trees.

Ortholog and Fold Assignments

Orthologs were selected from the COGs (clusters of orthologous groups) database (Tatusov et al. 1997; Koonin et al. 1998). This database lists groups of ortholog sequences in eight of the first genomes sequenced based on whether or not they form a mutually consistent sequence of best matches between genomes. This database is in wide use and is accepted as a valid source of functional annotation. It groups orthologs into a hierarchy of functional classes-(e.g. class J, transcription, is part of the "Information Storage and Processing" superclass). The presence or absence of specific proteins for all the COGs for different genomes can be derived from the web site data files.

Folds were assigned to the genome sequences based on a previously described approach (Gerstein 1997, 1998b; Teichmann and Mitchison 1999b; Hegyi and Gerstein 1999). We compared the structure databank (the PDB) against the genome sequences by using both pairwise and multiple-sequence methods and standard thresholds (FASTA and PSI-BLAST, Lipman and Pearson 1985; Pearson 1996; Altschul et al. 1997). We used the SCOP classification to group the domain-level structure matches into different fold families (Murzin et al. 1995). The SCOP (structural classification of proteins) classification is assembled based on expert manual judgement, and we have augmented it with our automatically derived protein-structural alignments (Gerstein and Levitt 1998). Like the COG scheme, the SCOP classification is in wide use and accepted as a reliable classification of a protein's fold.

Single-gene Trees, a Reference Point

Traditional Ribosomal RNA Trees

View larger version (14K): [in this window] [in a new window]   Figure 1   Representative single-gene trees. (A) The traditional small subunit ribosomal phylogenetic tree. This is a tree of eight completely sequenced representative organisms constructed with the SSU rRNA. Trees could be constructed using data from two different sources: the Ribosomal Database Project (RDP, http://www.cme.msu.edu/RDP, Maidak et al. 1999) and the rRNA WWW Server (http://www-rrna.uia.ac.be, Van de Peer et al. 1999). Although a tree can be abstracted from the RDP, the tree cannot contain both prokaryotes and eukaryotes. Instead, we took sequences from the RDP and the rRNA WWW server and aligned them with Clustal (Thompson et al. 1997). Phylip and PAUP were used to construct trees from the aligned sequences using distance and parsimony methods. There was little variation in the resulting trees displayed using TreeView (Page 1996), which was used to show all the trees used in this survey. The PAUP distance-based tree is shown. (B) The large subunit ribosomal tree. Another common method of building phylogenetic trees is the use of the large subunit rRNA (De Rijk et al. 1999). Because of the lack of large subunit rRNA information from the RDP, the sequences were downloaded from the rRNA WWW Server. The same method of tree construction was used as in A. The tree shown in B is the PAUP distance-based tree. Because of the large divergence of the species, the topology of the tree varied slightly when compared to the SSU ribosomal tree in A. The placement of Synechocystis was slightly different, as it is placed closer to the eukaryote and Archeae in the large subunit tree. This was relatively less significant when considering the branch lengths of the tree in A . (C , D) Representative trees based on sequence similarity of orthologs. The sequences of proteins for the different organisms were obtained from the COGs web site (http://www.ncbi.nlm.nih.gov/COG, Tatusov et al. 1999). Clusters of orthologous groups were chosen that had one protein for each organism in the group. There were eight such COGs with representatives from four different classes. Distance-based trees and parsimony trees were both constructed for each of the orthologous groups. There was great variation in the resulting trees. The tree, which had the highest similarity to the traditional ribosomal tree, is shown in C. In fact, the distance-based tree based on the 30S ribosomal protein S3 (COG92, Class J) in C is exactly the same in topology to the traditional tree. This is not surprising because we expect a ribosomal protein tree to be similar to ribosomal rRNA trees because of their interaction and conservation. For the bootstrap values, all bootstrap replicates grouped E. coli with H. influenzaee, S. cerevisiae with M. jannaschii, and M. genitalium with M. pneumoniae. In all, the conserved topology coupled with high bootstrap values shows that phylogenetic trees with even a single protein can exhibit very high fidelity to the traditional ribosomal tree. Besides trees with high similarity to the traditional tree as in C, there were trees that varied significantly from the traditional ribosomal tree. Part D shows a distance-based tree based on the metabolic enzyme triosephosphate isomerase (TIM). In general, there are a lot of differences between this tree and the traditional tree. M. jannaschii is grouped with M. genitalium and M. pneumoniae; M. jannaschii is not grouped with S. cerevisiae at all. The connectivity of S. cerevisiae and H. pylori is also different from the traditional tree. The low bootstrap values of 59% and 40% suggest that within the sequence there is great variation and the tree is generated with lower certainty. In general, there were a wide variety of trees produced using sequence similarity of orthologous proteins.

Single-gene Ortholog Trees

Genomic Occurrence Trees

Now that we have described the single-gene perspective as a reference, we can progress to the focus of our analysis, constructing genomic trees that consider more than the variation of individual genes. These trees were defined in terms of presence or absence of shared characteristics throughout the whole genome. Broadly, these characteristics potentially could be orthologs, homologs, or folds. We focused on orthologs and folds. We used both distance-based and parsimony methods for tree construction. For the distance-based methods, we defined the distance between two organisms with a normalized Hamming distance, which was expressed as the fraction of unshared characters divided by the total number of characters in the genomesthat is (A + B2S)/(A + B), where A and B are the characters in the first and second genomes, respectively, and S is the number of shared characters between A and B.

We had hoped that parsimony would produce reasonable trees, because this method would automatically propose ancestral organisms that had the intermediate configurations of orthologs or folds. However, we found that, in general, distance-based methods resulted in trees closer to the traditional phylogeny. This may be because of the great divergence of the organisms studied. We give an example of the superiority of distance-based methods in Figure 3, which compares fold trees based on distances and parsimony. Also, because of the divergence of the organisms, a number of our trees may show some evidence of long-branch attraction. This arises when there are differing rates of variation among different sites in a gene, resulting in the clustering of organisms with higher rates of sequence change (Felsenstein 1996). However, we feel long-branch attraction affects the ribosomal tree as much as, if not more than, the whole-genome trees, as evident in its longer relative branch lengths and more star-shaped appearance (i.e., with less well-resolved branching). Furthermore, it is known that distance-based methods are less sensitive to long-branch attraction than parsimony, perhaps suggesting why we found the distance-based trees more reasonable.

Genomic Tree Derived from Occurrence of Orthologs

View larger version (17K): [in this window] [in a new window]   Figure 2   Genomic trees based on the occurrence of orthologs. (A) Distance-based genomic tree based on the overall occurrence of orthologous proteins in the complete genome. One of the alternative methods we used for phylogenetic analysis involved building trees based on the presence or absence of orthologs in the complete genome, using the information from the original COGs web site with eight genomes (http://www.ncbi.nlm.nih.gov/COG, Tatusov et al. 1999). For each of the microbial organisms, the occurrence of proteins in each of the clusters of orthologous groups was tabulated with 1 for present and 0 for absent. With the parsed data, a distance matrix was then calculated using the normalized Hamming distance, as described in the text. The trees were subsequently constructed using the kitsch program in the PHYLIP package, which allowed for easy automation. For the bootstrap values, we used PAUP. The resulting tree shown is a distance-based tree using the information of the occurrence of all the COGs in the genomes. As expected, the M. pneumoniae and M. genitalium are grouped with bootstrap values of 100%. However, interestingly, E. coli and Synechocystis are also clustered with this bootstrap valuea grouping that is not in the traditional tree. Also, M. jannaschii is clustered with M. pneumoniae and M. genitalium with a bootstrap value of 81%. Furthermore, the eukaryote, S. cerevisiae, is placed among the bacteria. (B, C, and D) Ortholog occurrence genomic trees based on a three-way partition of the whole ortholog set. As described in the text, the total COGs were divided into three large subsets, the information, cellular, and metabolic subsets. The pie chart in Figure 3 shows the number of COGs in each group as percentages. The metabolic subset dominated the total group with 362 COGs, approximately half of all the COGs. The information subset has 190 COGs, just above one quarter, while the cellular subset has 132 COGs, just less than a quarter. For each of the subsets, distance-based trees were generated using the same methods described in A. Because of the smaller sizes of these subsets, the bootstrap values were often ill-defined. The largest subset was the metabolic partition shown in B. There was a high correlation between the trees in A and B. Aside from the different placement of H. pylori and S. cerevisiae, the trees are nearly identical, even having similar branch lengths. The second largest partition was the information subset shown in C. Surprisingly, this subset produced a tree almost identical to the traditional ribosomal tree. The only difference is the switch in the placement of H. pylori and Synechocystis. This shows that although using the entire group of COGs may produce trees much different from the traditional tree, using a smaller subset may in fact produce a tree that is closer to the traditional topology. Part D shows the smallest partition, the cellular subset. (E and F) Representative genomic trees of ortholog occurrence based on specific functional classes J and H. Using the functional classes obtained from the COGs web site, the metabolic, information, and cellular partitions were subdivided further, into specific functional classes. For each of the different functional classes, there was a range of trees produced. Two representatives were chosen to show this variety. Class J (translation, ribosomal structure, and biogenesis), which has 108 clusters of orthologous proteins, is a further subdivision of the information subset. It has a tree very similar to the traditional ribosomal tree in Figure 1A. Class H (Coenzyme metabolism), which has 77 clusters of orthologous proteins, is a further subdivision of the metabolism subset. It produced a tree that did not correspond well to the traditional phylogeny.

Subdivision by Functional Class

Fold Trees

View larger version (15K): [in this window] [in a new window]   Figure 3   Genomic trees based on the occurrence of folds. (A) Genomic tree based on the overall occurrence of folds in the genomes, generated by a distance-based method. For each of the microbial organisms the presence or absence of folds was marked with 1 or 0, respectively. The folds that were not present in any of the genomes were excluded, because this does not provide any distinguishing information. Similar to the ortholog occurrence, a distance matrix was generated with the Hamming distance. (B) Genomic tree based on the overall occurrence of folds in the genomes, generated by parsimony. Instead of generating a distance matrix, parsimony can be used for tree construction. For this task, PAUP was used and the resulting tree is mostly similar to the distance-based tree. However, the locations of S. cerevisiae and H. pylori are switched. Also, in contrast to the traditional ribosomal tree, S. cerevisiae is placed closer to M. jannaschii, whereas H. pylori is placed with the other bacteria. Therefore, the distance-based method as described in A seems to be better. For all the trees presented here, both distance-based and parsimony trees were generated; in general, as observed in this instance, the distance-based tree is closer to the ribosomal tree. The star shown in the bootstrap value represents a node where the bootstrap consensus tree results in a star decomposition and cannot be resolved. (C, D, E, and F) Distance-based genomic trees based on occurrence of folds in particular fold classes. In this analysis, instead of dividing the COGs into functional classes, the folds are fractionated into classes: all-alpha, all-beta, alpha+beta, and alpha/beta. As seen in the pie chart, the distribution of folds among the different classes is rather equal; each has approximately one quarter of the total. Of the four divisions of folds, the alpha+beta group is most similar to the overall tree, having the exact same topology. It also has the largest number of folds (81, 29% of the total). The all-alpha fold group has 27% (75) of the total folds and has almost the exact topology of the overall tree, except that H. pylori and Synechocystis are grouped together instead of just being close to each other. The alpha/beta group has 24% (68) of the total folds and is also very similar to the overall fold tree. The most surprising tree is that of the all-beta group. This is based on the smallest number of folds, which is 20% (55) of the total folds.

Subdivision by Fold Class

Genome Composition Trees

Because we cannot assign every single ORF in a genome to a known fold or ortholog family, the genomic occurrence trees based on these characters are in a strict sense partial proteome trees. Consequently, they suffer from potential biases because the orthologs or folds that are selected may not represent a truly random sampling of proteins in the genomes. One simple way of building a tree that takes into account all the information within the genome in unbiased fashion is using the overall nucleotide composition. To complete our analysis, we built trees based on dinucleotide and amino acid (essentially trinucleotide) composition. We constructed vectors representing the normalized composition of the genome, denoted by f, and then took the difference of these vectors to define our tree. We thus used the following relation for the distance between genomes i and j:

where f(i,k) represents the composition and the sum over k runs from 1 to M=16 or M=20, depending on whether the tree is for dinucleotide composition or amino acid. Clearly, in the computation of composition, while we are broadly considering the entire genome, we are discarding much information by reducing the entire genome into a single composition vector.

Dinucleotide Composition

View larger version (9K): [in this window] [in a new window]   Figure 4   Trees based on overall composition. (A) Dinucleotide composition tree. We counted the relative frequency of the dinucleotides for the complete genomes of the eight organisms. Distance between two species of dinucleotides is the distance between the 16-dimensional vectors, with each axis representing a dinucleotide pair. PAUP then generated trees using the distance matrix. Figure 4A shows the resulting dinucleotide composition tree, which has almost no resemblance to the traditional ribosomal tree in Figure 1A. Even the M. genitalium and M. pneumoniae clustering, which is conserved throughout the survey, does not appear. This suggests that the dinucleotide method is not very accurate in the production of phylogenetic trees. Although it encompasses entire genomes, it reduces them to a 16-dimensional vector, losing much information. (B) Amino acid composition tree. This shows the tree generated from amino acid composition. Again, the relative frequencies of the amino acids were counted and a similar distance measure as in A was used. The distances between the genomes are calculated using 20-dimensional vectors, one for each amino acid. The resulting distance matrices were used to generate trees using PAUP. Interestingly, although this tree is still significantly different from the traditional tree in Figure 1A, it indeed is a great improvement upon the dinucleotide composition tree. Relatively, the organisms are closer in position to the traditional tree.

Amino Acid Composition

	CONCLUSION

TOP ABSTRACT INTRODUCTION RESULTS AND DISCUSSION CONCLUSION REFERENCES

We built trees grouping organisms based on the overall occurrence of molecular features throughout their genomes. Most broadly, these characteristics could be orthologs, homologs, or folds. We focused on orthologs and folds. For folds we found that the overall genomic tree agreed surprisingly well with the traditional ribosomal tree. However, the distribution of all-beta folds was somewhat different. For orthologs we found that an occurrence tree based just on proteins involved in transcription and translation also agreed quite well with the traditional phylogeny. However, one built based on metabolic proteins had a rather skewed topology, and as the metabolic subset comprised most of orthologs, the overall ortholog tree also shared this appearance. This implies that adding more features does not necessarily increase the accuracy of the tree, an observation that, of course, has been made numerous times in relation to traditional phylogeny (Swofford et al. 1996). We compared our occurrence trees with many other possible trees, ranging from single-gene trees based on sequence similarity of individual orthologous proteins to entire-genome composition trees. We found that many of these alternate trees had rather unusual topologies, providing a good context for appreciating how remarkable was the agreement between whole-genome occurrence trees, particularly the fold tree, and the traditional tree.

Prospects: Trees Based on More Genomes

The number of genomes being sequenced is increasing at a fast rate and obviously the eight-genome scale of analysis presented here will be soon out of date. However, the real question is whether our approach of comparing genomes in terms of the occurrence of orthologs or folds will scale with more and more organisms. We believe it will. Recently, we have built whole-genome occurrence trees based on more than eight genomes and found that they had quite a reasonable topology. As an illustration, in Figure 5, we show a fold tree based on 20 genomes.

View larger version (12K): [in this window] [in a new window]   Figure 5   Prospects for the future. The figure shows a 20-genome tree based on the occurrence of folds. This is similar to Figure 3A. The unit in the SCOP classification that was used was the structural superfamily rather than the fold. For eight genome occurrence trees there is no difference between one made at the fold or superfamily level. However, for the 20-genome tree this distinction matters. The additional species names in the 20-genome tree are: Aaeo (Aquifex aeolicus), Aful (Archaeoglobus fulgidus), Bsub (Bacillus subtilis), Bbur (Borrelia burgdorferi), Cpne (Chlamydia pneumoniae), Ctra (Chlamydia trachomatis), Ecol (Escherichia coli), Hinf (Haemophilus influenzae), Hpyl (Helicobacter pylori), Mthe (Methanobacterium thermoautotrophicum), Mjan (Methanococcus jannaschii), Mtub (Mycobacterium tuberculosis), Mgen (Mycoplasma genitalium), Mpne (Mycoplasma pneumoniae), Phor (Pyrococcus horikoshii), Rpro (Rickettsia prowazekii), Scer (Saccharomyces cerevisiae), Syne (Synechocystis sp.), and Tpal (Treponema pallidum).