BACKGROUND
comparative genomics involves large scale investigations to identify which parts of different genomes are of common descent in order to predict function or to study genome evolution.
a common first step towards detecting homology between genes or proteins within a genome or between different genomes, is to do a blast search with a set of genes or proteins against a database and regard each hit with an e-value below a certain cutoff to be homologous  <cit> .
additionally, several filters and clustering algorithms can be applied to separate sets of homologs into orthologous groups .
usually, a stringent score cutoff is used to ensure that the hits that are included are indeed homologs.
naturally, homologs whose sequences have diverged strongly, are incorrectly excluded.
on a smaller scale, more sensitive searches based on profiles of groups of related amino acid sequences  or, if available, protein three dimensional structures are commonly used to avoid false negatives without losing confidence in the putative homologs returned  <cit> .
in these searches, instead of using the same scores or probability for each position, a multiple sequence alignment is used to define position specific substitution scores or transition probabilities.
besides improving sequence based homology searches, one can also use information on the genomic context of sequences to aid detection of a common descent of sequences.
genome alignments can be very useful when there are difficulties in determining homology between sequences, for example between intergenic regions.
boekhorst and snel showed that genome alignments can be used to select candidates from a set of insignificant blast hits in prokaryotes  <cit> .
in eukaryotes, gene order is less conserved across large phylogenomic distances such as between fungi and animals and therefore less likely to make a valuable contribution to the detection of homology at these large evolutionary distances  <cit> .
as a result, conserved synteny is mainly employed in eukaryotes for the detection of orthologs, between closely related species, e.g.
within ascomycete fungi or within vertebrates  <cit> .
the availability of protein interaction networks allows for the comparison of genomes and the functional context simultaneously.
information on the functional context of proteins is already used in comparative genomics of eukaryotes to select from a set of inparalogs, the protein that is functionally similar to the query sequence   <cit> .
in the comparative analysis of protein interaction networks, spurious protein interactions can be separated from biologically relevant interactions if the protein-protein interaction occurs in different species.
we here test if the reverse is also in principle applicable: can the network alignment help to separate spurious homology links from real ones?
analogously to genome alignment, we test the expectation that the insignificant blast hit between protein a from species a and protein b from species b is more likely to reflect homology if protein a is functionally closely related to proteins which are readily identifiable as orthologous to proteins in species b that are functionally closely related to b .
to answer this question, we select candidate pairs from blast hits between human and yeast proteins based on conserved functional context, in this case homologous complexes, and determine whether this selection contains relatively more homologs than a background of hits with similar blast scores.
RESULTS
are hits with conserved functional context more likely to be homologous?
we perform an all-against-all blast search between the human and yeast proteomes using a substantially more inclusive threshold than normally is applied to allow a comprehensive survey of insignificant blast hits.
for each query-hit pair blast returns an e-value.
we bin the e-values into  <dig> bins ranging from  to .
we define co-complex networks for human and yeast based on two curated complex datasets per species, and use inparanoid clusters between human and yeast to align these networks   <cit> .
if the query and the hit contain a domain which belongs to the same pfam clan, we consider them to be true positives.
for each of our  <dig> bins, we calculate the fraction of query-hit pairs which are true positives, with and without co-complex network alignment.
we find that the use of co-complex information results in a considerable increase in the fraction of true homologs among the returned hits, compared to blast without co-complex information .
this difference is most eminent in bins representing e-values normally considered to be insignificant .
at e-values between  <dig> and  <dig> almost 90% of the returned hits share a pfam clan, which means a substantial,  <dig> fold increase in the percentage of true positives.
this is not due to a bias resulting from being a member of the co-complex network or being in a conserved region of the co-complex network, as only after alignment of the co-complex network we see a big improvement in the fraction of true positives .
only a small subset of yeast and human proteins  is part of a co-complex network within each species.
moreover, many of those are not functionally linked to proteins that have readily identifiable orthologs in the other species.
as a consequence, this method is applicable to only a small fraction of query-hit pairs .
if we include high-throughput co-complex datasets for yeast and human, the coverage is increased a little at a cost of a slightly inferior performance .
each row contains the number of query-hit pairs and the number of distinct human query proteins in a particular e-value bin, for all blast hits and the subset of blast hits which falls into the 'co-complex network alignment' category.
we show that alignment of co-complex networks can facilitate the identification of true homologs among gray zone blast hits.
in a simple and completely automated procedure, we obtain a subset of hits which, despite very high e-values, is substantially enriched for homologs.
this allows us to infer homology for pairs with co-complex network alignment with an e-value ranging between  <dig>  and  <dig> with the similar confidence as for pairs before co-complex network alignment and an e-value of  <dig>  .
our framework would likely be improved if we could use statistics on  missing connections in both co-complex networks.
to date, protein complex datasets are too fragmentary to make any sensible estimates of the number of missing connections.
detection of missing complex subunits
previous large scale investigations towards presence and absence of protein complex subunits in prokaryotes and eukaryotes reveal that most complexes are only partially present in other species  <cit> .
in these studies, an orthology definition based on blast is used to determine presence and absence of subunits in different species and part of the subunits regarded absent may be missing due to detection problems.
hence the disrupted co-evolution of protein complexes might partly be an artefact.
the use of co-complex information is potentially useful in the detection of yeast homologs of subunits of human protein complexes.
especially as the most important disadvantage, the lack of coverage of the co-complex networks, is less urgent because the queries are subunits and hence are all part of the human co-complex network.
we take the opportunity to test the applicability of our method to a problem in comparative genomics and assess the added value of co-complex network alignment in detecting homologs in yeast for subunits of human complexes.
for the complexes in the corum dataset, we initially find homologs for complex components by running a blast search with all subunits against the yeast proteome, applying a commonly used e-value cutoff of  <dig> .
then, for the subunits we did not find homologs for, we use a less stringent e-value cutoff of  <dig>  in combination with co-complex network alignment, to see how many additional subunits we pick up.
using blast only with an e-value cutoff of  <dig> , we find yeast homologs for  <dig> out of  <dig>  subunits.
we find that  <dig> out of  <dig> complexes  have a homolog in yeast for all subunits,  <dig>  have homologs for some subunits and  <dig>  complexes are completely absent.
even when only comparing two species, we find that for most human complexes, only part of all subunits have a homolog in yeast.
however, as we have argued before, some subunits may be called absent due to detection problems.
for the  <dig> subunits for which we detected no homolog in yeast, we select, using the co-complex network alignment, candidate homologs in yeast for  <dig> additional subunits, belonging to  <dig> complexes .
using pfam, cdd and psi-blast, we confirm that the  <dig> out of  <dig> candidates recovered with co-complex network alignment are in fact homologous.
with the  <dig> confirmed homologs we retrieved, an additional  <dig> complexes are completely present in yeast .
one striking observation when comparing individual complexes in human to complexes in yeast, is that there is very little congruence between human and yeast complex definitions .
factors such as the incompleteness of data in both species, individual decisions on what does belong to a complex and what does not, and proteins belonging to multiple complexes, obscure a one-to-one relation between yeast and human complexes, assuming such a correspondence exists.
fortunately, because we align human and yeast complexes on a network level rather than as individual complexes, we are able to retrieve homologs with the co-complex network alignment for complexes which do not exist as such in yeast.
a good example is the multisynthetase complex .
this complex is composed of  <dig> aminoacyl-trna synthetases and  <dig> auxiliary proteins.
the individual trna synthetases all have a homolog in yeast found with the initial straightforward blast search.
the yeast homologs of the trna sythetases are not known to be organized in a complex, with one important exception: methionyl and glutamyl synthetases mes <dig> and gus <dig> associate into a complex with arc <dig>  an auxiliary protein  which increases catalytic efficiency and ensures correct localization into the cytoplasm.
via this complex, human jtv <dig>  a scaffold required for the assembly and stability of the multi-trna synthetase complex, is linked to a short n-terminal stretch of yeast gus <dig>  whose c-term is unambiguously homologous to the glutaminyl synthetase in human, qars .
when we do a psi-blast with human jtv <dig> as a query protein, we retrieve gus <dig>  aligned to the gst_c domain in jtv <dig>  after three iterations.
we recovered a homolog for another subunit of the multisynthetase complex via an unrelated complex: the ribosome.
human eef1e <dig> has a hit with yeast efb <dig> with an e-value of  <dig> .
efb <dig> is located at the ribosome, as is yhr020w, which is the readily identifiable yeast ortholog of the human bifunctional glutamyl-prolyl trna synthetase eprs.
both efb <dig> and eef1e <dig> are translation elongation factors  and both contain a domain which belongs to the gst_c_superfamily.
the hsp lies in the regions where the gst_c_superfamily domain lies in both proteins and these regions in the protein sequences are, albeit very distantly, evolutionary related.
efb <dig> has a much more similar homolog in human , suggesting that eef1e <dig> and efb are related through a very old duplication event and the translation elongation factor  <dig> epsilon eef1e <dig> ortholog is lost in yeast.
applying the co-complex network alignment to the set of protein complex subunits in corum, we select candidate homologs in yeast for  <dig> proteins, out of which we could confirm homology with pfam, cdd or psi-blast for  <dig> pairs.
the observation reported in both large and small scale investigations  <cit> , that most complexes are 'incomplete' in many species, remains unchallenged because we can only show for a few complexes that their incompleteness is a result of an undetected homology
are the recovered distant homologs orthologs?
exploiting the co-complex network alignment we find yeast homologs for  <dig> subunits of human complexes that are not revealed by standard blast.
this is markedly less than the  <dig> human queries for which co-complex information is applicable .
the likely crucial difference between our initial survey of all blast hit pairs and the detection of missing complex subunits is the fact that in the latter, we applied the co-complex alignment only to those query proteins for which we could not find a homolog with blast alone.
therefore we expect that many query proteins for which we recover a distant homolog with the co-complex network alignment in the initial survey, have an additional, significant hit in yeast and are therefore not used as a query when looking for additional homologs for complex subunits.
indeed, we find that this is the case for no less than 85%  of the query-hit pairs with an e-value >  <dig> .
there are a few possible evolutionary histories that can explain the fact that for a certain query protein in human, we find a close homolog and a distant homolog with conserved functional context in yeast.
first of all, distant homologs recovered by co-complex network alignment could be ancient paralogs , in which the high degree of divergence is due to time rather than rapid sequence evolution .
for instance, eef1e <dig> and efb <dig> in the multisynthetase example discussed above are ancient paralogs.
another possibility is a more recent duplication in yeast followed by asymmetric divergence in the duplicates, in which case the divergence is caused by accelerated evolution on one branch  <cit> .
finally, the two yeast hits may be homologous to different regions of the query protein due to fusion, fission or domain recombination events , in which one domain/region has a markedly higher rate of sequence evolution than the other.
in the fusion/fission/domain recombination scenario, the two yeast hits of the human query protein in yeast are not homologous.
for  <dig> of our  <dig> trios the two yeast hits are not a significant hit in blast, neither do they share a homologous domain according to pfam.
for  <dig> of these trios the best scoring blast hsp of the two yeast proteins is in a different region in the human protein.
in the remaining two pairs, the distant homologs that we retrieve share only a short kow motif with the query protein, while the best hit shares both the kow motif  and also the adjacent ribosomal l27e domain.
if we consider only those  <dig> trios of proteins in which the two yeast proteins are homologous according to pfam, we find that in  <dig> of them, the distant homolog has a significant hit in human, suggesting it is in fact an ancient paralog .
a recent study towards the fate of duplicated protein complex subunits showed that 31% of duplicates resides in different complexes, 31% stayed in the same complex and in 38% of the cases one of the duplicates is not known to be part of any complex  <cit> .
we investigate the fate of the  <dig> yeast pairs that are outparalogs according to our analysis.
the yeast pairs are not a random sample of ancient yeast duplicates, on the contrary.
because one of the yeast paralogs is a close homolog of a human protein which is part of a complex which is homologous to the complex the other yeast paralog is part of, we expect a bias towards duplicates remaining in the same complex.
we find that for  <dig> pairs , both duplicates are in the same complex, for  <dig> pairs  the duplicates are in overlapping complexes , for  <dig> pairs  they are in a different complexes and for  <dig> pairs one of the duplicates  is not known to be part of any complex in yeast.
we expect that the human homologs of the  <dig> pairs in which the yeast ancient duplicates belong to distinct complexes, are more often part of multiple complexes, indicating that the yeast duplicates subfunctionalized.
we do observe a significant overrepresentation of proteins that are part of multiple complexes in ancient paralogs when compared to all subunits in the corum complex dataset , but not in ancient paralogs which are part of the same complex when compared to those which have ended up in distinct complexes .
the lion's share of distant homologs we recover using the co-complex network alignment consists of ancient paralogs rather than orthologs.
duplications in general are very important in the evolution of protein complexes  <cit>  and many structures are known to consist of subunits resulting from very old duplications .
we find that in most cases both duplicates are part of the same or overlapping complexes.
this suggests that the duplicates we detect have sub- or neofunctionalized within one complex, although some might be the result of outparalogs that have been independently recruited to a biological process.
CONCLUSIONS
we test whether contextual information from the functional network, in this case conserved co-complex relations, can aid homology detection.
functional context information has been used before to help in choosing functional orthologs from a set of inparalogs, but to our best knowledge, this is the first time functional networks are used to aid distant homology detection.
using an aligned co-complex network, we can identify a subset highly enriched for homologs of blast hits with an e-value which would normally be regarded as insignificant.
this shows that, even though evolution takes place at the sequence level, one can use co-complex networks as circumstantial evidence to improve confidence in the homology of distantly related sequences.
the interspecies co-complex network includes only a small fraction of all proteins, which impedes applicability.
as more high-throughput datasets become available in more species, we expect that the proof of principle we established here, can be applied and tested on a larger scale, between more distantly related species and with other types of functional relations.
we apply our co-complex network alignment to a dataset of human complexes in order to determine how many homologous subunits we can detect that we missed in an initial blast search.
we thereby recovered homologs for only a few additional subunits, despite the fact that coverage is less a limiting factor in this context.
we find that one reason we retrieve less additional subunits than expected, is that with the co-complex alignment, we mainly detect outparalogs rather than orthologs.
it has been shown that subunits of a protein complex diverge at similar rates, presumably because subunits of a protein complex are functionally strongly interdependent and subject to very similar evolutionary constraints  <cit> .
in contrast, the co-complex network alignment method is based on the fact that some subunits diverged between human and yeast to such an extent that they are not picked up in a regular blast search and other subunits are conserved such that the human and yeast orthologs are still detected by inparanoid.
in this light it is not surprising that most homologs we recover with our method are ancient paralogs rather than orthologs: the difference in the extent of divergence is due to difference in time, as opposed to difference in evolutionary rates between subunits of the same protein complex.
researchers studying the evolution of individual protein complexes have used functional information to find diverged homologs successfully despite absence of proof from a large scale study  <cit> .
our results provide this proof.
numerous predictions made in these small scale studies were subsequently confirmed by profile vs profile alignments or the comparison of protein three dimensional structures upon availability.
interestingly, many of these predictions represent initial blast hits with e-values even higher than  <dig> .
hence it is possible that in our study still many homologs have gone undetected, and the formal integration of functional context with more sensitive homology detection methods might help in the development of automatic bioinformatic methods to uncover these distant homologs and improve our insights into the ancient evolution of the protein interaction network.

 comparative genomics involves large scale investigations to identify which parts of different genomes are of common descent in order to predict function or to study genome evolution. a common first step towards detecting homology between genes or proteins within a genome or between different genomes, is to do a blast search with a set of genes or proteins against a database and regard each hit with an e-value below a certain cutoff to be homologous. additionally, several filters and clustering algorithms can be applied to separate sets of homologs into orthologous groups. usually, a stringent score cutoff is used to ensure that the hits that are included are indeed homologs. naturally, homologs whose sequences have diverged strongly, are incorrectly excluded. on a smaller scale, more sensitive searches based on profiles of groups of related amino acid sequences or, if available, protein three dimensional structures are commonly used to avoid false negatives without losing confidence in the putative homologs returned. in these searches, instead of using the same scores or probability for each position, a multiple sequence alignment is used to define position specific substitution scores or transition probabilities. besides improving sequence based homology searches, one can also use information on the genomic context of sequences to aid detection of a common descent of sequences. genome alignments can be very useful when there are difficulties in determining homology between sequences, for example between intergenic regions. boekhorst and snel showed that genome alignments can be used to select candidates from a set of insignificant blast hits in prokaryotes. in eukaryotes, gene order is less conserved across large phylogenomic distances such as between fungi and animals and therefore less likely to make a valuable contribution to the detection of homology at these large evolutionary distances. as a result, conserved synteny is mainly employed in eukaryotes for the detection of orthologs, between closely related species, e.g. within ascomycete fungi or within vertebrates. the availability of protein interaction networks allows for the comparison of genomes and the functional context simultaneously. information on the functional context of proteins is already used in comparative genomics of eukaryotes to select from a set of inparalogs, the protein that is functionally similar to the query sequence. in the comparative analysis of protein interaction networks, spurious protein interactions can be separated from biologically relevant interactions if the protein-protein interaction occurs in different species. we here test if the reverse is also in principle applicable: can the network alignment help to separate spurious homology links from real ones? analogously to genome alignment, we test the expectation that the insignificant blast hit between protein a from species a and protein b from species b is more likely to reflect homology if protein a is functionally closely related to proteins which are readily identifiable as orthologous to proteins in species b that are functionally closely related to b. to answer this question, we select candidate pairs from blast hits between human and yeast proteins based on conserved functional context, in this case homologous complexes, and determine whether this selection contains relatively more homologs than a background of hits with similar blast scores.  are hits with conserved functional context more likely to be homologous? we perform an all-against-all blast search between the human and yeast proteomes using a substantially more inclusive threshold than normally is applied to allow a comprehensive survey of insignificant blast hits. for each query-hit pair blast returns an e-value. we bin the e-values into bins ranging from to. we define co-complex networks for human and yeast based on two curated complex datasets per species, and use inparanoid clusters between human and yeast to align these networks. if the query and the hit contain a domain which belongs to the same pfam clan, we consider them to be true positives. for each of our bins, we calculate the fraction of query-hit pairs which are true positives, with and without co-complex network alignment. we find that the use of co-complex information results in a considerable increase in the fraction of true homologs among the returned hits, compared to blast without co-complex information. this difference is most eminent in bins representing e-values normally considered to be insignificant. at e-values between and almost 90% of the returned hits share a pfam clan, which means a substantial, fold increase in the percentage of true positives. this is not due to a bias resulting from being a member of the co-complex network or being in a conserved region of the co-complex network, as only after alignment of the co-complex network we see a big improvement in the fraction of true positives. only a small subset of yeast and human proteins is part of a co-complex network within each species. moreover, many of those are not functionally linked to proteins that have readily identifiable orthologs in the other species. as a consequence, this method is applicable to only a small fraction of query-hit pairs. if we include high-throughput co-complex datasets for yeast and human, the coverage is increased a little at a cost of a slightly inferior performance. each row contains the number of query-hit pairs and the number of distinct human query proteins in a particular e-value bin, for all blast hits and the subset of blast hits which falls into the'co-complex network alignment' category. we show that alignment of co-complex networks can facilitate the identification of true homologs among gray zone blast hits. in a simple and completely automated procedure, we obtain a subset of hits which, despite very high e-values, is substantially enriched for homologs. this allows us to infer homology for pairs with co-complex network alignment with an e-value ranging between and with the similar confidence as for pairs before co-complex network alignment and an e-value of. our framework would likely be improved if we could use statistics on missing connections in both co-complex networks. to date, protein complex datasets are too fragmentary to make any sensible estimates of the number of missing connections. detection of missing complex subunits previous large scale investigations towards presence and absence of protein complex subunits in prokaryotes and eukaryotes reveal that most complexes are only partially present in other species. in these studies, an orthology definition based on blast is used to determine presence and absence of subunits in different species and part of the subunits regarded absent may be missing due to detection problems. hence the disrupted co-evolution of protein complexes might partly be an artefact. the use of co-complex information is potentially useful in the detection of yeast homologs of subunits of human protein complexes. especially as the most important disadvantage, the lack of coverage of the co-complex networks, is less urgent because the queries are subunits and hence are all part of the human co-complex network. we take the opportunity to test the applicability of our method to a problem in comparative genomics and assess the added value of co-complex network alignment in detecting homologs in yeast for subunits of human complexes. for the complexes in the corum dataset, we initially find homologs for complex components by running a blast search with all subunits against the yeast proteome, applying a commonly used e-value cutoff of. then, for the subunits we did not find homologs for, we use a less stringent e-value cutoff of in combination with co-complex network alignment, to see how many additional subunits we pick up. using blast only with an e-value cutoff of, we find yeast homologs for out of subunits. we find that out of complexes have a homolog in yeast for all subunits, have homologs for some subunits and complexes are completely absent. even when only comparing two species, we find that for most human complexes, only part of all subunits have a homolog in yeast. however, as we have argued before, some subunits may be called absent due to detection problems. for the subunits for which we detected no homolog in yeast, we select, using the co-complex network alignment, candidate homologs in yeast for additional subunits, belonging to complexes. using pfam, cdd and psi-blast, we confirm that the out of candidates recovered with co-complex network alignment are in fact homologous. with the confirmed homologs we retrieved, an additional complexes are completely present in yeast. one striking observation when comparing individual complexes in human to complexes in yeast, is that there is very little congruence between human and yeast complex definitions. factors such as the incompleteness of data in both species, individual decisions on what does belong to a complex and what does not, and proteins belonging to multiple complexes, obscure a one-to-one relation between yeast and human complexes, assuming such a correspondence exists. fortunately, because we align human and yeast complexes on a network level rather than as individual complexes, we are able to retrieve homologs with the co-complex network alignment for complexes which do not exist as such in yeast. a good example is the multisynthetase complex. this complex is composed of aminoacyl-trna synthetases and auxiliary proteins. the individual trna synthetases all have a homolog in yeast found with the initial straightforward blast search. the yeast homologs of the trna sythetases are not known to be organized in a complex, with one important exception: methionyl and glutamyl synthetases mes and gus associate into a complex with arc an auxiliary protein which increases catalytic efficiency and ensures correct localization into the cytoplasm. via this complex, human jtv a scaffold required for the assembly and stability of the multi-trna synthetase complex, is linked to a short n-terminal stretch of yeast gus whose c-term is unambiguously homologous to the glutaminyl synthetase in human, qars. when we do a psi-blast with human jtv as a query protein, we retrieve gus aligned to the gst_c domain in jtv after three iterations. we recovered a homolog for another subunit of the multisynthetase complex via an unrelated complex: the ribosome. human eef1e has a hit with yeast efb with an e-value of. efb is located at the ribosome, as is yhr020w, which is the readily identifiable yeast ortholog of the human bifunctional glutamyl-prolyl trna synthetase eprs. both efb and eef1e are translation elongation factors and both contain a domain which belongs to the gst_c_superfamily. the hsp lies in the regions where the gst_c_superfamily domain lies in both proteins and these regions in the protein sequences are, albeit very distantly, evolutionary related. efb has a much more similar homolog in human, suggesting that eef1e and efb are related through a very old duplication event and the translation elongation factor epsilon eef1e ortholog is lost in yeast. applying the co-complex network alignment to the set of protein complex subunits in corum, we select candidate homologs in yeast for proteins, out of which we could confirm homology with pfam, cdd or psi-blast for pairs. the observation reported in both large and small scale investigations, that most complexes are'incomplete' in many species, remains unchallenged because we can only show for a few complexes that their incompleteness is a result of an undetected homology are the recovered distant homologs orthologs? exploiting the co-complex network alignment we find yeast homologs for subunits of human complexes that are not revealed by standard blast. this is markedly less than the human queries for which co-complex information is applicable. the likely crucial difference between our initial survey of all blast hit pairs and the detection of missing complex subunits is the fact that in the latter, we applied the co-complex alignment only to those query proteins for which we could not find a homolog with blast alone. therefore we expect that many query proteins for which we recover a distant homolog with the co-complex network alignment in the initial survey, have an additional, significant hit in yeast and are therefore not used as a query when looking for additional homologs for complex subunits. indeed, we find that this is the case for no less than 85% of the query-hit pairs with an e-value >. there are a few possible evolutionary histories that can explain the fact that for a certain query protein in human, we find a close homolog and a distant homolog with conserved functional context in yeast. first of all, distant homologs recovered by co-complex network alignment could be ancient paralogs, in which the high degree of divergence is due to time rather than rapid sequence evolution. for instance, eef1e and efb in the multisynthetase example discussed above are ancient paralogs. another possibility is a more recent duplication in yeast followed by asymmetric divergence in the duplicates, in which case the divergence is caused by accelerated evolution on one branch. finally, the two yeast hits may be homologous to different regions of the query protein due to fusion, fission or domain recombination events, in which one domain/region has a markedly higher rate of sequence evolution than the other. in the fusion/fission/domain recombination scenario, the two yeast hits of the human query protein in yeast are not homologous. for of our trios the two yeast hits are not a significant hit in blast, neither do they share a homologous domain according to pfam. for of these trios the best scoring blast hsp of the two yeast proteins is in a different region in the human protein. in the remaining two pairs, the distant homologs that we retrieve share only a short kow motif with the query protein, while the best hit shares both the kow motif and also the adjacent ribosomal l27e domain. if we consider only those trios of proteins in which the two yeast proteins are homologous according to pfam, we find that in of them, the distant homolog has a significant hit in human, suggesting it is in fact an ancient paralog. a recent study towards the fate of duplicated protein complex subunits showed that 31% of duplicates resides in different complexes, 31% stayed in the same complex and in 38% of the cases one of the duplicates is not known to be part of any complex. we investigate the fate of the yeast pairs that are outparalogs according to our analysis. the yeast pairs are not a random sample of ancient yeast duplicates, on the contrary. because one of the yeast paralogs is a close homolog of a human protein which is part of a complex which is homologous to the complex the other yeast paralog is part of, we expect a bias towards duplicates remaining in the same complex. we find that for pairs, both duplicates are in the same complex, for pairs the duplicates are in overlapping complexes, for pairs they are in a different complexes and for pairs one of the duplicates is not known to be part of any complex in yeast. we expect that the human homologs of the pairs in which the yeast ancient duplicates belong to distinct complexes, are more often part of multiple complexes, indicating that the yeast duplicates subfunctionalized. we do observe a significant overrepresentation of proteins that are part of multiple complexes in ancient paralogs when compared to all subunits in the corum complex dataset, but not in ancient paralogs which are part of the same complex when compared to those which have ended up in distinct complexes. the lion's share of distant homologs we recover using the co-complex network alignment consists of ancient paralogs rather than orthologs. duplications in general are very important in the evolution of protein complexes and many structures are known to consist of subunits resulting from very old duplications. we find that in most cases both duplicates are part of the same or overlapping complexes. this suggests that the duplicates we detect have sub- or neofunctionalized within one complex, although some might be the result of outparalogs that have been independently recruited to a biological process.  we test whether contextual information from the functional network, in this case conserved co-complex relations, can aid homology detection. functional context information has been used before to help in choosing functional orthologs from a set of inparalogs, but to our best knowledge, this is the first time functional networks are used to aid distant homology detection. using an aligned co-complex network, we can identify a subset highly enriched for homologs of blast hits with an e-value which would normally be regarded as insignificant. this shows that, even though evolution takes place at the sequence level, one can use co-complex networks as circumstantial evidence to improve confidence in the homology of distantly related sequences. the interspecies co-complex network includes only a small fraction of all proteins, which impedes applicability. as more high-throughput datasets become available in more species, we expect that the proof of principle we established here, can be applied and tested on a larger scale, between more distantly related species and with other types of functional relations. we apply our co-complex network alignment to a dataset of human complexes in order to determine how many homologous subunits we can detect that we missed in an initial blast search. we thereby recovered homologs for only a few additional subunits, despite the fact that coverage is less a limiting factor in this context. we find that one reason we retrieve less additional subunits than expected, is that with the co-complex alignment, we mainly detect outparalogs rather than orthologs. it has been shown that subunits of a protein complex diverge at similar rates, presumably because subunits of a protein complex are functionally strongly interdependent and subject to very similar evolutionary constraints. in contrast, the co-complex network alignment method is based on the fact that some subunits diverged between human and yeast to such an extent that they are not picked up in a regular blast search and other subunits are conserved such that the human and yeast orthologs are still detected by inparanoid. in this light it is not surprising that most homologs we recover with our method are ancient paralogs rather than orthologs: the difference in the extent of divergence is due to difference in time, as opposed to difference in evolutionary rates between subunits of the same protein complex. researchers studying the evolution of individual protein complexes have used functional information to find diverged homologs successfully despite absence of proof from a large scale study. our results provide this proof. numerous predictions made in these small scale studies were subsequently confirmed by profile vs profile alignments or the comparison of protein three dimensional structures upon availability. interestingly, many of these predictions represent initial blast hits with e-values even higher than. hence it is possible that in our study still many homologs have gone undetected, and the formal integration of functional context with more sensitive homology detection methods might help in the development of automatic bioinformatic methods to uncover these distant homologs and improve our insights into the ancient evolution of the protein interaction network. 
