Predicting protein function by genomic context: quantitative evaluation and qualitative inferences

Function prediction and protein networks

In the genomics era, the interactions between proteins are at the center of attention. Genomic-context methods used to predict these interactions have been put on a quantitative basis, revealing that they are at least on an equal footing with genomics experimental data. A survey of experimentally confirmed predictions proves the applicability of these methods, and new concepts to predict protein interactions in eukaryotes have been described. Finally, the interaction networks that can be obtained by combining the predicted pair-wise interactions have enough internal structure to detect higher levels of organization, such as 'functional modules'.

A phylogenetic analysis of the pSymB replicon from the Sinorhizobium meliloti genome reveals a complex evolutionary history

Microbial genomes are thought to be mosaic, making it difficult to decipher how these genomes have evolved. Whole-genome nearest-neighbor analysis was applied to the Sinorhizobium meliloti pSymB replicon to determine its origin, the degree of horizontal transfer, and the conservation of gene order. Prediction of the nearest neighbor based on contextual information, i.e., the nearest phylogenetic neighbor of adjacent genes, provided useful information for genes for which phylogenetic relationships could not be established. A large portion of pSymB genes are most closely related to genes in the Agrobacterium tumefaciens linear chromosome, including the rep and min genes. This suggests a common origin for these replicons. Genes with the nearest neighbor from the same species tend to be grouped in "patches". Gene order within these patches is conserved, but the content of the patches is not limited to operons. These data show that 13% of pSymB genes have nearest neighbors in species that are not members of the Rhizobiaceae family (including two archaea), and that these likely represent genes that have been involved in horizontal transfer.

Exploiting the co-evolution of interacting proteins to discover interaction specificity

Protein interactions are fundamental to the functioning of cells, and high throughput experimental and computational strategies are sought to map interactions. Predicting interaction specificity, such as matching members of a ligand family to specific members of a receptor family, is largely an unsolved problem. Here we show that by using evolutionary relationships within such families, it is possible to predict their physical interaction specificities. We introduce the computational method of matrix alignment for finding the optimal alignment between protein family similarity matrices. A second method, 3D embedding, allows visualization of interacting partners via spatial representation of the protein families. These methods essentially align phylogenetic trees of interacting protein families to define specific interaction partners. Prediction accuracy depends strongly on phylogenetic tree complexity, as measured with information theoretic methods. These results, along with simulations of protein evolution, suggest a model for the evolution of interacting protein families in which interaction partners are duplicated in coupled processes. Using these methods, it is possible to successfully find protein interaction specificities, as demonstrated for >18 protein families.

Bioinformatics in the post-sequence era

In the past decade, bioinformatics has become an integral part of research and development in the biomedical sciences. Bioinformatics now has an essential role both in deciphering genomic, transcriptomic and proteomic data generated by high-throughput experimental technologies and in organizing information gathered from traditional biology. Sequence-based methods of analyzing individual genes or proteins have been elaborated and expanded, and methods have been developed for analyzing large numbers of genes or proteins simultaneously, such as in the identification of clusters of related genes and networks of interacting proteins. With the complete genome sequences for an increasing number of organisms at hand, bioinformatics is beginning to provide both conceptual bases and practical methods for detecting systemic functional behaviors of the cell and the organism.

STRING: a database of predicted functional associations between proteins

Functional links between proteins can often be inferred from genomic associations between the genes that encode them: groups of genes that are required for the same function tend to show similar species coverage, are often located in close proximity on the genome (in prokaryotes), and tend to be involved in gene-fusion events. The database STRING is a precomputed global resource for the exploration and analysis of these associations. Since the three types of evidence differ conceptually, and the number of predicted interactions is very large, it is essential to be able to assess and compare the significance of individual predictions. Thus, STRING contains a unique scoring-framework based on benchmarks of the different types of associations against a common reference set, integrated in a single confidence score per prediction. The graphical representation of the network of inferred, weighted protein interactions provides a high-level view of functional linkage, facilitating the analysis of modularity in biological processes. STRING is updated continuously, and currently contains 261 033 orthologs in 89 fully sequenced genomes. The database predicts functional interactions at an expected level of accuracy of at least 80% for more than half of the genes; it is online at http://www.bork.embl-heidelberg.de/STRING/.

Cyanobacterial signature genes

A comparison of 8 cyanobacterial genomes reveals that there are 181 shared genes that do not have obvious orthologs in other bacteria. These signature genes define aspects of the genotype that are uniquely cyanobacterial. Approximately 25% of these genes have been associated with some function. These signature genes may or may not be involved in photosynthesis but likely they will be in many cases. In addition, several examples of widely conserved gene order involving two or more signature genes were observed. This suggests there may be regulatory processes that have been preserved throughout the long history of the cyanobacterial phenotype. The results presented here will be especially useful because they identify which of the many genes of unassigned function are likely to be of the greatest interest.

