Automatic prediction of protein function

Burkhard Rost ^{1, 2, 3, *}, Jinfeng Liu ^{1, 3, 4}, Rajesh Nair ^{1, 5}, Kazimierz O. Wrzeszczynski ¹ and Yanay Ofran ^1,6

Abstract

Most methods annotating protein function utilise sequence homology to proteins of experimentally known function. Such a homology-based annotation transfer is problematic and limited in scope. Therefore, computational biologists have begun to develop ab initio methods that predict aspects of function, including sub-cellular localization, post-translational modifications, functional type, and protein-protein interactions. For the first two cases, the most accurate approaches rely on identifying short signalling motifs, while the most general methods utilise tools of artificial intelligence. An outstanding new method predicts classes of cellular function directly from sequence. Similarly, promising methods have been developed predicting protein-protein interaction partners at acceptable levels of accuracy for some pairs in entire proteomes. No matter how difficult the task, successes over the last few years have clearly paved the way for ab initio prediction of protein function.

Key words: genome analysis; protein function prediction; ab initio prediction; neural networks; multiple alignments; sequence analysis; sub-cellular localization; post-translational modifications; protein-protein interactions; bioinformatics

Abbreviations used

Introduction

'Protein function' is an operational concept. Proteins perform most important tasks in organisms, such as catalysis of biochemical reactions, transport of nutrients, recognition and transmission of signals. The plethora of aspects of the role of any particular protein is referred to as its 'function'. However, protein function is not a well-defined term, instead function is a complex phenomenon that is associated with many mutually overlapping levels: biochemical, cellular, organism mediated, developmental, and physiological. These overlapping levels are intertwined in complex ways, for example, protein kinases can be related to different cellular functions (such as cell cycle), and to a chemical function (transferase); the same kinase may also 'mis-function' thereby causing disease. Here, we use the generalised, operational notion that 'function is everything that happens to or through a protein'.

Sequence-structure and sequence-function gaps. The first entire genome (DNA) sequence of a free-living organism, Haemophilus influenzae, was published in 1995 [3] . Now, we know the genomes for over 100 organisms; for over 60, the data is publicly available and contributes about 250K protein sequences, i.e. one fourth of all known protein sequences [4, 5, 6, 7] . This explosion of sequence information has widened the gap between the number of protein sequences and the number of experimentally characterised proteins [8, 9, 10, 4] . Computational biology plays a central role in bridging this gap [11, 12, 13, 14, 15, 16] . For about 10-40% of all sequences, we can deduce structure from homology to known structures [17, 18, 19, 20, 4, 21, 22] . For more than 40-60% of all sequences from current genome projects, sequence homology suggests some aspects of function [23, 24, 25, 10] . However, a firm conclusion about function is not always clear, as predictions can be anything from cellular function (e.g. ATPase or ion channel) to details about cofactor binding sites (e.g. ATP binding sites).

Transfer of function based on sequence homology. Querying MEDLINE [26] with 'predict protein function' retrieves over 1000 papers from one year. The vast majority describes single-case studies in which experts combine many tools to guess aspects of function for a particular protein or protein family. Recently, James Whisstock and Arthur Lesk have focused on these aspects in an excellent, comprehensive review [27] . Here, we focus mainly on ab initio methods that predict function in absence of experimental annotations for homologues. We discuss some problems of homology transfer. We ignore methods that successfully identify functionally important residues from multiple alignments and/or protein structures [28, 29, 30, 31, 32, 33, 34, 35] . Arguably the most successful approaches combine tools from artificial intelligence (neural networks, Hidden Markov models, Support Vector machines) with evolutionary information contained in multiple alignments and aspects of protein structure.

Annotations and annotation transfer of protein function

Molecular biology databases with functional information. Information about protein sequences is stored in public databases such as SWISS-PROT and TrEMBL (Table 1). SWISS-PROT [2] is a curated database of protein sequences that also contains annotations about function added by a team of experts who extract this information primarily from journal publications [36] . TrEMBL [2] consists of entries that are derived from the translation of all coding sequences in the EMBL nucleotide sequence database [37] and are not in SWISS-PROT. Unlike SWISS-PROT records, those in TrEMBL are awaiting manual annotation. SWISS-PROT currently contains 122,564 sequence entries while the TrEMBL database contains over 821,014 sequence entries [2] . Many databases of protein families are derived from these original resources [12, 38, 39, 10, 40, 41, 42, 43, 44] . An issue that becomes increasingly important is the redundancy in original and derived databases. Such redundancy causes problems for database search techniques (alignments) and complicates estimates for the accuracy of annotation transfer [45] . A few resources address this problem by maintaining non-redundant sub-sets like KIND [46] , CluSTR [47] , or BLOCKS+ [48] databases, others provide tools to address the problem [49, 50, 51] .

