Open Access

Research Article

• Download: XML | PDF | Citation
• E-mail this Article
• Order Reprints
• Print this Article
• Bookmark this page:
  

Introduction

An intriguing question in the analysis of biological networks is whether biological characteristics of a protein, such as essentiality, can be explained by its placement in the network, i.e., whether topological prominence implies biological importance. One of the first connections between the two in the context of a protein interaction network, the so-called centrality-lethality rule, was observed by Jeong and colleagues [3], who demonstrated that high-degree nodes or hubs in a protein interaction network of Saccharomyces cerevisiae contain more essential proteins than would be expected by chance. Since then the correlation between degree and essentiality was confirmed by other studies [4]–[7], but until recently there was no systematic attempt to examine the reasons for this correlation. In particular, what is the main topological determinant of essentiality? Is it the number of immediate neighbors or some other, more global topological property that essential proteins may have in a protein interaction network?

Jeong and colleagues [3] suggested that overrepresentation of essential proteins among high-degree nodes can be attributed to the central role that hubs play in mediating interactions among numerous, less connected proteins. Indeed, the removal of hubs disrupts the connectivity of the network, as measured by the network diameter or the size of the largest connected component, more than the removal of an equivalent number of random nodes [3],[8]. Therefore, under the assumption that an organism's function depends on the connectivity among various parts of its interactome, hubs would be predominantly essential because they play a central role in maintaining this connectivity.

Recently, He and colleagues challenged the hypothesis of essentiality being a function of a global network structure and proposed that the majority of proteins are essential due to their involvement in one or more essential protein–protein interactions that are distributed uniformly at random along the network edges [9]. Under this hypothesis, hubs are proposed to be predominantly essential because they are involved in more interactions and thus are more likely to be involved in one which is essential.

In this work we carefully evaluate each of the proposed explanations for the centrality-lethality rule. Recently several hypotheses that linked structural properties of protein interaction networks to biological phenomena have come under scrutiny, with the main concern being that the observed properties are due to experimental artifacts and/or other biases present in the networks and as such lack any biological implication. To limit the impact of such biases on the results reported in our study we use six variants of the genomewide protein interaction network for Saccharomyces cerevisiae compiled from diverse sources of interaction evidence [10]–[15].

To assess whether the essentiality of hubs is related to their role in maintaining network connectivity we performed two tests. First, if this were the case, then we would expect essential hubs to be more important for maintaining network connectivity than nonessential hubs. We found that this is not the case. Next, in addition to node degree, we consider several other measures of topological prominence, and we demonstrate that some of them are better predictors of the role that a node plays in network connectivity than node degree. Thus, if essentiality were related to maintaining network connectivity, then one would expect essentiality to be better correlated with these centrality measures than with the node degree. However, we found that node degree is a better predictor of essentiality than any other measure tested.

To reject the essential protein interaction model [9], we used a hypothesis testing approach. Namely, we observed that this model implies that the probability that a protein is essential is independent of the probability that another noninteracting protein is essential. However, in the tested networks the essentiality of noninteracting proteins that share interaction partners is correlated. Thus, we reject the independence assumption and, as a result, the essential protein interaction model with high confidence.

Motivated by our findings we propose an alternative explanation for the centrality-lethality rule. Our explanation draws on a growing realization that phenotypic effect of gene-knockout experiments is a function of a group of functionally related genes, such as genes whose gene products are members of the same multiprotein complex [16]. It is well known that densely connected subnetworks are enriched in proteins that share biological function. Therefore, one would expect that dense subnetworks of protein interaction networks should be either enriched or depleted in essential proteins. Indeed, Hart and colleagues observed that essential proteins are not distributed evenly among the set of automatically indentified multiprotein complexes [17]. In this work we observe that the same phenomenon holds for potentially larger groups of densely connected and functionally related proteins, which we call COmplex BIological Modules (or COBIMs). We demonstrate that due to the uneven distribution of essential proteins among COBIMs the majority of the essential proteins lie in those COBIMs that are enriched in essential proteins, which we call Essential COmplex BIological Modules (or ECOBIMs).