Detection of novel members, structure-function analysis and evolutionary classification of the 2H phosphoesterase superfamily

2',3' Cyclic nucleotide phosphodiesterases are enzymes that catalyze at least two distinct steps in the splicing of tRNA introns in eukaryotes. Recently, the biochemistry and structure of these enzymes, from yeast and the plant Arabidopsis thaliana, have been extensively studied. They were found to share a common active site, characterized by two conserved histidines, with the bacterial tRNA-ligating enzyme LigT and the vertebrate myelin-associated 2',3' phosphodiesterases. Using sensitive sequence profile analysis methods, we show that these enzymes define a large superfamily of predicted phosphoesterases with two conserved histidines (hence 2H phosphoesterase superfamily). We identify several new families of 2H phosphoesterases and present a complete evolutionary classification of this superfamily. We also carry out a structure- function analysis of these proteins and present evidence for diverse interactions for different families, within this superfamily, with RNA substrates and protein partners. In particular, we show that eukaryotes contain two ancient families of these proteins that might be involved in RNA processing, transcriptional co-activation and post-transcriptional gene silencing. Another eukaryotic family restricted to vertebrates and insects is combined with UBA and SH3 domains suggesting a role in signal transduction. We detect these phosphoesterase modules in polyproteins of certain retroviruses, rotaviruses and coronaviruses, where they could function in capping and processing of viral RNAs. Furthermore, we present evidence for multiple families of 2H phosphoesterases in bacteria, which might be involved in the processing of small molecules with the 2',3' cyclic phosphoester linkages. The evolutionary analysis suggests that the 2H domain emerged through a duplication of a simple structural unit containing a single catalytic histidine prior to the last common ancestor of all life forms. Initially, this domain appears to have been involved in RNA processing and it appears to have been recruited to perform various other functions in later stages of evolution.

The catalytic domains of thiamine triphosphatase and CyaB-like adenylyl cyclase define a novel superfamily of domains that bind organic phosphates

BACKGROUND

The CyaB protein from Aeromonas hydrophila has been shown to possess adenylyl cyclase activity. While orthologs of this enzyme have been found in some bacteria and archaea, it shows no detectable relationship to the classical nucleotide cyclases. Furthermore, the actual biological functions of these proteins are not clearly understood because they are also present in organisms in which there is no evidence for cyclic nucleotide signaling.

RESULTS

We show that the CyaB like adenylyl cyclase and the mammalian thiamine triphosphatases define a novel superfamily of catalytic domains called the CYTH domain that is present in all three superkingdoms of life. Using multiple alignments and secondary structure predictions, we define the catalytic core of these enzymes to contain a novel alpha+beta scaffold with 6 conserved acidic residues and 4 basic residues. Using contextual information obtained from the analysis of gene neighborhoods and domain fusions, we predict that members of this superfamily may play a central role in the interface between nucleotide and polyphosphate metabolism. Additionally, based on contextual information, we identify a novel domain (called CHAD) that is predicted to functionally interact with the CYTH domain-containing enzymes in bacteria and archaea. The CHAD is predicted to be an alpha helical domain, and contains conserved histidines that may be critical for its function.

CONCLUSIONS

The phyletic distribution of the CYTH domain suggests that it is an ancient enzymatic domain that was present in the Last Universal Common Ancestor and was involved in nucleotide or organic phosphate metabolism. Based on the conservation of catalytic residues, we predict that CYTH domains are likely to chelate two divalent cations, and exhibit a reaction mechanism that is dependent on two metal ions, analogous to nucleotide cyclases, polymerases and certain phosphoesterases. Our analysis also suggests that the experimentally characterized members of this superfamily, namely adenylyl cyclase and thiamine triphosphatase, are secondary derivatives of proteins that performed an ancient role in polyphosphate and nucleotide metabolism.

Structural and nucleotide-binding properties of YajQ and YnaF, two Escherichia coli proteins of unknown function

Structural genomics is a new approach in functional assignment of proteins identified via whole-genome sequencing programs. Its rationale is that nonhomologous proteins performing similar or related biological functions might have similar tertiary structure. We used dye pseudoaffinity chromatography, two-dimensional gel electrophoresis, and mass spectrometry to identify two novel Escherichia coli nucleotide-binding proteins, YnaF and YajQ. YnaF exhibited significant sequence identity with MJ0577, an ATP-binding protein from a hyperthermophile (Methanococcus jannaschii), and with UspA, a protein from Haemophilus influenzae that belongs to the Universal Stress Protein family. YnaF conserves the ATP-binding site and the dimeric structure observed in the crystal of MJ0577. The protein YajQ, present in many bacterial genomes, is missing in eukaryotes. In the absence of significant similarities of YajQ to any solved structure, we determined its structural and ligand-binding properties by NMR and isothermal titration calorimetry. We demonstrate that YajQ is composed of two domains, each centered on a beta-sheet, that are connected by two helical segments. NMR studies, corroborated with local sequence conservation among YajQ homologs in various bacteria, indicate that one of the beta-sheets is mostly involved in biological activity.