Transfer of annotation through homology. Experimentally determining protein function continues to be a laborious task that may take enormous resources. For instance, more than a decade after its discovery, we still do not know the precise and entire functional role of the prion protein [52] . The automatic elucidation of protein function is therefore an appealing challenge [53, 38, 54, 27] . Bioinformatics exploits that two proteins with similar sequence often have similar function. Albeit, this concept appears straightforward, in practice, there are many hurdles to over-come. First, function is not well defined, hence it is very difficult to create controlled vocabularies [55, 56, 57] . Second, the precise values for thresholds of significant sequence similarity (T) are actually specific to particular aspects of function and have to be re-established for any given task [58, 59, 60, 61, 62, 56, 63, 45, 64, 65] ( Fig. 1 ). The problem of annotating function was illustrated immediately after the release of the first genome [3] : 148 amendments were published a few weeks after the original publication [66] . Similar amendments followed most papers presenting entirely sequenced genomes [67, 68, 69] . Several pitfalls in transferring annotations of function have been reported, e.g. inadequate knowledge of thresholds for 'significant sequence similarity', or using only the best database hit, or ignoring the domain organisation of proteins [70, 68, 71, 69, 72, 73, 74] . However, Eugene Koonin and colleagues turned the issue of annotation transfer errors around by collecting a few examples for which subsequent experiments showed that theoretical predictions had been more accurate than previous experiments [75] .

Problem 1: Multiple levels of description. Several groups and associations have ventured to introduce numerical schemata to define function. The first attempt was the introduction of Enzyme Classification numbers (EC [76] ); this classification uses four digits to classify enzymatic activity [56] . The MIPS database attempts extending this idea to a wider perspective of more proteins and more roles through their classification catalogue [77] . Another characterisation of protein function originates from the Gene Ontology (GO) consortium [55] . GO distinguishes three levels of protein function. (1) Molecular function: at the molecular level, the protein can, for example, catalyse a metabolic reaction, recognize or transmit a signal. (2) Biological process: a set of many co-operating proteins is responsible for achieving broad biological goals, for example, mitosis or purine metabolism, or signal transduction cascades (3) Cellular component: this category includes the structure of sub-cellular compartments, the localization of proteins, and macromolecular complexes. Examples include nucleus, telomere, and origin recognition complex. The sub-cellular localization of a protein is an essential attribute for this level. The totality of the physiological sub-systems of the cell and their interplay with various environmental stimuli determines properties of the phenotype, the morphology and physiology of the organism and its behaviour. Although not complete, GO constitutes the best set of definitions available today.

Problem 2: Functional information not machine-readable. Nearly all databases present the protein sequence in formats that are more or less straightforward to parse by computers. However, annotations are mostly written in free text using a rich biological vocabulary that often varies in different areas of research. Such annotations are primarily meant for the eyes of human experts, hence, they are not machine-readable [78] . Another problem that hampers automatic annotations is the quality of database annotations: only few database groups attempt a quality control of curated annotations [79] .