analogous to the use of the genomics context in genome alignments, we test whether conserved functional context can be used to select candidate homologs from insignificant blast hits. usually a stringent score cutoff is applied to distinguish putative homologs from possible false positive hits. as a consequence, some blast hits are discarded that are in fact homologous. the algorithm probably most widely used for homology detection in comparative genomics, is blast. homology is a crucial concept in comparative genomics. we make a co-complex network alignment between complex subunits in yeast and human and find that proteins with an insignificant blast hit that are part of homologous complexes, are likely to be homologous themselves. further analysis of the distant homologs we recovered using the co-complex network alignment, shows that a large majority of these distant homologs are in fact ancient paralogs. our results show that, even though evolution takes place at the sequence and genome level, co-complex networks can be used as circumstantial evidence to improve confidence in the homology of distantly related sequences.
 homology is a crucial concept in comparative genomics. the algorithm probably most widely used for homology detection in comparative genomics, is blast. usually a stringent score cutoff is applied to distinguish putative homologs from possible false positive hits. as a consequence, some blast hits are discarded that are in fact homologous.  analogous to the use of the genomics context in genome alignments, we test whether conserved functional context can be used to select candidate homologs from insignificant blast hits. we make a co-complex network alignment between complex subunits in yeast and human and find that proteins with an insignificant blast hit that are part of homologous complexes, are likely to be homologous themselves. further analysis of the distant homologs we recovered using the co-complex network alignment, shows that a large majority of these distant homologs are in fact ancient paralogs.  our results show that, even though evolution takes place at the sequence and genome level, co-complex networks can be used as circumstantial evidence to improve confidence in the homology of distantly related sequences. 