BACKGROUND
high-throughput detection of protein-protein interactions  has long been one of the most intensively studied areas in systems biology.
currently, recent progress in experimental techniques, such as the yeast two-hybrid  method or tandem-affinity-purification method coupled to mass spectrometry   <cit> , has allowed the compilation of massive data set for protein interactions of the budding yeast, saccharomyces cerevisiae .
from the vast amount of ppi data, protein interaction networks  have been vigorously investigated.
in pin, proteins are represented as nodes, and two proteins are linked if they interact with each other.
basic topological measures, such as a degree , and their correlations are adopted to explain various properties of proteomes.
for instance, a degree in pin is the number of partner proteins with which an individual protein interacts.
one of the earliest achievements is the heavy-tailed degree distribution  and its importance in characterizing the essentiality of proteins  <cit> .
in addition, there have been further explorations on the negative degree-degree correlation profile  related to the modular structure of protein interactome  <cit> .
models for pin have been developed by incorporating such characteristics  <cit> .
in this way, it has been witnessed during the last decade that studies on complex networks  <cit>  play a great role in characterizing such interacting entities, and the term "network biology" was coined to refer to networks whose nodes correspond to proteins, metabolites, genes, etc  <cit> .
in spite of such recent progress, there are shortcomings of that type of simplified network representation of ppi in that detailed mechanisms or higher structures of interactions are often neglected.
most of all, only the pairwise binary interactions between two proteins are considered in ppi, and they are not sufficient to capture real biological processes involving a stable form of proteins grouped according to their biological functions.
for instance, two proteins a and b can be involved in a certain biological process by forming a linear chain with another protein c, such as a-c-b, without any direct contact between a and b. to overcome such problems, it is crucial to consider protein complexes, which are groups of proteins performing specific cellular tasks  <cit> .
in this paper, we focus on protein complexes and their component proteins in s. cerevisiae whose data set has been established through the recently developed tap-ms technique  <cit> .
we apply the concept of bipartite network  <cit>  to the protein complexes and proteins associated with them.
a bipartite network is composed of two types of nodes, and there exist links only between nodes of different types, as usually found in social "affiliation" networks, where individuals are joined by common membership of groups  <cit> .
in our case, protein complexes and their component proteins are the two types of nodes, and a complex is connected to a protein if the protein is one of the components of the complex, as shown in figure  <dig>  we construct the bipartite network and obtain its one-mode projections  <cit> , i.e., the weighted network of individual proteins  and the weighted network of complexes , where the weight on each link is given by the number of shared complexes or proteins, respectively.
the weighted network is an extension of complex networks, with additional information, weight, on each link, and has been investigated in the context of network theory  <cit> , including the metabolic network analysis  <cit> .
from this weighted network analysis, we can extract quantitative topological characteristics of the interrelationship among protein complexes and component proteins.
in this work, we analyze the distributions of degree and strength .
for both bipartite and projection networks, the distributions approximately follow the exponential distribution, while most pins in the literature are claimed to show more inhomogeneous degree distributions  <cit> .
furthermore, two classes of proteins denoted as "core" proteins and "attachment" proteins are shown to play different roles in the complex formation.
besides the aforementioned preliminary analysis on the structural properties of networks, as a main topic of our work, we suggest a new method for the systematic estimation on cellular abundance of protein complexes and the assignment of biological functions to them, as well as those of individual proteins.
for further researches, such as kinetic modeling of the cell, estimating the abundances and functions of complexes and component proteins can provide a much more quantitative description of behaviors in a cell than a list of protein interactions.
however, most of previous attempts about the assignment of unknown functions to proteins or complexes usually rely on local information.
for example, there is a method mapping the problem to the local-similarity-based potts model  <cit> , which is an intrinsically stochastic method and depends on a temperature-like parameter.
another previous work is a statistical argument based on hypergeometric tests, as in ref.
<cit> , but it also requires a specific external threshold and additional corrections to fit the data to biological reality.
in contrast, our deterministic method is based on the optimization problem related to the global organization of protein complexes, and yields a number of experimentally verifiable results.
from the results of the optimization, we cross-analyze the condition-dependent abundance and functions of complexes, which also supports the reliability of our method as well as our extensive statistical validation process.
all of these examples clearly show the effectiveness of our method, and we believe that this method has the potential to significantly stimulate further experimental studies.
methods
bipartite network representation of protein complexes
note that the bipartite network itself is not a weighted network, while the protein-protein and complex-complex networks are weighted ones, based on the information provided by the bipartite network.
similar approaches have been presented in previous works  <cit> , with older datasets  <cit> .
for instance, mashaghi et al.
<cit>  used a similar approach, but we consider all three kinds of networks, while ref.
<cit>  dealt only with the bipartite network and the complex-mode projection.
in addition, we use a weighted version of one-mode projections in this work, while the unweighted one-mode projection networks were considered in the previous work  <cit> .
we analyze the basic statistical characteristics of these three networks, using the methodology derived from a decade of complex network studies  <cit> .
the dataset of protein complexes and their component proteins in s. cerevisiae is listed in ref.
<cit> , where significant overlaps  among protein complexes make it possible for us to analyze the interconnected network structure, and determine the abundance and functions.
in ref.
<cit> , gavin et al.
use the tap-ms technique  <cit>  to generate the list of protein complexes and their component proteins.
the proteins in each complex are classified as cores and attachments, according to their significance in the formation of specific complexes.
we will discuss the different roles of core proteins and attachment proteins later on.
the datasets consist of  <dig> protein complexes and  <dig>  component proteins, among which  <dig>  proteins participate in complexes as cores and  <dig>  proteins as attachments.
therefore,  <dig> proteins are used as both cores and attachments.
estimation of complexes' abundance based on optimization
proteins interact with each other and form complexes in order to perform specific biological functions.
naturally each protein complex executes specific biological functions with its characteristic composition of component proteins, and the identification of such functions and abundance in terms of complexes is important.
unfortunately, such exact identification of complexes' functions and estimation of their abundance is far from being complete.
only heuristic methods, using local  interaction of proteins, were used in previous studies  <cit> , and there were some limitations, such as the arbitrarily specific values of threshold.
in this section, we present our new optimization method to determine the abundance and function of protein complexes, based on the information of their global organization.
estimation of abundance would be especially crucial, and is directly applicable to various works, such as setting up kinetic models that involves proteins, by providing reaction coefficients.
suppose that the copy number of protein i  and the number of complex j  are given by pi and cj, respectively.
also, let us denote the number of protein i in the complex j as sij, where sij =  <dig> if the complex j does not harbor the protein i as its component.
then, in an ideal situation where all the abundances or concentrations of proteins in a cell correspond to the exact amount to be used in forming a complex, similar to the approach used for kinetic modeling in  <cit> , the variable sets {pi} and {cj} satisfy
the question is how to determine {cj}  with known values of {pi} and {sij} .
however, since the number of proteins n is larger than the number of complexes m, the set of linear equations above is over-determined, and we assume that in reality it is not feasible to satisfy all the equations in eq.
.
in practice, therefore, we assume that the number of proteins in a cell should be greater than or equal to that necessary to form complexes, i.e., , which is the basic constraint of our optimization scheme.
therefore, instead of looking for an exact solution satisfying eq.
, we try to minimize the deviation from the ideal situation in eq.
, given by
where the summation is only for indices i where pi >  <dig>  now, for the given values of pi and {sij}, our basic strategy is to determine cj values that minimize da in eq.
, and this problem is numerically solved by the linear programming  technique.
moreover, after the determination of cj values, if some values of pi are unknown, we can assign those values of pi using eq.
for the ideal situation.
this optimization is based on an assumption that organisms have been evolved in a way that increases efficiency by reducing wasted resources.
we use the abundance data of yeast proteins {pi}, in ref.
<cit> , because the datasets for both rich  and minimal  media are available, and we exploit those conditional changes of abundance later on for our analysis.
the values of {sij} are given by the list of protein complexes used in this work.
inference of complexes' biological functions based on optimization
for a functional annotation of complexes, we consider the following optimization scheme.
suppose fpik =  <dig> if protein i performs a function k  and fpik =  <dig> otherwise.
similarly, fcjk =  <dig> if complex j performs a function k and fcjk =  <dig> otherwise.
the organization of protein complexes is given by uij, where uij =  <dig> if protein i is a component of complex j and uij =  <dig> otherwise .
in this case, the constraint is given by
meaning that every function assigned to a protein must be assigned to at least one of the complexes in which the protein participates, which is reasonable, based on the assumption that each biological function is usually expressed cooperatively in the form of protein complexes.
we are aware that our dataset of proteins and munich information center for protein sequences  database  <cit>  are not exhaustive, so the outcome is not a perfect functional catalogue.
however, since our method itself is stable and resilient, as we demonstrate later on the validation part, the result will become more accurate as the input dataset becomes more reliable.
even if there are some errors and exceptions, such as single proteins not being included in our complex datasets, we emphasize that, based on notable examples presented later, our method clearly produces biologically significant results.
our criterion used for the optimization process is to assign the most definite functions to each complex.
in other words, we try to find functions that are inevitably assigned among all the other solutions satisfying the constraint , in the "safest" way.
in the spirit of parsimony, we minimize the number of complexes assigned with each function.
mathematically, this corresponds to minimizing the following quantity for each k:
therefore, our strategy of determining each protein complex's functions is determining {fcjk} which minimizes either eq.
under the constraint , with the given values of {fpik} and {uij}.
note that all variables and constants in this case are integer values, in contrast to the abundance estimation.
this optimization problem is numerically solved with the mixed integer programming  technique.
after determining the {fcjk} set, similar to the case of abundance case, we can conjecture the function of protein i as k, if ∑j uij fcjk ≥  <dig> while fpik =  <dig>  because the protein i is considered to perform the function k by participating in at least one of the complexes to which the function is assigned.
the function assignment of proteins, i.e., {fpik} is available from various sources, such as mips  <cit>  or the yeast genome database  <cit> , and the values of {uij} are given by the list of protein complexes used in this work so far  <cit> .
we use the mips database for the initial function assignment of individual proteins, which is set {fpik}, because its hierarchical organization of functional catalogue   <cit>  helps the systematic interpretation of results in different hierarchical levels.
we would like to emphasize that our method, for the first time, systematically assigns multiple numbers of functions to all the complexes in the genome-wide scale, without any free parameter or initial condition dependency, in contrast to other previous methods  <cit> .
there is a certain degree of resemblance between our method and the message passing algorithm, such as the belief propagation   <cit> , in inferring or assigning  properties to variables in bipartite graphs.
for instance, the message from a variable node v to a factor node u in bp is analogous to assigning function or abundance of complexes , and the following process of message passing from u to v corresponds to assignment to proteins with previously unknown functions or abundance.
we can even consider the configuration of object functions in eqs.
as the "energy landscape" of constraint optimization problems, where methods like bp play important roles.
in spite of this analogy, there are significant differences as well.
first, our method is designed to deal with a specific type of problems composed of the set of factor nodes with no a priori information and the set of variable nodes with information except for a small fraction of unknown cases.
second, and more importantly, in contrast to bp, where the local flow of inference is used, our method is based on global optimization of object functions.
in this respect, the previous works using local or bayesian inference to assign protein functions  <cit>  are similar to the message passing algorithm than our method.
of course, finding deeper mathematical analogy between our method and such traditional inference algorithms would be certainly interesting, but that would be beyond the scope of this paper.
RESULTS
statistical properties of the bipartite and one-mode projection networks
first, we construct the bipartite network without distinguishing between core and attachment proteins.
as mentioned in the 'methods' section, the bipartite network consists of  <dig> complexes and  <dig>  proteins as its two different types of nodes.
the average degree of complexes  is  <dig>  , and the average degree of proteins  is  <dig>  .
figure  <dig> shows the degree distributions of the bipartite network, where we separate the distributions for complexes and proteins since they are different types of nodes.
as shown from the fitted curves in figure  <dig>  the degree distributions for both kinds of nodes are much closer to the exponential distribution p ~ exp  than the power-law distribution, because the cumulative distribution p of the exponential distribution p ~ exp also follows the exponential distribution from the relation , in the continuum limit.
two complexes, denoted as complexes  <dig> and  <dig> in ref.
<cit> , include prominently many component proteins, especially including proteins affiliated to the ribosome, as shown in table  <dig>  the two proteins, with the maximum connectivity  <dig> in the bipartite network, are rps22a and rpl36b, which are ribosomal proteins  <cit> .
the annotated complexes in ref.
<cit>  are following: *u <dig> snrnp complex, †prp19-associate complex, **ribosome-associate complex , ††translation initiation factor eif <dig> complex, •complexes assigned as 'ribosomal proteins' function, ••trna modification function, and •••fatty acid metabolism and aromate anabolism predicted by our optimization method .
one-mode projections of our bipartite network represent interactions or relatedness among complexes and individual proteins.
in the complex-mode projection, intuitively, two complexes are considered to be related if they share proteins, and the "intensity" of their relatedness, the number of proteins they share, is quantified as the weight.
similarly, in the protein-mode projection, two proteins are thought to be related if they participate in common complexes, due to the fact that proteins perform a biological function as a unit of the protein complex.
because more than two proteins can be cooperatively involved in the protein interactions, investigating protein interactions from the formation of complexes has its own advantages over other methods using only the pairwise interactions, such as the y2h method  <cit> .
the degree distributions of the complex-mode projection shown in figure  <dig> and the protein-mode projection in figure  <dig> show the exponential distribution.
the strength si of a node i in a weighted network is defined as  <cit>
where wij is the weight of the link connecting the node i and j, and vi is the set of neighbor nodes of i. it can be considered as a natural extension of the degree of a node in weighted networks, and the strength distributions of our weighted complex-complex and protein-protein networks are shown in additional file  <dig>  figure s <dig>  the strength distributions are also closer to the exponential form, rather than the power-law distribution observed in many other biological and other real-world weighted networks  <cit> .
it is true that the maximum degree  of complex-mode projection network is very large, considering the number of nodes , but this is merely due to the large connectivity  of distribution, not to the "scale-free" functional shape.
although the notion of hub, referring to nodes with many connections to others, in the exponential degree distribution is not as strong as in the power-law degree distribution, we can still identify nodes with relatively large degrees and strengths by examining the "tail" part of the distributions.
table  <dig> lists the complexes and proteins with the ten largest degree and strength values in both the bipartite and projection networks.
again, the ribosome-associated complex  is a notable example annotated in the datasets  <cit> .
other unknown complexes with large degrees and strengths also include many ribosomal proteins  as their components.
some ribosomal proteins have the largest degrees and strengths in the protein-mode projection as well, e.g., rpl33a, rpl <dig>  rpl16b, and rpl26b  <cit> .
the fact that many complexes and proteins with largest degrees and strengths are affiliated to the ribosome can be interpreted in two ways.
one hypothesis is that because the ribosome is involved in the production of proteins, ribosomal proteins might be promiscuously attached to many unspecific complexes.
the other is that ribosomal complexes are usually large and composed of many ribosomal proteins, which implies the genuine property in this case.
to determine which hypothesis is more plausible, we have manually checked the complexes in which those proteins are involved and found that most component proteins of those complexes are also ribosomal proteins, which supports the latter hypothesis.
for instance, complexes  <dig>   <dig>   <dig>  which have the three largest degree  in the bipartite network, are all assigned with 'ribosomal proteins' from our optimization method.
we note that in some previous works, the ribosomal proteins are considered as non-specific contaminants involved in promiscuous interactions and filtered out, for example, in ref.
<cit> .
however, our dataset from ref.
<cit>  already passed the stringent test based on socio-affinity index, taking into account the frequency of proteins within the dataset and naturally discriminating true from spurious interactions  <cit> .
we believe that the criterion used in ref.
<cit>  can be more systematic and reasonable than the "3% rule" used in ref.
<cit> , so the statistics related to the ribosomal proteins may actually be reflective of the biological reality.
however, it would also be meaningful to mention some non-ribosomal complex/proteins with such large degree/strength values.
therefore, we have identified other examples such as complexes assigned with trna modification function, fatty acid metabolism, and aromatic anabolism from our optimization method among the top  <dig> largest complexes and indicated in table  <dig>
the exponential distribution is different from the earlier notion of the power-law degree distribution of pin  <cit> , but the power-law distribution for pin has been contested by number of researches as well  <cit> .
statistically, the diversity of degrees and strengths in the complex-complex and protein-protein networks is less than that of pin.
therefore, we conclude that the existence and strength of interactions with other proteins for each protein in terms of participation in protein complexes are less diverse than those for the pairwise interactions.
these exponentially-decaying distributions are in contrast to the results from earlier works on biological networks  <cit> , but recent studies suggest the different frameworks of assessing the protein interactions.
it turns out that these homogeneous distributions correspond to the stable complex formation.
for example, in a recent "benchmark" paper by yu et al.
revealed the intrinsically different natures of detected interactions from the y2h for detecting more transient and condition-specific interactions and mass spectrometry  methods for detecting stable protein complexes  <cit> , which can support our findings of the exponential distribution of degrees, in contrast to the power-law distribution for pin from the y2h method.
to be more specific, the detection of complexes with tap-ms method used in our data corresponds to the ms technique, which is basically to detect "prey" proteins with the "bait" proteins so the collection of prey proteins is considered as an entity of interactome, in contrast to y2h method using 1: <dig> pairwise screening.
the differences between the "spoke model"  and "matrix model"  described in ref.
<cit>  are also a good mechanism causing the different kind of distributions.
interestingly, there are lots of proteins having more than  <dig> neighbors in the projection network as shown in figure  <dig>  while the recent pin analysis shows the maximum degree less than  <dig> in spite of their power-law distribution  <cit> .
here we do not claim that our finding is in conflict with the previous studies on the binary ppi, but that this projection network based on tap-ms complex data clearly reflects fundamentally different type of interactions in the yeast proteome, as well-documented in ref.
<cit> .
the exponential or at least "bounded" degree distribution of complexes in the bipartite network can be thought to originate from, for example, the "crowding effect" in a cell.
cytoplasm of a cell is occupied by various macromolecules such as enzymes, whose concentration cannot be further increased without affecting protein-protein association or transport dynamics  <cit> .
specifically, there should be a limit in the available cytoplasmic volume a complex can take, and thus the number of component proteins it can bear within the limited physical space.
also, it is empirically observed that the number of complexes a protein can participate in  is limited as well.
for the exponential degree distributions for both parties in the bipartite network, the projected networks' degree distributions actually turn out to be exponential-like unless there are nontrivial correlations, because each party's degree distribution mainly determines the projected network's degree distribution as shown in ref.
<cit> .
we have derived more rigorous proof of this fact by adopting a similar technique to ref.
<cit> , where the generating function for the degree distribution is used to derive the degree-degree correlation for projected networks.
it is straightforward to calculate the generating function of the projected protein network's degree distribution given by
where the degree distributions of proteins and complexes in a bipartite network are given by pprotein ~ exp and pcomplex ~ exp and there is no degree-degree correlation , which we have checked that as a reasonable assumption from our dataset, by the way.
the resultant degree distribution of proteins in the projected network is calculated with the formula  and we numerically check that the distribution is indeed very close to exponential one for k ≫  <dig>  as shown in additional file  <dig>  figure s <dig>
one may argue that it is hard to tell something about the distribution with the limited number of datasets, but in any case, we can safely exclude the power-law distribution from fitted curves from figures  <dig>   <dig> and s <dig>  also, we emphasize that our dataset from the tap-ms method, modified to successfully overcome the membrane protein under-representation problem  <cit> , is fairly genome-wide.
even if there might be missing proteins or complexes as a result of experimental limitation of detecting heterodimer complexes, the degree distribution would not be severely affected by sampling.
in a previous work including pin data  <cit> , we showed that the functional form of degree distribution is conserved under sampling up to quite a low sampling fraction.
in this respect, we conclude that the different type of distribution in this case reflects the actually different characteristics of the binary interaction and the interaction as forming complexes.
to check this property of network statistics in case of other organisms, we use the list of protein complexes of escherichia coli  data  <cit>  and human protein reference database   <cit> .
first, since the e. coli dataset defined in ref.
<cit>  does not provide any overlapped component protein between complexes, we observe only the degree distribution of complexes, meaning the number of component proteins each complex has.
it is difficult to reach a definite conclusion of the distribution's functional form with a very small range of degree values, but the maximum degree is less than  <dig> and the argument of crowding effect seems to hold here as well .
in hprd datasets, there are both the list of protein complexes and binary ppi, which allows the comparative analysis.
as a result, the degree distributions of complexes and proteins in the bipartite network are less broad than the ones in the binary ppi , which indicates a similar result to our s. cerevisiae dataset.
the degree distributions of the bipartite network of hprd themselves do not seem to follow the exponential distribution, though, and we suspect that this difference may stem from the fact that hprd dataset is basically manual literature mining of small-scale experiments, not the result from a systematic high-throughput experiment.
on the other hand, if the degree distribution from hprd reflects biological reality rather than such sampling biases, we suppose that the relatively large size of mammalian cells may "relax" the aforementioned macromolecular crowding effect, thereby enriching the tail part of the degree distribution, compared to the case of yeast cells.
distinction between core and attachment proteins
the list of component proteins for each protein complex is divided into two groups, cores and attachments in ref.
<cit> .
the "standard" complex-protein dataset is selected in terms of best accuracy and coverage in a set of manually-curated complexes, but there can be other possible variations of complex-protein sets if the threshold of accuracy and coverage for clustering becomes more flexible.
these variations in reasonable ranges are denoted as "isoforms," and whether a protein is core or attachment is determined by the participation ratio in the isoforms.
in other words, proteins present at a certain complex in a significant portion of the isoforms are classified as core proteins of that complex, and denoted as attachment proteins of that complex otherwise.
note that the entire set of proteins is not exactly partitioned into two groups, because a core protein for a complex can be an attachment protein in another complex.
in fact, as mentioned in the 'methods' section,  <dig> proteins among the total number of  <dig>  proteins act as both cores and attachments.
core proteins seem to bind more rigidly, and form the basic unit of a given complex.
if only the core proteins are considered to construct the bipartite network for complexes and proteins, the average degree of core proteins in the bipartite network is  <dig> , and most  proteins participate in only one complex, while the largest degree is only  <dig>  on the other hand, when considering only attachment proteins, the average degree of attachment proteins in the bipartite network is  <dig>  and the largest degree is  <dig>  the average degree is  <dig>   in case of all proteins, and from this comparative analysis we can observe that core proteins are much less promiscuous than the attachment ones.
the degree distributions of proteins for both cases are closer to the exponential distribution, as shown in figure  <dig>  this quantitatively different participation pattern suggests that the core proteins in a protein complex act as its "skeleton" and the attachment proteins play the role of "seasoning," because attachment proteins are likely to participate in the formation of a relatively large number of complexes.
one-mode projections, when only core proteins or only attachment proteins are considered, are shown to have exponential degree and strength distributions for both complex-mode and protein-mode projections, similar to the case without the distinction between those two kinds of proteins.
different roles of core and attachment proteins are also reflected in the clustering structure of complex-mode projection network.
if only the core proteins are considered, the complex-mode projection network is composed of  <dig> separate connected components, which is a highly fragmented configuration.
thus, core proteins are important as a stable component for individual complexes, rather than a mediator which "binds" complexes together.
on the other hand, if only the attachment proteins are used to bond complexes, one single giant component emerges, except for a single tiny component with only two complexes.
this small component is also merged into the single giant component if we consider both core and attachment proteins.
as a representative example, we present the exosome 3'-5' exoribonuclease complex  which contains all the core components of ski complex  as attachments, supporting previous works that the association is necessary for cytoplasmic messenger rna 3'-to-5' decay  <cit> .
therefore, the attachment proteins  indeed specify a particular function for the exosome complex.
inference of abundance and functions: statistical validation
there are core and attachment proteins, as stated and analyzed in the previous subsection.
to make our predictions as conservative as possible, we adopt the following scheme about selecting core and attachment component proteins.
for the abundance estimation, we consider only the core proteins as components of complexes, based on the fact that the core proteins play the role of the skeletons as previously mentioned, i.e., unlike the attachment proteins shared by relatively large number of complexes which can overestimate the number of complexes.
in other words, we expect that utilizing only the core proteins leads us to a more accurate estimate of the abundance.
in contrast, both the core and attachment proteins are used in function assignment of complexes.
in this way, it allows more alternative ways of function assignments, and if a function is assigned in spite of all those possibilities, we can consider it to be a genuine function, with more certainty.
however, in case of assignment of previously unknown functions to proteins after the function assignments for complexes, only core proteins are considered instead, reflecting the fact that the proteins' main biological functions are achieved by participating as core components.
finally, we remark that the {sij} matrix for abundance estimation is approximated by {uij} matrix, due to the limitation of available information.
however, note that more and more accurate datasets will become available in the future, and applying our method for those new datasets would be straightforward.
with the lp and mip method, we have numerically solved the optimization problems to obtain the abundance  and functions  of complexes and their component proteins.
as the input datasets for individual proteins, we use condition-dependent abundance  of proteins  <cit>  and the mips functional database for individual proteins  <cit> .
in total,  <dig> different mips funcat functions are assigned to our individual protein set.
since the mips funcat classifications are hierarchically organized  <cit> , we can divide the set of functions into more coarse-gained "functional categories" from their higher level hierarchy to observe more general trends, as demonstrated in the next paragraph.
before we apply the method for the main result, we have divided the known input datasets into several training and test sets and verified its effectiveness for various settings.
the full results for our function assignments for both complexes and proteins are available .
note that we also present an alternative optimization method in additional files, denoted as 'gavin_2nd' in additional file  <dig>  table s <dig> and additional file  <dig>  table s <dig>  minimizing the number of proteins for each newly assigned function, instead of the number of complexes described in eq.
.
the mip method does not produce a unique solution in general, and there can be multiple numbers of solutions.
among those solutions, we select high confidence  outcomes among the original outcomes  from our method.
in other words, hc outcomes contain only the functions which are assigned to complexes and proteins, in all the multiple solutions.
to check the accuracy of our method, we first divide the set of proteins with known values of abundance into training and test sets.
assuming that the values of abundance for the proteins in the test set are unknown, we estimate the abundance for those proteins in case of rich media   <cit>  and compare them with real values.
we define the relative deviation as
then, we plot the ranked α values, compared to the ones for random pairing of estimated abundance and real abundance in additional file  <dig>  figure s <dig>  the real deviation values are always significantly smaller than those of random counterparts outside the error range, demonstrating the statistical significance of our results.
we have also observed the similar result for minimal media   <cit>  as well.
for the function assignment, we also divide the set of proteins with already-known functions into training and test sets.
assuming all the protein functions in the test set are unknown, we assign those functions based on our function assignment method; the results are shown in table  <dig>  we measure two complementary quantities to show both sensitivity and specificity, for both the raw outcomes and hc outcomes.
from the results, we conclude that our method works reasonably well, especially for hc outcomes, considering the noise level of this kind of high-throughput dataset.
one remarkable thing is that our method works quite well for a very small fraction of training set such as 20% for both abundance estimation and function assignment, and this fact implies that highly interconnected relationship among proteins via complex membership greatly helps us to correctly assign functions.
to compare our results with a recent function assignment scheme, we adopt the hypergeometric test used in ref.
<cit>   and applied the method with the same threshold  to our dataset.
note that the result obviously depends on the threshold value, and also the original cyc <dig> method does not include the "re-substitution" process of copying functions from complexes to their components.
therefore, we have to combine our re-substitution process after the cyc <dig> procedure for function assignment for complexes.
the compared results  clearly show that the performance of our method is better than or at least comparable to that of cyc <dig> in many cases, and especially the number of predicted functions itself is much smaller for cyc <dig> method.
to be more specific, 'fraction of proteins for our high-confidence  result' shown in the third column is always better than the cyc <dig> result in the fourth column, and even our raw result in the second column is better than cyc <dig> in case of large values of training set fraction p or at least comparable to each other for small p. the only case worse than cyc <dig> is the 'fraction of functions for our raw result' in the fifth column for small p, but this can also be overcome by using hc dataset in the sixth column.
therefore, we conclude that our global optimization method is much better at guessing the unknown protein functions, in terms of sensitivity or recall rate, let alone the problem of dependence on an arbitrary parameter, which is the wholesale e-value threshold for the cyc <dig> method.
here p is the fraction of training set.
*among all the newly assigned functions to the entire test set proteins, fraction of functions which are also on the original mips functional datasets.
†fraction of test proteins with at least one function assigned, which has at least one assigned function on the original mips functional datasets.
raw outcomes correspond to the original outcomes from our method, and high confidence  outcomes are the selected subset of them whose function assignments are invariant even if the multiple solutions are considered.
inference of abundance and functions: condition-dependent abundance with regard to functional categories
first, we show the average change of complexes' abundance depending on the condition , classified as each mips functional category in figure  <dig>  note that a complex can be assigned with multiple functions, so there are overlaps among different functional categories.
we believe that this cross-analysis of abundance and function assignment strongly supports the reliability of our method, in addition to the statistical test presented in the previous subsection.
from figure  <dig>  one can check that each functional category shows a unique pattern of the condition-dependent abundance changes.
the most notable case is the increased abundance of complexes doing metabolism in the minimal media compared to the rich media, indicating that many proteins induced in minimal medium are involved in the production of small molecules that cannot be taken up from the surrounding environment.
another notable category of increased abundance in the minimal media is the cellular communication.
for instance, the protein kinase complex  <dig> in additional file  <dig>  table s <dig> is significantly more abundant in the minimal media, and this result can be interpreted from the nutrient sensing role of component protein tpk <dig> involved in the cell growth via the ras-camp signaling pathway, at facing the nutrient starvation  <cit> .
also, the abundance of complex  <dig> in additional file  <dig>  table s <dig> is increased in the minimal media and one possible explanation is its component protein transketolase's  involvement in the pentose phosphate pathway of processing glucose 6-phosphate to produce ribose-5-phosphate, which can be demanded more in the minimal media  <cit> .
in contrast, many complexes with functions of cell cycle and protein synthesis tend to show decreased abundance in minimal media, indicating that many proteins induced in rich media are involved in cell growth and division.
a fraction of the complexes with each functional category, for three different ranges of abundance ratio changes, shown in figure  <dig>  also shows a similar trend.
our findings are consistent with the argument in ref.
<cit> , which discusses such effects on the individual protein level.
note that, however, the previous work in ref.
<cit>  is about individual proteins, while our results are about complexes, by which the real biological functions are expressed.
it indicates that the similar arguments are applied to abundance and functions of complexes.
inference of abundance and functions: other examples
from our results about the functional annotations for complexes, we find a number of intriguing examples.
for instance, both the complex  <dig>  whose core proteins are ste <dig> and ste <dig>  and the complex  <dig>  whose core proteins are bcy <dig> and tpk <dig>  are assigned with the cytoskeleton formation and signal transduction.
the relationship between the cytoskeleton proteins and the cell signal transduction is discussed in recent literatures  <cit> , arguing that the filaments of the cytoskeleton provide guiding tracks so that transport becomes more focused.
the core component proteins of those complexes we have found, ste <dig>  ste <dig>  bcy <dig>  and bcy <dig>  are also shown in ref.
<cit> .
another example is related to the shifting process from fermentation to respiration in yeast  <cit> , depending on the temporal order of environmental stimuli, such as osmotic pressure and heat shock.
as shown in additional file  <dig>  table s <dig>  there are complexes co-assigned with those functions related to the process such as complex  <dig>   <dig>   <dig> , and complex  <dig> .
our optimization scheme does not only give the systematic estimate of complexes' abundance and function assignment, but also conjecture previously unknown new functions to individual proteins, as stated in the 'methods' section.
table  <dig> shows biologically interesting examples from our results with manually curated references for validation.
for instance, the metabolic enzyme eno <dig> was not assigned with any functions related to the cell division, but assigned with the cell division functions as a result from our optimization technique.
an important point here is that, as we will demonstrate with eno <dig> in the next paragraph, we know exactly where the functions come from , i.e., by actually tracing the complex to which the function is assigned and looking for another component protein participating in the complex, as the "source" of the function.
reference  <cit>  refers to the case that the predicted functions are not given by the mips data  <cit>  so that the functions are not assigned initially, but found by our method and on the gene ontology  database  <cit> .
in this case, we consider go database as the validation source, similar to other references  <cit> .
in case of the protein eno <dig>  it participates in the complex  <dig>  as a core component, and the complex is involved in the cell division process .
the function assigned to that complex originates from another core component protein chs <dig> in the mips datasets.
the protein eno2's involvement in the cell division is also supported by a recent experiment  <cit> , showing that the overexpression of the protein significantly delays the progression of yeast cell cycle.
of course, the experimental results need to be carefully interpreted, since g <dig> arrest can also be made by perturbing proteins not directly involved in the cell division process, as exemplified by sko <dig> activating the pheromone response pathway  <cit> .
this type of evidence, therefore, may not be a sufficient condition for the direct involvement in the cell division process, but can be a necessary condition which hints the candidate targets for further investigation in a more elaborate way.
with such procedure, we find quite a number of examples indeed, as shown in table  <dig>  and suggest small-scale experiments to confirm the functional annotations of these proteins.
discussion
it is indispensable for the future of proteomics to understand the composition structure and interactions of protein complexes.
however, relatively fewer works about the protein complexes have been done in the genome-wide level, except for a few cases  <cit> , compared to works about pairwise ppi.
in this work, we have investigated and shown the applications of the interactions in the recently published protein complex database of the budding yeast  <cit> .
we have adopted the notion of bipartite network, which is suitable for the case where there are two kinds of elements and one of them acts as the set of components of the other.
by constructing the bipartite network with protein complexes and their component proteins, we have checked the degree distributions of complexes and proteins.
as results of the analysis, the degree distribution of the bipartite network asymptotically follows the exponential distribution.
the same is true for the degree and strength distributions of the one-mode projection networks as well.
interestingly, the resultant exponential degree distributions are different from the heavy-tailed distribution observed in most pairwise ppi networks.
many complexes and proteins with largest degrees and strengths are affiliated to the ribosome, allowing for the stable formation of large ribosomal complexes.
furthermore, we have shown that the core and attachment proteins in the datasets show different participation patterns in the formation of complexes, which illustrates the different roles in the complexes.
the most valuable contribution of our work is presenting the new optimization method without external tuning parameters to determine the abundance and function of protein complexes, along with the previously unknown properties of individual proteins, based on the information of their global organization.
the effectiveness of our optimization method is proved by various biologically relevant examples compared with experimental results.
since we provide the full results from our results as additional files, we hope our result can encourage other researchers to utilize it as their new dataset for deeper understanding of proteomics.
CONCLUSIONS
thanks to the rich proteomics datasets of s. cerevisiae, many genome-wide researches have been achieved.
analyses based on the protein complexes can open a door to a new understanding of how proteins interact and work in organisms.
important future works include more investigation about our bipartite  network topology, along with more systematic comparison with the conventional pin to see the detailed origin of the different form of the degree distribution.
ultimately, it is essential to perform the small-scale experiments to validate the results claimed by our new optimization method.
we hope this work can make a substantial contribution to this direction of research.
competing interests
the authors declare that they have no competing interests.
authors' contributions
shl, pjk, and hj conceived and designed the study.
shl collected the data.
shl and pjk performed the numerical simulation and statistical analysis, and analyzed the results.
shl, pjk, and hj wrote, read, and approved the final manuscript.
supplementary material
additional file 1
strength distributions of  complex-mode projection and  proteins-mode projection .
here, the strength in  corresponds to the sum of number of proteins shared with the neighboring complexes for each complex, and the strength  corresponds to the sum of number of complexes shared with the neighboring proteins for each protein.
the blue squares correspond to the cumulative strength distribution p = ∑s′ ≥ s p, and the pink lines and gray curves are the best exponential and power-law fittings, respectively.
click here for file
additional file 2
projected network's degree distribution from the generating function approach .
assuming that both protein and complex's degree distributions follow the exponential degree distribution p ~ exp, the projected network's degree distribution is numerically calculated with the generating function approach mentioned in the main text.
one can clearly observe that the degree distribution follows the exponential tail for k ≫  <dig>
click here for file
additional file 3
degree distribution of complexes in the bipartite network for e. coli protein complex data in  semi-log scale and  double-log scale .
here, the degree corresponds to the number of component proteins for each complex.
the blue squares correspond to the cumulative degree distribution p = ∑k′ ≥ k p.
click here for file
additional file 4
degree distribution of complexes and proteins in the bipartite network for human protein complex data, in comparison with the protein-protein interaction network .
here, a complex's degree  corresponds to the number of component proteins for each complex, and a protein's degree  corresponds to the number of complexes in which a protein participates as a component.
the degree distribution of proteins in the binary protein-protein interaction is shown as pink triangles, as a comparison.
click here for file
additional file 5
list of all the protein complexes with mips functions assigned by our method .
list of all the protein complexes with mips functions assigned by our method, where the core and attachment components are taken from ref.
<cit>  .
we classify each function into the following three categories.
gavin_1st : minimizing the number of complexes for each newly assigned function, described as eq.
in the main text.
gavin_2nd : minimizing the number of proteins for each newly assigned function, instead of that of complexes  the functions assigned by both  and  .
note that we only select high confidence  outcomes among the raw outcomes, whose reliability of function assignment considering the multiple solutions is large.
click here for file
additional file 6
list of all the proteins with mips functions newly assigned by our method .
list of all the proteins with mips functions newly assigned by our method , along with the ones from the mips database  which is used as "input function."
hc outcomes are selected as in additional file  <dig>  table s <dig>  sometimes the functions already annotated in mips and the ones assigned by our method are quite similar, and very different in some cases.
therefore, we suggest the latter case be worth investigating further, as we did in the main text.
click here for file
additional file 7
statistical validation of abundance estimation .
for each value of fraction of training set p, the relative deviation
is ranked and shown compared to its random counterparts .
the real deviation values are always on the left side  of the random counterparts outside the error range, which implies its statistical significance.
click here for file
additional file 8
statistical validation of the function assignment, in comparison with the hypergeometric test in ref.
<cit>  .
here p is the fraction of training set.
†fraction of test proteins with at least one function assigned, which has at least one assigned function on the original mips functional datasets.
*among all the newly assigned functions to the entire test set proteins, fraction of functions which are also on the original mips functional datasets.
raw outcomes correspond to the original outcomes from our method, and high confidence  outcomes are the selected subset of them whose function assignments are invariant even if the multiple solutions are considered.
click here for file
acknowledgements
this work is supported by the swedish research foundation  and the korean systems biology research project  of the ministry of education, science and technology  through the national research foundation of korea .
the authors greatly acknowledge sangjo han, yong-su jin, carl t. bergstrom, and petter holme for fruitful discussions and thoughtful comments.
we also thank sejun lee, juhyun jung, and doheon lee for providing information about the previous works, and jimin hwang and seung ki baek for their linguistic advice.

 high-throughput detection of protein-protein interactions has long been one of the most intensively studied areas in systems biology. currently, recent progress in experimental techniques, such as the yeast two-hybrid method or tandem-affinity-purification method coupled to mass spectrometry, has allowed the compilation of massive data set for protein interactions of the budding yeast, saccharomyces cerevisiae. from the vast amount of ppi data, protein interaction networks have been vigorously investigated. in pin, proteins are represented as nodes, and two proteins are linked if they interact with each other. basic topological measures, such as a degree, and their correlations are adopted to explain various properties of proteomes. for instance, a degree in pin is the number of partner proteins with which an individual protein interacts. one of the earliest achievements is the heavy-tailed degree distribution and its importance in characterizing the essentiality of proteins. in addition, there have been further explorations on the negative degree-degree correlation profile related to the modular structure of protein interactome. models for pin have been developed by incorporating such characteristics. in this way, it has been witnessed during the last decade that studies on complex networks play a great role in characterizing such interacting entities, and the term "network biology" was coined to refer to networks whose nodes correspond to proteins, metabolites, genes, etc. in spite of such recent progress, there are shortcomings of that type of simplified network representation of ppi in that detailed mechanisms or higher structures of interactions are often neglected. most of all, only the pairwise binary interactions between two proteins are considered in ppi, and they are not sufficient to capture real biological processes involving a stable form of proteins grouped according to their biological functions. for instance, two proteins a and b can be involved in a certain biological process by forming a linear chain with another protein c, such as a-c-b, without any direct contact between a and b. to overcome such problems, it is crucial to consider protein complexes, which are groups of proteins performing specific cellular tasks. in this paper, we focus on protein complexes and their component proteins in s. cerevisiae whose data set has been established through the recently developed tap-ms technique. we apply the concept of bipartite network to the protein complexes and proteins associated with them. a bipartite network is composed of two types of nodes, and there exist links only between nodes of different types, as usually found in social "affiliation" networks, where individuals are joined by common membership of groups. in our case, protein complexes and their component proteins are the two types of nodes, and a complex is connected to a protein if the protein is one of the components of the complex, as shown in figure we construct the bipartite network and obtain its one-mode projections, i.e., the weighted network of individual proteins and the weighted network of complexes, where the weight on each link is given by the number of shared complexes or proteins, respectively. the weighted network is an extension of complex networks, with additional information, weight, on each link, and has been investigated in the context of network theory, including the metabolic network analysis. from this weighted network analysis, we can extract quantitative topological characteristics of the interrelationship among protein complexes and component proteins. in this work, we analyze the distributions of degree and strength. for both bipartite and projection networks, the distributions approximately follow the exponential distribution, while most pins in the literature are claimed to show more inhomogeneous degree distributions. furthermore, two classes of proteins denoted as "core" proteins and "attachment" proteins are shown to play different roles in the complex formation. besides the aforementioned preliminary analysis on the structural properties of networks, as a main topic of our work, we suggest a new method for the systematic estimation on cellular abundance of protein complexes and the assignment of biological functions to them, as well as those of individual proteins. for further researches, such as kinetic modeling of the cell, estimating the abundances and functions of complexes and component proteins can provide a much more quantitative description of behaviors in a cell than a list of protein interactions. however, most of previous attempts about the assignment of unknown functions to proteins or complexes usually rely on local information. for example, there is a method mapping the problem to the local-similarity-based potts model, which is an intrinsically stochastic method and depends on a temperature-like parameter. another previous work is a statistical argument based on hypergeometric tests, as in ref., but it also requires a specific external threshold and additional corrections to fit the data to biological reality. in contrast, our deterministic method is based on the optimization problem related to the global organization of protein complexes, and yields a number of experimentally verifiable results. from the results of the optimization, we cross-analyze the condition-dependent abundance and functions of complexes, which also supports the reliability of our method as well as our extensive statistical validation process. all of these examples clearly show the effectiveness of our method, and we believe that this method has the potential to significantly stimulate further experimental studies. methods bipartite network representation of protein complexes note that the bipartite network itself is not a weighted network, while the protein-protein and complex-complex networks are weighted ones, based on the information provided by the bipartite network. similar approaches have been presented in previous works, with older datasets. for instance, mashaghi et al. used a similar approach, but we consider all three kinds of networks, while ref. dealt only with the bipartite network and the complex-mode projection. in addition, we use a weighted version of one-mode projections in this work, while the unweighted one-mode projection networks were considered in the previous work. we analyze the basic statistical characteristics of these three networks, using the methodology derived from a decade of complex network studies. the dataset of protein complexes and their component proteins in s. cerevisiae is listed in ref., where significant overlaps among protein complexes make it possible for us to analyze the interconnected network structure, and determine the abundance and functions. in ref., gavin et al. use the tap-ms technique to generate the list of protein complexes and their component proteins. the proteins in each complex are classified as cores and attachments, according to their significance in the formation of specific complexes. we will discuss the different roles of core proteins and attachment proteins later on. the datasets consist of protein complexes and component proteins, among which proteins participate in complexes as cores and proteins as attachments. therefore, proteins are used as both cores and attachments. estimation of complexes' abundance based on optimization proteins interact with each other and form complexes in order to perform specific biological functions. naturally each protein complex executes specific biological functions with its characteristic composition of component proteins, and the identification of such functions and abundance in terms of complexes is important. unfortunately, such exact identification of complexes' functions and estimation of their abundance is far from being complete. only heuristic methods, using local interaction of proteins, were used in previous studies, and there were some limitations, such as the arbitrarily specific values of threshold. in this section, we present our new optimization method to determine the abundance and function of protein complexes, based on the information of their global organization. estimation of abundance would be especially crucial, and is directly applicable to various works, such as setting up kinetic models that involves proteins, by providing reaction coefficients. suppose that the copy number of protein i and the number of complex j are given by pi and cj, respectively. also, let us denote the number of protein i in the complex j as sij, where sij = if the complex j does not harbor the protein i as its component. then, in an ideal situation where all the abundances or concentrations of proteins in a cell correspond to the exact amount to be used in forming a complex, similar to the approach used for kinetic modeling in, the variable sets {pi} and {cj} satisfy the question is how to determine {cj} with known values of {pi} and {sij}. however, since the number of proteins n is larger than the number of complexes m, the set of linear equations above is over-determined, and we assume that in reality it is not feasible to satisfy all the equations in eq.. in practice, therefore, we assume that the number of proteins in a cell should be greater than or equal to that necessary to form complexes, i.e.,, which is the basic constraint of our optimization scheme. therefore, instead of looking for an exact solution satisfying eq., we try to minimize the deviation from the ideal situation in eq., given by where the summation is only for indices i where pi > now, for the given values of pi and {sij}, our basic strategy is to determine cj values that minimize da in eq., and this problem is numerically solved by the linear programming technique. moreover, after the determination of cj values, if some values of pi are unknown, we can assign those values of pi using eq. for the ideal situation. this optimization is based on an assumption that organisms have been evolved in a way that increases efficiency by reducing wasted resources. we use the abundance data of yeast proteins {pi}, in ref., because the datasets for both rich and minimal media are available, and we exploit those conditional changes of abundance later on for our analysis. the values of {sij} are given by the list of protein complexes used in this work. inference of complexes' biological functions based on optimization for a functional annotation of complexes, we consider the following optimization scheme. suppose fpik = if protein i performs a function k and fpik = otherwise. similarly, fcjk = if complex j performs a function k and fcjk = otherwise. the organization of protein complexes is given by uij, where uij = if protein i is a component of complex j and uij = otherwise. in this case, the constraint is given by meaning that every function assigned to a protein must be assigned to at least one of the complexes in which the protein participates, which is reasonable, based on the assumption that each biological function is usually expressed cooperatively in the form of protein complexes. we are aware that our dataset of proteins and munich information center for protein sequences database are not exhaustive, so the outcome is not a perfect functional catalogue. however, since our method itself is stable and resilient, as we demonstrate later on the validation part, the result will become more accurate as the input dataset becomes more reliable. even if there are some errors and exceptions, such as single proteins not being included in our complex datasets, we emphasize that, based on notable examples presented later, our method clearly produces biologically significant results. our criterion used for the optimization process is to assign the most definite functions to each complex. in other words, we try to find functions that are inevitably assigned among all the other solutions satisfying the constraint, in the "safest" way. in the spirit of parsimony, we minimize the number of complexes assigned with each function. mathematically, this corresponds to minimizing the following quantity for each k: therefore, our strategy of determining each protein complex's functions is determining {fcjk} which minimizes either eq. under the constraint, with the given values of {fpik} and {uij}. note that all variables and constants in this case are integer values, in contrast to the abundance estimation. this optimization problem is numerically solved with the mixed integer programming technique. after determining the {fcjk} set, similar to the case of abundance case, we can conjecture the function of protein i as k, if ∑j uij fcjk ≥ while fpik = because the protein i is considered to perform the function k by participating in at least one of the complexes to which the function is assigned. the function assignment of proteins, i.e., {fpik} is available from various sources, such as mips or the yeast genome database, and the values of {uij} are given by the list of protein complexes used in this work so far. we use the mips database for the initial function assignment of individual proteins, which is set {fpik}, because its hierarchical organization of functional catalogue helps the systematic interpretation of results in different hierarchical levels. we would like to emphasize that our method, for the first time, systematically assigns multiple numbers of functions to all the complexes in the genome-wide scale, without any free parameter or initial condition dependency, in contrast to other previous methods. there is a certain degree of resemblance between our method and the message passing algorithm, such as the belief propagation, in inferring or assigning properties to variables in bipartite graphs. for instance, the message from a variable node v to a factor node u in bp is analogous to assigning function or abundance of complexes, and the following process of message passing from u to v corresponds to assignment to proteins with previously unknown functions or abundance. we can even consider the configuration of object functions in eqs. as the "energy landscape" of constraint optimization problems, where methods like bp play important roles. in spite of this analogy, there are significant differences as well. first, our method is designed to deal with a specific type of problems composed of the set of factor nodes with no a priori information and the set of variable nodes with information except for a small fraction of unknown cases. second, and more importantly, in contrast to bp, where the local flow of inference is used, our method is based on global optimization of object functions. in this respect, the previous works using local or bayesian inference to assign protein functions are similar to the message passing algorithm than our method. of course, finding deeper mathematical analogy between our method and such traditional inference algorithms would be certainly interesting, but that would be beyond the scope of this paper.  statistical properties of the bipartite and one-mode projection networks first, we construct the bipartite network without distinguishing between core and attachment proteins. as mentioned in the'methods' section, the bipartite network consists of complexes and proteins as its two different types of nodes. the average degree of complexes is, and the average degree of proteins is. figure shows the degree distributions of the bipartite network, where we separate the distributions for complexes and proteins since they are different types of nodes. as shown from the fitted curves in figure the degree distributions for both kinds of nodes are much closer to the exponential distribution p ~ exp than the power-law distribution, because the cumulative distribution p of the exponential distribution p ~ exp also follows the exponential distribution from the relation, in the continuum limit. two complexes, denoted as complexes and in ref., include prominently many component proteins, especially including proteins affiliated to the ribosome, as shown in table the two proteins, with the maximum connectivity in the bipartite network, are rps22a and rpl36b, which are ribosomal proteins. the annotated complexes in ref. are following: *u snrnp complex, †prp19-associate complex, **ribosome-associate complex, ††translation initiation factor eif complex, •complexes assigned as'ribosomal proteins' function, ••trna modification function, and •••fatty acid metabolism and aromate anabolism predicted by our optimization method. one-mode projections of our bipartite network represent interactions or relatedness among complexes and individual proteins. in the complex-mode projection, intuitively, two complexes are considered to be related if they share proteins, and the "intensity" of their relatedness, the number of proteins they share, is quantified as the weight. similarly, in the protein-mode projection, two proteins are thought to be related if they participate in common complexes, due to the fact that proteins perform a biological function as a unit of the protein complex. because more than two proteins can be cooperatively involved in the protein interactions, investigating protein interactions from the formation of complexes has its own advantages over other methods using only the pairwise interactions, such as the y2h method. the degree distributions of the complex-mode projection shown in figure and the protein-mode projection in figure show the exponential distribution. the strength si of a node i in a weighted network is defined as where wij is the weight of the link connecting the node i and j, and vi is the set of neighbor nodes of i. it can be considered as a natural extension of the degree of a node in weighted networks, and the strength distributions of our weighted complex-complex and protein-protein networks are shown in additional file figure s the strength distributions are also closer to the exponential form, rather than the power-law distribution observed in many other biological and other real-world weighted networks. it is true that the maximum degree of complex-mode projection network is very large, considering the number of nodes, but this is merely due to the large connectivity of distribution, not to the "scale-free" functional shape. although the notion of hub, referring to nodes with many connections to others, in the exponential degree distribution is not as strong as in the power-law degree distribution, we can still identify nodes with relatively large degrees and strengths by examining the "tail" part of the distributions. table lists the complexes and proteins with the ten largest degree and strength values in both the bipartite and projection networks. again, the ribosome-associated complex is a notable example annotated in the datasets. other unknown complexes with large degrees and strengths also include many ribosomal proteins as their components. some ribosomal proteins have the largest degrees and strengths in the protein-mode projection as well, e.g., rpl33a, rpl rpl16b, and rpl26b. the fact that many complexes and proteins with largest degrees and strengths are affiliated to the ribosome can be interpreted in two ways. one hypothesis is that because the ribosome is involved in the production of proteins, ribosomal proteins might be promiscuously attached to many unspecific complexes. the other is that ribosomal complexes are usually large and composed of many ribosomal proteins, which implies the genuine property in this case. to determine which hypothesis is more plausible, we have manually checked the complexes in which those proteins are involved and found that most component proteins of those complexes are also ribosomal proteins, which supports the latter hypothesis. for instance, complexes which have the three largest degree in the bipartite network, are all assigned with'ribosomal proteins' from our optimization method. we note that in some previous works, the ribosomal proteins are considered as non-specific contaminants involved in promiscuous interactions and filtered out, for example, in ref.. however, our dataset from ref. already passed the stringent test based on socio-affinity index, taking into account the frequency of proteins within the dataset and naturally discriminating true from spurious interactions. we believe that the criterion used in ref. can be more systematic and reasonable than the "3% rule" used in ref., so the statistics related to the ribosomal proteins may actually be reflective of the biological reality. however, it would also be meaningful to mention some non-ribosomal complex/proteins with such large degree/strength values. therefore, we have identified other examples such as complexes assigned with trna modification function, fatty acid metabolism, and aromatic anabolism from our optimization method among the top largest complexes and indicated in table the exponential distribution is different from the earlier notion of the power-law degree distribution of pin, but the power-law distribution for pin has been contested by number of researches as well. statistically, the diversity of degrees and strengths in the complex-complex and protein-protein networks is less than that of pin. therefore, we conclude that the existence and strength of interactions with other proteins for each protein in terms of participation in protein complexes are less diverse than those for the pairwise interactions. these exponentially-decaying distributions are in contrast to the results from earlier works on biological networks, but recent studies suggest the different frameworks of assessing the protein interactions. it turns out that these homogeneous distributions correspond to the stable complex formation. for example, in a recent "benchmark" paper by yu et al. revealed the intrinsically different natures of detected interactions from the y2h for detecting more transient and condition-specific interactions and mass spectrometry methods for detecting stable protein complexes, which can support our findings of the exponential distribution of degrees, in contrast to the power-law distribution for pin from the y2h method. to be more specific, the detection of complexes with tap-ms method used in our data corresponds to the ms technique, which is basically to detect "prey" proteins with the "bait" proteins so the collection of prey proteins is considered as an entity of interactome, in contrast to y2h method using 1: pairwise screening. the differences between the "spoke model" and "matrix model" described in ref. are also a good mechanism causing the different kind of distributions. interestingly, there are lots of proteins having more than neighbors in the projection network as shown in figure while the recent pin analysis shows the maximum degree less than in spite of their power-law distribution. here we do not claim that our finding is in conflict with the previous studies on the binary ppi, but that this projection network based on tap-ms complex data clearly reflects fundamentally different type of interactions in the yeast proteome, as well-documented in ref.. the exponential or at least "bounded" degree distribution of complexes in the bipartite network can be thought to originate from, for example, the "crowding effect" in a cell. cytoplasm of a cell is occupied by various macromolecules such as enzymes, whose concentration cannot be further increased without affecting protein-protein association or transport dynamics. specifically, there should be a limit in the available cytoplasmic volume a complex can take, and thus the number of component proteins it can bear within the limited physical space. also, it is empirically observed that the number of complexes a protein can participate in is limited as well. for the exponential degree distributions for both parties in the bipartite network, the projected networks' degree distributions actually turn out to be exponential-like unless there are nontrivial correlations, because each party's degree distribution mainly determines the projected network's degree distribution as shown in ref.. we have derived more rigorous proof of this fact by adopting a similar technique to ref., where the generating function for the degree distribution is used to derive the degree-degree correlation for projected networks. it is straightforward to calculate the generating function of the projected protein network's degree distribution given by where the degree distributions of proteins and complexes in a bipartite network are given by pprotein ~ exp and pcomplex ~ exp and there is no degree-degree correlation, which we have checked that as a reasonable assumption from our dataset, by the way. the resultant degree distribution of proteins in the projected network is calculated with the formula and we numerically check that the distribution is indeed very close to exponential one for k ≫ as shown in additional file figure s one may argue that it is hard to tell something about the distribution with the limited number of datasets, but in any case, we can safely exclude the power-law distribution from fitted curves from figures and s also, we emphasize that our dataset from the tap-ms method, modified to successfully overcome the membrane protein under-representation problem, is fairly genome-wide. even if there might be missing proteins or complexes as a result of experimental limitation of detecting heterodimer complexes, the degree distribution would not be severely affected by sampling. in a previous work including pin data, we showed that the functional form of degree distribution is conserved under sampling up to quite a low sampling fraction. in this respect, we conclude that the different type of distribution in this case reflects the actually different characteristics of the binary interaction and the interaction as forming complexes. to check this property of network statistics in case of other organisms, we use the list of protein complexes of escherichia coli data and human protein reference database. first, since the e. coli dataset defined in ref. does not provide any overlapped component protein between complexes, we observe only the degree distribution of complexes, meaning the number of component proteins each complex has. it is difficult to reach a definite conclusion of the distribution's functional form with a very small range of degree values, but the maximum degree is less than and the argument of crowding effect seems to hold here as well. in hprd datasets, there are both the list of protein complexes and binary ppi, which allows the comparative analysis. as a result, the degree distributions of complexes and proteins in the bipartite network are less broad than the ones in the binary ppi, which indicates a similar result to our s. cerevisiae dataset. the degree distributions of the bipartite network of hprd themselves do not seem to follow the exponential distribution, though, and we suspect that this difference may stem from the fact that hprd dataset is basically manual literature mining of small-scale experiments, not the result from a systematic high-throughput experiment. on the other hand, if the degree distribution from hprd reflects biological reality rather than such sampling biases, we suppose that the relatively large size of mammalian cells may "relax" the aforementioned macromolecular crowding effect, thereby enriching the tail part of the degree distribution, compared to the case of yeast cells. distinction between core and attachment proteins the list of component proteins for each protein complex is divided into two groups, cores and attachments in ref.. the "standard" complex-protein dataset is selected in terms of best accuracy and coverage in a set of manually-curated complexes, but there can be other possible variations of complex-protein sets if the threshold of accuracy and coverage for clustering becomes more flexible. these variations in reasonable ranges are denoted as "isoforms," and whether a protein is core or attachment is determined by the participation ratio in the isoforms. in other words, proteins present at a certain complex in a significant portion of the isoforms are classified as core proteins of that complex, and denoted as attachment proteins of that complex otherwise. note that the entire set of proteins is not exactly partitioned into two groups, because a core protein for a complex can be an attachment protein in another complex. in fact, as mentioned in the'methods' section, proteins among the total number of proteins act as both cores and attachments. core proteins seem to bind more rigidly, and form the basic unit of a given complex. if only the core proteins are considered to construct the bipartite network for complexes and proteins, the average degree of core proteins in the bipartite network is, and most proteins participate in only one complex, while the largest degree is only on the other hand, when considering only attachment proteins, the average degree of attachment proteins in the bipartite network is and the largest degree is the average degree is in case of all proteins, and from this comparative analysis we can observe that core proteins are much less promiscuous than the attachment ones. the degree distributions of proteins for both cases are closer to the exponential distribution, as shown in figure this quantitatively different participation pattern suggests that the core proteins in a protein complex act as its "skeleton" and the attachment proteins play the role of "seasoning," because attachment proteins are likely to participate in the formation of a relatively large number of complexes. one-mode projections, when only core proteins or only attachment proteins are considered, are shown to have exponential degree and strength distributions for both complex-mode and protein-mode projections, similar to the case without the distinction between those two kinds of proteins. different roles of core and attachment proteins are also reflected in the clustering structure of complex-mode projection network. if only the core proteins are considered, the complex-mode projection network is composed of separate connected components, which is a highly fragmented configuration. thus, core proteins are important as a stable component for individual complexes, rather than a mediator which "binds" complexes together. on the other hand, if only the attachment proteins are used to bond complexes, one single giant component emerges, except for a single tiny component with only two complexes. this small component is also merged into the single giant component if we consider both core and attachment proteins. as a representative example, we present the exosome 3'-5' exoribonuclease complex which contains all the core components of ski complex as attachments, supporting previous works that the association is necessary for cytoplasmic messenger rna 3'-to-5' decay. therefore, the attachment proteins indeed specify a particular function for the exosome complex. inference of abundance and functions: statistical validation there are core and attachment proteins, as stated and analyzed in the previous subsection. to make our predictions as conservative as possible, we adopt the following scheme about selecting core and attachment component proteins. for the abundance estimation, we consider only the core proteins as components of complexes, based on the fact that the core proteins play the role of the skeletons as previously mentioned, i.e., unlike the attachment proteins shared by relatively large number of complexes which can overestimate the number of complexes. in other words, we expect that utilizing only the core proteins leads us to a more accurate estimate of the abundance. in contrast, both the core and attachment proteins are used in function assignment of complexes. in this way, it allows more alternative ways of function assignments, and if a function is assigned in spite of all those possibilities, we can consider it to be a genuine function, with more certainty. however, in case of assignment of previously unknown functions to proteins after the function assignments for complexes, only core proteins are considered instead, reflecting the fact that the proteins' main biological functions are achieved by participating as core components. finally, we remark that the {sij} matrix for abundance estimation is approximated by {uij} matrix, due to the limitation of available information. however, note that more and more accurate datasets will become available in the future, and applying our method for those new datasets would be straightforward. with the lp and mip method, we have numerically solved the optimization problems to obtain the abundance and functions of complexes and their component proteins. as the input datasets for individual proteins, we use condition-dependent abundance of proteins and the mips functional database for individual proteins. in total, different mips funcat functions are assigned to our individual protein set. since the mips funcat classifications are hierarchically organized, we can divide the set of functions into more coarse-gained "functional categories" from their higher level hierarchy to observe more general trends, as demonstrated in the next paragraph. before we apply the method for the main result, we have divided the known input datasets into several training and test sets and verified its effectiveness for various settings. the full results for our function assignments for both complexes and proteins are available. note that we also present an alternative optimization method in additional files, denoted as'gavin_2nd' in additional file table s and additional file table s minimizing the number of proteins for each newly assigned function, instead of the number of complexes described in eq.. the mip method does not produce a unique solution in general, and there can be multiple numbers of solutions. among those solutions, we select high confidence outcomes among the original outcomes from our method. in other words, hc outcomes contain only the functions which are assigned to complexes and proteins, in all the multiple solutions. to check the accuracy of our method, we first divide the set of proteins with known values of abundance into training and test sets. assuming that the values of abundance for the proteins in the test set are unknown, we estimate the abundance for those proteins in case of rich media and compare them with real values. we define the relative deviation as then, we plot the ranked α values, compared to the ones for random pairing of estimated abundance and real abundance in additional file figure s the real deviation values are always significantly smaller than those of random counterparts outside the error range, demonstrating the statistical significance of our results. we have also observed the similar result for minimal media as well. for the function assignment, we also divide the set of proteins with already-known functions into training and test sets. assuming all the protein functions in the test set are unknown, we assign those functions based on our function assignment method; the results are shown in table we measure two complementary quantities to show both sensitivity and specificity, for both the raw outcomes and hc outcomes. from the results, we conclude that our method works reasonably well, especially for hc outcomes, considering the noise level of this kind of high-throughput dataset. one remarkable thing is that our method works quite well for a very small fraction of training set such as 20% for both abundance estimation and function assignment, and this fact implies that highly interconnected relationship among proteins via complex membership greatly helps us to correctly assign functions. to compare our results with a recent function assignment scheme, we adopt the hypergeometric test used in ref. and applied the method with the same threshold to our dataset. note that the result obviously depends on the threshold value, and also the original cyc method does not include the "re-substitution" process of copying functions from complexes to their components. therefore, we have to combine our re-substitution process after the cyc procedure for function assignment for complexes. the compared results clearly show that the performance of our method is better than or at least comparable to that of cyc in many cases, and especially the number of predicted functions itself is much smaller for cyc method. to be more specific,'fraction of proteins for our high-confidence result' shown in the third column is always better than the cyc result in the fourth column, and even our raw result in the second column is better than cyc in case of large values of training set fraction p or at least comparable to each other for small p. the only case worse than cyc is the'fraction of functions for our raw result' in the fifth column for small p, but this can also be overcome by using hc dataset in the sixth column. therefore, we conclude that our global optimization method is much better at guessing the unknown protein functions, in terms of sensitivity or recall rate, let alone the problem of dependence on an arbitrary parameter, which is the wholesale e-value threshold for the cyc method. here p is the fraction of training set. *among all the newly assigned functions to the entire test set proteins, fraction of functions which are also on the original mips functional datasets. †fraction of test proteins with at least one function assigned, which has at least one assigned function on the original mips functional datasets. raw outcomes correspond to the original outcomes from our method, and high confidence outcomes are the selected subset of them whose function assignments are invariant even if the multiple solutions are considered. inference of abundance and functions: condition-dependent abundance with regard to functional categories first, we show the average change of complexes' abundance depending on the condition, classified as each mips functional category in figure note that a complex can be assigned with multiple functions, so there are overlaps among different functional categories. we believe that this cross-analysis of abundance and function assignment strongly supports the reliability of our method, in addition to the statistical test presented in the previous subsection. from figure one can check that each functional category shows a unique pattern of the condition-dependent abundance changes. the most notable case is the increased abundance of complexes doing metabolism in the minimal media compared to the rich media, indicating that many proteins induced in minimal medium are involved in the production of small molecules that cannot be taken up from the surrounding environment. another notable category of increased abundance in the minimal media is the cellular communication. for instance, the protein kinase complex in additional file table s is significantly more abundant in the minimal media, and this result can be interpreted from the nutrient sensing role of component protein tpk involved in the cell growth via the ras-camp signaling pathway, at facing the nutrient starvation. also, the abundance of complex in additional file table s is increased in the minimal media and one possible explanation is its component protein transketolase's involvement in the pentose phosphate pathway of processing glucose 6-phosphate to produce ribose-5-phosphate, which can be demanded more in the minimal media. in contrast, many complexes with functions of cell cycle and protein synthesis tend to show decreased abundance in minimal media, indicating that many proteins induced in rich media are involved in cell growth and division. a fraction of the complexes with each functional category, for three different ranges of abundance ratio changes, shown in figure also shows a similar trend. our findings are consistent with the argument in ref., which discusses such effects on the individual protein level. note that, however, the previous work in ref. is about individual proteins, while our results are about complexes, by which the real biological functions are expressed. it indicates that the similar arguments are applied to abundance and functions of complexes. inference of abundance and functions: other examples from our results about the functional annotations for complexes, we find a number of intriguing examples. for instance, both the complex whose core proteins are ste and ste and the complex whose core proteins are bcy and tpk are assigned with the cytoskeleton formation and signal transduction. the relationship between the cytoskeleton proteins and the cell signal transduction is discussed in recent literatures, arguing that the filaments of the cytoskeleton provide guiding tracks so that transport becomes more focused. the core component proteins of those complexes we have found, ste ste bcy and bcy are also shown in ref.. another example is related to the shifting process from fermentation to respiration in yeast, depending on the temporal order of environmental stimuli, such as osmotic pressure and heat shock. as shown in additional file table s there are complexes co-assigned with those functions related to the process such as complex, and complex. our optimization scheme does not only give the systematic estimate of complexes' abundance and function assignment, but also conjecture previously unknown new functions to individual proteins, as stated in the'methods' section. table shows biologically interesting examples from our results with manually curated references for validation. for instance, the metabolic enzyme eno was not assigned with any functions related to the cell division, but assigned with the cell division functions as a result from our optimization technique. an important point here is that, as we will demonstrate with eno in the next paragraph, we know exactly where the functions come from, i.e., by actually tracing the complex to which the function is assigned and looking for another component protein participating in the complex, as the "source" of the function. reference refers to the case that the predicted functions are not given by the mips data so that the functions are not assigned initially, but found by our method and on the gene ontology database. in this case, we consider go database as the validation source, similar to other references. in case of the protein eno it participates in the complex as a core component, and the complex is involved in the cell division process. the function assigned to that complex originates from another core component protein chs in the mips datasets. the protein eno2's involvement in the cell division is also supported by a recent experiment, showing that the overexpression of the protein significantly delays the progression of yeast cell cycle. of course, the experimental results need to be carefully interpreted, since g arrest can also be made by perturbing proteins not directly involved in the cell division process, as exemplified by sko activating the pheromone response pathway. this type of evidence, therefore, may not be a sufficient condition for the direct involvement in the cell division process, but can be a necessary condition which hints the candidate targets for further investigation in a more elaborate way. with such procedure, we find quite a number of examples indeed, as shown in table and suggest small-scale experiments to confirm the functional annotations of these proteins. discussion it is indispensable for the future of proteomics to understand the composition structure and interactions of protein complexes. however, relatively fewer works about the protein complexes have been done in the genome-wide level, except for a few cases, compared to works about pairwise ppi. in this work, we have investigated and shown the applications of the interactions in the recently published protein complex database of the budding yeast. we have adopted the notion of bipartite network, which is suitable for the case where there are two kinds of elements and one of them acts as the set of components of the other. by constructing the bipartite network with protein complexes and their component proteins, we have checked the degree distributions of complexes and proteins. as results of the analysis, the degree distribution of the bipartite network asymptotically follows the exponential distribution. the same is true for the degree and strength distributions of the one-mode projection networks as well. interestingly, the resultant exponential degree distributions are different from the heavy-tailed distribution observed in most pairwise ppi networks. many complexes and proteins with largest degrees and strengths are affiliated to the ribosome, allowing for the stable formation of large ribosomal complexes. furthermore, we have shown that the core and attachment proteins in the datasets show different participation patterns in the formation of complexes, which illustrates the different roles in the complexes. the most valuable contribution of our work is presenting the new optimization method without external tuning parameters to determine the abundance and function of protein complexes, along with the previously unknown properties of individual proteins, based on the information of their global organization. the effectiveness of our optimization method is proved by various biologically relevant examples compared with experimental results. since we provide the full results from our results as additional files, we hope our result can encourage other researchers to utilize it as their new dataset for deeper understanding of proteomics.  thanks to the rich proteomics datasets of s. cerevisiae, many genome-wide researches have been achieved. analyses based on the protein complexes can open a door to a new understanding of how proteins interact and work in organisms. important future works include more investigation about our bipartite network topology, along with more systematic comparison with the conventional pin to see the detailed origin of the different form of the degree distribution. ultimately, it is essential to perform the small-scale experiments to validate the results claimed by our new optimization method. we hope this work can make a substantial contribution to this direction of research. competing interests the authors declare that they have no competing interests. authors' contributions shl, pjk, and hj conceived and designed the study. shl collected the data. shl and pjk performed the numerical simulation and statistical analysis, and analyzed the results. shl, pjk, and hj wrote, read, and approved the final manuscript. supplementary material additional file 1 strength distributions of complex-mode projection and proteins-mode projection. here, the strength in corresponds to the sum of number of proteins shared with the neighboring complexes for each complex, and the strength corresponds to the sum of number of complexes shared with the neighboring proteins for each protein. the blue squares correspond to the cumulative strength distribution p = ∑s′ ≥ s p, and the pink lines and gray curves are the best exponential and power-law fittings, respectively. click here for file additional file 2 projected network's degree distribution from the generating function approach. assuming that both protein and complex's degree distributions follow the exponential degree distribution p ~ exp, the projected network's degree distribution is numerically calculated with the generating function approach mentioned in the main text. one can clearly observe that the degree distribution follows the exponential tail for k ≫ click here for file additional file 3 degree distribution of complexes in the bipartite network for e. coli protein complex data in semi-log scale and double-log scale. here, the degree corresponds to the number of component proteins for each complex. the blue squares correspond to the cumulative degree distribution p = ∑k′ ≥ k p. click here for file additional file 4 degree distribution of complexes and proteins in the bipartite network for human protein complex data, in comparison with the protein-protein interaction network. here, a complex's degree corresponds to the number of component proteins for each complex, and a protein's degree corresponds to the number of complexes in which a protein participates as a component. the degree distribution of proteins in the binary protein-protein interaction is shown as pink triangles, as a comparison. click here for file additional file 5 list of all the protein complexes with mips functions assigned by our method. list of all the protein complexes with mips functions assigned by our method, where the core and attachment components are taken from ref.. we classify each function into the following three categories. gavin_1st: minimizing the number of complexes for each newly assigned function, described as eq. in the main text. gavin_2nd: minimizing the number of proteins for each newly assigned function, instead of that of complexes the functions assigned by both and. note that we only select high confidence outcomes among the raw outcomes, whose reliability of function assignment considering the multiple solutions is large. click here for file additional file 6 list of all the proteins with mips functions newly assigned by our method. list of all the proteins with mips functions newly assigned by our method, along with the ones from the mips database which is used as "input function." hc outcomes are selected as in additional file table s sometimes the functions already annotated in mips and the ones assigned by our method are quite similar, and very different in some cases. therefore, we suggest the latter case be worth investigating further, as we did in the main text. click here for file additional file 7 statistical validation of abundance estimation. for each value of fraction of training set p, the relative deviation is ranked and shown compared to its random counterparts. the real deviation values are always on the left side of the random counterparts outside the error range, which implies its statistical significance. click here for file additional file 8 statistical validation of the function assignment, in comparison with the hypergeometric test in ref.. here p is the fraction of training set. †fraction of test proteins with at least one function assigned, which has at least one assigned function on the original mips functional datasets. *among all the newly assigned functions to the entire test set proteins, fraction of functions which are also on the original mips functional datasets. raw outcomes correspond to the original outcomes from our method, and high confidence outcomes are the selected subset of them whose function assignments are invariant even if the multiple solutions are considered. click here for file acknowledgements this work is supported by the swedish research foundation and the korean systems biology research project of the ministry of education, science and technology through the national research foundation of korea. the authors greatly acknowledge sangjo han, yong-su jin, carl t. bergstrom, and petter holme for fruitful discussions and thoughtful comments. we also thank sejun lee, juhyun jung, and doheon lee for providing information about the previous works, and jimin hwang and seung ki baek for their linguistic advice.
