article: Network analysis became a powerful tool giving new insights to the understanding of cellular behavior. Heat shock, the archetype of stress responses, is a well-characterized and simple model of cellular dynamics. S. cerevisiae is an appropriate model organism, since both its protein-protein interaction network (interactome) and stress response at the gene expression level have been well characterized. However, the analysis of the reorganization of the yeast interactome during stress has not been investigated yet. We calculated the changes of the interaction-weights of the yeast interactome from the changes of mRNA expression levels upon heat shock. The major finding of our study is that heat shock induced a significant decrease in both the overlaps and connections of yeast interactome modules. In agreement with this the weighted diameter of the yeast interactome had a 4. 9-fold increase in heat shock. Several key proteins of the heat shock response became centers of heat shock-induced local communities, as well as bridges providing a residual connection of modules after heat shock. The observed changes resemble to a ‘stratus-cumulus’ type transition of the interactome structure, since the unstressed yeast interactome had a globally connected organization, similar to that of stratus clouds, whereas the heat shocked interactome had a multifocal organization, similar to that of cumulus clouds. Our results showed that heat shock induces a partial disintegration of the global organization of the yeast interactome. This change may be rather general occurring in many types of stresses. Moreover, other complex systems, such as single proteins, social networks and ecosystems may also decrease their inter-modular links, thus develop more compact modules, and display a partial disintegration of their global structure in the initial phase of crisis. Thus, our work may provide a model of a general, system-level adaptation mechanism to environmental changes.
  In the last decade due to the advance of high-throughput technologies system level inquiries became widespread. The network approach emerged as a versatile tool to assess the background of the regulation and changes of cellular functions. Analysis of protein-protein interaction (PPI) networks gives particularly rich system level information to understand the functional organization of living cells [1]–[6]. Determination of network modules (i. e. network groups, or communities) became a focal point of the analysis of network topology leading to more than a hundred independent methods to solve this challenging problem. In protein-protein interaction networks tight modules are corresponding to large protein complexes. However, more extensive, pervasively overlapping modules detected by recent methods, including ours, revealed a deeper insight to the multi-functionality of cellular proteins [7]–[9]. Despite of the widespread studies on network modules, the overlaps of interactome modules have not been studied yet in detail. Network dynamics received an increasing attention in recent years. The stress response, inducing a genome-wide up- and down-regulation of gene expression after an abrupt environmental stimulus, is a particularly good model of the reorganization of cellular networks, where the observed changes have a paramount importance in survival, adaptation and evolution [10]–[13]. Yeast is an appropriate model organism for studying the system-level changes after stress, since we have an extensive knowledge on the organization of the yeast PPI network (interactome) [14]–[17], and stress-induced changes in the yeast gene expression pattern have also been studied in detail [18], [19]. Despite of major interest in key biological examples of network dynamics, changes of protein-protein interaction networks in stress have not been analyzed yet. There are two main ways to integrate gene expression data with interactome, identifying active subnetworks [20]–[22] or analysing the whole interactome under genomic responses [15], [16], [23]. In the current study we used the latter approach and assessed the changes of the yeast interactome after the archetype of stress, heat shock. Upon heat shock the yeast PPI network became a much ‘larger world’: heat shock induced a close to 5-fold increase in the weighted diameter and a significant, but partial disintegration of the modular structure of the yeast interactome. The decrease of inter-modular protein-protein contacts may enable a ‘post heat shock’ re-integration of the yeast protein-protein interaction network communities, where the slightly different inter-modular contacts may provide a cost-efficient adaptation response to the changed environment.
  To investigate the changes of the yeast interactome topology in heat shock, a well-characterized form of stress, we calculated the weight of each protein-protein interaction both in resting state and after heat shock. We used the physical protein-protein interaction subset of the BioGRID database [24], combining the benefits of this comprehensive, literature curated database with the more reliable, direct relationship of physical interactions. (We also extended our studies to a high-confidence PPI dataset, and found similar results as described in Materials and Methods.) Link weights of both basal state and heat shocked yeast cells were approximated using mRNA levels, since large-scale, complete datasets for protein abundances are currently missing (see Materials and Methods). We chose heat shock, as the form of stress we studied in detail, since it is considered to be a ‘severe stress’, where a good correlation between the transcriptome and the translatome has been demonstrated [25]. Interaction weights of the yeast PPI network were generated by averaging of the mRNA abundances of the two interacting proteins. Baseline and 15 min, 37°C heat shocked mRNA levels were obtained from the Holstege- [26] and Gasch-datasets [19], respectively, as described in the Materials and Methods section in detail. The distribution of interaction weights showed a significant decrease upon heat shock (Figure S1 of Text S1; Wilcoxon paired test, p<2. 2*10−16). To interpret this change we note, that the PPI networks of ‘resting’ and heat shocked yeast cells had the same links. However, the two interactomes had a largely different weight structure due to the differences in mRNA expression pattern upon heat shock. Table 1 shows a few main attributes of the interactome topology of unstressed and heat shocked yeast cells. In agreement with the significant change in weight distribution, the median weight of interactions had a 14% decrease in heat shock yeast cells. Interestingly, in unstressed yeast cells larger mRNA levels were predominantly associated with larger unweighted degrees, while in heat shocked yeast cells larger mRNA levels were predominantly associated with lower unweighted degrees. Thus, heat shock induces a shift of connection weights from hub-like proteins to non-hubs (see Figure S2 of Text S1), which may indicate a partial uncoupling of the local segments of yeast interactome upon heat shock. The most remarkable change was the close to 5-fold (491%) increase of weighted diameter (Table 1). This was a rather suprising finding, which reflected that the interactome became a much ‘larger world’ after heat shock. The increase of weighted diameter was accompanied by shift in the distribution of weighted shortest path lengths (based on Dijkstra' s algorithm [27]) towards longer paths, causing a significant difference (Wilcoxon paired test, p<2. 2*10−16). Similarly to these findings, the average weighted shortest path length also showed a large increase (47. 1 in unstressed versus 263. 8 in heat shocked yeast cells). The distribution of ‘effective weighted degrees’ showed a scale-free like pattern, and a significant shift towards lower degrees after heat shock (Figure S3 of Text S1; Wilcoxon paired test, p<2. 2*10−16). We note, that the ‘effective weighted degree’ captures the total number of fractional weighted connections of a node to another (see Materials and Methods and [8] for details). The shift towards lower weighted degrees was reflected by the decrease in both the median weighted degree and the number of hubs (14% and 22% decrease, respectively; Table 1). The decrease of median interaction weights, median weighted degree and number of hubs indicated that heat shocked yeast cells developed a generally less intensive, ‘resource-sparing’ interactome. The ‘resource-sparing’ character is in agreement with the close to 5-fold increase of weighted diameter showing that the yeast interactome preferably ‘spares’ the shortcuts, and becomes much less integrated upon stress. Visual inspection of stress-induced changes of the entire yeast interactome is of limited value, since the multitude of interactions makes the comparison difficult. However, there are comprehensible subnetworks allowing an easy, pair-wise assessment. We show the subnetworks of the strongest and weakest links on Figure 1. The subnetwork of strongest links (cf. Figure 1A and Figure 1B) of unstressed yeast cells contained a highly connected ribosomal protein complex (see Figure 1A, inset) and an additional center of carbohydrate metabolism (see Figure 1A, right bottom). Both centers are crucial for the fast cell divisions characteristic to unstressed yeast cells. Please note that the number of links is the same in both panels. Therefore, the link-density of the two major centers is much larger than the apparent density shown on Figure 1A. Upon heat shock several locally dense regions appeared, which were centered on heat-shock proteins (see circles on Figure 1B). This structure showed a re-organization of the interactome around proteins crucial in cell survival and recovery including dehydrogenases, proteins of glucose metabolism, a key player of protein degradation (polyubiquitin), as well as the molecular chaperones, Hsp70 and Hsp104 as detailed in the legend of Figure 1. The subnetwork of network-integrating weakest links [1]–[3], [6], [28] had a uniform link-density in basal state (Figure 1C). After heat shock a very densely connected twin-centre of nucleolar proteins emerged (see the right side of Figure 1D) responsible for rRNA processing and ribosome biogenesis (∼80 and ∼90% of genes by GO term, respectively; p<10−30 in both cases by hypergeometric test). This is in agreement with the key role of nucleolar protein complexes in cell survival [29]. In these representations the unstressed yeast interactome was closer to an organization resembling to the flat, dense, dark and low-lying stratus clouds, whereas the interactome after heat shock was closer to a multifocal structure, resembling to puffy and white cumulonimbus clouds. In former studies ‘stratus’ and ‘cumulus’ forms were described as alternative structures of the general form of yeast interactome [30]. Stratus- and cumulus-type organizations may be differing topology classes in many types of networks, such as in protein structure networks as we proposed recently [31]. In summary, the general network parameters suggested a partial disintegration of the interactome of heat shocked yeast cells represented by the large increase in weighted diameter (Table 1), and by the emergence of a cumulus-like global organization of the subnetworks of strongest and weakest links (Figure 1). Interestingly, metabolic networks of the symbiont, Buchnera aphidicola [32] and the free-living bacterium, Escherichia coli (Figure S4 of Text S1) displayed similar patterns like the interactomes of unstressed and heat shocked yeast cells. Metabolic pathways of B. aphidicola (Figure S4A of Text S1) showed a rather compact organization similar to a ‘stratus-type’ structure, whereas E. coli (Figure S4B of Text S1) had a more multifocal structure similar to a ‘cumulus-type’ network. The latter, cumulus-like structure may show that adaptation to a variable environment resulted in a multifocal pathway structure of E. coli, while the stratus-like structure of the B. aphidicola metabolism may be a consequence of a more stable environment. These assumptions are supported by the larger modularity of metabolic networks in organisms living in variable environment than that evolved under more constant conditions [33]. After our first results suggesting a partial disintegration of the yeast interactome in heat shock exemplified by the increased network weighted diameter and the emergence of a multifocal-like structure of the subnetworks of strongest and weakest links, we examined the heat shock-induced changes of yeast PPI network modules. For the determination of yeast interactome modules we used our recently developed ModuLand framework [8], since it detects pervasive overlaps like other recent methods [34], and therefore gives a more detailed description of PPI network modules than other modularization techniques [8], [34]. Moreover, the ModuLand method introduces community centrality, which is a measure of the overall influence of the whole network to one of its nodes or links. Community centrality enables an easy discrimination of module cores, containing the most central proteins of interactome modules, and makes the functional annotation of PPI network modules rather easy [8]. These modular cores are the hill-tops of the 3D representation of the interactome on Figure 2. On Figure 2 the horizontal plane corresponds to a conventional 2D network layout of the yeast interactome, while the vertical scale shows the community centrality value of yeast proteins. Functional annotations of the most central interactome modules are listed in Table S1 of Text S1 and Table S2 of Text S1. In the unstressed condition (Figure 2A) the central position was occupied by two ribosomal modules showing the overwhelming influence of protein synthesis on yeast cellular functions in exponentially growing yeast cells. Though this module pair was overlapping, their cores were different. Moreover, upon heat shock the two ribosomal modules showed different alterations. The third central module contained proteins of carbohydrate metabolism reflecting the importance of energy supply in yeast growth and proliferation. The additional modules recovered several modules identified before (e. g. the proteasome, ribosome biogenesis and the nuclear pore complex, see [8]). The larger functional diversity of the modules here than that obtained in our preliminary investigations using a much smaller, un-weighted dataset [8] showed the advantages of using a large dataset and interaction weights. In contrast with the unstressed situation, the ribosomal modules had a much smaller community centrality upon heat shock (Figure 2B), which is in agreement with the inhibition of translation after heat shock. The carbohydrate metabolism module kept its central position (Table S1 of Text S1 and Table S2 of Text S1). A novel central module emerged containing proteins involved in the regulation of autophagy, a key process in cellular survival. Several other interactome communities also increased their community centrality, such as modules of heat shock proteins containing several major molecular chaperones and their co-chaperones (e. g. : Sti1, Hsp70, Hsp82 and Hsp104), which all play a key role in sequestering and refolding misfolded proteins after heat shock. Another module of growing centrality was the trehalose synthase module providing an important chemical chaperone for yeast survival (Table S2 of Text S1). Finally, a module of negative regulators of cellular processes (such as that of Bhm1 and Bhm2) also gained centrality (Table S2 of Text S1), exemplifying the energy-saving efforts of the yeast cell in heat shock. The more multifocal modular structure of the yeast cell after heat shock (Figure 2B) compared to the more centralized, compact modular structure of resting cells (Figure 2A) is in agreement with the partial disintegration of the yeast interactome suggested by the increasing weighted diameter (Table 1) and changes of subnetworks containing the strongest and weakest links (Figure 1). To analyze the changes of yeast interactome modules after heat shock further, we compared the modular distribution of proteins in unstressed and heat shocked yeast cells. Figure 3A shows the cumulative distribution of the ‘effective number of modules’. The ‘effective number of modules’ measure efficiently captures the cumulative number of all modular fractions, where a protein belongs to (see Materials and Methods and [8] for details). After heat shock yeast proteins belonged to a significantly fewer number of interactome modules (Wilcoxon paired test, p<2. 2*10−16). In other words this means that modules of the yeast interactome had a smaller overlap after heat shock than in the unstressed state, since there were less proteins belonging to multiple modules, i. e. modular overlaps. Assessing the modular structure one level higher, where modules were treated as elements of a coarse-grained network [8], we compared the effective degree of modules of unstressed and heat shocked yeast cells (Figure 3B). The effective degree captures the total number of fractional weighted connections of a module to another (for details, see Materials and Methods). Upon heat shock interactome modules were connected to significantly smaller number of other modules (Mann-Whitney U test, p = 0. 02299). Since a link between modules is related to the overlap between them ([8], for details see Materials and Methods), the decrease of inter-modular contacts upon heat shock reflects once again a smaller overlap between the interactome communities. The decrease of modular overlap was similar in other stress conditions (e. g. in oxidative stress, reductive stress, osmotic stress, nutrient limitation, see Figure S5 of Text S1), although the heterogeneity of these conditions did not allow to create a coherent picture in every details. The partial decoupling of the interactome modules of stressed yeast cells (Figure 3) is in agreement with the increase of weighted network diameter (Table 1) and with the appearance of a larger multifocality in both the subnetworks of strongest and weakest links (Figure 1), as well as in the 3D image of modular structure (Figure 2). All these findings show a partial disintegration of the yeast interactome upon heat shock. Prompted by our data showing a partial disintegration of the yeast interactome after heat shock, we became interested to assess those proteins, which preserve the residual integration of the interactome upon heat shock. First, we assessed the community centrality changes of yeast proteins after heat shock, since high community centrality values characterize those yeast proteins, which receive a large influence from others [8], and thus integrate the responses of the yeast interactome. As a second step, we studied the bridges, i. e. the inter-modular proteins playing a key role in the remaining connection of interactome modules after heat shock. Figure 4 shows the comparison of the community centrality values [8] of yeast proteins before and after heat shock highlighting five markedly different behaviors. Group A proteins increased their community centrality upon heat shock, Groups B and C contain proteins, which had a continuously high community centrality, while those proteins, which decreased their community centrality are in Group D. Finally, Group E proteins had a continuously low community centrality. Table S3 of Text S1 lists the proteins of the various groups of Figure 4 with their name and functional annotation. Proteins increasing their community centrality (Group A) upon heat shock included major molecular chaperones sequestering, disaggregating and refolding misfolded proteins (Hsp42 and Hsp104), as well as stabilizing cellular membranes (Hsp12) [35]. Group A proteins were also involved in stress signaling and in stress response regulation (e. g. Psr2 phosphatase, Rsp5 ubiquitin ligase) [36], [37], in autophagy regulation (Tor1, Tor2), in the reorganization of the cytoskeleton (Las17 actin assembly factor) [38] and also in yeast carbohydrate metabolism (Glk1 glucokinase, Hxt6 and Hxt7 glucose transporters). These proteins were all heat shock proteins, since they showed increased mRNA expression upon heat shock. Yeast proteins with continuously high community centrality (Group B) included ubiquitin, a ribosome associated, constitutive form of Hsp70 and several key enzymes of carbohydrate metabolism. Proteins having a high, but decreasing importance upon heat shock (Group C) were constituents of the ribosome. Importantly, enzymes and proteins involved in pre-rRNA processing, thus in the synthesis of new ribosomes, showed a large decrease in their community centrality and formed a major part of Group D. These changes reflected the down-regulation of protein synthesis and cell proliferation, which are hallmarks of the heat shock response. Group E proteins with a continuously low importance included several proteins with yet unknown functions, which is understandable knowing the minor role of these proteins both in unstressed and heat shocked yeast cells. In summary, chaperones, proteins of stress signaling and other heat shock proteins, redirecting yeast carbohydrate metabolism in heat-shock, became key players in the residual integration of yeast protein-protein interaction network after heat shock. On the contrary, those proteins, which had been major integrators of the non-stressed yeast interactome (such as proteins of the ribosome or ribosome synthesis) lost their integrating function, and contributed to the partial, modular disintegration of yeast interactome after heat shock. Next, we selected Group A through C proteins as they had large community centrality value in heat shocked conditions, and examined their localization in the subnetwork of the yeast interactome containing the strongest links (Figure 5). Considering that Group A proteins had low community centrality values in unstressed condition, it is not surprising that only one of Group A protein was visible in the subnetwork containing the top 4% of strongest links (Figure 5A). Group A proteins (small→large community centrality) appeared as nodes having strongest links, and occupied rather dispersed locations after heat shock (Figure 5B). Group B proteins (large→large community centrality) were accumulated in one of the two alternative centers of the subnetwork in unstressed condition, and became more dispersed after heat shock (cf. Figure 5C and Figure 5D). Group C proteins (extra large→large community centrality) occupied the other alternative center, the dense core of the subnetwork in unstressed yeast cells, while, similarly to the other groups, they became more dispersed after heat shock (cf. Figure 5E and Figure 5F). In summary, proteins with large community centralities had rather condensed positions in the interactomes of unstressed yeast cells, while they occupied more scattered, dispersed positions after heat shock. This reflects well the key role of the proteins with large community centralities to maintain the integration of the cumulus-type, multifocal interactome of heat shocked yeast cells at multiple positions. As a first inquiry to assess the role of bridges in the maintenance of interactome integrity after heat shock, we highlight a group of four proteins (Table 2; Hsp42, Hsp70, Hsp104 and glycogen phosphorylase). These proteins, beyond their very remarkable increase in community centrality values, were the only proteins, which had a parallel increase in their modular overlap upon heat shock (where the latter was defined as the effective number of their modules, the measure used already in Figure 3A). We note that this behavior was peculiar, since the modular overlap had a general decrease after heat shock (see Figure 3). Therefore it was plausible to claim that the 4 proteins listed in Table 2 were not only central, but also behaved as bridges, connecting parts of the partially disintegrated interactome after heat shock. It is noteworthy that 3 out of the 4 proteins are molecular chaperones (Hsp42, Hsp70, Hsp104), while glycogen phosphorylase is a key enzyme of energy mobilization, a necessity in stress. This finding is in agreement with the results of previous studies and assumptions [39], [40]. As a second inquiry to study the role of bridges in the interactome of unstressed and heat shocked yeast cells, we examined changes of bridgeness of yeast proteins. Figure 6 plots the bridgeness of yeast proteins before and after heat shock. Bridgeness was defined as before [8], involving the smaller of the two modular assignments of a node in two adjacent modules summed up for every module pairs. This value is high, if the node belongs more equally to two adjacent modules in many cases, i. e. it behaves as a bridge between a single pair, or between multiple pairs of modules. Such bridging positions correspond to saddles between the ‘community-hills’ of the 3D interactome community landscape shown on Figure 2. Note that the bridgeness measure characterizes an inter-modular position of the node between adjacent modules, while the modular overlap measure reveals the simultaneous involvement of the node in multiple modules. The highlighted zones of Figure 6 show that the importance of 9 bridges increased, that of 7 bridges remained fairly unchanged, while the importance of only 3 bridges decreased upon heat shock. The increase of the number of key bridging proteins upon heat shock shows the increased importance of a few interactome-intergating proteins after stress (a very strong tendency for a significant change, with p = 0. 051 by Mann-Whitney U test, between the highlighted bridges of Figure 6 having a value larger than 10). The position of the 7 persistently high bridges and the 9 heat shock-induced bridges in the subnetwork of the yeast interactome containing the strongest links is shown on Figure S6 of Text S1. Bridges appeared in this subnetwork at a larger ratio (31% compared to 69% before and after heat shock, respectively), and were re-organized to more inter-modular positions in the interactome of the strongest links after heat shock (Figure S6 of Text S1). Name and function of key bridges are listed in Table S4 of Text S1. The 5 bridges present in both the unstressed condition and after heat shock in the strongly linked subnetwork were Srp1, Yef3, Smt3, Ubi4 and Med7, key proteins of nuclear transport, transcription, translation and protein degradation complexes, respectively. The 6 additional bridges appearing only after heat shock in the strongly linked subnetwork were Whi3, Rpn3, Rsp5, Cbk1, Hek2 and Srs2, key proteins of protein degradation, DNA repair, mRNA sequestration and metabolism, respectively: all essential processes for cell survival in stress. In summary, a rather interesting, complex picture emerged on interactome changes of heat shocked yeast cells. On one hand, the interactome developed a decreased integrity apperaring at several hierarchical levels of the local to global topology. The most remarkable change of all these was the heat shock-induced partial uncoupling of interactome modules. On the other hand, the remaining inter-modular connections remained or became enforced by a few key proteins involved in cell survival.
  The major findings of the current paper are the following: heat shock induces i.) an increase in the weighted diameter of yeast protein-protein interaction network (Table 1); ii.) subnetworks of strongest and weakest links as well as the modular structure show a more multifocal appearance upon heat shock (Figure 1 and Figure 2); iii.) modules became partially decoupled in heat shock (Figure 3); and finally, iv.) a few, selected, inter-modular proteins help the integration of the partially uncoupled interactome of heat shocked yeast cells (Figure 4, Figure 5 and Figure 6). A minor part of our findings was rather obvious. As an example of this: it is more-less expected that many heat shock-induced proteins will have a larger community centrality, since they have an increased weight of their interactions (Figure S1 of Text S1), and therefore, may receive a larger influence of other interactome segments. However, the partial disintegration of the yeast interactome after heat shock is by far not an obvious consequence of heat shock-induced mRNA changes, but a highly non-trivial adaptation to stress at the system level. It is important to note, that this major finding, the partial disintegration of yeast interactome after heat shock, appeared at several levels on network topology. At the very local level, a significant decrease was observed in the weighted degrees upon heat shock (Table 1; Figure S3 of Text S1). At the mesoscopic level a remarkable and highly robust decrease of modular overlaps occurred (Figure 3). At the global scale, a close to 5-fold increase of the weighted network diameter was observed (Table 1.). All these changes point to the same direction and suggest that a more ‘sparing’ contact structure develops upon heat shock allowing a better isolation and discrimination of cellular functions. The heat shock-mediated isolation and discrimination of cellular functions is also reflected by the change in the structure of strongest links (cf. Figure 1A and Figure 1B), where a large number of disjunct network centres develop, and became connected by a few strong links after heat shock (Figure 1B), as opposed to a large density of strong links in a few centres in unstressed yeast cells (see Figure 1A, where the density is so large that it can not be readily visualized even in the magnified inset). The observed findings were in a way indirect. Regretfully, no direct PPI network data exist for heat shocked cells, including yeast. Therefore, we had to calculate the yeast interactome weights after heat shock from mRNA data. As we noted earlier, this approach was justified by the finding that heat shock is a severe form of stress, where transcriptional and translational changes are better coupled [25]. Protein levels are also regulated by protein degradation. Though large-scale data on yeast protein half-lives exist [41], even these data cover only a part of the yeast genome, and their modification in heat shock is not known. Despite of these shortcomings of exact system level data in heat shock, the robustness of our major finding, the partial uncoupling of yeast interactome modules, suggests that the phenomenon we observed is a real, in vivo response of yeasts cells to heat shock. The interactome modules of unstressed yeast cells defined in this paper correspond to the results of other modularization methods. When comparing our results with those obtained by the MCODE method [42] and of another method based on semantic similarity [43], the size of predicted complexes were different, but good functional matches could be identified. When we extended the comparison to methods detecting modules having a wide range of size, like the CNM method [44] or that of Mete et al. [45], besides some minor discrepances, nearly indentical modules were found having either a large size (like that of ribosomal assembly and maintenance) or a small size (like that of tRNA processing; data not shown). In a very interesting study Gavin et al. [14] defined core components and attachments of yeast protein complexes. Core components were constant parts, while attachments were more flexible, fluctuating parts of the protein complexes. Cores of several modules (see Table S2 of Text S1) were often highly similar to the core components Gavin et al. [14] (e. g. in case of the proteasome, mitochondrial translation or RNA polymerase complexes). Core proteins of the ribosome and carbohydrate metabolism were found to be in many attachment regions of Gavin et al. [14] (15 and 4 attachments as opposed to 0. 2 and 0. 8 cores on the average, respectively). This is in agreement with our current results showing that these proteins have an extremely high community centrality, i. e. accommodate a large influence of multiple interactome segments. Our study provides the first detailed comparison of the interactome structure before and after heat shock. However, there were a few studies, which contained a part of this information directly, or indirectly. Valente and Cusick [16] mapped the modular structure of unstressed yeast cells, and (assuming that the structure is invariant) determined which modules are up- and downregulated under heat shock. They found several modules with similar functions to those of the unstressed cells detected in our study (e. g. ribosomes, proteasomes and complexes involved in cell cycle control, or the organization of the chromosome and cytoskeleton). The heat shock-induced changes were also similar, showing a high similarity of downregulated modules (e. g. those responsible for ribosomal function, or chromosome organization). The upregulated modules were partially consistent with our results (cell cycle control) with the exception of the proteasome and cytoskeleton organization complex. In these two exceptions we detected a central role of these two modules in the unstressed condition already, which made the detection of their further upregulation difficult. Another comparison arose from the study of Komurov and White [15], who identified static and dynamic modules. Very interestingly, modules that were found only in unstressed or heat shocked conditions in our study corresponded to their dynamic modules (regulation of intracellular pH, proteasome, ribosome biogenesis, trehalose biosynthesis). Wang and Chen [46] developed an integrated framework of gene expression profiles, genome-wide location data, protein-protein interactions and several databases to study the yeast stress response. Their study shows the system-level mechanism of the yeast stress response highlighting the major transcription factors of this process. The study complements ours describing stress-induced consequences at the systems level. The results of Wang and Chen [46] demonstrated a large degree of general similarity of various stress responses in yeast (among others showing that 136 out of 190 transcription factors are conserved in osmotic, oxidative and heat shock), which is in agreement with the similarity of interactome-level changes of network topology after various types of stresses we observed in yeast (Figure S5 of Text S1). Our results may put the ‘stratus/cumulus debate’ [30], [47], [48] in the new contextual framework of cellular dynamics. Our findings showed that the unstressed yeast interactome resembles more to a stratus-type, whereas the heat shocked (stressed) interactome resembles more to a cumulus-type organization. This indicates that the stratus and cumulus interactome conformations may not be as antagonistic as thought before, and none of them may be a clear artifact. Our results suggest that both network conformations may occur in vivo, and may characterize different states of the organism. Regretfully no quantitative measures for this structural feature have been defined so far. This will be a subject of further interesting studies. Our earlier surveys of the literature anticipated a stress-induced decrease in the number and weights of interactions, as well as the decoupling of network modules. Chaperones were hypothesized to play a major role in the coupling/decoupling processes, since they occupied a more central position during stress, and their occupation by damaged, misfolded proteins after heat shock led to a release of their former targets. This phenomenon was termed by us as ‘chaperone overload’ [39], [49]. Our recent results support these previous considerations. Moreover, the present findings considerably extend the earlier assumptions showing the details of the heat shock-induced partial disintegration of the yeast interactome. What may be the reasons, which make a partial disintegration of the interactome an evolutionarily profitable response for yeast cells after heat shock? i.) The decreased number and weights of interactions may be regarded as parts of the energy saving mechanisms, which are crucial for survival. The specific decrease of inter-modular contacts may ‘slow down’ the information transfer of stressed cells, which is a further help to save energy. ii.) The increased weighted diameter and the partially decoupled modular structure of the interactome may localize harmful damages (e. g. free radicals, dysfunctional proteins), and thus may prevent the propagation of damage. iii.) Dissociation of modules may help the mediation of ‘intracellular conflicts’, e. g. opposing changes in protein abundance and dynamics in stress. iv.) The appearance of a more pronounced modular structure may allow a larger autonomy of the modules. This is beneficial, since more distinct functional units may work in a more specialized, more effective way, and at the same time may also explore a larger variety of different behavior, since in their exploratory behavior they are not restricted by other modules to the extent than before stress. The larger autonomy of modules increases both the efficiency and learning potential of the cell sparing additional energy. The observed partial disintegration of the yeast interactome after heat shock is most probably only transient. The partial de-coupling of the interactome modules is presumably followed by a re-coupling after stress, which not only restores a part of the original, denser inter-modular connections, but may also build novel inter-modular contacts, giving a structural background to the adaptation of the novel situation [39], [40], [50], [51]. This brings a novel perspective to those proteins, which help to maintain the integration of the yeast interactome during heat shock, since some of these inter-modular proteins may play a role in the adaptive reconfiguration of PPI network as a response to the changed environment. The presence of 3 major chaperones among those 4 proteins, which increased their inter-modular overlap upon heat shock (Table 2), supports this assumption, since chaperones are well-known mediators of cellular adaptation in stress and during evolution [39], [49]. The decrease of modular overlap was similar in other stress conditions (e. g. in oxidative stress, reductive stress, osmotic stress, nutrient limitation; see Figure S5 of Text S1), although the heterogeneity of these conditions inhibited to create a coherent picture in every details. Prompted by the generality of stress-induced partial disintegration of the yeast protein-protein interaction network, and by the generality of the beneficial reasons behind these changes, we were interested to see, whether similar changes may occur in other complex systems. Bagrow et al. [52] showed that network failures of a model system cause the uncoupling of overlapping modules before the loss of global connectivity. A similarly modular, sequential disruption of (presumably inter-modular) links was observed, when single molecules of the giant protein, titin were pulled introducing a physical stress [53]. Bandyopadhyay et al. [54] showed that while protein complexes tend to be stable in response to DNA damage in a genetic network, genetic interactions between these complexes are reprogrammed. Similarly to the changes shown on Figure S4 of Text S1, the group of Uri Alon found that networks of organisms in variable environment are significantly more modular than networks that evolved under more constant conditions [33], [55]. These studies all revealed the stress-related dynamism of intermodular regions in other cellular contexts. Looking at even broader analogies Tinker et al. [56] showed that food limitation causes a diversification and specialization of sea otters that greatly resembles to the changes of yeast interactome modules in stress. A similar increase of modularization (patchiness) was observed in increasingly arid environments suffering from a larger and larger drought stress [57]. A partial decoupling of social modules was also observed, when criminal networks faced increased prosecution [58]. A recent study detected a reorganization of brain network modules during the learning process [59]. As a far-fetched analogy, stress-induced psychological dissociation [60] may also be perceived as a partial decoupling of psychological modalities. The stress-induced uncoupling/recoupling cycle greatly resembles Dabrowski' s psychological development theory of positive disintegration [61], as well as the Schumpeterian concept of “creative destruction” describing long-term socio-economic changes [62]. In agreement with this general picture, Brian Uzzi and co-workers [63] recently showed that brokers shift their link-structure of instant messaging from weak to strong ties under the initial phase of crisis-like events at the stock-exchange, which may reflect a partial de-coupling of weakly linked broker-network modules together with an increase of strong link-mediated intra-modular cohesion. Estrada et al. [64] proposed a model, where communicability and community structure of socio-economic networks are affected by external stress (e. g. by social agitation, or crisis). They showed that community overlaps diminished with the increase of stress. Increased modularity of the banking system may be a very efficient way to prevent the return and extension of the recent crisis in economy as pointed out recently by Haldane and May [65], and as applied by the Volcker Rule in the USA. These broad analogies are supported further by the previously proposed [31] generality of the two basic network conformations, the stratus- and cumulus-like network topology observed here before and after heat shock, respectively. In summary, the major finding of our study was that heat shock i.) induces the increase in the weighted diameter of the yeast interactome; ii.) sets up multifocality in both subnetworks and modules of the yeast interactome, as well as iii.) contributes to the decoupling of the modules of the heat shocked yeast interactome. Parallel with these changes a few remaining inter-modular connections play an enhanced, prominent role in the residual integration of the yeast interactome. Our work may provide a model of a general, system-level adaptation mechanism to environmental changes.
  The budding yeast (S. cerevisiae) PPI data were from the BioGRID dataset [24] (www. thebiogrid. com, 2. 0. 58 release), which is a freely accessible database of physical and genetic interactions. To avoid indirect interactions only the physical interactions of the database were used. These interactions (contained in the experimental system column of the database) included physical in vitro interactions such as biochemical activity-derived, co-crystal structure-related, far-Western, protein-peptide, protein-RNA, or reconstituted complex interactions, as well as physical in vivo (like) interactions, such as affinity capture mass spectrometry, affinity capture RNA, affinity capture Western, co-fractionation, co-localization, co-purification, fluorescence resonance energy transfer and two-hybrid interactions. The giant component of the obtained PPI network was used containing 5,223 nodes and 44,314 interactions. In the absence of reliable and large-scale weighted yeast protein-protein interaction data, network link weights were generated from mRNA microarray datasets as described later. We also analyzed the high-confidence PPI dataset of Ekman et al. [23], where the giant component of the network comprised 2,444 proteins and 6,271 interactions. These results were consistent with our presented findings (Figure S7A of Text S1), although the small scale of network and the nature of interactions (which were not restricted to physical interactions as our dataset), reduced the biological relevance of this latter analysis. Yeast whole-genome mRNA expression datasets were from Holstege et al. [26] (called as the “Holstege-dataset”) as a reference dataset for the baseline, non-stressed yeast gene expression profile, and from Gasch et al. [19] (called as the “Gasch-dataset”) measuring relative expression profiles in various stress conditions. The Holstege-dataset contained data of 5,449, while the Gasch-dataset contained data of 6,152 yeast genes, respectively. From the Gasch-dataset we selected heat shock as the archetype of stress conditions. Besides being a widely examined form of stress, heat shock is considered as a “severe stress” by Halbeisen and Gerber [25], where a good correlation between translational and transcriptional changes have been found. We analyzed the ‘hs-1’ condition of the Gasch-dataset (15 minutes of 37°C heat shock), where broader time series were monitored than at ‘hs-2’ or other heat shock conditions (the stress condition names are the same as used by Gasch et al. [19]). We performed our analysis using longer durations of 37°C heat shock (40 and 80 minutes compared to that of the 15 minutes of the “hs-1” dataset, [19]). In line with the expectations, heat shock induced gene expression was less remarkable after 40 minutes and returned close to the baseline level after 80 minutes. Therefore we performed a detailed analysis only with the 15 minutes heat shock dataset. Importantly, our major finding, the decrease of modular overlaps after stress was robust, and persisted in all heat shock conditions tested. The decrease of modular overlap was similar in other stress conditions (e. g. in oxidative stress, reductive stress, osmotic stress, nutrient limitation, see Figure S5 of Text S1), although the specificity and heterogeneity of these conditions inhibited to create a coherent picture in every details. Although logarithmic transformations are extensively applied in the literature, we used absolute expression values. The use of absolute expression values instead of logarithmic values was in part due to the technical difficulty that after the logarithmization step negative protein-protein interaction weights would also arose that could not be interpreted. Negative weights of the logarithmized mRNA data could be avoided applying a 1000-fold increase as a rescaling correction, which is appropriate all the more, since protein levels are roughly by this magnitude higher than the corresponding mRNA levels [66]. Using this methodology, we got similar major findings as those shown in the paper (Figure S7B of Text S1). However, due to the larger number of correction steps we did not pursue this approach in detail. Weights of interactions in the PPI network were generated from the mRNA expression data in two steps. 1.) In the first step the baseline, non-stressed protein abundances were taken as the mRNA expression levels of the Holstege-dataset [26], then the baseline protein abundance values were multiplied by the relative mRNA changes of the Gasch-dataset [19], resulting in the approximated protein abundances after heat shock. Since the Gasch-dataset contained only relative values, and therefore could not be used as a baseline-dataset, we had to use the Holstege-dataset to calculate the baseline weights of the PPI network. To check, whether our results are sensitive for baseline selection, we performed our analysis using another gene expression dataset, where time zero data were also provided [18]. This approach resulted in a similar decrease of modular overlaps (data not shown), showing that using two different datasets for mRNA abundances do not cause unexpected variability. Due to the greater ratio of missing data (∼14% in baseline data and ∼11% after heat shock) we did not prefer this dataset in detailed analyses. We also tried to use protein abundances instead of mRNA abundances for the unstressed condition [67], [68], but due to the large amount of missing data in these data sets (>50%) we have not pursued this approach further. When using the mRNA changes as approximations of changes in protein levels, in agreement with Halbeisen and Gerber [25], we assumed that the mRNA expression data in heat shock correlate well with protein abundance. Missing expression data for proteins in the PPI network (436 nodes total in the baseline network, less than 9% in case of the Holstege-dataset, as well as 504 nodes total in the network after heat shock, less than 10% of the Gasch-dataset) were substituted by the median expression values (0. 8 in case of the Holstege-dataset, and 0. 9931 in case of the Gasch-dataset), where the median was selected instead of the mean, since the distributions also contained extreme values. 2.) In the second step link-weights of the PPI network were generated by averaging of the abundances of the two proteins linked. We also tried multiplication instead of averaging that gave very similar results and provided sufficiently robust data in case of the smaller, high-confidence PPI dataset of Ekman et al. [23] (see Figure S7A of Text S1). However, we rejected this approach in case of the BioGRID dataset, as in case of this much larger dataset it resulted in a ‘rougher’ community landscape with more extreme changes of community centralities than averaging, which has been generally used in calculation of our data. The use of an unweighted baseline PPI network resulted in much less consistent data due to the large difference between the homogeneity of the unweighted baseline and the inhomogeneity of the weighted heat shocked PPI networks. The physical meaning of heat shock-induced changes in gene expression is encoded precisely by the changes of link weights at the network level. This assumption makes it understandable that an unweigthed network gave false positive results in important parts of the analysis. This has two major reasons. On one hand, community centrality values are largely affected by the density of interactions. Therefore, in an unweigthed network, proteins having a high link density in their neighborhood would result in high community centrality values independently from their expression level. On the other hand, the metrics used in the analysis (e. g. overlap as the effective number of modules) are sensitive measures of fine topological changes, therefore they were largely different in the unweighted, homogenous interactome as compared to the weighted, heterogeneous interactome. In principle, ‘relative changes’ of mRNA expressions could also be used for comparison (where a, say, 4-fold increase in mRNA expression of a given gene can be split to a 2-fold decrease of its baseline abundance and a 2-fold increase of its abundance after stress corresponding to the abundances of the same protein in resting and stressed yeast cells, respectively). However the use of these ‘relative changes’ of mRNA expression resulted in a large variability of the baseline PPI network weights (Figure S8 of Text S1). The method using the average of protein abundance values as interaction weights, we described above, gave a reliable probabilistic model, since the more abundance the associated proteins had, the more possible they interacted, and the more weight of their PPI network link possessed. Moreover, by considering the baseline expression rates, we received a more exact description of the importance of proteins in the yeast cell in both baseline and stressed conditions. Yeast PPI network modules were determined using the NodeLand influence function calculation algorithm with the ProportionalHill module membership assignment method of the ModuLand module determination method family described by the authors' lab recently [8]. During the post-processing of the module assignment no merging of primary modules was applied. The ModuLand method determines extensively overlapping network modules by assigning proteins to multiple modules, which reflects well the functional diversity of proteins. The ModuLand method constructs a community landscape, where the landscape height of a protein corresponds to a community centrality value showing the influence of the whole PPI network to the given protein, thus the importance of the appropriate protein in the whole yeast interactome. In fact, community centrality is a summarized value, where in the first step of the method (currently: the NodeLand influence function calculation algorithm) all increments of the influence of other proteins to the given protein are summed up. In the second step of the calculation process (currently: the ProportionalHill modules membership assignment method) proteins with locally high community centrality (corresponding to ‘hills’ of the community landscape, see the 3D image of Figure 2) form the core of a module of the interactome. Individual proteins are characterized by their membership assignment strength to all interactome modules. (Usually one or a few of the modules are the ones, where the protein belongs the most, while all the other modules contain the protein only marginally). With the ModuLand framework the functional annotation of modules becomes rather easy, since it can be derived from the functions of the ‘core proteins’ having the largest community centrality in the module. In the current work core proteins of a given module were determined as the 5 proteins having the maximal community centrality (the number of core proteins has been extended to 8 in some exceptional cases, where indicated). Comparison of the functions of proteins with lower community centralities than that of the core proteins did not change the consensus of functional annotation of modules ([8] and Table S1 of Text S1). The effective degree of nodes and modules, as well as the effective number of modules were calculated as described earlier [8]. All effective numbers refer to a set of data, where the sum is not calculated as a discrete measure, but as a continuous measure taking into account the weighted values of the data. The effective numbers were calculated using the subsequent equation: , where data were in set V, V[i] was the value of data i, and. The dataset, V contained i.) in case of the effective degree of nodes the weights of the interactions of the given node as defined earlier; ii.) in case of the effective degree of modules the weights of the links of the given module to all neighboring modules as defined here later; and iii.) in case of the effective number of modules the module membership assignment strengths of the given node to all modules of the yeast interactome. The weight of the link between modules i and j was the sum of the node-wise calculated overlap values Oij (n): , where Oij (n) was proportional to the module membership assignment strengths Hi (n) and Hj (n), and was normalized to the community centrality as: , where c (n) was the community centrality of node n, and the factor 2 referred to that both directions between the modules have been taken into account. For the functional categorization of yeast PPI network modules (see Table S1 of Text S1 and Table S2 of Text S1), the Gene Ontology (GO) term, biological process [69] (http: //www. yeastgenome. org/cgi-bin/GO/goTermFinder. pl) of the core modular proteins (as defined above) were compared. A modular GO term was assigned, if the core proteins shared a significant (p<0. 01) amount of their GO terms. GO terms of only the most central modules were identified, since they were supposed to have a relevant role in cellular functions. The threshold was applied by the community centrality values of the most central proteins of modules (where community centrality values were greater, than 500), and this resulted in 15 or 14 modules for the unstressed or heat shocked conditions, respectively. In those exceptional cases, when the 5 core modular proteins did not result in a meaningful functional assignment (in case of 5 modules representing 17% of the 29 modules total), we extended the core-set to 8 proteins. Only 2 modules (representing 7% of the 29 modules total) were found, where none of these definitions resulted in any common assignment. For the statistical evaluation of data the non parametric statistical tests of the Mann-Whitney U test and the Wilcoxon paired test were applied using the R-statistical program (https: //www. r-project. org) as described in the actual experiments. The hypergeometric test was performed as provided by the Gene Ontology Term Finder: http: //www. yeastgenome. org/cgi-bin/GO/goTermFinder. pl.
