BACKGROUND
elucidating protein function is still one of the major challenges in the post-genomic era  <cit> .
even for the best-studied model organisms, such as yeast and fly, a substantial fraction of proteins is still uncharacterized  <cit> .
as high-throughput techniques increase the availability of completely sequenced organisms, annotation of protein function becomes more and more a bottleneck in the progress of biomolecular sciences and the gap between available sequence data and functionally characterized proteins is still widening  <cit> .
manual annotation, using, for instance, the scientific literature, and experimental identification of protein function remains a difficult, time- and cost-intensive task  <cit> .
reliable methods for assigning functions to uncharacterized proteins are required to support and supplement these methods.
there are various automatic approaches for the prediction of protein function.
these use, for instance, protein sequences and 3d-structures  <cit> , evolutionary relationships  <cit> , phylogenetic profiles  <cit> , domain structures  <cit> , or functional linkages  <cit> .
another important class of information for function prediction are protein-protein interactions .
ppis are a type of data that is close to the biological role of a protein within cells and therefore ideally suited to form the basis for function prediction methods  <cit> .
furthermore, more and more such data sets are becoming available .
these data sets may be used to identify functional modules within protein networks  <cit> , to find protein complexes  <cit> , or to determine evolutionary conserved processes  <cit> , all of which provide valuable clues to the function of a protein  <cit> .
the approaches that use ppi for function prediction can be classified into two main classes:
<dig>  link-based methods predict novel functions for a protein by transferring known functions from directly or indirectly interacting proteins.
this may be achieved by studying the set of neighbors  <cit> , by considering the position of the protein within its neighborhood  <cit> , or by looking at the position of the protein in the entire interaction network  <cit> .
<dig>  module-based methods assign functions to proteins by first computing clusters  within the protein network  <cit> .
based on the hypothesis that cellular functions are organized in a highly modular manner  <cit> , all members of a cluster are assigned annotations that are enriched within the module  <cit> .
both approaches have their benefits and their drawbacks.
ppi-based prediction methods provide a better coverage but are sensitive to the high level of false-positives  <cit>  and false negatives  <cit>  in current ppi data sets.
module-based methods are more robust to missing or wrong interactions, but are able to predict function only within dense regions of a species network disregarding, for instance, chain-like pathways.
this largely reduces their coverage  <cit> .
module-based methods have been shown to be less accurate than for example simple guilt-by-association approaches but their performance improves in networks with less functional coverage  <cit> .
furthermore, both methods in first place only work within a species, which disregards the wealth of information that might be available in evolutionary related other species .
this limitation can be removed by using annotations of homologous proteins.
however, purely homology-driven prediction strategies are rather imprecise  <cit> .
although prediction precision may be improved by using only orthology, the overall precision remains below that of most ppi-based methods  <cit> .
in this paper, we describe a novel algorithm for protein function prediction that combines link-based and module-based prediction with orthology, thus overcoming the respective limitations of each individual approach.
the key to our method is to analyze proteins within modules that are defined by evolutionary conserved processes.
to this end, we first compute ppis that are highly conserved within a given set of species.
these so-called interologs  <cit>  are assembled to highly conserved protein sub-networks.
for a given protein, we then predict functions of other proteins in the same ccs using both directly interacting proteins as well as orthology relationships.
we apply our function prediction strategy to different sets of species, ranging from species pairs to groups of up to four species.
we show that our approach reaches very high prediction precision, especially for three and four species.
especially due to the combination of different sources of evidence for functional similarity between proteins, our method is able to predict many functions even for uncharacterized or only weakly characterized proteins.
these functions are not reflected in the recall since these functions are novel, i.e., counted as fp in the comparison against a gold standard.
for instance, when combining the novel predictions from different species combinations, we suggest  <dig>  new functional annotations for  <dig>  human proteins that previously had only zero or one function annotated.
overall, our method produces  <dig>  novel annotations for human with an estimated precision of ~76% and  <dig>  for mouse with ~81% precision.
these numbers by far outreach that of comparable methods.
it is also remarkable that our predictions are rather specific, which is reflected in a mean go-depth of  <dig> for humans and  <dig> for mice.
to confirm our estimated precision values, we manually verified a number of predictions in the context of colon cancer.
specifically, we studied the gene products mlh <dig>  pms <dig> and ephb <dig>  which received  <dig>   <dig>  and  <dig> novel annotations through our method.
detailed literature analysis indicates that at least 73% of the novel functions actually are true predictions.
finally, we compare our approach against three other approaches, neighbor counting  <cit> , χ <dig>  <cit> , and fs-weighted averaging  <cit> .
we show that our ccs-based method performs significantly better than those methods in almost all settings we studied, especially in terms of precision.
methods
we devise an algorithm for predicting functional annotations of proteins using gene ontology   <cit>  terms.
our approach is based on comparison of interaction networks from various species and utilizes orthology relationships, conserved modules and local ppi neighborhoods.
it is divided into the  integration of ppi data from various databases,  detection of maximal conserved and connected subgraphs  using approximate cross-species network comparisons and  prediction of new annotations for proteins within functionally coherent ccs .
data
we use interaction data of the model organisms s. cerevisiae, d. melanogaster and c. elegans, and the mammals r. norvegicus, m. musculus and h. sapiens.
corresponding ppi data were obtained from the major public ppi databases dip  <cit> , intact  <cit> , bind  <cit> , mips-mppi  <cit> , hprd  <cit> , mint  <cit>  and biogrid  <cit> .
since the individual coverage and overlap between the data of these resources is comparably low  <cit> , we integrate ppi data from the different sources to generate comprehensive data sets for our study.
for data integration we map the interacting proteins from external or database specific identifiers to unique protein identifiers from uniprot and entrezgene  <cit>  to enable the combination of the different data sets to one comprehensive set of interaction data for each species.
from the combined data sets we generated comprehensive species-specific protein interaction networks.
besides the interaction data we utilize protein sequences and protein domain information  <cit>  from uniprotkb/swiss-prot  <cit> .
all proteins in the protein interaction network are associated with the respective information.
additionally, proteins are annotated with go annotations retrieved from uniprotkb/swiss-prot, entrezgene and species-specific databases, such as flybase  <cit> , mgd  <cit> , rgd  <cit> , sgd  <cit>  and wormbase  <cit>  .
note, when annotating proteins we consider all available go annotations except for annotations that are assigned without curatorial judgment .
moreover, we filter for go subontology root terms to exclude molecular function, biological process and cellular component.
the annotated species-specific protein interaction networks  provide the basis of our protein function prediction method.
ppi networks for each species are created by integrating ppi data from dip, bind, intact, biogrid, mips-mppi, mint and hprd.
proteins within the networks are additionally associated with sequences, protein domains and go annotations.
for each species the number of proteins and protein interactions as well as the median number of go terms per protein is specified.
network comparison
we compare protein interaction networks across different species to detect subgraphs that are evolutionary conserved and likely represent functional modules.
figure  <dig> depicts the strategy of our network comparison approach which involves  the identification of orthologous proteins and  the detection and assembly of interologs into ccs.
orthology is a strong indicator for functional conservation.
however, the presence of large protein families, typical for mammals and higher eukaryotes in general, makes it hard to distinguish between true orthologs, in-paralogs and paralogs  <cit> .
we determine orthology relationships among multiple species by applying orthomcl  <cit>  using default parameters.
previous work showed that orthomcl is able to discriminate between orthologs, in-paralogs and functionally unrelated paralogs at a balanced trade-off between specificity and sensitivity  <cit> .
for comparing protein networks across species, we consider all ortholog groups that comprise at least one protein of each species under consideration.
we then use an adaption of an algorithm for frequent subgraph discovery  <cit>  to assemble interologs into ccs.
our approach first identifies all interactions  that are conserved across the different species.
for identifying interologs we use two different definitions for interologs depending on the number of species that are involved.
when comparing only two species, we use the classical, strict definition considering each interaction as interolog that is present in both species.
when comparing more than two species, we consider each interaction as interolog that is present in more than 50% of the species networks .
out of the set of interologs, one interolog is chosen as subgraph seed and all interologs adjacent to this subgraph are added recursively.
if a subgraph can not be further extended we store this maximal and connected subgraph as ccs .
prediction of functional annotation
ccs are conserved subgraphs of interacting proteins and therefore a strong indicator for functional similarity of proteins within a ccs even across species.
however, not all detected ccs are good candidates for function prediction due to the noise and incompleteness within the existing ppi and annotation data sets.
therefore, we first filter for ccs that are too heterogeneous or simply too small to be used for function prediction.
we then use different methods for predicting functional annotations for all proteins in a ccs, namely transfer of annotations from other species along orthology relationships and transfer within species from all ppi neighbors.
in both cases, only proteins within the same ccs are considered.
finally, special care has to be taken for the processing of large ccs which, due to their sheer size, usually are functionally heterogeneous.
in the following, we give details for each of these steps.
filtering coherent ccs
we first test all detected ccs for functional coherence using a functional similarity measure proposed by couto et al.
<cit>  that is based on semantic similarity.
we compute, for each ccs, its average functional similarity within a species  and across the species .
the formal definitions of both similarity measures are provided in the additional file  <dig> .
we further only consider ccs which have  more than two proteins and  whose similarity score, either simortho or simneigh, exceeds a given threshold.
we applied three different thresholds  to study the performance of our method for different levels of functional coherence.
this scheme is applied separately for each subontology of go , biological process , cellular component ).
prediction using orthology relationships
for inferring protein function from orthology relationships within a ccs, we determine orthologous groups that differ significantly in their individual functional similarity from the similarity score of the ccs by computing the standardized z-score .
in groups with significant differences  we transfer all known protein annotations to poorly annotated or uncharacterized orthologs.
note that an orthologous protein group might consist of more than one protein per species .
although all proteins within such a group in theory should be functionally highly similar, this is, probably due to missing or wrong annotations, not always reflected in the data .
we define the consensus annotation of all proteins of one species in an orthologous group to be the set of all go terms that are associated to more than half of the annotated proteins of that species in that group.
when considering more than two species we combine the species-specific sets of consensus annotations and transfer them to the other proteins in the same group.
prediction using neighboring proteins
given a protein in a ccs, we decide for each go term annotated to any of its direct neighbors whether it also should be annotated to the protein itself.
let g be the set of terms annotated to at least one neighbor of a protein p, and let ng be the set of neighbors of p annotated with a term g ∈ g. we transfer g to p if there are more than f proteins in ng whose functional similarity to p is higher than a given threshold t. for functional similarity between proteins, we again use the method from couto et al.
<cit>  .
because this approach cannot predict functions for proteins without any annotation , we also consider the pairwise functional relation between interaction partners, assuming that a high functional similarity between indirectly linked partners should also hold for the protein itself.
again, if the pairwise similarity scores exceed the threshold t we predict common go annotations to the candidate protein.
combined prediction method
we combine the two different methods to predict protein functions within a ccs .
proteins that are only weakly and incompletely characterized or not annotated at all are candidates for our prediction approach.
for each candidate protein we infer novel protein function  within functionally coherent ccs by exploiting its  orthology relationship across other species as well as  the information shared by its neighboring proteins.
processing large ccs
comparing evolutionary close species  often results in very large ccs with up to several hundreds of proteins.
however, biological processes typically involve only between  <dig> and  <dig> proteins  <cit> .
consequently, large ccs often encompass various functions  which is reflected in a minor functional homogeneity.
our results confirm this fact, as large ccs always get low coherence scores .
to adequately treat such ccs, we split ccs with more than  <dig> proteins into smaller, overlapping sub-subgraphs.
sub-subgraphs are built by considering each protein of the ccs as seed of a new, smaller ccs.
subsequently, we add all direct neighbors of this seed to the new ccs .
subgraphs with less than three proteins are removed.
we then consider each of these subgraphs as an independent ccs.
performance evaluation
we use a leave-one-out cross-validation to estimate the expected precision and recall of function prediction using  only orthology within ccs,  only neighbors within ccs, and  the combination of both methods.
precision p and recall r are defined as:
p=tptp+fp
r=tptp+fn
where tp and fp denote true and false positives, respectively, and fn denotes false negatives.
for cross-validation we 'hide' selected annotations before applying our algorithm.
predicted terms are then compared to the held out annotations.
we count a go term as correctly predicted if the proposed term was an ancestor of the original term on the path to the root or the term itself .
for all methods involving ccs, we give recall values on the basis of all annotations of proteins within qualifying ccs.
we call this measure per-protein recall.
it must be distinguished from the traditional per-species recall  which is also used frequently, but which punishes all methods that first filter proteins.
when determining the per-protein recall  we consider only proteins p that are part of a ccs:
rpp=∑p ∈ ccstpp∑p ∈ ccs,
where tpp denotes the number of correctly predicted functions for a protein p in a ccs and  corresponds to the number of annotations that are originally associated with the protein p. to also give an idea of the per-species performance, we always complement precision and recall values with the coverage measure, which simply counts the total number of predictions.
keep in mind that, as always when comparing to an incomplete gold standard, cross-validation inherently considers any new annotations as false, although new annotations are the primary target of function prediction.
therefore, we also performed an extensive literature evaluation to judge the correctness of selected new annotations.
comparison to other methods
we compare our approach against a number of different techniques.
first, we use two baseline methods: the orthology baseline purely considers orthology ignoring structural network conservation.
we randomly select one third of the orthologous protein groups, remove annotations from one protein in the group and predict their functions using only its orthologs.
the link-based baseline takes only direct interaction partners into account, again independently of conservation of interactions.
for each species we randomly choose one third of the proteins from the corresponding interaction network and exploit their direct neighbors for deriving new functions.
we repeat this procedure  <dig> times for each baseline and compute average and standard deviation across all runs.
we also compare our results with three popular ppi-based function prediction methods.
the neighbor counting approach from schwikowski et al.
is a local prediction approach that derives new annotations for a protein based on the frequency of annotations within its direct interaction partners  <cit> .
the χ <dig> algorithm from hishigaki et al.
extended this idea by also considering the background frequency of a functional term  <cit> .
finally, the functional similarity weighted averaging method from chua et al., a weighted averaging method to predict the function of a protein based on its direct and indirect interaction partner  <cit> .
chua et al.
demonstrate in  <cit>  that the fs-weighted averaging significantly outperforms local and global network approaches, e.g.
methods that are based on markov random field or functional flow  <cit> .
for comparisons, we adapted a script provided by chua et al.
that implements these three methods .
to enable a valid direct comparison, we evaluate the three related predictions methods only on proteins that are involved in ccs.
the individual performance of each method on the entire data set is shown for completeness in the additional file  <dig>
RESULTS
we integrated ppi data for rat , mouse , human , fly , worm  and yeast  from several public databases to generate species-specific ppi networks .
we computed ccs for  <dig> combinations of two species,  <dig> comparison with three, and  <dig> with four species, and subjected them to our function prediction method.
the number of detected ccs for combinations of five and six species is too low for a systematic and detailed analysis .
in the following, we focus on four selected species combinations that cover different interactome sizes and evolutionary distances to discuss properties and results of our function prediction strategy.
complete results are given as additional file  <dig>  table s <dig> and additional file  <dig>  table s <dig>
network comparisons
we compared protein interaction networks across different species to identify evolutionary and functionally conserved subgraphs that are used as basis for function prediction.
conserved sub-networks are assembled by combining conserved interactions, called interologs, using different definitions of interologs depending on the number of species being compared.
for species pairs, we use the classical, strict definition: an interolog is an interaction present in both species.
we relax this demand when comparing more than two species to cater for evolutionary variation  <cit>  and for the incompleteness  <cit>  and noise within present ppi data sets  <cit> : an interolog then is defined as an interaction which is present in more than 50% of the species being compared.
we present a brief overview on the respective network comparison of rno-dme, rno-hsa-sce, hsa-dme-sce, hsa-dme-cel-sce and mmu-hsa-dme-cel .
table  <dig> summarizes the outcomes for the selected species combinations in terms of orthologous protein groups, identified interologs and assembled ccs.
as expected, the number of orthologous protein groups, interologs and identified ccs differs depending on the number of compared species, their evolutionary distance as well as their current interactome coverage.
comparison of fly and yeast results in  <dig> ccs  with at least three proteins.
for more than two species we use the relaxed interolog definition which generally results in a considerable higher number of ccs.
for instance, we identify  <dig> ccs for hsa-dme-sce of which  <dig> comprise more than two proteins.
these ccs are shown in additional file  <dig>  figure s <dig>  even combinations with four species result in a reasonable number of ccs, such as mmu-hsa-dme-cel producing  <dig> ccs with more than two proteins.
for each species combination the number of orthologous groups, interologs, ccs are presented as well as the size of the largest ccs.
note, we use the strict interolog definition for two species and the relaxed criterion for multiple species .
function prediction
we use orthology relationships, functionally conserved modules, and direct and indirect protein interactions for predicting functional annotations for proteins in a ccs by transferring annotations from other species along orthology relationships and within species from interaction partners.
we evaluated our approach in three ways.
first, we compared our combined strategy to baseline methods which disregard conservation in networks.
second, we compared it to the results obtained from using orthology and ppi neighborhood within ccs in isolation.
third, we performed a comparison to three recent function prediction methods from the literature.
we first show the performance of our two baseline methods, orthology and link-based, for function prediction.
precision for predictions based solely on orthology relationships varies between 3% and 11% .
recall is higher , but decreases steeply with the number of species being compared.
precision of the link-based baseline ranges from 3% to 17%.
contrary to the orthology baseline, recall is rather high, varying between 51% and 75% .
thus, the link-based baseline reaches a similar precision but higher recall than the orthology baseline.
both baselines yield very low precisions.
the orthology baseline indicates the challenges transferring function from ortholog templates.
although function tends to be conserved in orthologs, orthology does not guarantee conservation of function  <cit> .
when transferring function solely based on protein sequences, more sophisticated approaches, e.g.
using advanced statistical frameworks  <cit> , are needed to ensure high prediction quality.
the precision of the link-based baseline is lower than expected most likely through the strong impact of the quality of the interaction data.
however, precision and recall are similar to the results of the two local prediction approaches of schwikowski et al.
and hishigaki et al.
that are applied to our data .
across orthology relationships within ccs
we use orthology relationships underpinned by interologs to infer novel functions from multiple species.
considering only orthology relationships for transferring functions to proteins within ccs results in predictions with medium to high precision.
additional file  <dig>  table s <dig> shows precision and recall estimated using cross-validation for the selected examples.
precision reaches 88% to 97% for yeast proteins when comparing hsa-dme-sce and 67% to 85% for mouse proteins when comparing mmu-hsa-dme-sce.
precision values increase considerably with a higher coherence threshold for ccs, but this improvement comes at the cost of lower coverage.
particularly low numbers of predictions are obtained for comparisons involving species with low ppi coverage.
this is especially prominent for rno, where comparison of rno-hsa-sce result in only  <dig> predictions - but with a precision of 100%.
besides the coherence threshold, also the number of species being compared has a strong impact on performance.
higher average precisions are achieved when analyzing multiple species compared to species pairs.
for instance, the average precision for mmu-hsa-dme-sce is 79% at  <dig>  in comparison to dme-sce with 54% at  <dig>  and  <dig> % at  <dig> .
this shows that using more species implicitly selects functions that are conserved more strongly, which underlines the impact of evolutionary functional conservation for protein function prediction.
this fact also shows up when comparing to the orthology baseline : precision and per-protein recall using orthology within ccs are much higher, but the overall coverage is much lower.
this means that ccs strongly restrict the number of proteins for which predictions are made, but this restriction is done in a very sensible way removing mostly false positive predictions.
across neighborhood within ccs
additional file  <dig>  table s <dig> shows precision and recall for inferring functions only from interaction partners within ccs.
compared to predicting function based on orthology within ccs, precision is higher, while per-protein recall roughly stays the same.
at the same time, neighbor-based prediction has a considerable better coverage.
however, there are also species combinations in which this method performs worse.
precision again correlates with the functional coherence of ccs and with the number of compared species, but the impact is less pronounced.
especially the step from coherence threshold  <dig>  to  <dig>  mostly makes only a small difference.
compared to the link-based baseline , precision is much higher and coverage and per-protein recall decreases.
combining module, orthology and link-based ppi evidences
we hypothesized that the integration of orthology relationships, evolutionary conserved functional modules, and direct and indirect protein-protein interactions into a single prediction strategy will combine the strengths of the three individual methods.
selected results from this combined strategy are shown in table  <dig> .
as before, precision varies  depending on the species combination and the threshold for functional coherence of ccs.
best results are obtained for rno-hsa-sce at a threshold of  <dig> , with precision of 85%, 89% and 86%, respectively.
precision  and per-protein recall  are estimated for low , medium  and high  functional similarity/conservation thresholds.
as mentioned before, one of the major drawbacks of using only ccs orthology relationships is the low number of predictions due to the restriction to orthologous proteins with at least one known function .
in contrast to orthology-only, the combined approach creates many more predictions .
it generates hundreds or even thousands of predictions also for those cases where the orthology-only method could not predict any function.
comparing the combined method and ccs link-based only  shows an increase within the amount of predictions , although it is less steep than observed for orthology-only.
this increase has mostly only minor influence on precision and recall.
precision reaches similar levels and the recall increases slightly.
note, for few combinations the combined method yields the same results as link-based-only because no predictions could be inferred through orthology relationships.
overall, the impact of our combined approach is dominant, especially in terms of the number of predictions.
precision drops for some combinations compared to the single methods.
however, the decrease of precision does not indicate a lower prediction quality.
it rather indicates that the combined method derives many more novel predictions that can not be validated during cross-validation rather than successfully reproducing known function for well-characterized proteins .
precision is affected the least for the highest similarity threshold  fostering the most reliable precisions.
overlap between orthology- and link-based predictions within ccs
we combined orthology- and link-based function prediction within ccs to benefit from the strengths of both methods.
to study whether the predictions of the individual methods result in the same or complementary sets of predictions we determined the overlap of go terms predicted by either strategy.
for hsa-dme-sce, the respective numbers are shown as venn diagrams in additional file  <dig>  figure s <dig>  in general, the major fraction of unique predictions is derived from neighboring proteins.
the overlap between predictions is comparably small and decreases when increasing the similarity threshold.
this shows that both methods complement each other very well as they predict rather different sets of functions.
for hsa-dme-sce, the respective numbers are shown as venn diagrams in additional file  <dig>  figure s <dig>  in general, the major fraction of unique predictions is derived from neighboring proteins.
the overlap between predictions is comparably small and decreases when increasing the similarity threshold.
this shows that both methods complement each other very well as they predict rather different sets of functions.
this behavior is also observable when predictions are analyzed separately per species .
however, contrary to fly and yeast proteins  and s5), the amount of orthology and link-based predictions is quite similar for human proteins ), which can be explained by the much denser ppi data available for the two model organisms .
this observation clarifies that different species pro t differently from our method.
especially less characterized species, such as human, benefit strongly from the functional knowledge of model organisms.
overlap between predictions derived from different species combinations
not only does the neighbor-based method complement the orthology-based method, but also predictions derived from different species combinations are rather complementary.
table  <dig> shows the overlap between predictions for human proteins inferred from different species pairs.
the overlap is determined by dividing the number of overlapping predictions through the total number of predictions of a combination .
the overlap mostly is far below 50% and strongly depends on evolutionary distance between the species.
for example, the overlap between predictions derived from ccs with mouse and those derived from rat is much larger than that of the sets derived from mouse and, say, fly.
the same holds for combinations of three and four species .
moreover, the more species we combine the more we focus our prediction on evolutionary conserved functions, which becomes clear when studying predictions for highly conserved housekeeping functions .
the overlap is defined as the number of overlapping predictions divided by the total number of predictions .
each cell contains two different values - i/j - that specify the overlap based on the total number of predictions of the two combinations.
i presents the overlap between the non-human species from row i and column j and value j presents the overlap between non-human species from column j and row.
large ccs
large ccs naturally encompass various biological functions.
in consequence, their functional homogeneity is often too low which excludes the entire ccs from function prediction.
however, large ccs actually are strong indicators for conserved functions.
for instance, figure  <dig> shows the largest ccs from hsa-dme-cel-sce consisting of  <dig> proteins and  <dig> interologs with its different biological subprocesses.
it clearly contains several functionally highly conserved clusters, probably forming discrete protein complexes.
considering such a large ccs as a whole is insufficient.
therefore, we modify our approach for large ccs by breaking them up into sub-subgraphs .
the impact on precision and recall is shown in additional file  <dig>  table s <dig> , which should be compared with entries of table  <dig> .
as can be seen, processing large ccs creates many more predictions with mostly better precision.
for example, the number of predictions almost triples for hsa-dme-sce at a similar or even better precision.
when comparing split and non-split results from hsa-dme-cel-sce the precision decreases for human along a five-fold increase of the number of predictions, but increases for all the other species .
comparing with other methods
we compare the performance of our ccs-based prediction approach against neighbor counting   <cit> , χ <dig> statistics  <cit>  and fs-weighted averaging   <cit>  considering only proteins that are involved in ccs.
the performance of the individual methods on the complete data is shown in additional file  <dig>  figure s <dig>  figure  <dig> presents precision - recall graphs  for predictions for human proteins separated by the three go subontologies.
ccs-based function prediction significantly outperforms nc and χ <dig> statistics.
precision and recall obtained from the latter two are very low and even below our baselines.
this also holds for yeast and fly .
when comparing fs-wa results with our approach, ccs-based function prediction performs consistently as well or better.
depending on species and subontology we achieve either higher precision at a similar recall or an improved precision and recall.
especially, when considering molecular function and biological process in human  our method clearly outperforms fs-wa.
discussion
we presented a novel approach to predict protein functions that uses data from multiple species and combines three different sources of evidences for functional similarity: orthology relationships, evolutionary conservation of functional modules in protein networks, and direct and indirect protein-protein interactions.
integrating these evidences into a single prediction algorithm overcomes the individual weaknesses of the base methods:  orthology restricts prediction to proteins that have at least one orthologous protein with known function and exhibits a very low precision.
considering only protein-protein interactions disregards the power of comparative genomics, leading to low coverage in organisms where ppi data is not available in abundance.
using only functional modules within protein networks yields high precision, but strongly affects recall on a species basis, as only highly conserved functions performed by dense protein clusters can be predicted.
we showed that combining these methods leads to high precision predictions with very good coverage.
essentially, we achieve high precision by looking only at subgraphs conserved in multiple species without restricting them to dense modules.
furthermore, we achieve high coverage when considering multiple species, by using a relaxed definition of interologs, and by transferring function from ppi neighbors and from orthologous proteins.
altogether, our method predicts thousands of protein functions for every species included in the analysis at varying, yet always high levels of precision .
total number of newly derived go annotations and their estimated average precision  and per-protein recall  for each species using low, medium and high similarity thresholds.
network comparison
for comparing protein interaction networks we used two definitions for determining interologs: the strict and the relaxed definition when studying either two or more than two species, respectively.
we also experimented with using the strict interolog definition for multiple species, but this often results in zero or only very few and small ccs within species groups .
this leads to a small but highly precise set of function predictions.
being less strict leads to a significant improvement in the coverage of our prediction method at comparable precision .
in turn, we also tested the effect of applying a relaxed definition of interologs to species pairs.
this leads to very few  yet very large networks, as it only creates the union of interactions between orthologous proteins of the two species.
however, this does not reflect evolutionary conservation of ppis and therefore misses the important signals of functional conservation.
function prediction
we evaluated or method in several ways using precision and recall, two baselines and three other function prediction methods.
however, besides pure precision and recall values, an important property of any function prediction method is the specificity of its predicted terms.
clearly, predicting only very general terms is much simpler but much less useful than predicting terms close to the leaves of go.
our methods predicts terms at a median level of  <dig> for cellular component,  <dig> for biological process, and  <dig> for molecular function.
thus, our method is capable of predicting quite specific functions .
compared to other methods presented in the literature, our method has also the important property that it is not limited to so-called "informative" go terms  <cit> .
many prediction methods use only go terms that are associated to more than ten or  <dig> genes  <cit> .
such an approach implicitly disregards more specific annotations, although those are the most valuable ones.
for example, in  <dig>  <dig> % of go annotations in human were associated to less than ten genes  <cit>  leaving only  <dig> % as annotation basis.
go-based methods have been shown to result in higher precisions when applied on a small number of frequently annotated go terms.
in contrast, we are able to generate accurate predictions also for rarely used go terms.
comparison to baselines
compared to the orthology baseline, including ccs yields precisions up to 10-times higher, confirming that information on conserved interactions is a very effective filter for avoiding false positive predictions across orthology relationships.
compared to the neighbor baseline, considering ccs also leads to a clear and significant increase in precision.
this effect can be explained by the fact that using interologs  instead of single interactions largely improves reliability of ppi data  <cit> , since false positive ppis are unlikely to be reproduced across multiple species.
our results show that combining various evidences into a single and comprehensive method leads to improved results.
evidently, the predictions made by different methods using information from different species complement each other quite well instead of only predicting the same functions again and again.
however, the concrete approach has to be chosen with care.
we showed that good results can only be achieved when using a proper definition of interaction conservation and when treating large ccs in an adequate manner.
failing to do so either restricts coverage of the method or leads to a higher false positive rates.
comparison to other function prediction methods
we compared precision and recall of our approach to neighbor counting, χ <dig> statistics and fs-weighted averaging .
our combined ccs-based approach significantly outperforms neighbor counting and χ <dig> statistics, especially in terms of precision.
moreover, we perform comparably well or better against fs-weighted averaging, mostly achieving much higher precision at higher recall.
notably, our method achieves better results especially for species without comprehensive ppi coverage, such as human.
however, precision for neighbor counting and χ <dig> is significantly lower  than reported in the respective original publications  <cit> .
there are three explanations for this drop .
first, both methods originally were evaluated only on the functional classification scheme from ypd.
this scheme covers, similar to go, three categories of yeast protein function: biochemical function, cellular role and subcellular localization.
however, categories have only  <dig>   <dig> and  <dig> members, respectively.
compared to our evaluation using go, in which methods have to chose between up-to  <dig> functional categories, this increases the chances to predict correct terms purely by chance.
furthermore, yeast is a particularly well-studied organism, while we applied the method also to less-well covered species.
a similar performance drop was observed by chua et al.
<cit> , which also applied both methods to go term prediction, with precision decreasing to 60%  and 20%  for yeast and 20%  and 16%  for fly.
the second point concerns the amount of interaction data.
for example, results from  <cit>  are based on only  <dig>  interactions among  <dig>  proteins.
in contrast, we integrated six different databases, leading to, for instance, almost  <dig>  interactions for  <dig>  proteins in yeast.
thus, we cover many more proteins and interactions which also increases the probability of false positives.
third, many prediction methods, including the two studies compared to here, consider only annotated proteins with at least one annotated interaction partner for their studies  <cit> .
we did not exclude those proteins because we believe that especially weakly or un-annotated proteins must be a primary target for function prediction.
in our combined approach, such proteins often receive functions from orthologous proteins in other species, an option missing in neighbor counting and χ <dig>  however, functions predicted for non-annotated proteins are necessarily counted as false positives although these are truly novel findings.
thus, disregarding such proteins results in higher precisions.
we did not compare to purely module-based prediction methods, as link-based techniques have been shown to outperform those  <cit> .
however, we evaluated the effect of requiring ccs to be "module-like", i.e., to exhibit a certain density of interactions between its members.
ccs-density is defined as 2*|e||v| where e presents the edges and v denotes the nodes within a ccs.
as expected, filtering ccs according to their density considerably improves precision , e.g.
in fly from 80% without filtering to 90% for a density of  <dig>  and 95% for a density of  <dig>  but this increase is at the cost of much fewer predictions .
effects of size of data sets
results of our prediction method vary depending on the level of available annotations and ppis for the species that are compared .
they are better when well-studied species, such as yeast or fly, are involved.
this is an inherent property of methods that transfer annotations, since better annotated species provide more source functions.
this property underpins the importance of comparative genomics for elucidating the function of human proteins.
it is also clearly visible that prediction precision is correlated to the threshold for functional conservation  and increases with the degree of evolutionary conservation of a ccs - from pairwise to multiple network comparisons .
obviously, the functional conservation threshold is an important possibility to tune or method to the specific needs of an application.
the higher the functional conservation, the higher is the precision of the predictions.
note that in any gold standard evaluation as ours, new findings are always counted as false positives, independently of their real, biological truthfulness.
consequently, prediction methods perform better on well-studied organisms than on species that are functionally less well characterized.
the precision values we report therefore should be considered as lower bounds on the true precision.
performance on weakly and non-annotated proteins
an important goal of protein function prediction is to derive novel functions for proteins without any or with only very little functional information.
thus, we analyzed how our method performs on such proteins.
we define as a weakly annotated protein  any protein which has at most two terms assigned a-priori in our data.
for wap, we count annotations as new if they are more specific than the existing ones or if they belong to another sub-branch in the subontology.
note that such annotations are counted as false positives in our evaluation as they cannot be validated from our gold standard data.
results from comparing hsa-dme-sce are shown in figure  <dig> and additional file  <dig>  figure s <dig>  as expected, the highest number of proteins without any annotation can be found in human.
annotation coverage of fly is not as good as for yeast but still much better than in human.
for example, ccs at threshold  <dig>  contain ~ <dig> human proteins without any functional annotation in biological process.
by means of our method, we predict  <dig> annotation for  <dig> of those proteins.
similarly,  <dig> fly proteins out of  <dig> are annotated with  <dig> go annotation in biological process.
but also well-studied species still contain many waps and benefit from our approach.
for instance, about  <dig> yeast proteins are only weakly characterized for cellular component and for more than a quarter of them we predict about  <dig> functions.
note that the fraction of waps receiving new annotations decreases with the increase of the similarity threshold for each species.
predictions for selected human proteins
in the following, we discuss specific predictions for proteins that are relevant for colorectal cancer.
note that these predictions were counted as false positives in our evaluation because they are not contained in the gene ontology annotations at all or only marked as putative .
however, we show that many predictions already have strong experimental support in the literature.
thus, the group of novel predictions falls into two classes - those that, given the current literature, can be considered as true but have not yet made it into the annotation databases and those for which we could not find conclusive evidence in the literature.
we argue that, given the large amount of predictions that fall in the first class, predictions from the second class should be considered as promising candidates for further studies.
we discuss predicted functions for the gene products of mlh <dig>  pms <dig> and ephb <dig>  all of which have an established importance for colorectal cancer  <cit> .
overall, literature curation largely confirms the predictions for these three genes by different experimental studies.
mlh <dig> and pms2
the dna mismatch repair protein mlh <dig> and the mismatch repair endonuclease pms <dig> belong to the main components of the post-replicative dna mismatch repair  system   <cit> .
the mmr system is required for correcting base mismatches and insertion or deletion loops resulting from dna replication, dna damage, or from recombination events between non-identical sequences during meiosis  <cit> .
curated annotation for mlh <dig> and pms <dig> from uniprot and entrezgene and newly inferred functions are listed in additional file  <dig>  table s <dig> and s <dig>
the majority of our predictions  is directly related to the functionality of the mutlα complex which is formed by mlh <dig> and pms <dig>  rich supporting evidence can be found from the respective orthologs in yeast and mouse.
for instance, pms <dig>  the pms <dig> ortholog in yeast, contributes to dinucleotide insertion or deletion binding, loop dna binding  <cit> .
mlh <dig>  the mouse ortholog of mlh <dig>  is annotated to guanine/thymine mispair binding  <cit>  and likely plays a role in the formation, stabilization and/or the resolution of holliday junction intermediates   <cit> .
high and low affinity atp binding sites have been observed for mlh <dig> and pms <dig> in yeast  <cit>  which supports the atp binding and atpase activity predictions for their human orthologs  <cit> .
moreover, pms <dig> contains a conserved metal-binding motif that constitutes part of the active site for the endonuclease activity of the protein and might enable magnesium ion binding  <cit> .
considering protein homodimerization activity, the dysregulated gene expression of pms <dig>  either as a monomer or homodimer, can disrupt mmr function in mammalian cells  <cit> .
note that, although we support our predictions by literature evidences that are mostly based on orthologs, our algorithm actually inferred them from conserved interaction partners as the orthologs in most cases do not carry the annotation we found in the literature.
our algorithm also generates a number of predictions that are not as clearly supported by the existing literature, such as guanine/thymine mispair binding, single guanine and thymine insertion binding or oxidized dna binding.
moreover, we associate both proteins to base-excision repair as well as postreplication repair and mlh <dig> to maintenance of dna repeat elements.
these are interesting hypotheses supported by recent findings from erdeniz et al.
who suggested that the endonuclease activity of pms <dig> in mutlα is not only important in mmr-dependent mutation avoidance but also for suppression of homologous recombination, dna damage signaling, and damage response functions  <cit> .
association of yeast pms <dig> with meiotic mismatch repair and dna recombination  <cit>  further support these predictions.
regarding their cellular components both proteins are associated to the mutlα complex  <cit> , an annotation predicted jointly from orthology and the ccs neighborhood.
mutlα complex is a clearly sensible refinement of the existing annotation nucleus and only seven others genes are annotated to this term, which emphasizes the specificity of our method.
ephb4
ephrin type-b receptor  <dig> is a transmembrane receptor for the ephrin-b family.
it belongs to the family of receptor tyrosine kinase  and is usually expressed in endothelial and neuronal cells.
known and predicted functional annotations are displayed in additional file  <dig>  table s <dig>
several predicted functions, such as protein, enzyme and atp binding, sh3/sh <dig> adaptor and enzyme regulator activity and protein amino acid phosphorylation, derived both from conserved interactions and orthology, are evidently consistent with the characteristics of receptor tyrosine kinases.
two functions inferred by orthology are transmembrane-ephrin receptor activity and transmembrane receptor protein tyrosine kinase signaling pathways.
both are supported by annotations from highly related receptors, such as ephb <dig> in mouse and ephb <dig> in human  <cit> .
less evident predictions are, for instance, cell-cell signaling  <cit> , cell migration  <cit> , angiogenesis and behavior  <cit> .
these functions were not predicted by orthology alone but only in combination with the conserved interaction neighborhood of ephb <dig>  ephb <dig> participates in the axon guidance pathway and in this context predictions like axon guidance or axon guidance receptor activity can be integrated  <cit> .
CONCLUSIONS
elucidating protein function is a major challenge in the post-genomic era.
we developed a method for predicting protein function based on the structural and functional conservation of ppi subnetworks in multiple species.
our approach integrates three different sources of evidences for inferring functional similarity.
altogether, we employ orthology relationships, evolutionary conservation of functional modules in protein networks, and direct and indirect protein-protein interactions for deriving novel functions for uncharacterized proteins.
using our method we derive thousands of protein functions for every species in our study at varying, yet high levels of precision.
thus, combining orthology relationships, functional modules and ppi neighborhood into a single, comprehensive prediction method yields high-quality predictions with very good coverage.
in comparison against three other function prediction approaches, neighbor counting,  <dig> statistics, and fs-weighted averaging, our ccs-based prediction strategy performs comparably well or significantly better, especially in terms of precision.
additionally, we predict a large amount of novel functions for a number of poorly or non-annotated proteins that can not be validated directly.
however, this shows that our method also generates novel functional knowledge rather than only reproducing known functions for well-characterized proteins.
the manual curation of predictions for three selected proteins confirms their high quality and precision as many predictions already have strong experimental support in the literature.
apart from the promising results of our prediction approach, our method currently only provides lists of yes/no predictions.
this binary behavior is implicit in the way we compute ccs and how we determine predicted terms and targets of prediction.
for further improvement and applicability we plan to derive confidence scores for each prediction based on the multiple biological evidences.
predictions ranked by reliability will provide a method of selection for focusing experimental resources on hypotheses  that are more likely to be true.
this is essential for experimental biologists to decide which proteins and predictions should be investigated further, e.g.
in follow-up experiments.
competing interests
the authors declare that they have no competing interests.
authors' contributions
sj: developed the methods to identify conserved protein interaction subgraphs and to predict protein functions, carried out the studies described in this paper and contributed to the manuscript.
cs: contributed to the manuscript.
ul: conceived the study and contributed to the manuscript.
all authors read and approved the final manuscript.
supplementary material
additional file 1
supplementary material.
the supplementary material includes supplementary figures and tables as well as additional analysis.
click here for file
additional file 2
complete results of the strict and relaxed network comparisons.
this files contains the complete results of the strict and relaxed network comparisons for pairs of species and three, four, five and six species combinations.
the number of orthomcl groups, interologs from strict and relaxed definition as well as the total number of ccs and the size of the largest ccs are given.
click here for file
additional file 3
complete results of the ccs-based function prediction approach.
this file contains the complete results of the combined ccs-based function prediction approach for pairs of species and three, four, five and six species combinations.
ccs from strict and relaxed network comparison are used depending on the species combinations.
click here for file
acknowledgements
we would like to thank hugues roest crollius for critical reading of the manuscript.
this work is funded by an elsa-neumann scholarship and the deutsche forschungsgemeinschaft .

 elucidating protein function is still one of the major challenges in the post-genomic era. even for the best-studied model organisms, such as yeast and fly, a substantial fraction of proteins is still uncharacterized. as high-throughput techniques increase the availability of completely sequenced organisms, annotation of protein function becomes more and more a bottleneck in the progress of biomolecular sciences and the gap between available sequence data and functionally characterized proteins is still widening. manual annotation, using, for instance, the scientific literature, and experimental identification of protein function remains a difficult, time- and cost-intensive task. reliable methods for assigning functions to uncharacterized proteins are required to support and supplement these methods. there are various automatic approaches for the prediction of protein function. these use, for instance, protein sequences and 3d-structures, evolutionary relationships, phylogenetic profiles, domain structures, or functional linkages. another important class of information for function prediction are protein-protein interactions. ppis are a type of data that is close to the biological role of a protein within cells and therefore ideally suited to form the basis for function prediction methods. furthermore, more and more such data sets are becoming available. these data sets may be used to identify functional modules within protein networks, to find protein complexes, or to determine evolutionary conserved processes, all of which provide valuable clues to the function of a protein. the approaches that use ppi for function prediction can be classified into two main classes: link-based methods predict novel functions for a protein by transferring known functions from directly or indirectly interacting proteins. this may be achieved by studying the set of neighbors, by considering the position of the protein within its neighborhood, or by looking at the position of the protein in the entire interaction network. module-based methods assign functions to proteins by first computing clusters within the protein network. based on the hypothesis that cellular functions are organized in a highly modular manner, all members of a cluster are assigned annotations that are enriched within the module. both approaches have their benefits and their drawbacks. ppi-based prediction methods provide a better coverage but are sensitive to the high level of false-positives and false negatives in current ppi data sets. module-based methods are more robust to missing or wrong interactions, but are able to predict function only within dense regions of a species network disregarding, for instance, chain-like pathways. this largely reduces their coverage. module-based methods have been shown to be less accurate than for example simple guilt-by-association approaches but their performance improves in networks with less functional coverage. furthermore, both methods in first place only work within a species, which disregards the wealth of information that might be available in evolutionary related other species. this limitation can be removed by using annotations of homologous proteins. however, purely homology-driven prediction strategies are rather imprecise. although prediction precision may be improved by using only orthology, the overall precision remains below that of most ppi-based methods. in this paper, we describe a novel algorithm for protein function prediction that combines link-based and module-based prediction with orthology, thus overcoming the respective limitations of each individual approach. the key to our method is to analyze proteins within modules that are defined by evolutionary conserved processes. to this end, we first compute ppis that are highly conserved within a given set of species. these so-called interologs are assembled to highly conserved protein sub-networks. for a given protein, we then predict functions of other proteins in the same ccs using both directly interacting proteins as well as orthology relationships. we apply our function prediction strategy to different sets of species, ranging from species pairs to groups of up to four species. we show that our approach reaches very high prediction precision, especially for three and four species. especially due to the combination of different sources of evidence for functional similarity between proteins, our method is able to predict many functions even for uncharacterized or only weakly characterized proteins. these functions are not reflected in the recall since these functions are novel, i.e., counted as fp in the comparison against a gold standard. for instance, when combining the novel predictions from different species combinations, we suggest new functional annotations for human proteins that previously had only zero or one function annotated. overall, our method produces novel annotations for human with an estimated precision of ~76% and for mouse with ~81% precision. these numbers by far outreach that of comparable methods. it is also remarkable that our predictions are rather specific, which is reflected in a mean go-depth of for humans and for mice. to confirm our estimated precision values, we manually verified a number of predictions in the context of colon cancer. specifically, we studied the gene products mlh pms and ephb which received and novel annotations through our method. detailed literature analysis indicates that at least 73% of the novel functions actually are true predictions. finally, we compare our approach against three other approaches, neighbor counting, χ, and fs-weighted averaging. we show that our ccs-based method performs significantly better than those methods in almost all settings we studied, especially in terms of precision. methods we devise an algorithm for predicting functional annotations of proteins using gene ontology terms. our approach is based on comparison of interaction networks from various species and utilizes orthology relationships, conserved modules and local ppi neighborhoods. it is divided into the integration of ppi data from various databases, detection of maximal conserved and connected subgraphs using approximate cross-species network comparisons and prediction of new annotations for proteins within functionally coherent ccs. data we use interaction data of the model organisms s. cerevisiae, d. melanogaster and c. elegans, and the mammals r. norvegicus, m. musculus and h. sapiens. corresponding ppi data were obtained from the major public ppi databases dip, intact, bind, mips-mppi, hprd, mint and biogrid. since the individual coverage and overlap between the data of these resources is comparably low, we integrate ppi data from the different sources to generate comprehensive data sets for our study. for data integration we map the interacting proteins from external or database specific identifiers to unique protein identifiers from uniprot and entrezgene to enable the combination of the different data sets to one comprehensive set of interaction data for each species. from the combined data sets we generated comprehensive species-specific protein interaction networks. besides the interaction data we utilize protein sequences and protein domain information from uniprotkb/swiss-prot. all proteins in the protein interaction network are associated with the respective information. additionally, proteins are annotated with go annotations retrieved from uniprotkb/swiss-prot, entrezgene and species-specific databases, such as flybase, mgd, rgd, sgd and wormbase. note, when annotating proteins we consider all available go annotations except for annotations that are assigned without curatorial judgment. moreover, we filter for go subontology root terms to exclude molecular function, biological process and cellular component. the annotated species-specific protein interaction networks provide the basis of our protein function prediction method. ppi networks for each species are created by integrating ppi data from dip, bind, intact, biogrid, mips-mppi, mint and hprd. proteins within the networks are additionally associated with sequences, protein domains and go annotations. for each species the number of proteins and protein interactions as well as the median number of go terms per protein is specified. network comparison we compare protein interaction networks across different species to detect subgraphs that are evolutionary conserved and likely represent functional modules. figure depicts the strategy of our network comparison approach which involves the identification of orthologous proteins and the detection and assembly of interologs into ccs. orthology is a strong indicator for functional conservation. however, the presence of large protein families, typical for mammals and higher eukaryotes in general, makes it hard to distinguish between true orthologs, in-paralogs and paralogs. we determine orthology relationships among multiple species by applying orthomcl using default parameters. previous work showed that orthomcl is able to discriminate between orthologs, in-paralogs and functionally unrelated paralogs at a balanced trade-off between specificity and sensitivity. for comparing protein networks across species, we consider all ortholog groups that comprise at least one protein of each species under consideration. we then use an adaption of an algorithm for frequent subgraph discovery to assemble interologs into ccs. our approach first identifies all interactions that are conserved across the different species. for identifying interologs we use two different definitions for interologs depending on the number of species that are involved. when comparing only two species, we use the classical, strict definition considering each interaction as interolog that is present in both species. when comparing more than two species, we consider each interaction as interolog that is present in more than 50% of the species networks. out of the set of interologs, one interolog is chosen as subgraph seed and all interologs adjacent to this subgraph are added recursively. if a subgraph can not be further extended we store this maximal and connected subgraph as ccs. prediction of functional annotation ccs are conserved subgraphs of interacting proteins and therefore a strong indicator for functional similarity of proteins within a ccs even across species. however, not all detected ccs are good candidates for function prediction due to the noise and incompleteness within the existing ppi and annotation data sets. therefore, we first filter for ccs that are too heterogeneous or simply too small to be used for function prediction. we then use different methods for predicting functional annotations for all proteins in a ccs, namely transfer of annotations from other species along orthology relationships and transfer within species from all ppi neighbors. in both cases, only proteins within the same ccs are considered. finally, special care has to be taken for the processing of large ccs which, due to their sheer size, usually are functionally heterogeneous. in the following, we give details for each of these steps. filtering coherent ccs we first test all detected ccs for functional coherence using a functional similarity measure proposed by couto et al. that is based on semantic similarity. we compute, for each ccs, its average functional similarity within a species and across the species. the formal definitions of both similarity measures are provided in the additional file. we further only consider ccs which have more than two proteins and whose similarity score, either simortho or simneigh, exceeds a given threshold. we applied three different thresholds to study the performance of our method for different levels of functional coherence. this scheme is applied separately for each subontology of go, biological process, cellular component ). prediction using orthology relationships for inferring protein function from orthology relationships within a ccs, we determine orthologous groups that differ significantly in their individual functional similarity from the similarity score of the ccs by computing the standardized z-score. in groups with significant differences we transfer all known protein annotations to poorly annotated or uncharacterized orthologs. note that an orthologous protein group might consist of more than one protein per species. although all proteins within such a group in theory should be functionally highly similar, this is, probably due to missing or wrong annotations, not always reflected in the data. we define the consensus annotation of all proteins of one species in an orthologous group to be the set of all go terms that are associated to more than half of the annotated proteins of that species in that group. when considering more than two species we combine the species-specific sets of consensus annotations and transfer them to the other proteins in the same group. prediction using neighboring proteins given a protein in a ccs, we decide for each go term annotated to any of its direct neighbors whether it also should be annotated to the protein itself. let g be the set of terms annotated to at least one neighbor of a protein p, and let ng be the set of neighbors of p annotated with a term g ∈ g. we transfer g to p if there are more than f proteins in ng whose functional similarity to p is higher than a given threshold t. for functional similarity between proteins, we again use the method from couto et al.. because this approach cannot predict functions for proteins without any annotation, we also consider the pairwise functional relation between interaction partners, assuming that a high functional similarity between indirectly linked partners should also hold for the protein itself. again, if the pairwise similarity scores exceed the threshold t we predict common go annotations to the candidate protein. combined prediction method we combine the two different methods to predict protein functions within a ccs. proteins that are only weakly and incompletely characterized or not annotated at all are candidates for our prediction approach. for each candidate protein we infer novel protein function within functionally coherent ccs by exploiting its orthology relationship across other species as well as the information shared by its neighboring proteins. processing large ccs comparing evolutionary close species often results in very large ccs with up to several hundreds of proteins. however, biological processes typically involve only between and proteins. consequently, large ccs often encompass various functions which is reflected in a minor functional homogeneity. our results confirm this fact, as large ccs always get low coherence scores. to adequately treat such ccs, we split ccs with more than proteins into smaller, overlapping sub-subgraphs. sub-subgraphs are built by considering each protein of the ccs as seed of a new, smaller ccs. subsequently, we add all direct neighbors of this seed to the new ccs. subgraphs with less than three proteins are removed. we then consider each of these subgraphs as an independent ccs. performance evaluation we use a leave-one-out cross-validation to estimate the expected precision and recall of function prediction using only orthology within ccs, only neighbors within ccs, and the combination of both methods. precision p and recall r are defined as: p=tptp+fp r=tptp+fn where tp and fp denote true and false positives, respectively, and fn denotes false negatives. for cross-validation we'hide' selected annotations before applying our algorithm. predicted terms are then compared to the held out annotations. we count a go term as correctly predicted if the proposed term was an ancestor of the original term on the path to the root or the term itself. for all methods involving ccs, we give recall values on the basis of all annotations of proteins within qualifying ccs. we call this measure per-protein recall. it must be distinguished from the traditional per-species recall which is also used frequently, but which punishes all methods that first filter proteins. when determining the per-protein recall we consider only proteins p that are part of a ccs: rpp=∑p ∈ ccstpp∑p ∈ ccs, where tpp denotes the number of correctly predicted functions for a protein p in a ccs and corresponds to the number of annotations that are originally associated with the protein p. to also give an idea of the per-species performance, we always complement precision and recall values with the coverage measure, which simply counts the total number of predictions. keep in mind that, as always when comparing to an incomplete gold standard, cross-validation inherently considers any new annotations as false, although new annotations are the primary target of function prediction. therefore, we also performed an extensive literature evaluation to judge the correctness of selected new annotations. comparison to other methods we compare our approach against a number of different techniques. first, we use two baseline methods: the orthology baseline purely considers orthology ignoring structural network conservation. we randomly select one third of the orthologous protein groups, remove annotations from one protein in the group and predict their functions using only its orthologs. the link-based baseline takes only direct interaction partners into account, again independently of conservation of interactions. for each species we randomly choose one third of the proteins from the corresponding interaction network and exploit their direct neighbors for deriving new functions. we repeat this procedure times for each baseline and compute average and standard deviation across all runs. we also compare our results with three popular ppi-based function prediction methods. the neighbor counting approach from schwikowski et al. is a local prediction approach that derives new annotations for a protein based on the frequency of annotations within its direct interaction partners. the χ algorithm from hishigaki et al. extended this idea by also considering the background frequency of a functional term. finally, the functional similarity weighted averaging method from chua et al., a weighted averaging method to predict the function of a protein based on its direct and indirect interaction partner. chua et al. demonstrate in that the fs-weighted averaging significantly outperforms local and global network approaches, e.g. methods that are based on markov random field or functional flow. for comparisons, we adapted a script provided by chua et al. that implements these three methods. to enable a valid direct comparison, we evaluate the three related predictions methods only on proteins that are involved in ccs. the individual performance of each method on the entire data set is shown for completeness in the additional file  we integrated ppi data for rat, mouse, human, fly, worm and yeast from several public databases to generate species-specific ppi networks. we computed ccs for combinations of two species, comparison with three, and with four species, and subjected them to our function prediction method. the number of detected ccs for combinations of five and six species is too low for a systematic and detailed analysis. in the following, we focus on four selected species combinations that cover different interactome sizes and evolutionary distances to discuss properties and results of our function prediction strategy. complete results are given as additional file table s and additional file table s network comparisons we compared protein interaction networks across different species to identify evolutionary and functionally conserved subgraphs that are used as basis for function prediction. conserved sub-networks are assembled by combining conserved interactions, called interologs, using different definitions of interologs depending on the number of species being compared. for species pairs, we use the classical, strict definition: an interolog is an interaction present in both species. we relax this demand when comparing more than two species to cater for evolutionary variation and for the incompleteness and noise within present ppi data sets: an interolog then is defined as an interaction which is present in more than 50% of the species being compared. we present a brief overview on the respective network comparison of rno-dme, rno-hsa-sce, hsa-dme-sce, hsa-dme-cel-sce and mmu-hsa-dme-cel. table summarizes the outcomes for the selected species combinations in terms of orthologous protein groups, identified interologs and assembled ccs. as expected, the number of orthologous protein groups, interologs and identified ccs differs depending on the number of compared species, their evolutionary distance as well as their current interactome coverage. comparison of fly and yeast results in ccs with at least three proteins. for more than two species we use the relaxed interolog definition which generally results in a considerable higher number of ccs. for instance, we identify ccs for hsa-dme-sce of which comprise more than two proteins. these ccs are shown in additional file figure s even combinations with four species result in a reasonable number of ccs, such as mmu-hsa-dme-cel producing ccs with more than two proteins. for each species combination the number of orthologous groups, interologs, ccs are presented as well as the size of the largest ccs. note, we use the strict interolog definition for two species and the relaxed criterion for multiple species. function prediction we use orthology relationships, functionally conserved modules, and direct and indirect protein interactions for predicting functional annotations for proteins in a ccs by transferring annotations from other species along orthology relationships and within species from interaction partners. we evaluated our approach in three ways. first, we compared our combined strategy to baseline methods which disregard conservation in networks. second, we compared it to the results obtained from using orthology and ppi neighborhood within ccs in isolation. third, we performed a comparison to three recent function prediction methods from the literature. we first show the performance of our two baseline methods, orthology and link-based, for function prediction. precision for predictions based solely on orthology relationships varies between 3% and 11%. recall is higher, but decreases steeply with the number of species being compared. precision of the link-based baseline ranges from 3% to 17%. contrary to the orthology baseline, recall is rather high, varying between 51% and 75%. thus, the link-based baseline reaches a similar precision but higher recall than the orthology baseline. both baselines yield very low precisions. the orthology baseline indicates the challenges transferring function from ortholog templates. although function tends to be conserved in orthologs, orthology does not guarantee conservation of function. when transferring function solely based on protein sequences, more sophisticated approaches, e.g. using advanced statistical frameworks, are needed to ensure high prediction quality. the precision of the link-based baseline is lower than expected most likely through the strong impact of the quality of the interaction data. however, precision and recall are similar to the results of the two local prediction approaches of schwikowski et al. and hishigaki et al. that are applied to our data. across orthology relationships within ccs we use orthology relationships underpinned by interologs to infer novel functions from multiple species. considering only orthology relationships for transferring functions to proteins within ccs results in predictions with medium to high precision. additional file table s shows precision and recall estimated using cross-validation for the selected examples. precision reaches 88% to 97% for yeast proteins when comparing hsa-dme-sce and 67% to 85% for mouse proteins when comparing mmu-hsa-dme-sce. precision values increase considerably with a higher coherence threshold for ccs, but this improvement comes at the cost of lower coverage. particularly low numbers of predictions are obtained for comparisons involving species with low ppi coverage. this is especially prominent for rno, where comparison of rno-hsa-sce result in only predictions - but with a precision of 100%. besides the coherence threshold, also the number of species being compared has a strong impact on performance. higher average precisions are achieved when analyzing multiple species compared to species pairs. for instance, the average precision for mmu-hsa-dme-sce is 79% at in comparison to dme-sce with 54% at and % at. this shows that using more species implicitly selects functions that are conserved more strongly, which underlines the impact of evolutionary functional conservation for protein function prediction. this fact also shows up when comparing to the orthology baseline: precision and per-protein recall using orthology within ccs are much higher, but the overall coverage is much lower. this means that ccs strongly restrict the number of proteins for which predictions are made, but this restriction is done in a very sensible way removing mostly false positive predictions. across neighborhood within ccs additional file table s shows precision and recall for inferring functions only from interaction partners within ccs. compared to predicting function based on orthology within ccs, precision is higher, while per-protein recall roughly stays the same. at the same time, neighbor-based prediction has a considerable better coverage. however, there are also species combinations in which this method performs worse. precision again correlates with the functional coherence of ccs and with the number of compared species, but the impact is less pronounced. especially the step from coherence threshold to mostly makes only a small difference. compared to the link-based baseline, precision is much higher and coverage and per-protein recall decreases. combining module, orthology and link-based ppi evidences we hypothesized that the integration of orthology relationships, evolutionary conserved functional modules, and direct and indirect protein-protein interactions into a single prediction strategy will combine the strengths of the three individual methods. selected results from this combined strategy are shown in table. as before, precision varies depending on the species combination and the threshold for functional coherence of ccs. best results are obtained for rno-hsa-sce at a threshold of, with precision of 85%, 89% and 86%, respectively. precision and per-protein recall are estimated for low, medium and high functional similarity/conservation thresholds. as mentioned before, one of the major drawbacks of using only ccs orthology relationships is the low number of predictions due to the restriction to orthologous proteins with at least one known function. in contrast to orthology-only, the combined approach creates many more predictions. it generates hundreds or even thousands of predictions also for those cases where the orthology-only method could not predict any function. comparing the combined method and ccs link-based only shows an increase within the amount of predictions, although it is less steep than observed for orthology-only. this increase has mostly only minor influence on precision and recall. precision reaches similar levels and the recall increases slightly. note, for few combinations the combined method yields the same results as link-based-only because no predictions could be inferred through orthology relationships. overall, the impact of our combined approach is dominant, especially in terms of the number of predictions. precision drops for some combinations compared to the single methods. however, the decrease of precision does not indicate a lower prediction quality. it rather indicates that the combined method derives many more novel predictions that can not be validated during cross-validation rather than successfully reproducing known function for well-characterized proteins. precision is affected the least for the highest similarity threshold fostering the most reliable precisions. overlap between orthology- and link-based predictions within ccs we combined orthology- and link-based function prediction within ccs to benefit from the strengths of both methods. to study whether the predictions of the individual methods result in the same or complementary sets of predictions we determined the overlap of go terms predicted by either strategy. for hsa-dme-sce, the respective numbers are shown as venn diagrams in additional file figure s in general, the major fraction of unique predictions is derived from neighboring proteins. the overlap between predictions is comparably small and decreases when increasing the similarity threshold. this shows that both methods complement each other very well as they predict rather different sets of functions. for hsa-dme-sce, the respective numbers are shown as venn diagrams in additional file figure s in general, the major fraction of unique predictions is derived from neighboring proteins. the overlap between predictions is comparably small and decreases when increasing the similarity threshold. this shows that both methods complement each other very well as they predict rather different sets of functions. this behavior is also observable when predictions are analyzed separately per species. however, contrary to fly and yeast proteins and s5), the amount of orthology and link-based predictions is quite similar for human proteins ), which can be explained by the much denser ppi data available for the two model organisms. this observation clarifies that different species pro t differently from our method. especially less characterized species, such as human, benefit strongly from the functional knowledge of model organisms. overlap between predictions derived from different species combinations not only does the neighbor-based method complement the orthology-based method, but also predictions derived from different species combinations are rather complementary. table shows the overlap between predictions for human proteins inferred from different species pairs. the overlap is determined by dividing the number of overlapping predictions through the total number of predictions of a combination. the overlap mostly is far below 50% and strongly depends on evolutionary distance between the species. for example, the overlap between predictions derived from ccs with mouse and those derived from rat is much larger than that of the sets derived from mouse and, say, fly. the same holds for combinations of three and four species. moreover, the more species we combine the more we focus our prediction on evolutionary conserved functions, which becomes clear when studying predictions for highly conserved housekeeping functions. the overlap is defined as the number of overlapping predictions divided by the total number of predictions. each cell contains two different values - i/j - that specify the overlap based on the total number of predictions of the two combinations. i presents the overlap between the non-human species from row i and column j and value j presents the overlap between non-human species from column j and row. large ccs large ccs naturally encompass various biological functions. in consequence, their functional homogeneity is often too low which excludes the entire ccs from function prediction. however, large ccs actually are strong indicators for conserved functions. for instance, figure shows the largest ccs from hsa-dme-cel-sce consisting of proteins and interologs with its different biological subprocesses. it clearly contains several functionally highly conserved clusters, probably forming discrete protein complexes. considering such a large ccs as a whole is insufficient. therefore, we modify our approach for large ccs by breaking them up into sub-subgraphs. the impact on precision and recall is shown in additional file table s, which should be compared with entries of table. as can be seen, processing large ccs creates many more predictions with mostly better precision. for example, the number of predictions almost triples for hsa-dme-sce at a similar or even better precision. when comparing split and non-split results from hsa-dme-cel-sce the precision decreases for human along a five-fold increase of the number of predictions, but increases for all the other species. comparing with other methods we compare the performance of our ccs-based prediction approach against neighbor counting, χ statistics and fs-weighted averaging considering only proteins that are involved in ccs. the performance of the individual methods on the complete data is shown in additional file figure s figure presents precision - recall graphs for predictions for human proteins separated by the three go subontologies. ccs-based function prediction significantly outperforms nc and χ statistics. precision and recall obtained from the latter two are very low and even below our baselines. this also holds for yeast and fly. when comparing fs-wa results with our approach, ccs-based function prediction performs consistently as well or better. depending on species and subontology we achieve either higher precision at a similar recall or an improved precision and recall. especially, when considering molecular function and biological process in human our method clearly outperforms fs-wa. discussion we presented a novel approach to predict protein functions that uses data from multiple species and combines three different sources of evidences for functional similarity: orthology relationships, evolutionary conservation of functional modules in protein networks, and direct and indirect protein-protein interactions. integrating these evidences into a single prediction algorithm overcomes the individual weaknesses of the base methods: orthology restricts prediction to proteins that have at least one orthologous protein with known function and exhibits a very low precision. considering only protein-protein interactions disregards the power of comparative genomics, leading to low coverage in organisms where ppi data is not available in abundance. using only functional modules within protein networks yields high precision, but strongly affects recall on a species basis, as only highly conserved functions performed by dense protein clusters can be predicted. we showed that combining these methods leads to high precision predictions with very good coverage. essentially, we achieve high precision by looking only at subgraphs conserved in multiple species without restricting them to dense modules. furthermore, we achieve high coverage when considering multiple species, by using a relaxed definition of interologs, and by transferring function from ppi neighbors and from orthologous proteins. altogether, our method predicts thousands of protein functions for every species included in the analysis at varying, yet always high levels of precision. total number of newly derived go annotations and their estimated average precision and per-protein recall for each species using low, medium and high similarity thresholds. network comparison for comparing protein interaction networks we used two definitions for determining interologs: the strict and the relaxed definition when studying either two or more than two species, respectively. we also experimented with using the strict interolog definition for multiple species, but this often results in zero or only very few and small ccs within species groups. this leads to a small but highly precise set of function predictions. being less strict leads to a significant improvement in the coverage of our prediction method at comparable precision. in turn, we also tested the effect of applying a relaxed definition of interologs to species pairs. this leads to very few yet very large networks, as it only creates the union of interactions between orthologous proteins of the two species. however, this does not reflect evolutionary conservation of ppis and therefore misses the important signals of functional conservation. function prediction we evaluated or method in several ways using precision and recall, two baselines and three other function prediction methods. however, besides pure precision and recall values, an important property of any function prediction method is the specificity of its predicted terms. clearly, predicting only very general terms is much simpler but much less useful than predicting terms close to the leaves of go. our methods predicts terms at a median level of for cellular component, for biological process, and for molecular function. thus, our method is capable of predicting quite specific functions. compared to other methods presented in the literature, our method has also the important property that it is not limited to so-called "informative" go terms. many prediction methods use only go terms that are associated to more than ten or genes. such an approach implicitly disregards more specific annotations, although those are the most valuable ones. for example, in % of go annotations in human were associated to less than ten genes leaving only % as annotation basis. go-based methods have been shown to result in higher precisions when applied on a small number of frequently annotated go terms. in contrast, we are able to generate accurate predictions also for rarely used go terms. comparison to baselines compared to the orthology baseline, including ccs yields precisions up to 10-times higher, confirming that information on conserved interactions is a very effective filter for avoiding false positive predictions across orthology relationships. compared to the neighbor baseline, considering ccs also leads to a clear and significant increase in precision. this effect can be explained by the fact that using interologs instead of single interactions largely improves reliability of ppi data, since false positive ppis are unlikely to be reproduced across multiple species. our results show that combining various evidences into a single and comprehensive method leads to improved results. evidently, the predictions made by different methods using information from different species complement each other quite well instead of only predicting the same functions again and again. however, the concrete approach has to be chosen with care. we showed that good results can only be achieved when using a proper definition of interaction conservation and when treating large ccs in an adequate manner. failing to do so either restricts coverage of the method or leads to a higher false positive rates. comparison to other function prediction methods we compared precision and recall of our approach to neighbor counting, χ statistics and fs-weighted averaging. our combined ccs-based approach significantly outperforms neighbor counting and χ statistics, especially in terms of precision. moreover, we perform comparably well or better against fs-weighted averaging, mostly achieving much higher precision at higher recall. notably, our method achieves better results especially for species without comprehensive ppi coverage, such as human. however, precision for neighbor counting and χ is significantly lower than reported in the respective original publications. there are three explanations for this drop. first, both methods originally were evaluated only on the functional classification scheme from ypd. this scheme covers, similar to go, three categories of yeast protein function: biochemical function, cellular role and subcellular localization. however, categories have only and members, respectively. compared to our evaluation using go, in which methods have to chose between up-to functional categories, this increases the chances to predict correct terms purely by chance. furthermore, yeast is a particularly well-studied organism, while we applied the method also to less-well covered species. a similar performance drop was observed by chua et al., which also applied both methods to go term prediction, with precision decreasing to 60% and 20% for yeast and 20% and 16% for fly. the second point concerns the amount of interaction data. for example, results from are based on only interactions among proteins. in contrast, we integrated six different databases, leading to, for instance, almost interactions for proteins in yeast. thus, we cover many more proteins and interactions which also increases the probability of false positives. third, many prediction methods, including the two studies compared to here, consider only annotated proteins with at least one annotated interaction partner for their studies. we did not exclude those proteins because we believe that especially weakly or un-annotated proteins must be a primary target for function prediction. in our combined approach, such proteins often receive functions from orthologous proteins in other species, an option missing in neighbor counting and χ however, functions predicted for non-annotated proteins are necessarily counted as false positives although these are truly novel findings. thus, disregarding such proteins results in higher precisions. we did not compare to purely module-based prediction methods, as link-based techniques have been shown to outperform those. however, we evaluated the effect of requiring ccs to be "module-like", i.e., to exhibit a certain density of interactions between its members. ccs-density is defined as 2*|e||v| where e presents the edges and v denotes the nodes within a ccs. as expected, filtering ccs according to their density considerably improves precision, e.g. in fly from 80% without filtering to 90% for a density of and 95% for a density of but this increase is at the cost of much fewer predictions. effects of size of data sets results of our prediction method vary depending on the level of available annotations and ppis for the species that are compared. they are better when well-studied species, such as yeast or fly, are involved. this is an inherent property of methods that transfer annotations, since better annotated species provide more source functions. this property underpins the importance of comparative genomics for elucidating the function of human proteins. it is also clearly visible that prediction precision is correlated to the threshold for functional conservation and increases with the degree of evolutionary conservation of a ccs - from pairwise to multiple network comparisons. obviously, the functional conservation threshold is an important possibility to tune or method to the specific needs of an application. the higher the functional conservation, the higher is the precision of the predictions. note that in any gold standard evaluation as ours, new findings are always counted as false positives, independently of their real, biological truthfulness. consequently, prediction methods perform better on well-studied organisms than on species that are functionally less well characterized. the precision values we report therefore should be considered as lower bounds on the true precision. performance on weakly and non-annotated proteins an important goal of protein function prediction is to derive novel functions for proteins without any or with only very little functional information. thus, we analyzed how our method performs on such proteins. we define as a weakly annotated protein any protein which has at most two terms assigned a-priori in our data. for wap, we count annotations as new if they are more specific than the existing ones or if they belong to another sub-branch in the subontology. note that such annotations are counted as false positives in our evaluation as they cannot be validated from our gold standard data. results from comparing hsa-dme-sce are shown in figure and additional file figure s as expected, the highest number of proteins without any annotation can be found in human. annotation coverage of fly is not as good as for yeast but still much better than in human. for example, ccs at threshold contain ~ human proteins without any functional annotation in biological process. by means of our method, we predict annotation for of those proteins. similarly, fly proteins out of are annotated with go annotation in biological process. but also well-studied species still contain many waps and benefit from our approach. for instance, about yeast proteins are only weakly characterized for cellular component and for more than a quarter of them we predict about functions. note that the fraction of waps receiving new annotations decreases with the increase of the similarity threshold for each species. predictions for selected human proteins in the following, we discuss specific predictions for proteins that are relevant for colorectal cancer. note that these predictions were counted as false positives in our evaluation because they are not contained in the gene ontology annotations at all or only marked as putative. however, we show that many predictions already have strong experimental support in the literature. thus, the group of novel predictions falls into two classes - those that, given the current literature, can be considered as true but have not yet made it into the annotation databases and those for which we could not find conclusive evidence in the literature. we argue that, given the large amount of predictions that fall in the first class, predictions from the second class should be considered as promising candidates for further studies. we discuss predicted functions for the gene products of mlh pms and ephb all of which have an established importance for colorectal cancer. overall, literature curation largely confirms the predictions for these three genes by different experimental studies. mlh and pms2 the dna mismatch repair protein mlh and the mismatch repair endonuclease pms belong to the main components of the post-replicative dna mismatch repair system. the mmr system is required for correcting base mismatches and insertion or deletion loops resulting from dna replication, dna damage, or from recombination events between non-identical sequences during meiosis. curated annotation for mlh and pms from uniprot and entrezgene and newly inferred functions are listed in additional file table s and s the majority of our predictions is directly related to the functionality of the mutlα complex which is formed by mlh and pms rich supporting evidence can be found from the respective orthologs in yeast and mouse. for instance, pms the pms ortholog in yeast, contributes to dinucleotide insertion or deletion binding, loop dna binding. mlh the mouse ortholog of mlh is annotated to guanine/thymine mispair binding and likely plays a role in the formation, stabilization and/or the resolution of holliday junction intermediates. high and low affinity atp binding sites have been observed for mlh and pms in yeast which supports the atp binding and atpase activity predictions for their human orthologs. moreover, pms contains a conserved metal-binding motif that constitutes part of the active site for the endonuclease activity of the protein and might enable magnesium ion binding. considering protein homodimerization activity, the dysregulated gene expression of pms either as a monomer or homodimer, can disrupt mmr function in mammalian cells. note that, although we support our predictions by literature evidences that are mostly based on orthologs, our algorithm actually inferred them from conserved interaction partners as the orthologs in most cases do not carry the annotation we found in the literature. our algorithm also generates a number of predictions that are not as clearly supported by the existing literature, such as guanine/thymine mispair binding, single guanine and thymine insertion binding or oxidized dna binding. moreover, we associate both proteins to base-excision repair as well as postreplication repair and mlh to maintenance of dna repeat elements. these are interesting hypotheses supported by recent findings from erdeniz et al. who suggested that the endonuclease activity of pms in mutlα is not only important in mmr-dependent mutation avoidance but also for suppression of homologous recombination, dna damage signaling, and damage response functions. association of yeast pms with meiotic mismatch repair and dna recombination further support these predictions. regarding their cellular components both proteins are associated to the mutlα complex, an annotation predicted jointly from orthology and the ccs neighborhood. mutlα complex is a clearly sensible refinement of the existing annotation nucleus and only seven others genes are annotated to this term, which emphasizes the specificity of our method. ephb4 ephrin type-b receptor is a transmembrane receptor for the ephrin-b family. it belongs to the family of receptor tyrosine kinase and is usually expressed in endothelial and neuronal cells. known and predicted functional annotations are displayed in additional file table s several predicted functions, such as protein, enzyme and atp binding, sh3/sh adaptor and enzyme regulator activity and protein amino acid phosphorylation, derived both from conserved interactions and orthology, are evidently consistent with the characteristics of receptor tyrosine kinases. two functions inferred by orthology are transmembrane-ephrin receptor activity and transmembrane receptor protein tyrosine kinase signaling pathways. both are supported by annotations from highly related receptors, such as ephb in mouse and ephb in human. less evident predictions are, for instance, cell-cell signaling, cell migration, angiogenesis and behavior. these functions were not predicted by orthology alone but only in combination with the conserved interaction neighborhood of ephb ephb participates in the axon guidance pathway and in this context predictions like axon guidance or axon guidance receptor activity can be integrated.  elucidating protein function is a major challenge in the post-genomic era. we developed a method for predicting protein function based on the structural and functional conservation of ppi subnetworks in multiple species. our approach integrates three different sources of evidences for inferring functional similarity. altogether, we employ orthology relationships, evolutionary conservation of functional modules in protein networks, and direct and indirect protein-protein interactions for deriving novel functions for uncharacterized proteins. using our method we derive thousands of protein functions for every species in our study at varying, yet high levels of precision. thus, combining orthology relationships, functional modules and ppi neighborhood into a single, comprehensive prediction method yields high-quality predictions with very good coverage. in comparison against three other function prediction approaches, neighbor counting, statistics, and fs-weighted averaging, our ccs-based prediction strategy performs comparably well or significantly better, especially in terms of precision. additionally, we predict a large amount of novel functions for a number of poorly or non-annotated proteins that can not be validated directly. however, this shows that our method also generates novel functional knowledge rather than only reproducing known functions for well-characterized proteins. the manual curation of predictions for three selected proteins confirms their high quality and precision as many predictions already have strong experimental support in the literature. apart from the promising results of our prediction approach, our method currently only provides lists of yes/no predictions. this binary behavior is implicit in the way we compute ccs and how we determine predicted terms and targets of prediction. for further improvement and applicability we plan to derive confidence scores for each prediction based on the multiple biological evidences. predictions ranked by reliability will provide a method of selection for focusing experimental resources on hypotheses that are more likely to be true. this is essential for experimental biologists to decide which proteins and predictions should be investigated further, e.g. in follow-up experiments. competing interests the authors declare that they have no competing interests. authors' contributions sj: developed the methods to identify conserved protein interaction subgraphs and to predict protein functions, carried out the studies described in this paper and contributed to the manuscript. cs: contributed to the manuscript. ul: conceived the study and contributed to the manuscript. all authors read and approved the final manuscript. supplementary material additional file 1 supplementary material. the supplementary material includes supplementary figures and tables as well as additional analysis. click here for file additional file 2 complete results of the strict and relaxed network comparisons. this files contains the complete results of the strict and relaxed network comparisons for pairs of species and three, four, five and six species combinations. the number of orthomcl groups, interologs from strict and relaxed definition as well as the total number of ccs and the size of the largest ccs are given. click here for file additional file 3 complete results of the ccs-based function prediction approach. this file contains the complete results of the combined ccs-based function prediction approach for pairs of species and three, four, five and six species combinations. ccs from strict and relaxed network comparison are used depending on the species combinations. click here for file acknowledgements we would like to thank hugues roest crollius for critical reading of the manuscript. this work is funded by an elsa-neumann scholarship and the deutsche forschungsgemeinschaft.