By the very definition, ECOBIMs contain, relative to their size, more essential nodes than a random group of proteins of the same size. But what fraction of all essential hubs are members of such ECOBIMs? How does this number relate to what is expected by chance? In fact, how does the enrichment of hubs that are members/nonmembers of ECOBIMs in essential proteins relate to the enrichment values expected by chance under a suitable randomization protocol? We propose that membership in ECOBIMs largely accounts for the enrichment of hubs in essential proteins. In support of this hypothesis, we found that the fraction of essential proteins among non-ECOBIM hubs is, depending on the network, only 13–35%, which is almost as low as the network average. Furthermore the essentiality of nodes that are not members of ECOBIMs is only weakly correlated with their degree. Finally, using a randomization experiment we demonstrated that these properties are characteristic of the protein interaction network and are unlikely in a corresponding randomized network.

Results

Our Study Uses Six Protein Interaction Networks

Our source of protein interaction data for the yeast Saccharomyces cerevisiae is numerous small-scale studies and seven high-throughput experiments [15], [18]–[23]. Interactions reported in targeted studies are believed to be biologically relevant as they are usually subjected to a variety of validation methods. Recently, Reguly et al. [11] curated about 30,000 literature abstracts to compile a network of protein interactions reported in small-scale experiments. We refer to this network as the LC network (Literature Curated network).

It was suggested that the centrality-lethality phenomenon is an artifact of a possible bias present in the networks mainly derived from small-scale experiments [24]. Namely, essential proteins are the focus of more studies and therefore tend to have a higher degree in these networks. Therefore, to complement the LC network, we included in our study two networks that contain interactions reported in both small-scale studies and high-throughput experiments. The DIP CORE network is derived from the pool of protein interactions deposited in the DIP database using a computational method of Deane et al. [10] that recruits evolutionary information to filter out unreliable interactions. The HC network (the High Confidence network) recently published by Batada et al. [12] is derived by intersecting small-scale data with the above-mentioned seven high-throughput datasets. More specifically, an interaction is included in the final network only if it was independently reported at least twice.

We also include two networks derived solely from high-throughput experimental data. The Y2H network is obtained from the genomewide yeast-two-hybrid interaction screen of Ito et al. [15] and contains high-confidence interactions that were experimentally detected at least three times. Recently, Collins et al. [13] published a statistical scoring scheme that maps raw complex purification experimental data to interaction confidence scores. The authors applied their method to raw purification data from two recent genomewide complex purification experiments [22],[23]. We refer to a network that contains all interactions with a confidence score above a certain threshold as the TAP-MS network.

Finally, we include a network of interactions predicted in silico using the computational approach of Jansen et al. [14]. The method trains a Bayesian network that combines a variety of genomic features such as mRNA coexpression, colocalization, etc. to derive interaction confidence scores for protein pairs. The authors used protein interactions derived from a set of manually curated protein complexes as the set of positive training examples and pairs of proteins localized to different cellular compartments as the set of negative training examples. We refer to this network as the BAYESIAN network.

Table 1 summarizes the structural properties of the six networks just described. (Here and throughout the paper we analyze the largest connected component of each protein interaction network.) Table 2 shows the overlap, fraction of interactions in common, between the networks. Given the differences in the experimental techniques used to construct these networks and the fact that the edges in the TAP-MS and BAYESIAN networks correspond to membership in multiprotein complexes, in the Y2H to physical contacts, and in the DIP CORE, LC, and HC networks to a mix of these two things, it is not surprising that the networks differ significantly in terms of density, cliquishness, and other parameters. The biggest outlier is the Y2H network. In fact, for this network, the relation between essentiality and lethality is less prominent as discussed in the next section.

Table 1. Structural properties of the tested protein interaction networks.

doi:10.1371/journal.pcbi.1000140.t001

Table 2. Amount of overlap between tested networks.

doi:10.1371/journal.pcbi.1000140.t002

The Centrality-Lethality Rule Holds in the Six Networks