Establish accuracy of homology transfer. The reliability of transfer by homology depends on the particular feature of function/structure considered. In order to estimate the accuracy in transferring function given a particular threshold in sequence similarity, we have to complete the following three steps ( Fig. 1 sketch on top): (1) build data sets that have experimental annotations about the presence (true, e.g. all proteins experimentally known to be nuclear) and absence (false, e.g. all proteins experimentally known NOT to be nuclear) of a certain aspect of function. (2) In order to avoid estimates that are incorrectly biased by the distribution of today's experimental information [45] , a representative sub-set of proteins from the true data has to be extracted and aligned against all proteins in the true set (minus the representative sub-set) and false set. (3) For all alignments, we then have to count how many true and false we find at every given threshold for sequence similarity. How to measure sequence similarity? The most popular way is the level of pairwise sequence identity, i.e. the percentage of residues that are identical in an alignment of two proteins (R on R -> 1, R on K -> 0). The major problem with such a score in the context of automatic annotations is that it does not reflect the length of the alignment. For example, 11 identical residues may differ in both function and structure [80, 63, 45] . On the other hand, levels of pairwise sequence identity like 33% for alignments longer than 100 residues, or 22% for alignments longer than 250 residues imply similarity in structure [80] . This observation is used to compile an empirical threshold for significant sequence similarity as a function of alignment length [81, 82, 80] . We refer to this threshold as the HSSP-value; it is empirically chosen such that any pair of proteins A, B have similar structure if HSSP-value(A,B)>0. Another measure of sequence similarity is the expectation value built into the popular PSI-BLAST [83] alignment program. An important point to realise for BLAST and PSI-BLAST users is that the expectation value depends on the database used to search for related proteins. This implies the following. Assume we align proteins A and B by pairwise BLAST in two ways: (i) by searching with A against SWISS-PROT, and (ii) by searching with A against SWISS-PROT + PDB [1] . Even if the resulting alignments between A and B are identical, the expectation values may differ significantly due to the difference in size of the two databases. Unfortunately, the accuracy of transferring different aspects of function differs substantially ( Fig. 1 A-C illustrate this for the case of localization and enzymatic activity).

Fig. 1 : Accuracy and power of homology transfer. Thresholds for sequence similarity implying functional similarity depend on the particular aspect of function that we want to infer. For example, transfer of annotations for enzymatic activity (thick lines with open plus signs A-C) requires higher levels of similarity than transfer for annotations about sub-cellular localization (thin lines with diamonds A-C). Even at levels above 80 <<<10^-150, we still make mistakes in transferring EC numbers. For which fraction of entirely sequenced organisms can we transfer annotations? An upper limit is provided by the fraction of proteins that have sequence similarity to proteins from SWISS-PROT (E-G). If we want the transfer at error levels <10% (arrows A-C), maximally 60% of all proteins from 62 entirely sequenced organisms can be annotated (arrow F). This estimate provides in upper-limit since its two basic assumptions are likely over-optimistic: (1) not all SWISS-PROT proteins have reliable and detailed experimental annotations about function and (2) the accuracy of homology transfer for details of the functional role may be much lower for mechanisms that are less local than enzymatic activity.