it is strongly supported by a number of biologically relevant examples, such as the relationship between the cytoskeleton proteins and signal transduction and the metabolic enzyme eno2's involvement in the cell division process. proteins in organisms, rather than act alone, usually form protein complexes to perform cellular functions. we analyze the topological network structure of protein complexes and their component proteins in the budding yeast in terms of the bipartite network and its projections, where the complexes and proteins are its two distinct components. compared to conventional protein-protein interaction networks, the networks from the protein complexes show more homogeneous structures than those of the binary protein interactions, implying the formation of complexes that cause a relatively more uniform number of interaction partners. in addition, we suggest a new optimization method to determine the abundance and function of protein complexes, based on the information of their global organization. with our new optimization method, we present genome-wide assignments of abundance and biological functions for complexes, as well as previously unknown abundance and functions of proteins, which can provide significant information for further investigations in proteomics. estimating abundance and biological functions is of great importance for many researches, by providing a quantitative description of cell behaviors, instead of just a "catalogues" of the lists of protein interactions. we believe that our methods and findings are applicable not only to the specific area of proteomics, but also to much broader areas of systems biology with the concept of optimization principle.
 proteins in organisms, rather than act alone, usually form protein complexes to perform cellular functions. we analyze the topological network structure of protein complexes and their component proteins in the budding yeast in terms of the bipartite network and its projections, where the complexes and proteins are its two distinct components. compared to conventional protein-protein interaction networks, the networks from the protein complexes show more homogeneous structures than those of the binary protein interactions, implying the formation of complexes that cause a relatively more uniform number of interaction partners. in addition, we suggest a new optimization method to determine the abundance and function of protein complexes, based on the information of their global organization. estimating abundance and biological functions is of great importance for many researches, by providing a quantitative description of cell behaviors, instead of just a "catalogues" of the lists of protein interactions.  with our new optimization method, we present genome-wide assignments of abundance and biological functions for complexes, as well as previously unknown abundance and functions of proteins, which can provide significant information for further investigations in proteomics. it is strongly supported by a number of biologically relevant examples, such as the relationship between the cytoskeleton proteins and signal transduction and the metabolic enzyme eno2's involvement in the cell division process.  we believe that our methods and findings are applicable not only to the specific area of proteomics, but also to much broader areas of systems biology with the concept of optimization principle. 