Prediction, assessment and validation of protein interaction maps in bacteria

High-throughput proteomics technologies, especially the yeast two-hybrid system, produce large volumes of protein-protein interaction data organized in networks. The complete sequencing of many genomes raises questions about the extent to which such networks can be transferred between organisms. We attempted to answer this question using the experimentally derived Helicobacter pylori interaction map and the recently described interacting domain profile pair (IDPP) method to predict a virtual map for Escherichia coli. The extensive literature concerning E.coli was used to assess all predicted interactions and to validate the IDPP method, which clusters protein domains by sequence and connectivity similarities. The IDPP method has a much better heuristic value than methods solely based on protein homology. The IDPP method was further applied to Campylobacter jejuni to generate a virtual interaction map. An in-depth comparison of the chemotaxis pathways predicted in E.coli and C.jejuni led to the proposition of new functional assignments. Finally, the prediction of protein-protein interaction maps across organisms enabled us to validate some of the interactions on the original experimental map.

Advances in proteomic technologies

Proteomics is a rapidly emerging set of key technologies that are being used to identify proteins and map their interactions in a cellular context. With the sequencing of the human genome, the scope of proteomics has shifted from protein identification and characterization to include protein structure, function and protein-protein interactions. Technologies used in proteomic research include two-dimensional gel electrophoresis, mass spectrometry, yeast two-hybrids screens, and computational prediction programs. While some of these technologies have been in use for a long time, they are currently being applied to study physiology and cellular processes in high-throughput formats. It is the high-throughput approach that defines and characterizes modern proteomics. In this review, we discuss the current status of these experimental and computational technologies relevant to the three major aspects of proteomics-characterization of proteomes, identification of proteins, and determination of protein function. We also briefly discuss the development of new proteomic technologies that are based on recent advances in analytical and biochemical techniques, engineering, microfabrication, and computational prowess. The integration of these advances with established technologies is invaluable for the drive toward a comprehensive understanding of protein structure and function in the cellular milieu.

Conservation of gene co-regulation in prokaryotes and eukaryotes

Genes that are part of the same operon in prokaryotes, or have the same expression pattern in eukaryotes, are transcriptionally co-regulated. If genes are consistently co-regulated across distantly related organisms, the genes have closely associated functions. It has been shown previously that such genes have a strong tendency to belong to the same protein complex in prokaryotes, and we show by an analysis of the sequences and their expression in the yeast Saccharomyces cerevisiae and the worm Caenorhabditis elegans that this is also true for eukaryotes. Our analysis reveals that the number of conserved co-regulated genes is small in eukaryotes, as has been shown previously in prokaryotes, indicating that there are extensive variations in the gene regulatory network across organisms.

Phylogenetic analysis and gene functional predictions: phylogenomics in action

Making accurate functional predictions for genes is a key step in this era of high throughput gene and genome sequencing. While most functional prediction methods are comparative in nature, many do not take advantage of the power that an evolutionary perspective provides to any comparative biology analysis. Here we review how evolutionary analysis can greatly benefit both homology-based and non-homology-based functional prediction methods. Examples that are discussed include phylogenetic determination of orthology, the use of character state reconstruction analysis of gene function, and evolutionary analysis of rates and patterns of gene evolution.

Computational methods for the prediction of protein interactions

Establishing protein interaction networks is crucial for understanding cellular operations. Detailed knowledge of the 'interactome', the full network of protein-protein interactions, in model cellular systems should provide new insights into the structure and properties of these systems. Parallel to the first massive application of experimental techniques to the determination of protein interaction networks and protein complexes, the first computational methods, based on sequence and genomic information, have emerged.

Comparative assessment of large-scale data sets of protein-protein interactions

Comprehensive protein protein interaction maps promise to reveal many aspects of the complex regulatory network underlying cellular function. Recently, large-scale approaches have predicted many new protein interactions in yeast. To measure their accuracy and potential as well as to identify biases, strengths and weaknesses, we compare the methods with each other and with a reference set of previously reported protein interactions.

Connected gene neighborhoods in prokaryotic genomes