summary: In the last two decades our knowledge on stress-induced changes has been expanded rapidly. As a part of this work a large number of key proteins and biological processes of cellular adaptation to stress have been uncovered. However, we know relatively little on the systems level changes of the cell in stress. In our study we used the network approach to study the changes of the yeast protein-protein interaction network (interactome) in the archetype of stress, heat shock. The major finding of our study is that heat shock induced a marked decrease in the inter-community connections of the yeast interactome. The observed changes resembled to a ‘stratus-cumulus’ type transition of the interactome structure, since the unstressed yeast interactome had a globally connected organization, similar to that of stratus clouds, whereas the heat shocked interactome had a multifocal organization, similar to that of cumulus clouds. Our results indicated that heat shock induces a partial disintegration of the global protein-protein network structure of yeast cells. This change may be rather general occurring at the initial phase of crises in many complex systems, such as proteins in physical stretch, ecosystems in abrupt environmental changes or social networks in economic crisis.
keywords: cellular stress responses
  protein interactions
  macromolecular assemblies
  synthetic biology
  signaling networks
  protein abundance
  protein folding
  chaperone proteins
  proteins
  regulatory networks
  biology
  proteomics
  biophysics
  molecular biology
  macromolecular complex analysis
  systems biology
  biochemistry
  cell biology
  computational biology
  molecular cell biology
  genetics and genomics
  macromolecular structure analysis
title: Heat Shock Partially Dissociates the Overlapping Modules of the Yeast Protein-Protein Interaction Network: A Systems Level Model of Adaptation