In their influential paper, Jeong et al. [3] observed that the degree of a node in a yeast protein interaction network correlates with the phenotypic effect of its deletion. More specifically, the authors observed that high-degree nodes are three times more likely to be essential than nodes having few interaction partners. It was further hypothesized that high-degree nodes tend to be essential due to the central role that they play in maintaining the overall connectivity of the network by mediating interactions among other less connected proteins. Consequently, high-degree nodes are also referred to as hubs, and the observed phenomenon is known as the centrality-lethality rule.

To confirm the centrality-lethality rule in the tested networks we used the results of a systematic gene deletion screen [25] in which 1,105 yeast genes were found to be essential for growth on rich glucose media. There are numerous ways of exposing positive correlation between degree and essentiality, two of which are used in this paper. First, one can ask whether hubs, nodes with a degree greater than or equal to a certain threshold, are more likely to be essential than an average network node, i.e., whether the fraction of essential proteins among hubs is greater than the network average. To choose an appropriate threshold value we relied on Figure 1A, which shows the enrichment values for nodes with a degree greater than or equal to k as a function of k. In some networks the steady increase of enrichment values is interrupted for very large values of k. Therefore, we chose the threshold value so that approximately 20% of the network nodes are hubs. (For the DIP CORE network the value of k is 7, for the LC network it is 10, for the HC network it is 10, for the TAP-MS network it is 24, for the BAYESIAN network it is 12, and for the Y2H network it is 3.) However, we repeated the experiments with hubs defined as 10% (data not shown) and found that our conclusions are robust to the specific choice of the threshold.

Figure 1. Relationship between degree and essentiality in the tested networks.

(A) For each tested network the fraction of essential nodes among nodes with highest degree (hubs) is shown. The horizontal axis shows the fraction of the total network nodes that were designated as hubs. (B) Correlation between degree and essentiality is assessed by Kendall's tau and Spearman's rho rank correlation coefficients.

doi:10.1371/journal.pcbi.1000140.g001

From Figure 1A it is clear that the enrichment values increase with k. Therefore, one can use a nonparametric measure of association, such as Kendall's tau and Spearman's rho rank correlation coefficients [26], to assess the correlation between degree and essentiality over all network nodes. As shown in Figure 1B these two measures agree in their estimates of the strength of the correlation; therefore all further evaluations were done with the Kendall's tau rank correlation coefficient. Then, to assess the correlation between other centrality measures and essentiality after correcting for correlation with degree, we used a partial Kendall's tau rank correlation.

It should be noted that in contrast to other networks the Y2H network exhibits only a weak correlation between degree and essentiality. This is in agreement with the study of Batada et al. [4]. They observed a highly significant difference in the average degree of essential and nonessential proteins in the LC network but found that the difference almost disappears when the analysis is restricted to interactions detected by only the yeast-two-hybrid experiments.

Essential Hubs Are Not More Important in Maintaining the Overall Network Connectivity Than Nonessential Hubs

A network centrality index assigns a centrality value to each node in the network that quantifies its topological prominence. Topological prominence can be defined in a number of ways, and over the years many centrality indices were introduced that emphasize different aspects of network topology [27]. In a local centrality index, the node's centrality value is mainly influenced by the topology of its local neighborhood. A well known example of a local centrality index is degree centrality, where the node's centrality value is equal to the number of its immediate neighbors. Betweenness indices, on the other hand, assign centrality values based on the node's role in maintaining the connectivity between pairs of other nodes in the network. A well-known example of a betweenness centrality index is shortest-path betweenness centrality, where the node's centrality value is proportional to the fraction of shortest paths that pass through it.

Even though degree centrality is a local centrality index, in some networks hubs may play an important role in maintaining the overall connectivity of the network. For example, it was demonstrated that in some scale-free networks the removal of hubs affects the ability of other nodes to communicate much more than the removal of random nodes [8]. To clarify the topological role of hubs in the tested networks, we compared degree centrality to two other local indices (eigenvector centrality (EC) [28] and subgraph centrality (SC) [29]) and to two betweenness indices (shortest-path betweenness centrality (SPBC) [30] and current-flow betweenness centrality (CFC) [31]). (See Figure 2 for an illustration, and Materials and Methods for a more detailed description of the centrality measures used in this study.)