A computational method was developed for delineating connected gene neighborhoods in bacterial and archaeal genomes. These gene neighborhoods are not typically present, in their entirety, in any single genome, but are held together by overlapping, partially conserved gene arrays. The procedure was applied to comparing the orders of orthologous genes, which were extracted from the database of Clusters of Orthologous Groups of proteins (COGs), in 31 prokaryotic genomes and resulted in the identification of 188 clusters of gene arrays, which included 1001 of 2890 COGs. These clusters were projected onto actual genomes to produce extended neighborhoods including additional genes, which are adjacent to the genes from the clusters and are transcribed in the same direction, which resulted in a total of 2387 COGs being included in the neighborhoods. Most of the neighborhoods consist predominantly of genes united by a coherent functional theme, but also include a minority of genes without an obvious functional connection to the main theme. We hypothesize that although some of the latter genes might have unsuspected roles, others are maintained within gene arrays because of the advantage of expression at a level that is typical of the given neighborhood. We designate this phenomenon 'genomic hitchhiking'. The largest neighborhood includes 79 genes (COGs) and consists of overlapping, rearranged ribosomal protein superoperons; apparent genome hitchhiking is particularly typical of this neighborhood and other neighborhoods that consist of genes coding for translation machinery components. Several neighborhoods involve previously undetected connections between genes, allowing new functional predictions. Gene neighborhoods appear to evolve via complex rearrangement, with different combinations of genes from a neighborhood fixed in different lineages.

Computational method to assign microbial genes to pathways

We present techniques that mine fully sequenced microbial genomes for functional relationships between genes. We show that genes related by one of four techniques are more likely to belong to the same cellular pathways. Furthermore, we demonstrate that the pathway of an uncharacterized gene may be inferred from those of its functionally related partners. Therefore, we are now able to assign most of the genes within bacteria to cellular pathways.

Protein interaction verification and functional annotation by integrated analysis of genome-scale data

Assays capable of determining the properties of thousands of genes in parallel present challenges with regard to accurate data processing and functional annotation. Collections of microarray expression data are applied here to assess the quality of different high-throughput protein interaction data sets. Significant differences are found. Confidence in 973 out of 5342 putative two-hybrid interactions from S. cerevisiae is increased. Besides verification, integration of expression and interaction data is employed to provide functional annotation for over 300 previously uncharacterized genes. The robustness of these approaches is demonstrated by experiments that test the in silico predictions made. This study shows how integration improves the utility of different types of functional genomic data and how well this contributes to functional annotation.

The identification of functional modules from the genomic association of genes

By combining the pairwise interactions between proteins, as predicted by the conserved co-occurrence of their genes in operons, we obtain protein interaction networks. Here we study the properties of such networks to identify functional modules: sets of proteins that together are involved in a biological process. The complete network contains 3,033 orthologous groups of proteins in 38 genomes. It consists of one giant component, containing 1,611 orthologous groups, and of 516 small disjointed clusters that, on average, contain only 2.7 orthologous groups. These small clusters have a homogeneous functional composition and thus represent functional modules in themselves. Analysis of the giant component reveals that it is a scale-free, small-world network with a high degree of local clustering (C = 0.6). It consists of locally highly connected subclusters that are connected to each other by linker proteins. The linker proteins tend to have multiple functions, or are involved in multiple processes and have an above average probability of being essential. By splitting up the giant component at these linker proteins, we identify 265 subclusters that tend to have a homogeneous functional composition. The rare functional inhomogeneities in our subclusters reflect the mixing of different types of (molecular) functions in a single cellular process, exemplified by subclusters containing both metabolic enzymes as well as the transcription factors that regulate them. Comparative genome analysis, thus, allows identification of a level of functional interaction between that of pairwise interactions, and of the complete genome.

Classification and evolutionary history of the single-strand annealing proteins, RecT, Redbeta, ERF and RAD52

BACKGROUND

The DNA single-strand annealing proteins (SSAPs), such as RecT, Redbeta, ERF and Rad52, function in RecA-dependent and RecA-independent DNA recombination pathways. Recently, they have been shown to form similar helical quaternary superstructures. However, despite the functional similarities between these diverse SSAPs, their actual evolutionary affinities are poorly understood.

RESULTS

Using sensitive computational sequence analysis, we show that the RecT and Redbeta proteins, along with several other bacterial proteins, form a distinct superfamily. The ERF and Rad52 families show no direct evolutionary relationship to these proteins and define novel superfamilies of their own. We identify several previously unknown members of each of these superfamilies and also report, for the first time, bacterial and viral homologs of Rad52. Additionally, we predict the presence of aberrant HhH modules in RAD52 that are likely to be involved in DNA-binding. Using the contextual information obtained from the analysis of gene neighborhoods, we provide evidence of the interaction of the bacterial members of each of these SSAP superfamilies with a similar set of DNA repair/recombination protein. These include different nucleases or Holliday junction resolvases, the ABC ATPase SbcC and the single-strand-binding protein. We also present evidence of independent assembly of some of the predicted operons encoding SSAPs and in situ displacement of functionally similar genes.