the combination of different methods into a single, comprehensive prediction method infers thousands of protein functions for every species included in the analysis at varying, yet always high levels of precision and very good coverage. for instance, our method generates more than novel protein functions for human with an estimated precision of ~76%, among which are new functional annotations for human proteins that previously had zero or only one function annotated. we report on a new method that predicts function based on a combination of information about protein interactions, orthology, and the conservation of protein networks in different species. we also verified our predictions on a set of genes that play an important role in colorectal cancer and could confirm more than 73% of them based on evidence in the literature. this has led to the development of a wide range of methods for predicting protein functions in silico.
 while the number of newly sequenced genomes and genes is constantly increasing, elucidation of their function still is a laborious and time-consuming task. this has led to the development of a wide range of methods for predicting protein functions in silico. we report on a new method that predicts function based on a combination of information about protein interactions, orthology, and the conservation of protein networks in different species.  we show that aggregation of these independent sources of evidence leads to a drastic increase in number and quality of predictions when compared to baselines and other methods reported in the literature. for instance, our method generates more than novel protein functions for human with an estimated precision of ~76%, among which are new functional annotations for human proteins that previously had zero or only one function annotated. we also verified our predictions on a set of genes that play an important role in colorectal cancer and could confirm more than 73% of them based on evidence in the literature.  the combination of different methods into a single, comprehensive prediction method infers thousands of protein functions for every species included in the analysis at varying, yet always high levels of precision and very good coverage. 