BACKGROUND
in recent years, systematic experimental studies, such as those using tap tag mass-spec techniques, have provided a draft map of yeast multi-protein complexes  <cit> .
this map shows the composition of the quaternary protein structures in this model organism.
the next challenge is to uncover which complexes work together to perform particular cellular tasks.
one way to accomplish this is to detect the synchronized regulation of multi-protein complexes.
coordinated regulation may be defined as a synchronous pattern of increased or reduced mrna transcription of several cellular multi-protein complexes in response to a given perturbation.
such coordinated regulation of complexes is found when cellular function requires several complexes to be co-expressed or when other complexes need to be repressed for a given complex to function.
for example, to achieve proper initiation of the translation process in eukaryotes, numerous cellular multi-protein complexes are regulated in a coordinated fashion.
in this process, the initiation factor complexes eif <dig>  eif <dig>  and the cap-binding protein complex  associate to bind the ribosomal small subunit complex  .
another example involves the tor complex  <dig> , a conserved ser/thr kinase that regulates cell growth and metabolism in response to nutrients and stress.
when nutrients are available, tor activates complexes related to ribosome biogenesis, translation and nutrient import.
in contrast, starvation inhibits tor activity, thereby inducing various cellular responses such as cell arrest in the early g <dig> phase, inhibition of protein synthesis, nutrient transporter turnover, transcriptional changes, and autophagy.
these responses are all mediated by multi-protein complexes  <cit> .
intricate relationships among genes and groups of genes  are not captured by simple pairwise correlations; rather, higher order analysis is necessary to derive more detailed relationships.
in the past few years diverse methods, such as binary and bayesian networks, have been developed to derive gene networks .
however, these approaches aim to detect co-regulated expression modules among individual genes, while methods to detect co-regulation among groups of genes, such as multi-protein complexes, still need to be developed.
in the present study, we apply logic analysis to gene expression data to identify gene triplets related by various types of logic functions  <cit> .
next, we combine these to study coordinated relationships among multi-protein complexes.
logic analysis is a method to relate triplets of genes/proteins by certain logic functions based on genomic data.
all eight possible logic functions among triplets of genes can be found in figure  <dig> and additional file 1: table s <dig>  the triplet logic approach was introduced by bowers et al.
<cit>  and applied to genomic data in the form of phylogenetic profiles .
subsequently, logic analysis was also applied to find relations between the expression of two genes and disease state phenotypes  <cit> .
in the current study, logic analysis is extended and modified for application to gene expression data.
the original approach assigned a binary value  to a gene for each organism or gene expression experiment.
in this work we use a three state model that describes genes as induced, repressed, or non-regulated.
we construct two separate regulatory state vectors for each gene, where one vector describes whether a gene is induced or not over the set of experiments, while the other describes whether the gene is repressed or not .
these vectors are then used to identify gene triplets whose regulation obeys logic functions  <cit> .
for example: gene c is induced/repressed if and only if  gene a is induced/repressed and gene b is induced/repressed.
we also introduce a p-value for each gene triplet that quantifies the likelihood of obtaining this triplet by chance .
next we grouped genes with the same logic function that mapped to the same set of three multi-protein complexes.
this type of grouping enables us to infer how the coordinated regulation of these complexes occurs in the cell .
to explore the utility of our approach, we applied triplet logic analysis to yeast microarray data that measures the response of gene expression levels to environmental changes  <cit> .
we identified genes whose regulation obeys triplet logic functions, and mapped these genes to distinct, multi-subunit complexes to infer coordinated regulation between the complexes.
among the many complexes inferred to have coordinated regulation, we discuss examples related to the biogenesis of the ribosome and support them with known regulatory data.
in addition, we derive a cellular network of all complexes that have different triplet relationships with the ribosome.
this network reveals that in stress conditions, all complexes belonging to the same functional classes are regulated in the same direction .
this observation may suggest the existence of global regulation of numerous cellular multi-protein complexes that belong to the same functional class.
RESULTS
identifying gene triplets whose regulatory patterns obey logic functions
we applied logic analysis to expression data to identify gene triplets whose regulation obeys one of the eight possible logic functions .
the analysis was applied to data of gasch et al.
, which measure the expression of all saccharomyces cerevisiae genes in response to various environmental stresses.
initially, we constructed two binary state vectors for each gene.
one vector describes whether the gene is repressed and the other vector describes whether the gene is induced across of the microarray experiments; vectors were retained for analysis only if induction or repression was seen in at least 10% of experimental conditions .
this resulted in  <dig>   gene vectors, 45% of which represent the induced state while 55% represent the repressed state.
next, using these binary vectors, we analyzed all possible gene triplets.
we identified about nine million potentially significant gene triplets, based on the associated uncertainty coefficient  and p-value.
these thresholds were chosen to filter out triplets that are only related by pairwise correlations between two genes .
some of the gene triplets were significant under more than one type of logic function.
in these cases we assigned to each gene triplet the most significant logic function as defined by the highest u value.
this assignment reduced the number of non-redundant triplets for further grouping and analysis to  <dig> , <dig>
the eight possible types of triplet logic relationships described earlier  <cit> , occur with different frequencies .
the four types , a xor b, a or b, and a and b represented  <dig> %,  <dig> %,  <dig> %, and  <dig> % of the cases, while the remaining four types almost never occurred.
we believe certain logic types are rare because the binary microarray data we are using is relatively sparse .
as a result, only logic functions where f =  <dig> are observed often, whereas functions where f =  <dig> are not.
additional file 2: figure s <dig> contains example heat maps of triplets of genes that obey the and and xor logic functions.
mapping gene triplets to multi-protein complexes
we mapped all gene triplets to complexes as described in methods.
we identified  <dig>  triplets that were composed of genes that mapped to multi-protein complexes.
of these triplets,  <dig>  mapped to a single multi-protein complex,  <dig>   triplets mapped to at least two different complexes and about 90% mapped to three different complexes.
as mentioned above, the u value was used to filter out gene triplets that are associated only by pairwise correlations .
that most gene triplets mapped to more than one complex supports our choice of this threshold.
grouping gene triplets that map to three complexes
next we grouped together gene triplets obeying the same logic function and mapping to the same set of three complexes .
we restricted our analysis to two logic functions: xor and and.
these two functions were abundant in our data and were judged to have more intuitive biological interpretations than the other logic types .
the logic function and yields  <dig> triplets of protein complexes.
for each triplet of complexes we computed the significance of the finding based on the number of gene triplets that map to these complexes and computed a p value using the hypergeometric distribution .
out of these  <dig> triplets of protein complexes,  <dig>  are significant .
a total of  <dig>  triplets of protein complexes were related through the logic function xor, of which  <dig>  are significant .
the significant triplets of protein complexes related through logic functions and and xor include  <dig> and  <dig> different protein complexes which are supported by  <dig> and  <dig>  gene triplets respectively.
the genes composing the triplets encode a subset of the subunits of each complex.
this may be explained by the incompleteness of the microarry data  and the strict parameters we choose.
to check if the subunits we identify are representative of the entire complex, we calculated the expression coherence between the subunits of a complex.
we found that in all complexes that appear in our study, the expression was indeed coherent .
the list of all triplets of protein complexes which have coordinated regulation  appears in additional files  <dig> and 5: tables s <dig> and s <dig>  below we discuss examples of the triplets of protein complexes whose synchronized regulation has been previously described in the literature, as well as novel predictions of co-regulation of complexes.
regulation of protein translation, autophagy degradation and n-linked glycosylation - examples of triplet complexes that have coordinated regulation obeying the and logic function
ribosome large subunit - 60s, eif2b initiation factor and rna polymerase i/iii
our results reveal that the transcription of the 60s ribosomal large subunit decreases if and only if  the transcription of the eif2b initiation factor and rna polymerase i/iii are decreased as well.
the three subunits of the rna polymerase, rpb <dig>  rpc <dig>  and rpo <dig> that participate in this logic relation are components of both polymerase i and iii.
figure  <dig> shows the subset of experiments  where the transcription of all three complexes decreases.
indeed, co-regulation between complexes involved in ribosome biogenesis  and protein translation  was shown recently to be mediated by tor signaling, as reviewed in wullschleger et al.
<cit> .
in response to nutrients, tor induces ribosome biogenesis, translation, and nutrient import, whereas stress conditions repress these functions  <cit> .
our results suggest the stress conditions tested in these experiments inhibit tor signaling and this inhibition leads to the repression  of all three complexes.
chip-chip data reveal that the genes encoding the subunits of ribosome 60s, rna polymerase and eif2b are bound by overlapping sets transcription factors.
genes encoding rna polymerase i/iii subunits and ribosome large subunits are bound by the abf <dig> transcription factor , whereas genes encoding the rna polymerase i subunit and the eif2b subunit genes are bound by rpn <dig>  and dig <dig> .
ribosome 60s and 40s subunits and the autophagy related complex
we find that the transcription of the 60s ribosome large subunit decreases only when the transcription of the 40s subunit decreases and the transcription of autophagy related complex increases.
figure  <dig>  shows that in a subset of experiments the transcription of the autophagy-related dimer complex aut2p/aut7p is increased when the transcription of both of the ribosomal complexes, 40s and 60s is decreased.
although the relation includes only one subunit of the 60s ribosomal complex, it is known that ribosomal subunits are strongly co-expressed  of 86% of possible pairs within the ribosome).
all other subunits of the 60s ribosome were assigned lower scores due to incompleteness of the microarray data in the specified experiments and the strict parameters we choose.
aut2p/aut7p has a role in protein degradation while the two ribosomal complexes 40s and 60s have a role in protein synthesis.
that these two complexes have opposite function likely explains their opposite transcriptional regulation in this subset of experiments .
in this example as in the previous one, the tor signaling pathway is known to mediate both the translation and the autophagy processes.
when the cell experiences stress conditions, the torc <dig> complex is inhibited.
this inhibition leads to decreased transcription of genes involved in translation and also leads to activation of the autophagy process  <cit> .
we identified tfs that bind genes of both the 40s and 60s ribosomal complexes, but could not identify tfs that also bind genes encoding the aut2/aut <dig> complex, possibly because we employed strict filtering of the chip-chip data .
moreover, we did find that genes encoding subunits of the torc <dig>  and ribosomal 40s and 60s subunits are all bound by the reb <dig> , pho <dig>  and msn <dig>  tfs.
ribosome 60s, rna polymerase i/iii and mannosyltransferase glycosylation complex
the transcription of the 60s ribosomal large subunit decreases only when the transcription of rna polymerase i/iii and the m-pol ii complex are both decreased.
figure  <dig> shows coordinated reduction in the transcription of the ribosome complex, the rna polymerase complex , and the m-pol ii complex in a subset of stress conditions .
the m-pol ii, mannosyltransferase ii is the third complex enzyme in mannan modification of n-linked glycan processing  mannan backbone) in the golgi apparatus.
the importance of n-linked glycan processing is underscored by the fact that mannoproteins make up about 40% of the yeast cell wall  <cit> .
the substrates of the pol-ii enzyme are n-linked glycan modified proteins from the er .
glycosylation in the er has been shown to be important for many polypeptides to undergo proper or complete folding .
thus, we expect tight regulation of ribosome translation in the cytoplasm, followed by modification of n-linked glycans  and subsequent mannan modification of n-linked glycan by the m-pol ii .
the subset of stress conditions for which the transcription of these three complexes decreases  are all known to reduce overall protein synthesis.
we find that the abf <dig> transcription factor binds to genes encoding subunits of all three complexes.
moreover, the yap <dig> basic leucine zipper  transcription factor was found to bind the genes encoding the ribosome 60s and the m-pol ii subunits.
we are unaware of evidence in the literature of coordinated regulation between translation - related complexes and mannan modification in the golgi.
our analysis therefore generates a novel prediction supported by tf binding data and the known biological roles of the complexes.
ribosome synthesis and regulation - an example of coordinated regulation among complexes obeying the xor logic function
one of the significant triplets of protein complexes that are related by an xor  logic function, involves the processome.
the example presented here results from combining two triplets of protein complexes: processome, proteasome and the 60s and 40s ribosomal subunits.
in this triplet, processome transcription decreases if the transcription of the ribosome  decreases, xor the transcription of the proteasome increases.
prior experimental studies of these three multi-protein complexes support the proposed logic relationship we find between these complexes.
it has been suggested that the rrna processome ssu  complex has two roles in the maturation process of the pre-ribosome 90s  <cit> .
the first role of the rrna processome is carried out by its sub complex t-utp , which is recruited to the pol i promoter upstream of the rdna gene for transcription initiation.
the second role of the processome is pre-rrna cleavage of the pre-ribosome 90s before transcription is completed.
in recent work with mammalian cells, stavreva et al.
found that complexes associated with pre rrna processing factors are ubiquitinated and hence labeled for processing by the proteasome, a step essential for proper activity in ribosome maturation.
one of the factors found to be ubiquitinated is fibrillarin, a yeast nop <dig> homolog that is a subunit of the rrna splicing processome  <cit> .
as the processome was found to regulate its own activity  <cit> , reduction of its abundance may lead to decrease of its own transcription.
the co-regulation of these three complexes is reasonable given the proposed regulation mechanism by the proteasome.
cellular network of all complexes having different triplet relationships with the ribosome
by grouping together all predicted complex triplets that obey the same type of logic function  and involve the ribosomal small or large subunits, we were able to generate a network.
figure  <dig> shows a subset of this network that includes complexes belonging to the "energy", "transcription" and "translation" functional classes .
the figure shows that complexes belonging to the same functional classes are regulated in the same direction.
in response to stress conditions, complexes belonging to the functional class "energy" are positively regulated , while complexes belonging to the functional classes "transcription" or "translation" are negatively regulated .
this result suggests that the regulation of different complexes may be determined by a master regulatory mechanism that differentially controls multi-protein complex expression, based on function.
discussion
in the current study we present a method that offers insights into how the regulation of numerous multi-protein complexes is coordinated.
in this method, we apply logic analysis to microarray data to identify gene triplets whose transcription obeys logic functions.
we then map these gene triplets to consistent sets of protein complexes.
this approach allows us to infer statistically significant coordinated regulation among triplets of protein complexes.
this mapping reduces the complexity associated with the analysis of gene triplets and increases the significance in our triplet identifications.
typically, in the triplets of protein complexes we identify, only subsets of experiments are coordinately regulated among all complexes.
several approaches were previously used to identify genes which function together in subsets of experiments.
ihmels et al.
developed the "signature algorithm", a clustering approach, to identify gene regulatory modules  <cit> .
segal et al.
identified regulatory modules and their condition-specific regulators from gene expression data using a probabilistic method  <cit> .
however, unlike these previous methods, the present work identifies higher order relationships between genes.
in our work, we specifically focus on relationships between triplets of genes that are not evident when genes are examined in a pairwise fashion.
to confirm this point, we analyzed pairwise correlations between the genes in our triplets of complexes and detected significant correlations  only between pairs of complexes but not among all three.
this result was further confirmed by analyzing the rank of the three correlation coefficients among all possible pair-wise complex relations .
the examples of triplets we discussed demonstrate the biological relevance of our findings.
however it is difficult to find a suitable benchmark to globally validate our results since the complexes within our triplets may have distinct biological functions.
one possible way to validate our approach is to use synthetic data.
to this end, we generated synthetic triplets by creating two random 0/ <dig> vectors and a third vector that matches one of the logical combinations of the pair.
a thousand such synthetic triplets were generated to match one of the logic functions and and xor and uncertainty coefficients and p-values for each triplet were calculated using our program.
as expected, all synthetic triplets were identified as significant .
in order to study the robustness of our method, we measured the number of significant complex triplet relations that could be identified based on random subsets of the gene triplets.
we found that for both logic types xor and and, the drop in significant complex triplets we identified is proportional to the size of the random fraction of logic gene triplet used .
the microarray data we used in this study measures mrna levels in yeast cells in response to environmental changes  <cit> .
a recent study using affinity purification of endogenously formed ribosmes and the analysis of associated mrnas with dna microarray shows that in stress dependent conditions there is a coordination of transcriptome and translatome in yeast  <cit> .
this recent finding indicates that the coordinated regulation we identified between triplets of complexes based on the mrna levels of the encoding subunits, may also extend to their protein levels.
by focusing on microarray data of environmental stresses we detected coordinated regulation among complexes centering on the ribosome.
because the ribosome is responsible for protein translation, a variety of mechanisms are required to regulate its biogenesis, especially under stress conditions.
similar results were reported in another study by levy et al.
which found that ribosome biogenesis genes responded more to changes in the environment and less to longer-term changes in growth rates  <cit> .
since the ribosomal subunits 40s and 60s  are large complexes composed of  <dig> and  <dig> subunits respectively  <cit> , the fact that we found many gene triplets that involve the ribosome is not surprising.
although these two subunits function together in the translation machinery, they are usually defined as two separate complexes that are not permanently associated throughout the entire translation process .
in addition, we find that these two subunits are independently regulated in different conditions .
using all triplets that involve complexes associated with the ribosome , we derived a network.
we found that all multi-protein complexes that belong to the same functional class are regulated in the same direction  .
this result suggests that the regulation of different complexes may be determined by a master regulatory mechanism that differentially controls multi-protein complex expression, based on function.
in a study by lichtenberg et al.
the authors analyzed the dynamics of complex formation during the yeast cell cycle.
the authors found that in many cases  only a few subunits of each complex are transcriptionally regulated in order to control the timing of the final assembly.
the authors claimed that this general design principle of "just-in-time" assembly would have an advantage over "just-in-time" synthesis of entire complexes since only a few components need to be tightly regulated in order to control the timing of the final complex assembly  <cit> .
in our study many of the complexes which we identified to have coordinated regulation with the ribosome are involved in transcription, translation and energy.
when we measured the level of co-expression among the subunits of these complexes , we found that many of them exhibit highly coherent transcription .
this may indicate that for complexes that are active across larger time scales, transcriptional regulation affects most subunits.
this is different from the regulation observed in complexes involved in cell-cycle activity which need to function during specific time frames, and for which a "just-in-time" assembly mechanism is more suitable.
in another study by teichman et al.
the authors found that for a few complexes  subsets of subunits have conserved co-regulation between yeast and worm  <cit> .
this evolutionary conservation may indicate that although those complexes exhibit highly coherent transcription regulation, tighter regulation might exist between a subset of all the subunits.
CONCLUSIONS
the importance of studying relationships between different modules in a cell such as multi-protein complexes has been demonstrated in different studies  <cit> .
in our approach we used pre-defined modules in the cell-- multi-protein complexes--  <cit>  and identified triplets of these whose regulation obeys logic functions.
this approach allows us to uncover coordinated regulation among complexes.
understanding this regulation allows us to infer higher-level modes of cellular function and also provides insight into the biological mechanisms underlying coordination between complexes.
our logic analysis can be applied to any transcriptional profiling data.
furthermore, this same methodology may be applied to other types of pre-defined functional modules, such as metabolic pathways.

 in recent years, systematic experimental studies, such as those using tap tag mass-spec techniques, have provided a draft map of yeast multi-protein complexes. this map shows the composition of the quaternary protein structures in this model organism. the next challenge is to uncover which complexes work together to perform particular cellular tasks. one way to accomplish this is to detect the synchronized regulation of multi-protein complexes. coordinated regulation may be defined as a synchronous pattern of increased or reduced mrna transcription of several cellular multi-protein complexes in response to a given perturbation. such coordinated regulation of complexes is found when cellular function requires several complexes to be co-expressed or when other complexes need to be repressed for a given complex to function. for example, to achieve proper initiation of the translation process in eukaryotes, numerous cellular multi-protein complexes are regulated in a coordinated fashion. in this process, the initiation factor complexes eif eif and the cap-binding protein complex associate to bind the ribosomal small subunit complex. another example involves the tor complex, a conserved ser/thr kinase that regulates cell growth and metabolism in response to nutrients and stress. when nutrients are available, tor activates complexes related to ribosome biogenesis, translation and nutrient import. in contrast, starvation inhibits tor activity, thereby inducing various cellular responses such as cell arrest in the early g phase, inhibition of protein synthesis, nutrient transporter turnover, transcriptional changes, and autophagy. these responses are all mediated by multi-protein complexes. intricate relationships among genes and groups of genes are not captured by simple pairwise correlations; rather, higher order analysis is necessary to derive more detailed relationships. in the past few years diverse methods, such as binary and bayesian networks, have been developed to derive gene networks. however, these approaches aim to detect co-regulated expression modules among individual genes, while methods to detect co-regulation among groups of genes, such as multi-protein complexes, still need to be developed. in the present study, we apply logic analysis to gene expression data to identify gene triplets related by various types of logic functions. next, we combine these to study coordinated relationships among multi-protein complexes. logic analysis is a method to relate triplets of genes/proteins by certain logic functions based on genomic data. all eight possible logic functions among triplets of genes can be found in figure and additional file 1: table s the triplet logic approach was introduced by bowers et al. and applied to genomic data in the form of phylogenetic profiles. subsequently, logic analysis was also applied to find relations between the expression of two genes and disease state phenotypes. in the current study, logic analysis is extended and modified for application to gene expression data. the original approach assigned a binary value to a gene for each organism or gene expression experiment. in this work we use a three state model that describes genes as induced, repressed, or non-regulated. we construct two separate regulatory state vectors for each gene, where one vector describes whether a gene is induced or not over the set of experiments, while the other describes whether the gene is repressed or not. these vectors are then used to identify gene triplets whose regulation obeys logic functions. for example: gene c is induced/repressed if and only if gene a is induced/repressed and gene b is induced/repressed. we also introduce a p-value for each gene triplet that quantifies the likelihood of obtaining this triplet by chance. next we grouped genes with the same logic function that mapped to the same set of three multi-protein complexes. this type of grouping enables us to infer how the coordinated regulation of these complexes occurs in the cell. to explore the utility of our approach, we applied triplet logic analysis to yeast microarray data that measures the response of gene expression levels to environmental changes. we identified genes whose regulation obeys triplet logic functions, and mapped these genes to distinct, multi-subunit complexes to infer coordinated regulation between the complexes. among the many complexes inferred to have coordinated regulation, we discuss examples related to the biogenesis of the ribosome and support them with known regulatory data. in addition, we derive a cellular network of all complexes that have different triplet relationships with the ribosome. this network reveals that in stress conditions, all complexes belonging to the same functional classes are regulated in the same direction. this observation may suggest the existence of global regulation of numerous cellular multi-protein complexes that belong to the same functional class.  identifying gene triplets whose regulatory patterns obey logic functions we applied logic analysis to expression data to identify gene triplets whose regulation obeys one of the eight possible logic functions. the analysis was applied to data of gasch et al., which measure the expression of all saccharomyces cerevisiae genes in response to various environmental stresses. initially, we constructed two binary state vectors for each gene. one vector describes whether the gene is repressed and the other vector describes whether the gene is induced across of the microarray experiments; vectors were retained for analysis only if induction or repression was seen in at least 10% of experimental conditions. this resulted in gene vectors, 45% of which represent the induced state while 55% represent the repressed state. next, using these binary vectors, we analyzed all possible gene triplets. we identified about nine million potentially significant gene triplets, based on the associated uncertainty coefficient and p-value. these thresholds were chosen to filter out triplets that are only related by pairwise correlations between two genes. some of the gene triplets were significant under more than one type of logic function. in these cases we assigned to each gene triplet the most significant logic function as defined by the highest u value. this assignment reduced the number of non-redundant triplets for further grouping and analysis to, the eight possible types of triplet logic relationships described earlier, occur with different frequencies. the four types, a xor b, a or b, and a and b represented %, %, %, and % of the cases, while the remaining four types almost never occurred. we believe certain logic types are rare because the binary microarray data we are using is relatively sparse. as a result, only logic functions where f = are observed often, whereas functions where f = are not. additional file 2: figure s contains example heat maps of triplets of genes that obey the and and xor logic functions. mapping gene triplets to multi-protein complexes we mapped all gene triplets to complexes as described in methods. we identified triplets that were composed of genes that mapped to multi-protein complexes. of these triplets, mapped to a single multi-protein complex, triplets mapped to at least two different complexes and about 90% mapped to three different complexes. as mentioned above, the u value was used to filter out gene triplets that are associated only by pairwise correlations. that most gene triplets mapped to more than one complex supports our choice of this threshold. grouping gene triplets that map to three complexes next we grouped together gene triplets obeying the same logic function and mapping to the same set of three complexes. we restricted our analysis to two logic functions: xor and and. these two functions were abundant in our data and were judged to have more intuitive biological interpretations than the other logic types. the logic function and yields triplets of protein complexes. for each triplet of complexes we computed the significance of the finding based on the number of gene triplets that map to these complexes and computed a p value using the hypergeometric distribution. out of these triplets of protein complexes, are significant. a total of triplets of protein complexes were related through the logic function xor, of which are significant. the significant triplets of protein complexes related through logic functions and and xor include and different protein complexes which are supported by and gene triplets respectively. the genes composing the triplets encode a subset of the subunits of each complex. this may be explained by the incompleteness of the microarry data and the strict parameters we choose. to check if the subunits we identify are representative of the entire complex, we calculated the expression coherence between the subunits of a complex. we found that in all complexes that appear in our study, the expression was indeed coherent. the list of all triplets of protein complexes which have coordinated regulation appears in additional files and 5: tables s and s below we discuss examples of the triplets of protein complexes whose synchronized regulation has been previously described in the literature, as well as novel predictions of co-regulation of complexes. regulation of protein translation, autophagy degradation and n-linked glycosylation - examples of triplet complexes that have coordinated regulation obeying the and logic function ribosome large subunit - 60s, eif2b initiation factor and rna polymerase i/iii our results reveal that the transcription of the 60s ribosomal large subunit decreases if and only if the transcription of the eif2b initiation factor and rna polymerase i/iii are decreased as well. the three subunits of the rna polymerase, rpb rpc and rpo that participate in this logic relation are components of both polymerase i and iii. figure shows the subset of experiments where the transcription of all three complexes decreases. indeed, co-regulation between complexes involved in ribosome biogenesis and protein translation was shown recently to be mediated by tor signaling, as reviewed in wullschleger et al.. in response to nutrients, tor induces ribosome biogenesis, translation, and nutrient import, whereas stress conditions repress these functions. our results suggest the stress conditions tested in these experiments inhibit tor signaling and this inhibition leads to the repression of all three complexes. chip-chip data reveal that the genes encoding the subunits of ribosome 60s, rna polymerase and eif2b are bound by overlapping sets transcription factors. genes encoding rna polymerase i/iii subunits and ribosome large subunits are bound by the abf transcription factor, whereas genes encoding the rna polymerase i subunit and the eif2b subunit genes are bound by rpn and dig. ribosome 60s and 40s subunits and the autophagy related complex we find that the transcription of the 60s ribosome large subunit decreases only when the transcription of the 40s subunit decreases and the transcription of autophagy related complex increases. figure shows that in a subset of experiments the transcription of the autophagy-related dimer complex aut2p/aut7p is increased when the transcription of both of the ribosomal complexes, 40s and 60s is decreased. although the relation includes only one subunit of the 60s ribosomal complex, it is known that ribosomal subunits are strongly co-expressed of 86% of possible pairs within the ribosome). all other subunits of the 60s ribosome were assigned lower scores due to incompleteness of the microarray data in the specified experiments and the strict parameters we choose. aut2p/aut7p has a role in protein degradation while the two ribosomal complexes 40s and 60s have a role in protein synthesis. that these two complexes have opposite function likely explains their opposite transcriptional regulation in this subset of experiments. in this example as in the previous one, the tor signaling pathway is known to mediate both the translation and the autophagy processes. when the cell experiences stress conditions, the torc complex is inhibited. this inhibition leads to decreased transcription of genes involved in translation and also leads to activation of the autophagy process. we identified tfs that bind genes of both the 40s and 60s ribosomal complexes, but could not identify tfs that also bind genes encoding the aut2/aut complex, possibly because we employed strict filtering of the chip-chip data. moreover, we did find that genes encoding subunits of the torc and ribosomal 40s and 60s subunits are all bound by the reb, pho and msn tfs. ribosome 60s, rna polymerase i/iii and mannosyltransferase glycosylation complex the transcription of the 60s ribosomal large subunit decreases only when the transcription of rna polymerase i/iii and the m-pol ii complex are both decreased. figure shows coordinated reduction in the transcription of the ribosome complex, the rna polymerase complex, and the m-pol ii complex in a subset of stress conditions. the m-pol ii, mannosyltransferase ii is the third complex enzyme in mannan modification of n-linked glycan processing mannan backbone) in the golgi apparatus. the importance of n-linked glycan processing is underscored by the fact that mannoproteins make up about 40% of the yeast cell wall. the substrates of the pol-ii enzyme are n-linked glycan modified proteins from the er. glycosylation in the er has been shown to be important for many polypeptides to undergo proper or complete folding. thus, we expect tight regulation of ribosome translation in the cytoplasm, followed by modification of n-linked glycans and subsequent mannan modification of n-linked glycan by the m-pol ii. the subset of stress conditions for which the transcription of these three complexes decreases are all known to reduce overall protein synthesis. we find that the abf transcription factor binds to genes encoding subunits of all three complexes. moreover, the yap basic leucine zipper transcription factor was found to bind the genes encoding the ribosome 60s and the m-pol ii subunits. we are unaware of evidence in the literature of coordinated regulation between translation - related complexes and mannan modification in the golgi. our analysis therefore generates a novel prediction supported by tf binding data and the known biological roles of the complexes. ribosome synthesis and regulation - an example of coordinated regulation among complexes obeying the xor logic function one of the significant triplets of protein complexes that are related by an xor logic function, involves the processome. the example presented here results from combining two triplets of protein complexes: processome, proteasome and the 60s and 40s ribosomal subunits. in this triplet, processome transcription decreases if the transcription of the ribosome decreases, xor the transcription of the proteasome increases. prior experimental studies of these three multi-protein complexes support the proposed logic relationship we find between these complexes. it has been suggested that the rrna processome ssu complex has two roles in the maturation process of the pre-ribosome 90s. the first role of the rrna processome is carried out by its sub complex t-utp, which is recruited to the pol i promoter upstream of the rdna gene for transcription initiation. the second role of the processome is pre-rrna cleavage of the pre-ribosome 90s before transcription is completed. in recent work with mammalian cells, stavreva et al. found that complexes associated with pre rrna processing factors are ubiquitinated and hence labeled for processing by the proteasome, a step essential for proper activity in ribosome maturation. one of the factors found to be ubiquitinated is fibrillarin, a yeast nop homolog that is a subunit of the rrna splicing processome. as the processome was found to regulate its own activity, reduction of its abundance may lead to decrease of its own transcription. the co-regulation of these three complexes is reasonable given the proposed regulation mechanism by the proteasome. cellular network of all complexes having different triplet relationships with the ribosome by grouping together all predicted complex triplets that obey the same type of logic function and involve the ribosomal small or large subunits, we were able to generate a network. figure shows a subset of this network that includes complexes belonging to the "energy", "transcription" and "translation" functional classes. the figure shows that complexes belonging to the same functional classes are regulated in the same direction. in response to stress conditions, complexes belonging to the functional class "energy" are positively regulated, while complexes belonging to the functional classes "transcription" or "translation" are negatively regulated. this result suggests that the regulation of different complexes may be determined by a master regulatory mechanism that differentially controls multi-protein complex expression, based on function. discussion in the current study we present a method that offers insights into how the regulation of numerous multi-protein complexes is coordinated. in this method, we apply logic analysis to microarray data to identify gene triplets whose transcription obeys logic functions. we then map these gene triplets to consistent sets of protein complexes. this approach allows us to infer statistically significant coordinated regulation among triplets of protein complexes. this mapping reduces the complexity associated with the analysis of gene triplets and increases the significance in our triplet identifications. typically, in the triplets of protein complexes we identify, only subsets of experiments are coordinately regulated among all complexes. several approaches were previously used to identify genes which function together in subsets of experiments. ihmels et al. developed the "signature algorithm", a clustering approach, to identify gene regulatory modules. segal et al. identified regulatory modules and their condition-specific regulators from gene expression data using a probabilistic method. however, unlike these previous methods, the present work identifies higher order relationships between genes. in our work, we specifically focus on relationships between triplets of genes that are not evident when genes are examined in a pairwise fashion. to confirm this point, we analyzed pairwise correlations between the genes in our triplets of complexes and detected significant correlations only between pairs of complexes but not among all three. this result was further confirmed by analyzing the rank of the three correlation coefficients among all possible pair-wise complex relations. the examples of triplets we discussed demonstrate the biological relevance of our findings. however it is difficult to find a suitable benchmark to globally validate our results since the complexes within our triplets may have distinct biological functions. one possible way to validate our approach is to use synthetic data. to this end, we generated synthetic triplets by creating two random 0/ vectors and a third vector that matches one of the logical combinations of the pair. a thousand such synthetic triplets were generated to match one of the logic functions and and xor and uncertainty coefficients and p-values for each triplet were calculated using our program. as expected, all synthetic triplets were identified as significant. in order to study the robustness of our method, we measured the number of significant complex triplet relations that could be identified based on random subsets of the gene triplets. we found that for both logic types xor and and, the drop in significant complex triplets we identified is proportional to the size of the random fraction of logic gene triplet used. the microarray data we used in this study measures mrna levels in yeast cells in response to environmental changes. a recent study using affinity purification of endogenously formed ribosmes and the analysis of associated mrnas with dna microarray shows that in stress dependent conditions there is a coordination of transcriptome and translatome in yeast. this recent finding indicates that the coordinated regulation we identified between triplets of complexes based on the mrna levels of the encoding subunits, may also extend to their protein levels. by focusing on microarray data of environmental stresses we detected coordinated regulation among complexes centering on the ribosome. because the ribosome is responsible for protein translation, a variety of mechanisms are required to regulate its biogenesis, especially under stress conditions. similar results were reported in another study by levy et al. which found that ribosome biogenesis genes responded more to changes in the environment and less to longer-term changes in growth rates. since the ribosomal subunits 40s and 60s are large complexes composed of and subunits respectively, the fact that we found many gene triplets that involve the ribosome is not surprising. although these two subunits function together in the translation machinery, they are usually defined as two separate complexes that are not permanently associated throughout the entire translation process. in addition, we find that these two subunits are independently regulated in different conditions. using all triplets that involve complexes associated with the ribosome, we derived a network. we found that all multi-protein complexes that belong to the same functional class are regulated in the same direction. this result suggests that the regulation of different complexes may be determined by a master regulatory mechanism that differentially controls multi-protein complex expression, based on function. in a study by lichtenberg et al. the authors analyzed the dynamics of complex formation during the yeast cell cycle. the authors found that in many cases only a few subunits of each complex are transcriptionally regulated in order to control the timing of the final assembly. the authors claimed that this general design principle of "just-in-time" assembly would have an advantage over "just-in-time" synthesis of entire complexes since only a few components need to be tightly regulated in order to control the timing of the final complex assembly. in our study many of the complexes which we identified to have coordinated regulation with the ribosome are involved in transcription, translation and energy. when we measured the level of co-expression among the subunits of these complexes, we found that many of them exhibit highly coherent transcription. this may indicate that for complexes that are active across larger time scales, transcriptional regulation affects most subunits. this is different from the regulation observed in complexes involved in cell-cycle activity which need to function during specific time frames, and for which a "just-in-time" assembly mechanism is more suitable. in another study by teichman et al. the authors found that for a few complexes subsets of subunits have conserved co-regulation between yeast and worm. this evolutionary conservation may indicate that although those complexes exhibit highly coherent transcription regulation, tighter regulation might exist between a subset of all the subunits.  the importance of studying relationships between different modules in a cell such as multi-protein complexes has been demonstrated in different studies. in our approach we used pre-defined modules in the cell-- multi-protein complexes-- and identified triplets of these whose regulation obeys logic functions. this approach allows us to uncover coordinated regulation among complexes. understanding this regulation allows us to infer higher-level modes of cellular function and also provides insight into the biological mechanisms underlying coordination between complexes. our logic analysis can be applied to any transcriptional profiling data. furthermore, this same methodology may be applied to other types of pre-defined functional modules, such as metabolic pathways. 