Figure 2. Centrality measures demonstrated on a toy network.

Here we demonstrate the difference in the five centrality measures on a toy network. (A) The toy network consists of two cliques: K₅₀ with nodes A₁–A₅₀ and K₁₀ with nodes B₁–B₁₀. The two cliques are interconnected by an edge (A₁, B₁) and through an additional vertex D. Additional node C attaches to the network through A₂. (B) As the measures assign centrality values based on different network properties they will rank nodes differently. Briefly, the eigenvector centrality measure (EC) will assign high-centrality values to nodes that are close to many other central nodes in the network. The subgraph centrality measure (SC) assigns centrality values to a node based on the number of closed walks that originate at the node. The shortest path betweenness centrality measure (SPBC) assigns the node centrality value based on the fraction of shortest paths that pass through the node averaged over all pairs of nodes in the network. The current-flow betweenness centrality measure (CFC) generalizes the SPBC measure by including additional paths, not just the shortest paths, in the computation. Here, the difference between the measures is exemplified by the rankings that they produce for the toy network nodes.

doi:10.1371/journal.pcbi.1000140.g002

Since betweenness indices rank nodes based on their role in mediating communication between pairs of other nodes in the network, it is interesting to compare the effectiveness of high-degree nodes and nodes with high betweenness centrality in disconnecting the network. One common way to measure the impact of the nodes' removal on the network connectivity is by monitoring the decrease in the size of the largest connected component. Figure 3A–F shows, for the six protein interaction networks, how the removal of the most central nodes, random nodes, and essential proteins affects the network connectivity. As expected, removing nodes with high local centrality values is much less disruptive than removing those with high betweenness centrality values. Interestingly, degree centrality is as efficient in shattering the network as betweenness in the DIP CORE, LC, and Y2H networks, is as inefficient as the local indices in the TAP-MS network, and is somewhere between the local and betweenness indices in the HC and BAYESIAN networks. The local measures strongly agree in their ranking of network nodes in all networks except the Y2H network. The agreement is the strongest in the TAP-MS network; as a result the curves for the EC and SC measures overlap completely in Figure 3D.

Figure 3. Vulnerability to attack against most central proteins.

(A–F) The impact of node removal is quantified by the fraction of nodes in the largest connected component. There is one curve for each centrality measure that shows the fraction of nodes in the largest connected component as a function of the fraction of the most central nodes removed. We also show the impact of node removal in a random order and the size of the largest connected component when all essential proteins are removed.

doi:10.1371/journal.pcbi.1000140.g003

While the removal of a set of nodes may not disconnect various parts of the network, it may impair significantly the “quality of communication” between them. For example, there can be an increase in the length of the shortest path or decrease in the number of alternative paths between pairs of nodes in the network. Therefore, we introduced two additional measures, which we call network integrity measures, to capture various aspects of the effect of the nodes' removal on the ability of other nodes to communicate. (See Materials and Methods for a description of the network integrity measures.) We find that even when these more sensitive measures are used the observations made above about the disruptive power of hubs relative to other most central proteins hold (Table S1).

Next, we examined whether the disruption power of hubs comes mainly from essential hubs. First, we observe that the removal of all essential proteins from the huge connected component is less disruptive than the removal of an equivalent number of the most central nodes according to any index (Figure 3A–F). Moreover, as shown in Table 3, the removal of essential nodes is not more disruptive than the removal of an equivalent number of random nonessential nodes that have the same degree distribution. We conclude that even though in most networks, the DIP CORE, LC, HC, and Y2H networks, the removal of high-degree nodes is disruptive, this disruption is not related to the essentiality of these nodes. On the contrary, essential genes are indistinguishable in that respect from the random nonessential genes with the same degree distribution.

Table 3. Impact of the removal of essential proteins as compared to the removal of an equivalent number of random nonessential proteins with the same degree distribution.

doi:10.1371/journal.pcbi.1000140.t003