CONCLUSIONS

There are three evolutionarily distinct superfamilies of SSAPs, namely the RecT/Redbeta, ERF, and RAD52, that have different sequence conservation patterns and predicted folds. All these SSAPs appear to be primarily of bacteriophage origin and have been acquired by numerous phylogenetically distant cellular genomes. They generally occur in predicted operons encoding one or more of a set of conserved DNA recombination proteins that appear to be the principal functional partners of the SSAPs.

Deciphering protein complexes and protein interaction networks by tandem affinity purification and mass spectrometry: analytical perspective

We employed a combination of tandem affinity purification and mass spectrometry for deciphering protein complexes and the protein interaction network in budding yeast. 53 genes were epitope-tagged, and their interaction partners were isolated by two-step immunoaffinity chromatography from whole cell lysates. 38 baits pulled down a total of 220 interaction partners, which are members of 19 functionally distinct protein complexes. We identified four proteins shared between complexes of different functionality thus charting segments of a protein interaction network. Concordance with the results of genome-wide two-hybrid screening was poor (14% of identified interactors overlapped) suggesting that the two approaches may provide complementary views on physical interactions within the proteome.

Genome and protein evolution in eukaryotes

The past year has seen the completion of the genome sequence of the flowering plant Arabidopsis thaliana and the initial sequence reports of the human genome. The availability of completely sequenced eukaryotic genomes from disparate phylogenetic lineages has opened the door to comparative analyses and a better understanding of the evolutionary processes shaping genomes. Complex many-to-many relationships between genes from different species appear to be the norm, suggesting that transfer of detailed functional annotation will not be straightforward. In addition to expansion and contraction of gene families, new genes evolve from recombination of pre-existing domains, although some domain families do appear to have evolved recently and to be specific to restricted phylogenetic lineages. The overall picture is of a huge diversity of gene content within eukaryotic genomes, reflecting different functional demands in different species.

A DNA repair system specific for thermophilic Archaea and bacteria predicted by genomic context analysis

During a systematic analysis of conserved gene context in prokaryotic genomes, a previously undetected, complex, partially conserved neighborhood consisting of more than 20 genes was discovered in most Archaea (with the exception of Thermoplasma acidophilum and Halobacterium NRC-1) and some bacteria, including the hyperthermophiles Thermotoga maritima and Aquifex aeolicus. The gene composition and gene order in this neighborhood vary greatly between species, but all versions have a stable, conserved core that consists of five genes. One of the core genes encodes a predicted DNA helicase, often fused to a predicted HD-superfamily hydrolase, and another encodes a RecB family exonuclease; three core genes remain uncharacterized, but one of these might encode a nuclease of a new family. Two more genes that belong to this neighborhood and are present in most of the genomes in which the neighborhood was detected encode, respectively, a predicted HD-superfamily hydrolase (possibly a nuclease) of a distinct family and a predicted, novel DNA polymerase. Another characteristic feature of this neighborhood is the expansion of a superfamily of paralogous, uncharacterized proteins, which are encoded by at least 20-30% of the genes in the neighborhood. The functional features of the proteins encoded in this neighborhood suggest that they comprise a previously undetected DNA repair system, which, to our knowledge, is the first repair system largely specific for thermophiles to be identified. This hypothetical repair system might be functionally analogous to the bacterial-eukaryotic system of translesion, mutagenic repair whose central components are DNA polymerases of the UmuC-DinB-Rad30-Rev1 superfamily, which typically are missing in thermophiles.

Functional organization of the yeast proteome by systematic analysis of protein complexes

Most cellular processes are carried out by multiprotein complexes. The identification and analysis of their components provides insight into how the ensemble of expressed proteins (proteome) is organized into functional units. We used tandem-affinity purification (TAP) and mass spectrometry in a large-scale approach to characterize multiprotein complexes in Saccharomyces cerevisiae. We processed 1,739 genes, including 1,143 human orthologues of relevance to human biology, and purified 589 protein assemblies. Bioinformatic analysis of these assemblies defined 232 distinct multiprotein complexes and proposed new cellular roles for 344 proteins, including 231 proteins with no previous functional annotation. Comparison of yeast and human complexes showed that conservation across species extends from single proteins to their molecular environment. Our analysis provides an outline of the eukaryotic proteome as a network of protein complexes at a level of organization beyond binary interactions. This higher-order map contains fundamental biological information and offers the context for a more reasoned and informed approach to drug discovery.

Predictome: a database of putative functional links between proteins