specifically, we identify gene triplets composed of genes whose expression profiles are found to be related by various types of logic functions. in order to focus on complexes, we associate the members of a gene triplet with the distinct protein complexes to which they belong. by grouping gene triplets, we are able to decipher coordinated regulation among sets of three complexes. the analysis proposed here focuses on relationships among triplets of genes that are not evident when genes are examined in a pairwise fashion as in typical clustering methods. we propose a new methodology that is able to detect such higher order relationships. one notable example is the relationship between the transcription of the ribosome, rna polymerase and mannosyltransferase ii, which is involved in n-linked glycan processing in the golgi. we detect coordinated regulation of multiple protein complexes using logic analysis of gene expression data. in this network we find that all multi-protein complexes that belong to the same functional class are regulated in the same direction as a group. many of the functional units in cells are multi-protein complexes such as rna polymerase, the ribosome, and the proteasome.
 many of the functional units in cells are multi-protein complexes such as rna polymerase, the ribosome, and the proteasome. for such units to work together, one might expect a high level of regulation to enable co-appearance or repression of sets of complexes at the required time. however, this type of coordinated regulation between whole complexes is difficult to detect by existing methods for analyzing mrna co-expression. we propose a new methodology that is able to detect such higher order relationships.  we detect coordinated regulation of multiple protein complexes using logic analysis of gene expression data. specifically, we identify gene triplets composed of genes whose expression profiles are found to be related by various types of logic functions. in order to focus on complexes, we associate the members of a gene triplet with the distinct protein complexes to which they belong. in this way, we identify complexes related by specific kinds of regulatory relationships. for example, we may find that the transcription of complex c is increased only if the transcription of both complex a and complex b is repressed. we identify hundreds of examples of coordinated regulation among complexes under various stress conditions. many of these examples involve the ribosome. some of our examples have been previously identified in the literature, while others are novel. one notable example is the relationship between the transcription of the ribosome, rna polymerase and mannosyltransferase ii, which is involved in n-linked glycan processing in the golgi.  the analysis proposed here focuses on relationships among triplets of genes that are not evident when genes are examined in a pairwise fashion as in typical clustering methods. by grouping gene triplets, we are able to decipher coordinated regulation among sets of three complexes. moreover, using all triplets that involve coordinated regulation with the ribosome, we derive a large network involving this essential cellular complex. in this network we find that all multi-protein complexes that belong to the same functional class are regulated in the same direction as a group. 