There Is No Relationship between the Disruptive Power of a Centrality Index and Its Enrichment in Essential Proteins

Above we demonstrated that various centrality indices vary considerably in their ability to predict disruption in the overall connectivity of the network. Next we asked whether this difference is reflected in the enrichment levels. Figure 4 shows the fraction of essential proteins among hubs and an equivalent number of most central proteins according to five centrality measures. We observe that the local centrality indices have enrichment levels comparable to those of betweenness indices and in some cases even higher. But most notably, degree centrality fares better than any other centrality index in five networks but is narrowly beaten by shortest-path centrality for the Y2H network. The superiority of degree centrality is even more apparent when Kendall's tau rank correlation coefficient is used to measure correlation between centrality values and essentiality over all network nodes (compare Table 2 to Table 4).

Figure 4. Enrichment of hubs and an equivalent number of most central nodes according to other centrality measures in essential proteins.

Fraction of essential proteins among hubs and an equivalent number of most central nodes according to four other centrality measures. The fraction of essential proteins among the nodes of the network is shown as ntwk.avg.

doi:10.1371/journal.pcbi.1000140.g004

Table 4. Correlation between centrality indices and essentiality.

doi:10.1371/journal.pcbi.1000140.t004

As there is considerable correlation between degree centrality and other centrality indices, we used Kendall's tau partial rank correlation coefficient to see whether any of the indices is correlated with essentiality beyond its correlation with degree centrality index. We found that, controlling for the correlation with degree, the correlation with essentiality is reduced to statistically insignificant values for betweenness centrality indices and is greatly reduced for local indices (Table 4).

The above observations indicate that the main topological determinant of essentiality is the node's local neighborhood rather than its role in maintaining the overall connectivity of the network. In particular, even though removing the nodes with high betweenness centrality indices is much more effective in shattering some of our protein interaction networks, their correlation with essentiality is reduced to statistically insignificant levels by subtracting their correlation with degree centrality.

We Reject the Essential Protein Interaction Model

Recently He and colleagues [9] proposed an explanation for the centrality-lethality rule in terms of essential protein interactions: a protein is essential either due to its involvement in one or more essential protein interactions or due to other factors. The authors argue that the determination of protein essentiality in the protein interaction network can be captured by a simple random process: (i) distribute essential protein interactions along the edges of the network uniformly at random with probability α; (ii) distribute essential proteins among the nodes of the network uniformly at random with probability β. Thus, according to the model, the probability (P_E) of a protein with k neighbors being essential is P_E = 1−(1−α)^k(1−β), and the natural logarithm of the fraction of nonessential proteins among proteins of degree k has a linear dependency on k: log(1−P_E) = log(1−α)k+log(1−β).

We note that from the assumptions of the essential protein interaction model it follows that if two proteins do not interact then the essentiality of one protein in such a pair does not depend on the essentiality of the other protein. Furthermore, this independence should also be observed when proteins share interaction neighbors. To test whether this holds in real data, we computed the number of nonadjacent protein pairs, with three or more neighbors (one or more neighbors in the Y2H network), that are either both essential or both nonessential in the tested networks and compared these numbers to the expected number of such pairs under the model. (The model parameters were estimated using three different strategies as described in the Materials and Methods. In their paper, He et al. point out that their model may not work in networks where the edges represent membership in the same protein complex. Thus, we excluded the TAP-MS and BAYESIAN networks from the analysis.) As shown in Table 5, the model does not capture the correlation in essentiality observed in the tested networks; i.e., there is a statistically significant difference between the number of such pairs observed in real data and the number expected under the model. Consequently, the essential interaction model is rejected with high confidence.

Table 5. Difference between the observed and expected number of pairs where both proteins are either essential or nonessential.

doi:10.1371/journal.pcbi.1000140.t005

We Propose an Alternative Explanation for the Centrality-Lethality Rule

