BACKGROUND
single-cell organisms such as yeasts constantly face changing or even harsh environments such as high temperature that threaten their survival or, at least, prevent them from performing optimally  <cit> .
by organizing the genome into gene regulatory modules , a yeast cell can coordinate the activities of many genes and carry out complex functions in response to high temperature.
therefore, identifying grms of heat response is instrumental for understanding cellular responses to heat shock.
the advances of high-throughput tools such as dna microarray  <cit>  and chromatin immunoprecipitation-dna chip   <cit>  have made the computational reconstruction of grms of a yeast cell possible.
several module inference methods have been proposed.
lee et al.
<cit>  performed chip-chip experiments on  <dig> tfs in yeast and discovered six types of network motifs in yeast gene regulation.
using microarray data, segal et al.
<cit>  developed a probabilistic model to identify yeast grms.
later, three studies were conducted to combine chip-chip and gene expression data to identify yeast grms.
first, xu et al.
<cit>  extended segal et al.
's probabilistic model to incorporate chip-chip data.
second, bar-joseph et al.
<cit>  developed gram to identify rich medium gene regulatory modules.
third, wu et al.
<cit>  developed mofa to identify grms of yeast cell cycle.
more data sources were used in more recent studies.
kato et al.
<cit>  identified grms of yeast cell cycle by combining sequence, chip-chip and gene expression data.
lemmens et al.
<cit>  developed remodiscovery to identify grms of the yeast cell cycle and yeast stress response by combining motif information, chip-chip and gene expression data.
tanay et al.
<cit>  applied a graph theoretic approach and developed samba to reveal the modular organization of the yeast regulatory system by combining protein interactions, growth phenotype data, chip-chip, and gene expression data.
however, all these module inference algorithms are statistics-based methods, treating dynamic time series gene expression data the same way as static steady state gene expression data.
that is, they do not consider the dependency between different time points of a time series and thus do not utilize the dynamic nature of time series data.
because many time series gene expression data sets are now available in the public domain  <cit> , it is desirable to develop a module inference method that can utilize the dynamic nature of time series gene expression data.
the aim of this study is to develop a module inference method that suits this need.
by combining current transcription factor binding site   <cit> , mutant  <cit> , chip-chip  <cit> , and heat shock time series gene expression data  <cit> , we developed a module inference method, called heat-inducible module identification algorithm , to reconstruct heat-inducible grms in yeast .
himia is divided into five steps.
first, three independent data sources  are used to construct a high-confidence tf-promoter binding matrix .
from the tf-promoter binding matrix, all the tfs that bind to any specific target gene can be inferred.
second, using heat shock time series gene expression data, a dynamic system model of gene regulation is applied to describe how a target gene's expression under heat shock is controlled by the tfs that bind to its promoter .
a dynamic system model is capable of utilizing the dynamic nature of time series gene expression data, making it different from the static statistics-based models in previous studies  <cit> .
after the dynamic system modeling, the tfs that have significant regulatory effects on the target gene's expression can be extracted from all tfs that bind to the target gene.
from this procedure, a high-confidence tf-gene regulatory matrix is constructed.
each tf-gene regulatory relationship in this matrix is supported by at least three independent data sources .
third, candidate heat-inducible genes are identified.
a gene is said to be heat-inducible if at least two time points of its gene expression profile measured under heat shock are induced by at least three folds compared to that under the unstressed condition.
causton et al.
<cit>  defined a candidate heat-inducible gene by the criterion that at least one time point of its gene expression profile shows a change fold of at least three.
in order to reduce the false positives, we use a criterion that requires at least two time points with a change fold of at least three.
fourth, using the list of candidate heat-inducible genes and the high-confidence tf-gene regulatory matrix, heat-responsive tf sets can be inferred by statistical methods.
a tf set is said to be heat-responsive only if a significant portion of the targets that are co-regulated by all the tfs in the tf set is heat-inducible.
the hypergeometric distribution is used to test the statistical significance.
fifth, for each heat-responsive tf set, we collect all their regulatory targets that are heat-inducible to form a candidate heat-inducible grm.
that is, a heat-inducible grm consists of a set of heat-inducible genes that are regulated by the same set of heat-responsive tfs.
because genes in the same grm are regulated by the same set of tfs, their gene expression profiles should be more similar to each other than those of a set of genes that are not in a single grm.
therefore, for each candidate grm we further extract a subset of genes whose gene expression profiles are more coherent than that of the set of all heat-inducible genes which are regulated by different sets of tfs.
finally, this subset of highly coherent genes forms a heat-inducible grm that is regulated by the same set of heat-responsive tfs.
RESULTS
by integrating tfbs, mutant, chip-chip, and gene expression data, himia identified  <dig> grms, which in total contain  <dig> heat-inducible genes regulated by  <dig> heat-responsive tfs .
according to the literature  <cit> ,  <dig> of the  <dig> genes and  <dig> of the  <dig> tfs are known to be involved in heat shock response.
validation of the identified modules
several lines of evidence support that himia identifies biologically relevant heat-inducible grms.
first, by the virtue of our method, each tf-gene regulatory relationship in a module is of high confidence because it is supported by at least three independent data sources .
second, each module is assigned to at least one tf that is known to be involved in heat shock response .
third, in the  <dig> modules that are controlled by more than one tf, 70%  of the tfs in the same module have physical or genetic interactions  <cit>  .
fourth, on average, 67% of genes in a heat-inducible grm are known to be involved in heat shock response .
fifth, 59%  of the identified modules include groups of genes that function in the same cellular process: each of these modules contains at least one over-represented mips functional category  <cit>  with the adjusted p-value <  <dig>   using the cumulative hypergeometric distribution .
finally, the modules are generally accurate in assigning tfs to sets of genes whose functions are consistent with the tfs' known roles.
for the  <dig> modules that contain groups of genes enriched in the same cellular process, we found that the regulatory functions of the 76%  of the tfs are consistent with one of their modules' over-represented functional categories .
taken together, these results provide evidence that himia identifies not only sets of biologically related heat-inducible genes, but also heat-responsive tfs that individually or collectively regulate these genes.
identification of important heat-responsive tfs
we identified  <dig> heat-responsive tfs,  <dig>  of which are known to be involved in heat shock response .
our findings are supported by the literature.
first, msn <dig> and msn <dig> are known to regulate the general stress response in yeast.
they regulate the expression of many genes in response to several stresses, including heat shock, osmotic shock, oxidative stress, low ph, glucose starvation, sorbic acid and high ethanol concentrations, by binding to the stress response element  located in the promoters of these genes  <cit> .
second, hsf <dig> is the well-known heat shock factor that binds to the heat shock element  to regulate the transcription of many heat-inducible genes, including genes involved in protein folding, detoxification, energy generation, carbohydrate metabolism, and cell wall organization  <cit> .
all these gene products are important for cell to counteract the deleterious effects of heat.
third, yap <dig>  a well-known oxidative shock factor, is also known to be involved in heat shock response  <cit> .
for example, yap <dig> induces the expression of gsh <dig> and gsh <dig> to synthesize glutathione in heat shock response  <cit> .
fourth, heat stress can cause unfolded proteins to accumulate in the endoplasmic reticulum , triggering the unfolded protein response .
hac <dig> binds to the upr element  to regulate genes that are involved in upr  <cit> .
fifth, heat stress causes a weakening of cell wall and membrane stretching which stimulates the protein kinase c  pathway  <cit> .
rlm <dig>  a component of the pkc pathway, is then activated to perform the function of maintaining the cell wall integrity  <cit> .
finally, cad <dig>  an ap- <dig> like bzip transcriptional activator involved in stress responses , controls a set of genes involved in stabilizing proteins  <cit> .
the involvement of cad <dig> in stress responses was also identified by segal et al.
<cit> .
seven well-known heat-responsive tfs are bold-faced and colored blue.
the tfs are ordered by the number of their inferred heat-inducible target genes.
in addition to the above seven known heat-responsive tfs, five novel heat-responsive tfs  have also been identified by himia.
rox <dig> contains a high-mobility group  domain that is responsible for dna bending activity  <cit> .
cst <dig> and ume <dig> regulate genes involved in the cell cycle and dna processing  <cit> .
ste <dig> and dig <dig> are involved in the regulation of mating-specific genes and the invasive growth pathway  <cit> .
identification of these five tfs as heat-responsive tfs suggests that heat shock response may have crosstalk with other cellular processes.
it is known that the cell cycle transiently arrests during a heat shock stress  <cit> , validating our proposal that heat shock response may have crosstalk with the cell cycle process.
moreover, these five novel heat-responsive tfs and the other seven known heat-responsive tfs form a highly connected network of interactions, supporting our prediction that these five novel heat-responsive tfs may play a role in heat shock response .
this dense network of interactions also suggests that different combinations of a fairly small number of heat-responsive tfs may be sufficient to regulate a large number of genes involved in heat shock response.
taken together, these results suggest that himia is effective for identifying tfs that play a role in heat shock response or are involved in other cellular processes that may crosstalk with heat shock response.
identification of important genes involved in heat shock response
disruption of a large number of cellular assemblies and processes, an increased protein unfolding and aggregation, and membrane structure alterations are paramount in cells exposed to high temperature.
heat shock response serves to counteract these deleterious effects.
through it cells increase their thermotolerance or ability to withstand heat stress  <cit> .
many events occur in yeast cells during heat shock response.
first, heat shock proteins  are rapidly synthesized.
many hsps function as protein chaperones, so named because of their ability to bind to partially unfolded proteins to protect them from degradation or aggregation  <cit> .
himia successfully identified heat shock protein genes hsp <dig> and hsp <dig>  to be regulated by heat-shock transcription factor hsf <dig> and hsp <dig> and hsp <dig>  to be regulated by the general stress factor msn <dig>  in addition, hsp <dig>  hsp <dig>  ssa <dig>  ssa <dig> and sse <dig>  are identified to be regulated by both hsf <dig> and msn <dig>  other genes involved in the protein folding or refolding are also found.
for example, eug <dig>  lhs <dig>  scj <dig> and ero <dig>  are regulated by hac <dig>  a tf known to be involved in protein unfolding response  <cit> .
second, heat shock causes the extremely rapid accumulation of a large cytoplasmic pool of trehalose.
trehalose is one of the most effective substances known for preservation of membranous structures and enzyme activities during heating.
one of the major roles for msn2/ <dig> in heat shock response is to regulate the expression of genes required for the synthesis of trehalose  <cit> .
himia successfully identified three genes for trehalose synthease subunits: tsl <dig> , tsp <dig>  and nth <dig>  are indeed regulated by msn <dig> or msn <dig>  third, heat shock increases the synthesis of certain components of the ubiquitination system for intracellular protein turnover, indicating a much greater requirement for turnover of abnormal proteins in cells recovering from heat stress  <cit> .
himia successfully identified several genes that are known to be involved in protein degradation.
der <dig> and pbi <dig>  are identified to be regulated by hac <dig>  apg <dig>  ubc <dig>  jem <dig> and ubi <dig>  are regulated by hsf <dig>  lap <dig> and asi <dig>  are regulated by msn <dig>  atg <dig> and ysp <dig>  are regulated by rlm <dig>  fourth, high temperature causes the weakness of cell walls and induces the expression of genes that are involved in cell wall biogenesis and maintenance  <cit> .
himia successfully identified seven genes  known to be involved in the cell wall biogenesis and maintenance  <cit> .
all these seven genes are in module  <dig> and regulated by rlm <dig>  an important cell integrity maintenance factor  <cit> .
finally, it is known that during heat shock cells induce a variety of genes related to carbohydrate metabolism, fatty acid metabolism, respiration and others  <cit> .
himia successfully identified genes that are involved in these cellular processes.
for example, hxk <dig>  glk <dig> and gph <dig>  involved in glucose metabolism are identified to be regulated by msn <dig>  faa <dig> and faa <dig>  involved in fatty acid metabolism are identified to be regulated by hsf <dig>  cyc <dig> and cox <dig>  involved in respiration are identified to be regulated by msn <dig>  the known functions of these genes hint the cellular processes that may be affected in response to heat shock, and suggest mechanisms the cell uses to protect itself in the face of a heat stress  <cit> .
annotating uncharacterized genes
among the  <dig> identified heat-inducible genes,  <dig> genes have unknown function according to the saccharomyces genome database  <cit> .
we suggest most if not all of these genes are involved in heat shock response.
our predictions are supported by the fact that all these  <dig> genes are induced by more than three folds at least at two time points of their expression profiles under heat shock.
moreover, all these  <dig> genes are regulated by known heat-responsive tfs and the tf-gene regulatory relationships are supported by at least three independent data sources .
as shown in additional file  <dig>   <dig> of these genes are regulated by hac <dig>   <dig> by hsf <dig>   <dig> by msn <dig>   <dig> by msn <dig>   <dig> by yap <dig>  and so on.
as an example, it is known that the weakening of cell wall during high temperature stimulates the cell integrity pathway  <cit> .
prm <dig> is known to be induced in the cell integrity pathway but its molecular function is unknown  <cit> .
himia identified prm <dig>  to be regulated by rlm <dig>  an important cell wall integrity maintenance factor, suggesting that prm <dig> is indeed involved in the cell wall maintenance during heat shock.
moreover, we successfully identified the putative heat shock protein gene yro <dig>  to be regulated by msn <dig>  in addition, putative genes that may be involved in protein degradation are also found.
for example, hbt <dig> and rim <dig>  are identified to be regulated by msn <dig>  mgr <dig> and add <dig>  are identified to be regulated by hac <dig>  all these examples show that these uncharacterized genes may play a role in heat shock response.
however, further experimental validations are needed to confidently annotate these uncharacterized genes as heat-inducible genes.
assigning regulatory roles of tfs that regulate a grm
we can assign the regulatory roles of tfs that regulate a module.
a tf is said to be an activator of a module if the p-value for observing so many tf-gene pairs in the module each with a significant positive correlation  is less than  <dig> .
the p-value is the probability that an observation would be made by chance, and is calculated using the cumulative binomial distribution  <cit> : p=∑x=n0np0xn−x
where n is the total number of genes in a module, n <dig> is the number of genes in the module that show a significant positive correlation in expression with the tf, and p <dig> is the probability of observing an arbitrary gene in the genome that has a significant positive correlation in expression with the tf.
as shown in table  <dig>  we assigned cst <dig> as an activator of four modules, hsf <dig> an activator of three modules, msn <dig> an activator of five modules, msn <dig> an activator of two modules, rlm <dig> an activator of two modules and yap <dig> an activator of four modules.
a tf is said to be an activator of a module if the p-value for observing so many tf-gene pairs in the module each with a significant positive correlation is less than  <dig> .
refining the clusters of the genes involved in the same cellular process
heat shock causes an increased protein unfolding and aggregation in a cell.
thus, many genes that are involved in protein folding are induced to bind to partially unfolded proteins to protect them from degradation or aggregation  <cit> .
among the  <dig> identified heat-inducible genes,  <dig> genes are known to be involved in protein folding.
although these genes are functionally similar, they may be under different transcriptional controls.
indeed, himia assigns these  <dig> genes into five modules .
for example, hsp <dig> and hsp <dig> are identified to be regulated by hsf <dig>  hsp <dig> by msn2/ <dig>  hsp <dig> and hsp <dig> by both hsf <dig> and msn2/ <dig>  and so on.
denatured proteins that cannot be properly refolded are targeted for degradation by ubiquitination, so it is not surprising that genes involved in protein degradation are induced under heat shock  <cit> .
among the  <dig> identified heat-inducible genes,  <dig> genes are known to be involved in protein degradation.
although these genes are functionally similar, they may be under different transcriptional controls.
himia assigns these  <dig> genes into five modules .
for example, pbi <dig>  add <dig> der <dig> and mgr <dig> are identified to be regulated by hac <dig>  atg <dig> and ysp <dig> by rlm <dig>  and so on.
therefore, himia can refine the cluster of genes involved in protein folding and degradation and can provide a better understanding of how the cell regulates the complex expression program of these genes.
discussion
performance comparison with existing methods
several module inference methods have been proposed.
gram  <cit>  and mofa  <cit>  are intuitive algorithms to identify yeast grms by combining chip-chip and gene expression data.
remodiscovery  <cit>  is an intuitive algorithm to identify yeast grms by combining motif information, chip-chip, and gene expression data.
samba  <cit>  uses a graph theoretic approach to identify grms by combining four data sources .
all these four module inference algorithms are statistics-based methods.
on the contrary, himia is a dynamic system model-based method that integrates four data sources .
since himia is different from the four pervious methods, a performance comparison was conducted.
we tested the ability of each of these five algorithms to retrieve the known stress-responsive tfs annotated in the mips database  <cit> .
performance comparison was based on the jaccard similarity score  <cit> , which scores the overlap between an algorithm's output and the list of known stress-responsive tfs .
therefore, the higher the jaccard similarity score, the better the ability of an algorithm to retrieve the known stress-responsive tfs.
table  <dig> shows that himia has the highest jaccard similarity score among the five tested algorithms.
performance comparison was based on the jaccard similarity score  <cit> , which scores the overlap between an algorithm's output and the list of known stress-responsive tfs.
specifically, the score is defined as tp/  <cit> , where tp stands for true positives, fp for false positives, and fn for false negatives.
note that the higher the jaccard similarity score, the better the ability of an algorithm to retrieve the known stress-responsive tfs.
randomization test and comparison with a null model
two randomization tests were performed to show that the output of himia is statistically meaningful.
first, we randomly permuted the gene expression data  <dig> times.
second, we randomly permuted the chip-chip data  <dig> times.
when either of the two randomized data sets was used as the input, himia could no longer effectively identify the known stress-responsive tfs .
this means that the output of himia is statistically meaningful and is far beyond random expectation.
two randomization tests were performed.
first, we randomly permuted the gene expression data  <dig> times.
second, we randomly permuted the chip-chip data  <dig> times.
when either of the two randomized data sets was used as the input, himia could no longer effectively identify the known stress-responsive tfs, indicating that the output of himia is statistically meaningful and is far beyond random expectation.
in addition, we compared the performance of himia and the null model to retrieve the known stress-responsive tfs annotated in the mips database  <cit> .
the null model was defined as using the same input data  but only the overlap was calculated instead of going through the iterative procedure described on figure  <dig>  the simulation result shows that himia has a better ability in retrieving the known stress-responsive tfs than does the null model .
parameter settings of himia
the choice of the relaxing the p-value to  <dig>   has a biological meaning.
two previous papers  <cit>  used a statistical error model to assign a p-value of the binding relationship of a tf-promoter pair.
they found that if p ≤  <dig> , the binding relationship of a tf-promoter pair is of high confidence and can usually be confirmed by promoter-specific pcr.
if p >  <dig> , the binding relationship of a tf-promoter pair is of low confidence and cannot be confirmed by promoter-specific pcr most of the time.
however, if  <dig>  <p ≤  <dig> , the binding relationship of a tf-promoter pair is ambiguous and can be confirmed by promoter-specific pcr in some cases but not in the other cases.
one of our aims in this study was to solve this ambiguity, so we chose  <dig>  to be the relaxed p-value.
however, we added the requirement that the promoter must contain one or more binding sites of the tf.
in the original paper, causton et al.
<cit>  defined a candidate heat-inducible gene by the criterion that at least one time point of its gene expression profile showed a change fold of at least three.
in order to reduce the chance of including false positives, we used a criterion that at least two time points showed a change fold of at least three.
using this criterion,  <dig> genes were identified as candidate heat-inducible genes.
of course, some false positives might still exist among these  <dig> genes.
in the subsequent steps, however, himia further refined this set of candidate heat-inducible genes using four independent data sources .
finally, only  <dig> genes were identified heat-inducible genes, which were classified into  <dig> heat-inducible grms regulated by heat-responsive tfs.
among the  <dig> identified genes,  <dig> are known to be involved in heat shock response.
we provided several lines of evidence to support the biological relevance of the  <dig> identified heat-inducible grms .
therefore, the possible existence of false positives should not be a serious problem in himia.
genes in the heat-inducible grms
himia identified  <dig> heat-inducible grms.
on average, 67% of the genes in a heat-inducible grm are known to be involved in heat shock response, 17% of the genes in a grm are uncharacterized genes , and 16% of the genes in a grm are annotated in other cellular processes.
although we cannot claim that all genes in the last two categories are heat-inducible genes, our predictions are supported by three observations.
first, all these genes are induced by more than three folds at least at two time points of their expression profiles under heat shock.
second, all these genes are regulated by at least one known heat-responsive tfs in the corresponding grms, and the tf-gene regulatory relationships are supported by at least three independent data sources .
third, it is known that during heat shock yeast cells express a variety of genes related to carbohydrate metabolism, fatty acid metabolism, energy generation, respiration, signaling pathways  and others  <cit> .
for the known genes in a grm that have not been annotated in heat shock response, most of them are related to one of the cellular processes mentioned above.
this provides indirect evidence for these genes to be possibly triggered by heat shock response.
however, further experimental validations are needed to reliably claim that these predicted heat-inducible genes do play a role in heat shock response.
we also found that genes with diverse functions may be in the same grm.
as an example, hsf <dig>  msn <dig>  and yap <dig> are known heat-responsive tfs  <cit>  and eight genes  are in the module {hsf <dig>  msn <dig>  yap1} .
hsp <dig>  hsp <dig>  ssa <dig> and sse <dig> are genes encoding heat shock proteins that function as protein chaperones  <cit> .
cpr <dig> encodes a protein that binds to hsp <dig> and contributes to chaperone activity  <cit> .
spi <dig> encodes a protein that is involved in cell wall biogenesis  <cit> .
tkl <dig> is involved in carbon metabolism and is induced in response to heat shock  <cit> .
yhr087w is an uncharacterized gene with unknown function  <cit> .
it is not surprising that we find genes encoding hsps, cell wall biogenesis protein, and carbon metabolic proteins in a grm because they are all needed when yeast cells are subjected to heat shock  <cit> .
hsps function as protein chaperones, so named because of their ability to bind to partially unfolded proteins to protect them from degradation or aggregation.
high temperature causes the weakness of cell wall and induces the expression of genes that are involved in cell wall biogenesis and maintenance.
it is known that heat stress imposes large demands for energy  generation by the cell  <cit> .
in short, heat shock response is multifaceted, involving the expression of genes with diverse functions.
CONCLUSIONS
we developed a method, called heat-inducible module identification algorithm , for reconstructing grms of heat shock response in yeast by integrating current chip-chip, mutant, tfbs, and time series gene expression data.
unlike previous module inference tools which are static statistics-based methods, himia is a dynamic system model-based method that utilizes the dynamic nature of time series gene expression data.
himia identified  <dig> grms, which in total contain  <dig> heat-inducible genes regulated by  <dig> heat-responsive tfs.
the literature indicates that  <dig> of the  <dig> genes and  <dig> of the  <dig> tfs are known to be involved in heat shock response.
the biological relevance of each inferred grm was validated by using the literature, enrichment for genes in the same mips functional category, protein-protein interaction data, and so on.
our analysis suggests that different combinations of a fairly small number of heat-responsive tfs may be responsible for regulating a large number of genes involved in heat shock response and that there may exist crosstalk between heat shock response and other cellular processes.
in addition, himia suggested that  <dig> uncharacterized genes may be involved in heat shock response and it also identified their plausible heat-responsive regulators.
furthermore, himia is capable of assigning the regulatory roles of the tfs that regulate grms and cst <dig>  hsf <dig>  msn <dig>  msn <dig>  and yap <dig> are found to be activators of several grms.
in addition, himia refined two clusters of genes that are involved in heat shock response and provided a better understanding of how the complex expression program of heat shock is regulated.
finally, we showed that himia outperformed four current module inference tools , and we conducted two randomization tests to show that the output of himia is statistically meaningful.

 single-cell organisms such as yeasts constantly face changing or even harsh environments such as high temperature that threaten their survival or, at least, prevent them from performing optimally. by organizing the genome into gene regulatory modules, a yeast cell can coordinate the activities of many genes and carry out complex functions in response to high temperature. therefore, identifying grms of heat response is instrumental for understanding cellular responses to heat shock. the advances of high-throughput tools such as dna microarray and chromatin immunoprecipitation-dna chip have made the computational reconstruction of grms of a yeast cell possible. several module inference methods have been proposed. lee et al. performed chip-chip experiments on tfs in yeast and discovered six types of network motifs in yeast gene regulation. using microarray data, segal et al. developed a probabilistic model to identify yeast grms. later, three studies were conducted to combine chip-chip and gene expression data to identify yeast grms. first, xu et al. extended segal et al.'s probabilistic model to incorporate chip-chip data. second, bar-joseph et al. developed gram to identify rich medium gene regulatory modules. third, wu et al. developed mofa to identify grms of yeast cell cycle. more data sources were used in more recent studies. kato et al. identified grms of yeast cell cycle by combining sequence, chip-chip and gene expression data. lemmens et al. developed remodiscovery to identify grms of the yeast cell cycle and yeast stress response by combining motif information, chip-chip and gene expression data. tanay et al. applied a graph theoretic approach and developed samba to reveal the modular organization of the yeast regulatory system by combining protein interactions, growth phenotype data, chip-chip, and gene expression data. however, all these module inference algorithms are statistics-based methods, treating dynamic time series gene expression data the same way as static steady state gene expression data. that is, they do not consider the dependency between different time points of a time series and thus do not utilize the dynamic nature of time series data. because many time series gene expression data sets are now available in the public domain, it is desirable to develop a module inference method that can utilize the dynamic nature of time series gene expression data. the aim of this study is to develop a module inference method that suits this need. by combining current transcription factor binding site, mutant, chip-chip, and heat shock time series gene expression data, we developed a module inference method, called heat-inducible module identification algorithm, to reconstruct heat-inducible grms in yeast. himia is divided into five steps. first, three independent data sources are used to construct a high-confidence tf-promoter binding matrix. from the tf-promoter binding matrix, all the tfs that bind to any specific target gene can be inferred. second, using heat shock time series gene expression data, a dynamic system model of gene regulation is applied to describe how a target gene's expression under heat shock is controlled by the tfs that bind to its promoter. a dynamic system model is capable of utilizing the dynamic nature of time series gene expression data, making it different from the static statistics-based models in previous studies. after the dynamic system modeling, the tfs that have significant regulatory effects on the target gene's expression can be extracted from all tfs that bind to the target gene. from this procedure, a high-confidence tf-gene regulatory matrix is constructed. each tf-gene regulatory relationship in this matrix is supported by at least three independent data sources. third, candidate heat-inducible genes are identified. a gene is said to be heat-inducible if at least two time points of its gene expression profile measured under heat shock are induced by at least three folds compared to that under the unstressed condition. causton et al. defined a candidate heat-inducible gene by the criterion that at least one time point of its gene expression profile shows a change fold of at least three. in order to reduce the false positives, we use a criterion that requires at least two time points with a change fold of at least three. fourth, using the list of candidate heat-inducible genes and the high-confidence tf-gene regulatory matrix, heat-responsive tf sets can be inferred by statistical methods. a tf set is said to be heat-responsive only if a significant portion of the targets that are co-regulated by all the tfs in the tf set is heat-inducible. the hypergeometric distribution is used to test the statistical significance. fifth, for each heat-responsive tf set, we collect all their regulatory targets that are heat-inducible to form a candidate heat-inducible grm. that is, a heat-inducible grm consists of a set of heat-inducible genes that are regulated by the same set of heat-responsive tfs. because genes in the same grm are regulated by the same set of tfs, their gene expression profiles should be more similar to each other than those of a set of genes that are not in a single grm. therefore, for each candidate grm we further extract a subset of genes whose gene expression profiles are more coherent than that of the set of all heat-inducible genes which are regulated by different sets of tfs. finally, this subset of highly coherent genes forms a heat-inducible grm that is regulated by the same set of heat-responsive tfs.  by integrating tfbs, mutant, chip-chip, and gene expression data, himia identified grms, which in total contain heat-inducible genes regulated by heat-responsive tfs. according to the literature, of the genes and of the tfs are known to be involved in heat shock response. validation of the identified modules several lines of evidence support that himia identifies biologically relevant heat-inducible grms. first, by the virtue of our method, each tf-gene regulatory relationship in a module is of high confidence because it is supported by at least three independent data sources. second, each module is assigned to at least one tf that is known to be involved in heat shock response. third, in the modules that are controlled by more than one tf, 70% of the tfs in the same module have physical or genetic interactions. fourth, on average, 67% of genes in a heat-inducible grm are known to be involved in heat shock response. fifth, 59% of the identified modules include groups of genes that function in the same cellular process: each of these modules contains at least one over-represented mips functional category with the adjusted p-value < using the cumulative hypergeometric distribution. finally, the modules are generally accurate in assigning tfs to sets of genes whose functions are consistent with the tfs' known roles. for the modules that contain groups of genes enriched in the same cellular process, we found that the regulatory functions of the 76% of the tfs are consistent with one of their modules' over-represented functional categories. taken together, these results provide evidence that himia identifies not only sets of biologically related heat-inducible genes, but also heat-responsive tfs that individually or collectively regulate these genes. identification of important heat-responsive tfs we identified heat-responsive tfs, of which are known to be involved in heat shock response. our findings are supported by the literature. first, msn and msn are known to regulate the general stress response in yeast. they regulate the expression of many genes in response to several stresses, including heat shock, osmotic shock, oxidative stress, low ph, glucose starvation, sorbic acid and high ethanol concentrations, by binding to the stress response element located in the promoters of these genes. second, hsf is the well-known heat shock factor that binds to the heat shock element to regulate the transcription of many heat-inducible genes, including genes involved in protein folding, detoxification, energy generation, carbohydrate metabolism, and cell wall organization. all these gene products are important for cell to counteract the deleterious effects of heat. third, yap a well-known oxidative shock factor, is also known to be involved in heat shock response. for example, yap induces the expression of gsh and gsh to synthesize glutathione in heat shock response. fourth, heat stress can cause unfolded proteins to accumulate in the endoplasmic reticulum, triggering the unfolded protein response. hac binds to the upr element to regulate genes that are involved in upr. fifth, heat stress causes a weakening of cell wall and membrane stretching which stimulates the protein kinase c pathway. rlm a component of the pkc pathway, is then activated to perform the function of maintaining the cell wall integrity. finally, cad an ap- like bzip transcriptional activator involved in stress responses, controls a set of genes involved in stabilizing proteins. the involvement of cad in stress responses was also identified by segal et al.. seven well-known heat-responsive tfs are bold-faced and colored blue. the tfs are ordered by the number of their inferred heat-inducible target genes. in addition to the above seven known heat-responsive tfs, five novel heat-responsive tfs have also been identified by himia. rox contains a high-mobility group domain that is responsible for dna bending activity. cst and ume regulate genes involved in the cell cycle and dna processing. ste and dig are involved in the regulation of mating-specific genes and the invasive growth pathway. identification of these five tfs as heat-responsive tfs suggests that heat shock response may have crosstalk with other cellular processes. it is known that the cell cycle transiently arrests during a heat shock stress, validating our proposal that heat shock response may have crosstalk with the cell cycle process. moreover, these five novel heat-responsive tfs and the other seven known heat-responsive tfs form a highly connected network of interactions, supporting our prediction that these five novel heat-responsive tfs may play a role in heat shock response. this dense network of interactions also suggests that different combinations of a fairly small number of heat-responsive tfs may be sufficient to regulate a large number of genes involved in heat shock response. taken together, these results suggest that himia is effective for identifying tfs that play a role in heat shock response or are involved in other cellular processes that may crosstalk with heat shock response. identification of important genes involved in heat shock response disruption of a large number of cellular assemblies and processes, an increased protein unfolding and aggregation, and membrane structure alterations are paramount in cells exposed to high temperature. heat shock response serves to counteract these deleterious effects. through it cells increase their thermotolerance or ability to withstand heat stress. many events occur in yeast cells during heat shock response. first, heat shock proteins are rapidly synthesized. many hsps function as protein chaperones, so named because of their ability to bind to partially unfolded proteins to protect them from degradation or aggregation. himia successfully identified heat shock protein genes hsp and hsp to be regulated by heat-shock transcription factor hsf and hsp and hsp to be regulated by the general stress factor msn in addition, hsp hsp ssa ssa and sse are identified to be regulated by both hsf and msn other genes involved in the protein folding or refolding are also found. for example, eug lhs scj and ero are regulated by hac a tf known to be involved in protein unfolding response. second, heat shock causes the extremely rapid accumulation of a large cytoplasmic pool of trehalose. trehalose is one of the most effective substances known for preservation of membranous structures and enzyme activities during heating. one of the major roles for msn2/ in heat shock response is to regulate the expression of genes required for the synthesis of trehalose. himia successfully identified three genes for trehalose synthease subunits: tsl, tsp and nth are indeed regulated by msn or msn third, heat shock increases the synthesis of certain components of the ubiquitination system for intracellular protein turnover, indicating a much greater requirement for turnover of abnormal proteins in cells recovering from heat stress. himia successfully identified several genes that are known to be involved in protein degradation. der and pbi are identified to be regulated by hac apg ubc jem and ubi are regulated by hsf lap and asi are regulated by msn atg and ysp are regulated by rlm fourth, high temperature causes the weakness of cell walls and induces the expression of genes that are involved in cell wall biogenesis and maintenance. himia successfully identified seven genes known to be involved in the cell wall biogenesis and maintenance. all these seven genes are in module and regulated by rlm an important cell integrity maintenance factor. finally, it is known that during heat shock cells induce a variety of genes related to carbohydrate metabolism, fatty acid metabolism, respiration and others. himia successfully identified genes that are involved in these cellular processes. for example, hxk glk and gph involved in glucose metabolism are identified to be regulated by msn faa and faa involved in fatty acid metabolism are identified to be regulated by hsf cyc and cox involved in respiration are identified to be regulated by msn the known functions of these genes hint the cellular processes that may be affected in response to heat shock, and suggest mechanisms the cell uses to protect itself in the face of a heat stress. annotating uncharacterized genes among the identified heat-inducible genes, genes have unknown function according to the saccharomyces genome database. we suggest most if not all of these genes are involved in heat shock response. our predictions are supported by the fact that all these genes are induced by more than three folds at least at two time points of their expression profiles under heat shock. moreover, all these genes are regulated by known heat-responsive tfs and the tf-gene regulatory relationships are supported by at least three independent data sources. as shown in additional file of these genes are regulated by hac by hsf by msn by msn by yap and so on. as an example, it is known that the weakening of cell wall during high temperature stimulates the cell integrity pathway. prm is known to be induced in the cell integrity pathway but its molecular function is unknown. himia identified prm to be regulated by rlm an important cell wall integrity maintenance factor, suggesting that prm is indeed involved in the cell wall maintenance during heat shock. moreover, we successfully identified the putative heat shock protein gene yro to be regulated by msn in addition, putative genes that may be involved in protein degradation are also found. for example, hbt and rim are identified to be regulated by msn mgr and add are identified to be regulated by hac all these examples show that these uncharacterized genes may play a role in heat shock response. however, further experimental validations are needed to confidently annotate these uncharacterized genes as heat-inducible genes. assigning regulatory roles of tfs that regulate a grm we can assign the regulatory roles of tfs that regulate a module. a tf is said to be an activator of a module if the p-value for observing so many tf-gene pairs in the module each with a significant positive correlation is less than. the p-value is the probability that an observation would be made by chance, and is calculated using the cumulative binomial distribution: p=∑x=n0np0xn−x where n is the total number of genes in a module, n is the number of genes in the module that show a significant positive correlation in expression with the tf, and p is the probability of observing an arbitrary gene in the genome that has a significant positive correlation in expression with the tf. as shown in table we assigned cst as an activator of four modules, hsf an activator of three modules, msn an activator of five modules, msn an activator of two modules, rlm an activator of two modules and yap an activator of four modules. a tf is said to be an activator of a module if the p-value for observing so many tf-gene pairs in the module each with a significant positive correlation is less than. refining the clusters of the genes involved in the same cellular process heat shock causes an increased protein unfolding and aggregation in a cell. thus, many genes that are involved in protein folding are induced to bind to partially unfolded proteins to protect them from degradation or aggregation. among the identified heat-inducible genes, genes are known to be involved in protein folding. although these genes are functionally similar, they may be under different transcriptional controls. indeed, himia assigns these genes into five modules. for example, hsp and hsp are identified to be regulated by hsf hsp by msn2/ hsp and hsp by both hsf and msn2/ and so on. denatured proteins that cannot be properly refolded are targeted for degradation by ubiquitination, so it is not surprising that genes involved in protein degradation are induced under heat shock. among the identified heat-inducible genes, genes are known to be involved in protein degradation. although these genes are functionally similar, they may be under different transcriptional controls. himia assigns these genes into five modules. for example, pbi add der and mgr are identified to be regulated by hac atg and ysp by rlm and so on. therefore, himia can refine the cluster of genes involved in protein folding and degradation and can provide a better understanding of how the cell regulates the complex expression program of these genes. discussion performance comparison with existing methods several module inference methods have been proposed. gram and mofa are intuitive algorithms to identify yeast grms by combining chip-chip and gene expression data. remodiscovery is an intuitive algorithm to identify yeast grms by combining motif information, chip-chip, and gene expression data. samba uses a graph theoretic approach to identify grms by combining four data sources. all these four module inference algorithms are statistics-based methods. on the contrary, himia is a dynamic system model-based method that integrates four data sources. since himia is different from the four pervious methods, a performance comparison was conducted. we tested the ability of each of these five algorithms to retrieve the known stress-responsive tfs annotated in the mips database. performance comparison was based on the jaccard similarity score, which scores the overlap between an algorithm's output and the list of known stress-responsive tfs. therefore, the higher the jaccard similarity score, the better the ability of an algorithm to retrieve the known stress-responsive tfs. table shows that himia has the highest jaccard similarity score among the five tested algorithms. performance comparison was based on the jaccard similarity score, which scores the overlap between an algorithm's output and the list of known stress-responsive tfs. specifically, the score is defined as tp/, where tp stands for true positives, fp for false positives, and fn for false negatives. note that the higher the jaccard similarity score, the better the ability of an algorithm to retrieve the known stress-responsive tfs. randomization test and comparison with a null model two randomization tests were performed to show that the output of himia is statistically meaningful. first, we randomly permuted the gene expression data times. second, we randomly permuted the chip-chip data times. when either of the two randomized data sets was used as the input, himia could no longer effectively identify the known stress-responsive tfs. this means that the output of himia is statistically meaningful and is far beyond random expectation. two randomization tests were performed. first, we randomly permuted the gene expression data times. second, we randomly permuted the chip-chip data times. when either of the two randomized data sets was used as the input, himia could no longer effectively identify the known stress-responsive tfs, indicating that the output of himia is statistically meaningful and is far beyond random expectation. in addition, we compared the performance of himia and the null model to retrieve the known stress-responsive tfs annotated in the mips database. the null model was defined as using the same input data but only the overlap was calculated instead of going through the iterative procedure described on figure the simulation result shows that himia has a better ability in retrieving the known stress-responsive tfs than does the null model. parameter settings of himia the choice of the relaxing the p-value to has a biological meaning. two previous papers used a statistical error model to assign a p-value of the binding relationship of a tf-promoter pair. they found that if p ≤, the binding relationship of a tf-promoter pair is of high confidence and can usually be confirmed by promoter-specific pcr. if p >, the binding relationship of a tf-promoter pair is of low confidence and cannot be confirmed by promoter-specific pcr most of the time. however, if <p ≤, the binding relationship of a tf-promoter pair is ambiguous and can be confirmed by promoter-specific pcr in some cases but not in the other cases. one of our aims in this study was to solve this ambiguity, so we chose to be the relaxed p-value. however, we added the requirement that the promoter must contain one or more binding sites of the tf. in the original paper, causton et al. defined a candidate heat-inducible gene by the criterion that at least one time point of its gene expression profile showed a change fold of at least three. in order to reduce the chance of including false positives, we used a criterion that at least two time points showed a change fold of at least three. using this criterion, genes were identified as candidate heat-inducible genes. of course, some false positives might still exist among these genes. in the subsequent steps, however, himia further refined this set of candidate heat-inducible genes using four independent data sources. finally, only genes were identified heat-inducible genes, which were classified into heat-inducible grms regulated by heat-responsive tfs. among the identified genes, are known to be involved in heat shock response. we provided several lines of evidence to support the biological relevance of the identified heat-inducible grms. therefore, the possible existence of false positives should not be a serious problem in himia. genes in the heat-inducible grms himia identified heat-inducible grms. on average, 67% of the genes in a heat-inducible grm are known to be involved in heat shock response, 17% of the genes in a grm are uncharacterized genes, and 16% of the genes in a grm are annotated in other cellular processes. although we cannot claim that all genes in the last two categories are heat-inducible genes, our predictions are supported by three observations. first, all these genes are induced by more than three folds at least at two time points of their expression profiles under heat shock. second, all these genes are regulated by at least one known heat-responsive tfs in the corresponding grms, and the tf-gene regulatory relationships are supported by at least three independent data sources. third, it is known that during heat shock yeast cells express a variety of genes related to carbohydrate metabolism, fatty acid metabolism, energy generation, respiration, signaling pathways and others. for the known genes in a grm that have not been annotated in heat shock response, most of them are related to one of the cellular processes mentioned above. this provides indirect evidence for these genes to be possibly triggered by heat shock response. however, further experimental validations are needed to reliably claim that these predicted heat-inducible genes do play a role in heat shock response. we also found that genes with diverse functions may be in the same grm. as an example, hsf msn and yap are known heat-responsive tfs and eight genes are in the module {hsf msn yap1}. hsp hsp ssa and sse are genes encoding heat shock proteins that function as protein chaperones. cpr encodes a protein that binds to hsp and contributes to chaperone activity. spi encodes a protein that is involved in cell wall biogenesis. tkl is involved in carbon metabolism and is induced in response to heat shock. yhr087w is an uncharacterized gene with unknown function. it is not surprising that we find genes encoding hsps, cell wall biogenesis protein, and carbon metabolic proteins in a grm because they are all needed when yeast cells are subjected to heat shock. hsps function as protein chaperones, so named because of their ability to bind to partially unfolded proteins to protect them from degradation or aggregation. high temperature causes the weakness of cell wall and induces the expression of genes that are involved in cell wall biogenesis and maintenance. it is known that heat stress imposes large demands for energy generation by the cell. in short, heat shock response is multifaceted, involving the expression of genes with diverse functions.  we developed a method, called heat-inducible module identification algorithm, for reconstructing grms of heat shock response in yeast by integrating current chip-chip, mutant, tfbs, and time series gene expression data. unlike previous module inference tools which are static statistics-based methods, himia is a dynamic system model-based method that utilizes the dynamic nature of time series gene expression data. himia identified grms, which in total contain heat-inducible genes regulated by heat-responsive tfs. the literature indicates that of the genes and of the tfs are known to be involved in heat shock response. the biological relevance of each inferred grm was validated by using the literature, enrichment for genes in the same mips functional category, protein-protein interaction data, and so on. our analysis suggests that different combinations of a fairly small number of heat-responsive tfs may be responsible for regulating a large number of genes involved in heat shock response and that there may exist crosstalk between heat shock response and other cellular processes. in addition, himia suggested that uncharacterized genes may be involved in heat shock response and it also identified their plausible heat-responsive regulators. furthermore, himia is capable of assigning the regulatory roles of the tfs that regulate grms and cst hsf msn msn and yap are found to be activators of several grms. in addition, himia refined two clusters of genes that are involved in heat shock response and provided a better understanding of how the complex expression program of heat shock is regulated. finally, we showed that himia outperformed four current module inference tools, and we conducted two randomization tests to show that the output of himia is statistically meaningful. 