The current deluge of genomic sequences has spawned the creation of tools capable of making sense of the data. Computational and high-throughput experimental methods for generating links between proteins have recently been emerging. These methods effectively act as hypothesis machines, allowing researchers to screen large sets of data to detect interesting patterns that can then be studied in greater detail. Although the potential use of these putative links in predicting gene function has been demonstrated, a central repository for all such links for many genomes would maximize their usefulness. Here we present Predictome, a database of predicted links between the proteins of 44 genomes based on the implementation of three computational methods--chromosomal proximity, phylogenetic profiling and domain fusion--and large-scale experimental screenings of protein-protein interaction data. The combination of data from various predictive methods in one database allows for their comparison with each other, as well as visualization of their correlation with known pathway information. As a repository for such data, Predictome is an ongoing resource for the community, providing functional relationships among proteins as new genomic data emerges. Predictome is available at http://predictome.bu.edu.

Microbial computational genomics of gene regulation

Escherichia coli is a free-living bacterium that condensates a large legacy of knowledge as a result of years of experimental work in molecular biology. It represents a point of departure for analyses and comparisons with the ever-increasing number of finished microbial genomes. For years, we have been gathering knowledge from the literature on transcriptional regulation and operon organization in E. coli K-12, and organizing it in a relational database, RegulonDB. RegulonDB contains information of 20­25 % of the expected total sets of regulatory interactions at the level of transcription initiation. We have used this knowledge to generate computational methods to predict the missing sets in the genome of E. coli, focusing on prediction of promoters, regulatory sites, regulatory proteins, operons, and transcription units. These predictions constitute separate pieces of a single puzzle. By putting them all together, we shall be able to predict the complete set of regulatory interactions and transcription unit organization of E. coli. Orthologous genes in other genomes of known co-regulated sets of genes in E. coli, along with their corresponding predicted operons, and their predicted transcriptional regulators, shall permit the extension of the previous goal to many more microbial genomes.

The society of genes: networks of functional links between genes from comparative genomics

BACKGROUND

Comparative genomics provides at least three methods beyond traditional sequence similarity for identifying functional links between genes: the examination of common phylogenetic distributions, the analysis of conserved proximity along the chromosomes of multiple genomes, and observations of fusions of genes into a multidomain gene in another organism. We have previously generated the links according to each of these methods individually for 43 known microbial genomes. Here we combine these results to construct networks of functional associations.

RESULTS

We show that the functional networks obtained by applying these methods have different topologies and that the information they provide is largely additive. In particular, the combined networks of functional links contain an average of 57% of an organism's complete genetic complement, uncover substantial portions of known pathways, and suggest the function of previously unannotated genes. In addition, the combined networks are qualitatively different from the networks obtained using individual methods. They have a dominant cluster that contains approximately 80%-90% of the genes, independent of genome size, and the dominant clusters show the small world behavior expected of a biological system, with global connectivity that is nearly random, and local properties that are highly ordered.

CONCLUSIONS

When the information on functional linkage provided by three emerging computational methods is combined, the integrated network uncovers large numbers of conserved pathways and identifies clusters of functionally related genes. It therefore shows considerable utility and promise as a tool for understanding genomic structure, and for guiding high throughput experimental investigations.

The past, present and future of genome-wide re-annotation

Annotation, the process by which structural or functional information is inferred for genes or proteins, is crucial for obtaining value from genome sequences. We define the process of annotating a previously annotated genome sequence as 're-annotation', and examine the strengths and weaknesses of current manual and automatic genome-wide re-annotation approaches.

Recent advances in computational genomics

In the post-genomic era, the new discipline of functional genomics is now facing the challenge of associating a function (as well as estimating its relevance to industrial applications) to about 100,000 microbial, plant or animal genes of known sequence but unknown function. Besides the design of databases, computational methods are increasingly becoming intimately linked with the various experimental approaches. Consequently, bioinformatics is rapidly evolving into independent fields addressing the specific problems of interpreting i) genomic sequences, ii) protein sequences and 3D-structures, as well as iii) transcriptome and macromolecular interaction data. It is thus increasingly difficult for the biologist to choose the computational approaches that perform best in these various areas. This paper attempts to review the most useful developments of the last 2 years.

Similarity of phylogenetic trees as indicator of protein-protein interaction

Deciphering the network of protein interactions that underlines cellular operations has become one of the main tasks of proteomics and computational biology. Recently, a set of bioinformatics approaches has emerged for the prediction of possible interactions by combining sequence and genomic information. Even though the initial results are very promising, the current methods are still far from perfect. We propose here a new way of discovering possible protein-protein interactions based on the comparison of the evolutionary distances between the sequences of the associated protein families, an idea based on previous observations of correspondence between the phylogenetic trees of associated proteins in systems such as ligands and receptors. Here, we extend the approach to different test sets, including the statistical evaluation of their capacity to predict protein interactions. To demonstrate the possibilities of the system to perform large-scale predictions of interactions, we present the application to a collection of more than 67 000 pairs of E.coli proteins, of which 2742 are predicted to correspond to interacting proteins.