In the previous section we showed that proteins that share neighbors are more likely to have the same essentiality (be both essential or both nonessential) than expected under the essential PPI model. Moreover, it was observed in another study that essential proteins are not distributed uniformly among in the set of automatically derived multiprotein complexes [17]. This suggests that densely connected subnetworks are polarized toward being either highly enriched or significantly depleted of essential proteins. Furthermore, it is well known that densely connected subnetworks are enriched in proteins that share biological function. Therefore, one should expect that protein interaction networks contain densely connected functional modules that are highly enriched in essential proteins. Some large multiprotein complexes, for example, those involved in transcription regulation, are known to be highly enriched in essential proteins, but how general is this phenomenon and can it account for the centrality-lethality rule?

To investigate the above question, we introduce a notion of Essential Complex Biological Modules, which are groups of proteins with shared biological function that extensively interact with each other and are enriched in essential proteins. First, we describe an automatic method for the extraction of ECOBIMs from a protein interaction network. Next, we argue that the membership in ECOBIMs accounts to large extent for the centrality-lethality rule in the tested networks. Finally, we address statistical issues related to our selection procedure by applying suitable randomization protocols.

We developed an automatic method for extraction of ECOBIMs from a protein interaction network. In this work proteins are deemed to share biological function if they are annotated with the same GO biological process term from a set of 192 terms that were selected by a group of experts to represent relevant aspects of molecular biology [32]. Therefore, our method is applied to subnetworks induced by proteins annotated with the same GO biological process term, one subnetwork at a time. The high-level idea behind the method is to first identify groups of densely connected proteins, which we call Complex Biological Modules (or COBIMs), and then identify a subset of COBIMs as ECOBIMs based on the distribution of essential proteins among the COBIM nodes. More specifically, our heuristic selects a subset of COBIMs that are enriched in essential proteins. (The method is schematically shown in Figure 5 and is described in detail in the Materials and Methods section. Figure S1 shows the fraction of nodes that are members of r or more COBIMs for various values of r.)

Figure 5. The automatic method for extraction of ECOBIMs.

Here we demonstrate the major steps of the method on the HC network. The input to the method is a protein interaction network, GO annotation, and the set of essential nodes, which are shown in red. The method considers subnetworks induced by proteins annotated with the same GO biological process term, one subnetwork at a time, to identify densely connected regions or COBIMs. The COBIMs are shown by a COBIM intersection graph, where nodes correspond to COBIMs (the size of the node is proportional to the number of genes in the corresponding COBIM) and there is an edge between a pair of COBIMs if they have at least two proteins in common. The COBIMs that are enriched in essential proteins are selected as ECOBIMs, shown in green.

doi:10.1371/journal.pcbi.1000140.g005

To examine to what extent the membership in ECOBIMs accounts for the centrality-lethality rule we partitioned hubs into two groups, those that are members of one or more ECOBIMs (ECOBIM hubs) and those that are not (non-ECOBIM hubs), and compared their enrichment values. As shown in Figure 6 ECOBIM hubs are highly enriched in essential proteins, whereas non-ECOBIM hubs are depleted in essential proteins as compared to the network average enrichment values. But most importantly, as discussed in the next paragraph, the difference in the fraction of essential proteins among ECOBIM hubs and non-ECOBIM hubs is not a result of our greedy ECOBIM selection procedure or particular degree sequence of essential proteins in the network. We next asked whether there is a correlation between degree and lethality for network nodes that are not members of the ECOBIMs. As shown in Table 6 the correlation between essentiality and degree for non-ECOBIM nodes is much less than that for all network nodes.

Figure 6. Enrichment of ECOBIM and non-ECOBIM hubs in essential proteins.

Fraction of essential proteins among various types of hubs: all hubs, hubs that are members of ECOBIMs (ECOBIM hubs), and hubs that are not members of ECOBIMs (non-ECOBIM hubs). The fraction of essential proteins among all proteins in the network is also shown (ntwk.avg.). The numbers above the bars show the number of essential hubs out of the total number of hubs of this type for ECOBIM and non-ECOBIM hubs.

doi:10.1371/journal.pcbi.1000140.g006

Table 6. Membership in ECOBIMs and the centrality-lethality rule.

doi:10.1371/journal.pcbi.1000140.t006