unlike previous module inference tools which are static statistics-based methods, himia is a dynamic system model-based method that utilizes the dynamic nature of time series gene expression data. integrating transcription factor binding site, mutant, chip-chip, and heat shock time series gene expression data, we develop a method, called heat-inducible module identification algorithm, for reconstructing grms of yeast heat shock response. himia identifies grms, which in total contain heat-inducible genes regulated by heat-responsive tfs. our analysis suggests that different combinations of a fairly small number of heat-responsive tfs regulate a large number of genes involved in heat shock response and that there may exist crosstalk between heat shock response and other cellular processes. finally, we show that himia outperforms four current module inference tools, and we conduct two randomization tests to show that the output of himia is statistically meaningful. furthermore, himia is capable of assigning the regulatory roles of the tfs that regulate grms and cst hsf msn msn and yap are found to be activators of several grms. therefore, identifying grms is helpful for understanding gene regulation. using himia, we identify uncharacterized genes that may be involved in heat shock response and we also identify their plausible heat-responsive regulators. in addition, himia refines two clusters of genes involved in heat shock response and provides a better understanding of how the complex expression program of heat shock response is regulated. himia is effective for reconstructing grms of yeast heat shock response. using various types of published data, we validate the biological relevance of the identified grms.
 a gene regulatory module is a set of genes that is regulated by the same set of transcription factors. by organizing the genome into grms, a living cell can coordinate the activities of many genes in response to various internal and external stimuli. therefore, identifying grms is helpful for understanding gene regulation.  integrating transcription factor binding site, mutant, chip-chip, and heat shock time series gene expression data, we develop a method, called heat-inducible module identification algorithm, for reconstructing grms of yeast heat shock response. unlike previous module inference tools which are static statistics-based methods, himia is a dynamic system model-based method that utilizes the dynamic nature of time series gene expression data. himia identifies grms, which in total contain heat-inducible genes regulated by heat-responsive tfs. using various types of published data, we validate the biological relevance of the identified grms. our analysis suggests that different combinations of a fairly small number of heat-responsive tfs regulate a large number of genes involved in heat shock response and that there may exist crosstalk between heat shock response and other cellular processes. using himia, we identify uncharacterized genes that may be involved in heat shock response and we also identify their plausible heat-responsive regulators. furthermore, himia is capable of assigning the regulatory roles of the tfs that regulate grms and cst hsf msn msn and yap are found to be activators of several grms. in addition, himia refines two clusters of genes involved in heat shock response and provides a better understanding of how the complex expression program of heat shock response is regulated. finally, we show that himia outperforms four current module inference tools, and we conduct two randomization tests to show that the output of himia is statistically meaningful.  himia is effective for reconstructing grms of yeast heat shock response. indeed, many of the reconstructed grms are in agreement with previous studies. further, himia predicts several interesting new modules and novel tf combinations. our study shows that integrating multiple types of data is a powerful approach to studying complex biological systems. 