Modularity in the gain and loss of genes: applications for function prediction

Genes that are clustered on multiple genomes and are likely to functionally interact tend to be gained or lost together during genome evolution. Here, we demonstrate that exceptions to this pattern indicate relatively distant functional interactions between the encoded proteins. Hence, this can be used to divide predicted clusters of functionally interacting proteins into sub-clusters, and as such, to refine the prediction of their function and functional interactions.

SNAPping up functionally related genes based on context information: a colinearity-free approach

We describe a computational approach for finding genes that are functionally related but do not possess any noticeable sequence similarity. Our method, which we call SNAP (similarity-neighborhood approach), reveals the conservation of gene order on bacterial chromosomes based on both cross-genome comparison and context information. The novel feature of this method is that it does not rely on detection of conserved colinear gene strings. Instead, we introduce the notion of a similarity-neighborhood graph (SN-graph), which is constructed from the chains of similarity and neighborhood relationships between orthologous genes in different genomes and adjacent genes in the same genome, respectively. An SN-cycle is defined as a closed path on the SN-graph and is postulated to preferentially join functionally related gene products that participate in the same biochemical or regulatory process. We demonstrate the substantial non-randomness and functional significance of SN-cycles derived from real genome data and estimate the prediction accuracy of SNAP in assigning broad function to uncharacterized proteins. Examples of practical application of SNAP for improving the quality of genome annotation are described.

Inversions and the dynamics of eukaryotic gene order

Comparisons of the gene order in closely related genomes reveal a major role for inversions in the genome shuffling process. In contrast to prokaryotes, where the inversions are predominantly large, half of the inversions between Saccharomyces cerevisiae and Candida albicans appear to be small, often encompassing only a single gene. Overall the genome rearrangement rate appears higher in eukaryotes than in prokaryotes, and the current genome data do not indicate that functional constraints on the co-expression of neighboring genes have a large role in conserving eukaryotic gene order. Nevertheless, qualitatively interesting examples of conservation of gene order in eukaryotes can be observed.

Genes linked by fusion events are generally of the same functional category: a systematic analysis of 30 microbial genomes

Recent work in computational genomics has shown that a functional association between two genes can be derived from the existence of a fusion of the two as one continuous sequence in another genome. For each of 30 completely sequenced microbial genomes, we established all such fusion links among its genes and determined the distribution of links within and among 15 broad functional categories. We found that 72% of all fusion links related genes of the same functional category. A comparison of the distribution of links to simulations on the basis of a random model further confirmed the significance of intracategory fusion links. Where a gene of annotated function is linked to an unclassified gene, the fusion link suggests that the two genes belong to the same functional category. The predictions based on fusion links are shown here for Methanobacterium thermoautotrophicum, and another 661 predictions are available at http://fusion.bu.edu.

Advances in sequence analysis

In its early days, the entire field of computational biology revolved almost entirely around biological sequence analysis. Over the past few years, however, a number of new non-sequence-based areas of investigation have become mainstream, from the analysis of gene expression data from microarrays, to whole-genome association discovery, and to the reverse engineering of gene regulatory pathways. Nonetheless, with the completion of private and public efforts to map the human genome, as well as those of other organisms, sequence data continue to be a veritable mother lode of valuable biological information that can be mined in a variety of contexts. Furthermore, the integration of sequence data with a variety of alternative information is providing valuable and fundamentally new insight into biological processes, as well as an array of new computational methodologies for the analysis of biological data.

Determination of protein function, evolution and interactions by structural genomics

The genome sequencing projects and knowledge of the entire protein repertoires of many organisms have prompted new procedures and techniques for the large-scale determination of protein structure, function and interactions. Recently, new work has been carried out on the determination of the function and evolutionary relationships of proteins by experimental structural genomics, and the discovery of protein-protein interactions by computational structural genomics.

Mapping protein family interactions: intramolecular and intermolecular protein family interaction repertoires in the PDB and yeast