One may ask to what extent the difference in the behavior of ECOBIM hubs and non-ECOBIM hubs is due to the particular selection procedure that we employ to identify the putative ECOBIMs. More specifically, there are two concerns that need to be addressed. First, our method is guided by the enrichment in essential proteins when selecting ECOBIMs from COBIMs. Therefore, it is expected that the fraction of essential proteins among ECOBIM hubs should be higher than that among non-ECOBIM hubs. Second, our method considers only annotated yeast genes. Therefore, one might argue that the difference in behavior is due to the fact that ECOBIM hubs are necessarily annotated while non-ECOBIM hubs may include both annotated and unannotated genes.

To address the first concern we performed a control experiment where essential proteins were assigned to a random set of nodes having the same degree distribution as the true set of essential proteins in the network. (A total of 100,000 random assignments were performed, which resulted in 100,000 sets of ECOBIMs.) To address the second concern, we restricted the random assignment to annotated genes only. As shown in Table 6, the ECOBIMs resulting from the true assignment of essential proteins have dramatically different properties than these resulting from the random assignment of essential proteins. In particular, the fraction of essential proteins among non-ECOBIM hubs under the true assignment of essential proteins is significantly lower than that under the randomized assignment of essential proteins, even though the same selection procedure is used in both cases. Therefore, we conclude that the observed difference is the result of the particular distribution of essential proteins among the nodes of the network and not an artifact of our selection procedure. The same holds for the reduction in correlation between degree and essentiality for non-ECOBIM nodes.

We Identify Properties of the ECOBIMs

The identified ECOBIMs mostly correspond to large essential multiprotein complexes such as the anaphase promoting complex (APC) and the DAM1 protein complex but not exclusively complexes. For example, one of the largest ECOBIMs identified in the LC network contains multiprotein complexes involved in the process of RNA polymerase 2 transcription [33], such as RNA polymerase 2, general transcription factors, the mediator complex, etc. The ECOBIMs with at least 20 members are shown in Table 7; all ECOBIMs and their member proteins are given in Table S2.

Table 7. Largest ECOBIMs extracted from the tested networks.

doi:10.1371/journal.pcbi.1000140.t007

Moreover, the ECOBIMs are remarkably different than non-ECOBIM COBIMs. As shown in Table 8, the distribution of essential proteins among the COBIM nodes is highly uneven. In particular, the observed difference between fractions of essential proteins among the ECOBIM nodes and among non-ECOBIM COBIM nodes can not be accounted for neither by degrees of essential COBIM nodes nor by the particular ECOBIM selection procedure. The last claim is validated by performing 100,000 randomized assignments of essential proteins that preserve degrees and the number of essential COBIM nodes, selecting the ECOBIMs and computing the corresponding fractions. As shown in Table 8, the values obtained under the true assignment of essential proteins are significantly different from those obtained under the randomized assignment of essential proteins.

Table 8. ECOBIMs contain a large fraction of essential COBIM proteins.

doi:10.1371/journal.pcbi.1000140.t008

So far, we demonstrated that the high correlation between degree and essentially can be predominantly attributed to the ECOBIMs. In addition, it is well known that certain functions that are essential to the cell, for example, transcription regulation or cell-cycle regulation, rely on large multiprotein complexes. Indeed, many of the GO terms that are overrepresented among ECOBIM nodes are of this type, as seen in Figure 7. Do ECOBIMs play a distinguished role in those essential processes, or are they merely a byproduct of the above-mentioned observation? In particular, is the difference in the enrichment in essential proteins exclusively due to the fact that some essential GO processes contain ECOBIMs while others do not?

Figure 7. GO terms that are overrepresented among ECOBIM nodes.

For every network the GO terms that are overrepresented among ECOBIM nodes are shown. The overrepresentation of a GO term is quantified by the natural logarithm of a p-value, where the p-value is the probability that at least this number of ECOBIM genes would belong to the GO term had the ECOBIM genes been selected uniformly at random from the network genes.

doi:10.1371/journal.pcbi.1000140.g007