Most annotations of function through homology transfer. In general, the inference of function is reliable only for very high levels of sequence similarity [60, 63, 45] . Although some perceive the estimate that 30% of the annotations may contain errors as particularly high [73] , our analysis of the sequence conservation of enzymatic activity suggested that this value may be rather over-optimistic [45] : if we want to transfer the full enzymatic activity with less than 30% errors, we have to require levels of >60% pairwise sequence identity and for errors below 10% >75 sequence identity ( Fig. 1 <<<10%), the HSSP-value must be >5 (Fig. 1>-48 (Fig. 1C). How many proteins from entire proteomes can we annotate at such a level of accuracy? We aligned all proteins from 62 entirely sequenced organisms [5] by PSI-BLAST (protocol described in detail elsewhere [84] , basically three iterations at 10^-10 thresholds) against a database containing all proteins from SWISS-PROT, TrEMBL, and PDB. Then we monitored at which level of sequence similarity we found the most similar protein in SWISS-PROT or PDB. If we assume that all proteins in SWISS-PROT and PDB have complete annotations about function, and that the accuracy of homology transfer for all aspects of function is similar to that for enzymatic activity, we simply have to mark the points of 90% accuracy ( Fig. 1 D-F arrows). Maximally - when using the HSSP-value for annotation - we can thus transfer annotation for about 60% of all proteins in the 62 proteomes. When we require less than 5% errors, the number drops to about 35% of all proteins, and when permitting 40% errors, it rises to above 70% of all proteins. The latter (70%) also constitutes the saturation: for about 25-30% of the proteins from proteomes we find no protein in SWISS-PROT or PDB even at thresholds of sequence similarity that are far too permissive to transfer annotations ( Fig. 1 ). These estimates are likely to constitute upper limits since the assumption that all proteins in SWISS-PROT and PDB are fully annotated experimentally is over-optimistic. Nevertheless, we currently know over 1.4 million protein sequences. Even if we pessimistically expect the ratio of reliable transfers to be only 10%, we still conclude that most annotations about function result from homology transfer. Furthermore, all these numbers ignore the capability of experts who can increase accuracy by combining many resources to annotate families [27] as realised, for instance, in Pfam-A [85] and TIGRFAMS [86] .

Sub-cellular localization

Basic concept. Bacterial cells generally consist of a single intracellular compartment surrounded by a plasma membrane. In contrast, eukaryotic cells are elaborately subdivided into functionally distinct, membrane-bounded compartments. Most eukaryotic proteins are encoded in the nuclear genome and synthesised in the cytosol, and many need to be further sorted into other sub-cellular compartments. The sorting signals that direct the movement of a protein through the cell, and thereby determine its eventual sub-cellular localization, are contained in its amino acid sequence [87, 88] . Proteins that remain in the cytosol do not have sorting signals. Many others, however, have specific sorting signals that direct their transport from the cytosol into the nucleus, the ER, mitochondria, plastids (in plants), or peroxisomes; sorting signals can also direct the transport of proteins from the ER to other destinations in the cell [89] . Proteins must be localised in the same sub-cellular compartment to cooperate towards a common physiological function. Thus, the native sub-cellular localization of a protein is one indicator of protein function. Aberrant sub-cellular localization of proteins has been observed in the cells of several diseases, such as cancer and AlzheimerÕs disease. Attempts to predict sub-cellular localization have become a central task in bioinformatics [78, 90] . The main methods are based on homology transfer, motif recognition, or the correlation between sequence features and localization ( Fig. 2 ).

Fig. 2 : Methods predicting sub-cellular localization. Four types of methods currently predict sub-cellular localization. (1) Transfer by homology: if we know that protein A is nuclear and we find protein B very similar in sequence to A, we can usually infer that B is also nuclear (Fig. 1 A-C, thin lines). (2) Identification by motifs: many proteins are shuttled between different compartments by carrier proteins that recognise short sequence motifs. Some of these motifs are consecutive in sequence (signal peptide, nuclear localization signal), others are discernible only from the folded structure (lysosomal retention signals). (3) Ab initio methods exploit the correlation between sequence features and localization. (4) Protein-protein interactions are another mechanism to shuttle proteins between compartments. Assume that two interacting proteins A and B are nuclear and that A has a nuclear localization signal that is recognised by an importin that carries A into the nucleus; B could be imported into the nucleus by binding to the complex A-importin. Recently, we combined the first three methods with another method that automatically recognises keywords in SWISS-PROT annotations [180] to annotate the localization of all eukaryotic proteins of known structure [97, 112] . The vast majority of all annotations resulted from homology transfer or lexical analysis (inner circle of top pie-chart). When applying the same methods to the entire proteome of C. elegans, this picture changed completely: about 87% of all proteins could only be handled by ab initio methods. Interestingly, 43% of all eukaryotic proteins of known structure appear to be extra-cellular (lower pie).

Prediction of localization through sequence motifs. One means for predicting localization is the identification of local sequence motifs such as signal peptides or nuclear localization signals (NLS). A number of neural network-based tools identify signal peptides that target proteins to the secretory pathway and the mitochondria [91, 92] . In a recent benchmark study [93] , these tools predicted signal peptide cleavage site at >80% accuracy. A particular problem for methods detecting N-terminal signals is that start codons are predicted with less than 70% accuracy by genome projects [94, 95] . We have collected a data set of experimental and potential NLS motifs that predict nuclear localization at 100% accuracy [96, 97] ; the downside of this look-up library is that it is not complete: most proteins have no known NLS. Either the motif remains to be discovered, or the protein is imported into the nucleus through binding to another protein that has an NLS. Overall, known and predicted sequence motifs enable annotating about 30% of the proteins in six eukaryotic proteomes [22, 5] .

Ab initio methods predict localization for all proteins at lower accuracy. Another approach to predicting localization has been suggested by the observation that the total amino acid composition correlates with the sub-cellular localization [98, 99, 100, 101, 102, 103] . This observation has led to the development of a variety of prediction methods based solely on composition [104, 94, 105, 106] . With the availability of large numbers of completely sequenced genomes, phylogenetic profiles have been employed to identify sub-cellular localization [107] . So far, this approach has been much less accurate in predicting localization than methods based solely on composition. Other methods have tried to integrate rules based on amino acid composition with databases of known signal sequences, e.g., PSORT II is a knowledge-based expert system that integrates the two kinds of information [108] . In particular, PSORT II uses other original prediction methods such as SignalP [109] , ChloroP [110] , and NNPSL [94] as input. Consequently, we may expect that PSORT II would improve if these original methods were improved. Drawid & Gerstein have proposed a Bayesian system based on a diverse range of 30 different features [111] . They applied their method to predicting localization of the full Saccharomyces cerevisiae proteome and provide estimates of the fraction of all yeast proteins found in different compartments. We have recently combined homology transfer, motifs-based and ab initio predictions to annotate all eukaryotic proteins of known structure ( Fig. 2 ). We learned that combining evolutionary and structural information yielded the most accurate predictions and that prediction methods appeared far less accurate when presented with fragments of the native protein sequence [112] .

Post-translational modifications

Basic concept. Over 325 structural and regulatory post-translational modifications in proteins are known today [113] ; prediction methods are currently constrained to a few most relevant of these. These tools typically employ highly conserved sequence motifs, more complex sequence patterns, or structural properties such as solvent accessibility. Prominent post-translational modifications targeted for prediction include: N-terminal signal peptide cleavage sites [114, 102, 91, 115, 116, 117, 93, 118] , proteolytic cleavage and more specifically proteasome cleavage sites [119, 120, 117, 121, 118, 122, 123, 124] , phosphorylation sites [125, 126] , lipid modification [127] and N- and O-glycosylations [128, 129] .

Archiving known sequence motifs and predicting modifications. PhosphoBase [126] , includes information on over 400 phosphorylated proteins, their phosphorylation sites and the specific kinase of action. These data were used to develop an ab initio method that predicts phosphorylation sites (NetPhos [125] ); predictions for serine, threonine, and tyrosine residues reach 69-96% sensitivity. The method uses information about sequence and structure. Given the difficulty in predicting structure around the phosphorylation site and the considerable variation of consensus sequences for kinase substrate specificity, the prediction of phosphorylation remains a difficult task. A similar neural network approach based on charged residues within glycosylation sites together with sequence context and surface accessibility is used to identify O-glycosylation modifications at about 80% accuracy [128] . The limited substrate specificity for both N-glycosylation and O-glycosylation currently limits progress [130] . Predictions of lipid modifications are currently restricted to glycosyl-phosphatidyl-inositol (GPI) anchors [127] . C-terminal motifs (omega-site) and physical properties of GPI-anchors enabled accurate predictions for the effects of mutations on known anchors. N-terminal motifs apparently allow for accurate predictions of N-myristoyltransferase (NMT) substrate sites [131] . Finally, a comprehensive study of proteasome digestion data yields a method that accurately predicts MHC class I ligand boundaries after proteasomal degradation: 65% of the cleavage sites and 85% of the non-cleavage sites appeared to be predicted correctly [124] .

Functional type

Basic concept. Monica Riley introduced the most widely used schema for classes of cellular function to annotate E. coli [132] . TIGR (The Institute for Genome Research) [3] and many other genome centres have adopted this schema with minor modifications. Transferring annotations of cellular function by homology has for long been almost the only field in which methods were developed. In fact, many researchers consider exclusively such methods when referring to the prediction of protein function. However, recently groups have begun developing methods that predict functional classes in the absence of experimental annotations.

Functional classes can be predicted from sequence. An interesting hybrid system uses inductive logic programming to predict functional classes with and without homology to experimentally annotated proteins [133] . While it is not clear how successful the system is in ab initio prediction, the levels of accuracy published on average appear promising. Genes located in a close neighbourhood on the genome may have some functional commonalities. While such neighbourhood relations sometimes enable predicting aspects such as classes of cellular function, the average signal is very weak, i.e. most often neighbours are not related in function [134, 135, 136] . The most recent breakthrough in the field of predicting protein function came through a collaboration of the groups from S¿ren Brunak (CBS Copenhagen) and Alfonso Valencia (CNB Madrid). Their ends are to predict cellular function from sequence alone. Their means are complex, elaborate, and hierarchical systems of neural networks [137] . A first group of networks is used to identify 'sequence features' (like protein length or amino acid composition) that optimally separate between any two types of functional classes. These basic predictions are then combined into a final prediction step, again through neural networks. The authors applied their method to annotating functional classes for all human proteins. For example the prion protein is predicted to belong to the 'transport and binding category' and to 'not have enzymatic activity'. This appears compatible with the observation that prion binds and transports copper while no catalytic activity has ever been observed [138] . Recently, the Brunak group have applied their new concepts to identifying novel enzymes in archae [139] and to predicting the functional type of al human proteins according to the GO classification [140] . The most impressive news from these ground-breaking methods is that aspects of function can be predicted without homology, i.e. for completely uncharacterised proteins.

Protein-protein interactions

Basic concept. Every protein has a biological function, yet most of the biological functions are carried out by groups of proteins interacting in complex networks. Interactions between proteins can be physical, i.e. by chemically binding each other or by binding together to a third substrate, or they can be functional, e.g. by controlling each others expression or by participating in the same biochemical pathway. To fully understand the molecular mechanism that underlies a certain biological function (or malfunction) we need to decipher the meticulous networks of protein interactions that underlie these mechanisms. Therefore, an extensive research effort is invested in both experimental and computational methods that unravel protein-protein interactions [141, 142, 143, 144, 145, 146, 147, 148, 149, 32, 150, 151, 152, 16, 153, 154, 155, 156, 157] . Particularly, many methods and databases attempt to draw complete maps of interactions for entire proteomes. Once it is known with which other proteins a newly discovered protein interacts, it will be easier to predict its function. Furthermore, it is hoped that these interaction maps will surrender the secrets of biological processes, and enhance the understanding of the underlying molecular mechanisms. A complete picture of all the proteins that are involved in a certain biological process would also break new grounds in drug development by identifying new targets for drugs.

Databases and data-mining techniques compile existing information. A vast amount of information about protein-protein interactions already exists in the literature. However, this information is scattered across millions of text pages of scientific publications. A few different enterprises are aimed at extracting this information from the literature [158, 159, 160, 161, 16, 162, 154, 155, 156] . The DIP database [162] is an example of a database that is dedicated to protein interactions. The curators of DIP manually survey the literature to find experimentally determined interactions. They also employ automatic techniques to obtain data from other databases. Other approaches to this problem use natural language processing algorithms, as well as other computational methods, to automatically extract interaction information from scientific papers [163, 158, 164, 160, 165, 161, 15, 16] . SUISEKI, a system for information extraction on interactions, [158] , is reported to successfully extract 70-80% of the interactions in a large corpus of scientific abstracts.

Computational approaches predict protein-protein interactions. Many groups attempt to develop computational methods that predict protein-protein interactions in-silico [136, 16] ( Fig. 3 ). Although not all proteins that come from neighbouring genes on the genome interact with one-another, gene location occasionally reveals true protein-protein interactions [166, 167] . Another approach screens genomes for sequences that appear as two different chains in one genome, and are fused to create a single protein-chain in another genome, which is evolutionarily younger [168, 169] . The assumption is that evolution fused these two proteins into a single one because they interact with one another. Another comparative method searches for pairs of proteins that always occur together in all known genomes, i.e., there is no genome in which only one of the two proteins occurs [170, 169] . These types of protein pairs are very likely to interact. Using these two methods, Eisenberg and his co-workers proposed thousands of protein pairs that may interact. However, there is no confirmed statistics regarding the reliability of the predictions of these methods. The assumption that interacting proteins co-evolve gave rise to other prediction methods. One specific implementation uses the observation that interacting proteins sometimes have phylogenetic trees that are mirror images of each other [171, 172, 173] . Alfonso Valencia and his group introduced an approach based on the assumption that interacting proteins evolve together, hence the mutations that occur in two interacting proteins along evolution should be correlated. First, they demonstrated that such correlated mutations could distinguish between correct and incorrect docking solutions [174] . Then they developed a method that predicts protein-protein interaction partners by analysing the correlation between the mutations in different proteins across different species [175] . Preliminary results indicate that the predictions of these methods have a low false negative rate. Sprinzak and Margalit [176] predicted protein-protein interactions based on a very simple concept: assume we experimentally know that proteins P1 and P2 interact, and that both contain particular motifs or domains M1 and M2, if we find the same motifs in proteins P1' and P2', we might suspect that P1' and P2' also interact. The method can be improved by adding filters that take into account entire networks by skewing the probability for the prediction of the interaction between P1' and P2' according to how often in an organism this combination is observed [177] . Aloy and Russell use alignments and 3D structures of known interactions to predict possible binding partners [178] . Given a 3D structure of a complex, they assess the likelihood that homologues are involved in similar interactions. An extension of this concept has been proposed by Skolnick and co-workers, who applied algorithms developed to detect more distant sequence relations (threading) to identify binding partners given an experimentally known 3D complex [179] . However, the major restriction of all these methods is that each of them is applicable only to a limited set of proteins. Another shortcoming of most methods is that they merely indicate whether a pair of proteins is in interaction, but they do not identify the interaction sites - a crucial piece of information for molecular research.

Fig. 3 : Methods predicting protein-protein interactions. (A) Genomic profiles [170, 169] : Entire genome are searched for the presence of each protein; the table represents the presence (1) or absence (0) of a certain protein in a given genome. If two proteins have an identical pattern, i.e. neither of them appears in any of the genomes without the other, the method assumes that they interact. (B) Rosetta stone [168, 169] : If two separate proteins 1 and 2 are in genome A, and the same two are merged as one single protein in genome B, the method assumes that protein 1 and 2 interact with one another. (C) Correlated mutations [174] : If a particular pair of interacting residues is important to maintain the interaction between protein 1 and 2, we might expect to find examples of mutations that are correlated between 1 and 2, e.g. a positive acid in protein 1 salt-bridging a negative acid in 2 might be mutated to a negative acid; this could be compensated by a reverse mutations of the negative into a positive acid in protein 2. A refined version of this basic idea is implemented in methods that predict protein-protein interaction sites and interaction pairs based on correlated mutations. (D) Sequence signatures [177, 176] : sequence motifs are marked in pairs of proteins that interact. The likelihood of interaction between every pair of motifs is used to predict interactions between the proteins carrying these motifs.

Conclusions

Homology transfer of function: use with extreme caution! No matter what definition of 'the function' or 'the fold' of a protein you may have, function clearly involves fewer residues directly. Therefore, random mutations are more likely to influence function than structure. In other words, when proteins diverge they will - on average - first loose their function than their fold. This makes it more difficult for computational biology to predict function than to predict structure. Despite this problem, the most accurate means of predicting function for particular proteins undoubtedly is the expert-controlled transfer of experimental annotations through homology [27] . However, in the context of automatic, non-expert, and/or proteome-wide searches homology transfer becomes problematic: On the one hand, we need very high levels of sequence similarity to reliably infer aspects of function through homology ( Fig. 1 A). On the other hand, the likelihood of finding close homologues is exponentially smaller than that of finding more diverged homologues ( Fig. 1 D). Thus, we find relatively few homologues of known function that allow transfer at very high accuracy. Many estimates for the functional coverage of entire genomes appear over-optimistically high by accepting very high error rates. An additional complication is that computational biology has to establish thresholds for accuracy of transferring function by homology for any aspect of function. Due to the lack of experimental data in general, and of machine-readable data in particular, such analyses have just begun over the last few years. What we can learn from the large-scale analyses for the few aspects is extreme caution in transferring function by homology!

Ab initio prediction of function: first successes scored. For some aspects of function like sub-cellular localization ab initio prediction methods have been pursued since a while. However, for most aspects of function the transfer by homology has long been the only means. Thus, overall the field of predicting function in silico is still at its infancy. Nevertheless, a few very promising methods have been proposed recently. Methods that predict sub-cellular localization are becoming increasingly accurate; methods that predict post-translational modifications increasingly useful and comprehensive - although the vast majority of post-translational modifications experimentally observed has not been covered, yet. The first breakthroughs have been made in predicting protein-protein interactions and cellular function from sequence. In combination, all those novel methods may aid the advance of molecular biology considerably. Given that the appetite of molecular and medical biologists for functional annotations grows with the exponential increase in the number of known proteomes, the recent advances in computational biology are falling on fertile ground.

Acknowledgements

Particular thanks to Arthur Lesk (MRC, Cambridge, England) for essential comments and for making his master review available to us before publication. Our work was supported by the grants 1-P50-GM62413-01 and RO1-GM63029-01 from the National Institute of Health (NIH), and the grant DBI-0131168 from the National Science Foundation (NSF). Last, not least, thanks to the GeneOntology team around Michael Ashburner (Cambridge, England) for their Gargantuan effort, to Amos Bairoch (SIB, Geneva), Rolf Apweiler (EBI, Hinxton), Phil Bourne (San Diego Univ.), and their crews for maintaining excellent databases and to all experimentalists who enable computational biology by making their data publicly available.

References