In the postgenomic era, one of the most interesting and important challenges is to understand protein interactions on a large scale. The physical interactions between protein domains are fundamental to the workings of a cell: in multi-domain polypeptide chains, in multi-subunit proteins and in transient complexes between proteins that also exist independently. To study the large-scale patterns and evolution of interactions between protein domains, we view interactions between protein domains in terms of the interactions between structural families of evolutionarily related domains. This allows us to classify 8151 interactions between individual domains in the Protein Data Bank and the yeast Saccharomyces cerevisiae in terms of 664 types of interactions, between protein families. At least 51 interactions do not occur in the Protein Data Bank and can only be derived from the yeast data. The map of interactions between protein families has the form of a scale-free network, meaning that most protein families only interact with one or two other families, while a few families are extremely versatile in their interactions and are connected to many families. We observe that almost half of all known families engage in interactions with domains from their own family. We also see that the repertoires of interactions of domains within and between polypeptide chains overlap mostly for two specific types of protein families: enzymes and same-family interactions. This suggests that different types of protein interaction repertoires exist for structural, functional and regulatory reasons.

The -10 region is a key promoter specificity determinant for the Bacillus subtilis extracytoplasmic-function sigma factors sigma(X) and sigma(W)

Transcriptional selectivity derives, in large part, from the sequence-specific DNA-binding properties of the sigma subunit of RNA polymerase. There are 17 sigma factors in Bacillus subtilis which, in general, recognize distinct sets of promoters. However, some sigma factors have overlapping promoter selectivity. We hypothesize that the overlap between the regulons activated by the sigma(X) and sigma(W) factors can be explained by overlapping specificity for the -10 region: sigma(X) recognizes -10 elements with the sequence CGAC and sigma(W) recognizes CGTA, while both can potentially recognize CGTC. To test this model, we mutated the sigma(X)-specific autoregulatory site (P(X)), containing the -10 element CGAC, to either CGTC or GCTA. Conversely, the sigma(W) autoregulatory site (P(W)) was altered from CGTA to CGTC or CGAC. Transcriptional analyses, both in vitro and in vivo, indicate that changes to the -10 element are sufficient to switch a promoter from the sigma(X) to the sigma(W) regulon or, conversely, from the sigma(W) to the sigma(X) regulon, but context effects clearly play an important role in determining promoter strength. It seems likely that these subtle differences in promoter selectivity derive from amino acid differences in conserved region 2 of sigma, which contacts the -10 element. However, we were unable to alter promoter selectivity by replacements of two candidate recognition residues in sigma(W).

Integration of genome data and protein structures: prediction of protein folds, protein interactions and "molecular phenotypes" of single nucleotide polymorphisms

With the massive amount of sequence and structural data being produced, new avenues emerge for exploiting the information therein for applications in several fields. Fold distributions can be mapped onto entire genomes to learn about the nature of the protein universe and many of the interactions between proteins can now be predicted solely on the basis of the genomic context of their genes. Furthermore, by utilising the new incoming data on single nucleotide polymorphisms by mapping them onto three-dimensional structures of proteins, problems concerning population, medical and evolutionary genetics can be addressed.

Computational methods for protein function analysis

Two recent advances have had the greatest impact on protein function analysis so far: the complete sequences of genomes and mRNA expression level profiles. The former has spurred the development of novel techniques to study protein function: phylogenetic profiles and gene clusters. The latter has introduced a method, not based on sequence homology, that enables one to group together functionally related genes.

Evolution of gene order conservation in prokaryotes

BACKGROUND

As more complete genomes are sequenced, conservation of gene order between different organisms is emerging as an informative property of the genomes. Conservation of gene order has been used for predicting function and functional interactions of proteins, as well as for studying the evolutionary relationships between genomes. The reasons for the maintenance of gene order are still not well understood, as the organization of the prokaryote genome into operons and lateral gene transfer cannot possibly account for all the instances of conservation found. Comprehensive studies of gene order are one way of elucidating the nature of these maintaining forces.

RESULTS

Gene order is extensively conserved between closely related species, but rapidly becomes less conserved among more distantly related organisms, probably in a cooperative fashion. This trend could be universal in prokaryotic genomes, as archaeal genomes are likely to behave similarly to bacterial genomes. Gene order conservation could therefore be used as a valid phylogenetic measure to study relationships between species. Even between very distant species, remnants of gene order conservation exist in the form of highly conserved clusters of genes. This suggests the existence of selective processes that maintain the organization of these regions. Because the clusters often span more than one operon, common regulation probably cannot be invoked as the cause of the maintenance of gene order.

CONCLUSIONS

Gene order conservation is a genomic measure that can be useful for studying relationships between prokaryotes and the evolutionary forces shaping their genomes. Gene organization is extensively conserved in some genomic regions, and further studies are needed to elucidate the reason for this conservation.

Evolution of prokaryotic gene order: genome rearrangements in closely related species

Conservation of gene order in prokaryotes has become important in predicting protein function because, over the evolutionary timescale, genomes are shuffled so that local gene-order conservation reflects the functional constraints within the protein. Here, we compare closely related genomes to identify the rate with which gene order is disrupted and to infer the genes involved in the genome rearrangement.