BACKGROUND
several motif detection algorithms have been developed to discover overrepresented motifs in sets of coexpressed genes .
the rationale behind these methodologies is that a set of genes regulated by the same transcription factor should contain in their intergenic regions motifs that are statistically overrepresented as compared to their occurrences in unrelated sequences.
these methodologies have proven to be useful in many applications .
however, usually their performance rapidly drops as the signal to noise ratio  in the data set decreases  <cit> .
this drop in performance is also evident in an assessment study of  <dig> different computational de novo motif detection tools, where the number of correct motifs retrieved was very low in sets of noisy data  <cit> .
however, noisy data is mostly the case encountered in sequence sets derived from genome wide expression profiles, such as microarrays.
the high noise level in such sequence sets comes as a result of the processing of the microarray data , as well as the nature of the biological processes in the cell itself.
for instance, when comparing mrna expression between a wild type and a regulator knock out strain, besides the direct targets of the regulator, indirect targets are also affected in their mrna expression in the knock out.
in such mutants the complete regulatory network acting downstream of the mutated regulator is disturbed.
lists of genes derived from these experiments contain targets of more than one regulatory protein lowering the relative overrepresentation of a particular motif
in order to get over this problem, we have developed an approach that exploits orthology information besides coexpression, to discover de novo motifs.
orthology information is introduced by phylogenetic footprinting which is based on the assumption that among phylogenetically related species, the regulating sequences in the upstream regions of orthologous genes are selectively conserved by evolution.
phylogenetic footprinting has been used for the detection of motifs with relative success  <cit> .
in these approaches, however, the orthology information is only used within a set of orthologous intergenic regions to create motif models.
recently, a number of algorithms were developed that permit for the mutual comparison of the motif models derived from different sets of orthologous intergenic regions, followed by the clustering of the conserved regions that share the same regulatory motif.
in one approach, jensen et al.
<cit>  applied phylogenetic footprinting using gibbs sampling and then grouped the conserved regions using a bayesian clustering algorithm.
a similar way of clustering motif models derived from phylogenetic footprinting was developed by qin et al.
<cit>  and van nimwegen et al.
<cit> .
another approach is developed by wang and stormo  <cit> , where conserved regulatory regions were detected using wconsensus  <cit>  and where the regions sharing the same regulatory motif were clustered by gradually merging motif models of different orthologous sets .
in their recent paper, wang and stormo  <cit>  used a different clustering approach; they would first align the models and consequently cluster them according to their alignment scores .
our methodology is a combination of gibbs sampling-based phylogenetic footprinting, with two-step clustering .
for phylogenetic footprinting, we developed a new algorithm called blocksampler, which is an extension of the gibbs sampling-based motifsampler  <cit> , optimized towards phylogenetic footprinting.
for the alignment of the different motif models returned from blocksampler, we developed a second algorithm called blockaligner, which aligns matrices describing conserved regions using a smith-waterman approach  <cit> .
the methodology based on these two new algorithms is capable of detecting motifs with weak overrepresentation in a set of coregulated genes.
by applying our procedure on gene lists derived from real genome wide expression studies, we show its ability to function effectively in noisy data.
in this context, the use of orthology information compensates for a lower degree of motif overrepresentation we also compared its performance on a test data set, with that of two other motif detection tools: one that is exclusively based on coexpression information, alignace  <cit> , and another that is most similar to our method, phylocon  <cit> .
with this comparison, we demonstrated the robustness of our method over the two mentioned.
using our method on two real biological data sets proved its biological applicability.
RESULTS
general strategy
several motif detection algorithms have been developed to discover overrepresented motifs in sets of coexpressed genes.
however, in a noisy data set the motif might not be sufficiently overrepresented to allow detection by classical tools.
to be able to recover motifs in such context, we developed a procedure in which we first use phylogenetic footprinting to delineate all potential motifs in each gene.
then, we mutually compare all detected motifs and identify the ones that are shared by at least a few genes in the data set as potential candidates.
the complete analysis flow is represented in figure  <dig> and consists of the following steps: starting from a list of differentially expressed or coexpressed genes, we find the orthologs for each gene in a number of closely related species.
the obtained data sets, consisting of the intergenic sequences of orthologous genes, are subjected to phylogenetic footprinting using a gibbs sampling tool called blocksampler .
this yields a list of conserved regions  for each of the orthologous data sets, corresponding to all potential motifs.
searching for the motifs shared by at least some of the original list of coexpressed genes, we mutually align our blocks with blockaligner , and then we construct a multiple alignment using the pairwise alignment scores to delineate further the potential regulatory motifs .
as our methodology only detects motifs in genes for which orthologous information is available, some motif hits in the initial gene list might escape detection.
to recover these motifs, we use the motif models we obtained from the previous step to screen the intergenic sequences of the remaining genes .
here we give an overview of the main tools we used in our flow.
algorithmic details can be found in the methods section.
blocksampler is used to detect conserved motifs in intergenic sequences of orthologous genes.
the algorithm is an adapted version of motifsampler, a motif detection algorithm based on gibbs sampling  <cit> .
due to the specificities of the scoring scheme  the algorithm does not require the motif to be present in each single orthologous sequence.
although regions conserved in the entire set of sequences will receive a better score, the regions conserved in less than the entire set could still be retained.
in contrast to the original implementation  <cit> , blocksampler allows for scoring each orthologous intergenic sequence in the input data set with its corresponding species specific background model.
since it is often the case with closely related species that big stretches around the motifs are conserved  <cit> , blocksampler was adapted to look for long conserved sequence blocks.
blocksampler also allows for the choice of a reference species, usually corresponding to the species of interest for which the experimental data are available.
the consequence of using a reference species is that only the conserved regions that include the reference species will be retained.
blockaligner performs a local ungapped pairwise alignment, based on dynamic programming for the mutual comparison of sequence blocks, represented as frequency matrices.
the scoring scheme of blockaligner is based on the kullback-leiber distance.
we used a graph clustering algorithm to group the blocks shared by multiple genes  <cit> .
this algorithm is optimized to cluster sequences based on pairwise alignment scores.
evaluation of the analysis flow on test data
we applied our analysis flow on test data sets with known motif instances.
as shown in figure  <dig>  the data sets are made up of sequences with instances for the motifs phop, lexa, fur and metj, imbedded in a varying number of random sequences.
five collections of data sets were created with an increasing number of random sequences, decreasing the signal to noise ratio from 18- 7% for fur and lexa and 11- 4% for metj and phop .
for the purpose of evaluating the performance of the methodology, we adopted four measurements: recovery rate, number of false positives, specificity and sensitivity.
the former two are a reflection of how well a true motif model is extracted, while the latter two are measurements of the extracted motif's quality.
specifically, the recovery rate measures the number of times a motif model corresponding to a true motif is recovered by the algorithm; the number of false positives measures the average number of motif models not corresponding to the true motifs recovered by the algorithm; the sensitivity measures the ratio of true motif instances that contributed to the recovered motif model; the specificity measures the ratio of false motif instances that contributed to the recovered motif model .
note that these values were calculated before the last screening step of the algorithm, so that all instances recovered by screening are not included in the calculations.
as shown in figure  <dig> and the supplementary table  <dig> <cit> , our methodology performed well in retrieving the metj, lexa and phop motif models, with relatively low effect of the increasing noise in the data set.
only for the fur motif the recovery rate was low, but with high resistance to noise.
analysis of the results showed that during the run of the methodology, the fur motif instances were clustered in a single cluster , however, together with degenerated blocks lacking fur instances.
the presence of such blocks in the subsequent motif delineation step causes the consensus score of the fur motif model to drop below the selected threshold, explaining why it was not frequently recovered using our stringent criteria.
the number of false positives picked up by the algorithm was low , ranging between an average of  <dig>  in the low noise data sets to  <dig>  in the high noise sets.
this shows the robustness of the algorithm against noise in the data.
regarding the quality of the motif models recovered, figure  <dig> shows that the algorithm achieved relatively high sensitivity and specificity for fur, metj and lexa, indicating that most true instances contributed to the model, and that few false ones did.
in the case of phop, the sensitivity was low due to the fact that the model recovered by our algorithm was the dyad variant, while the two instances of the half site variant  did not contribute to the model.
importance of the selected species
to assess the importance of adding a distantly related species to the analysis , we tested to what extent motif instances in this species contributed to the motif models returned by our algorithm.
instances of y. pestis seemed to have contributed to the resulting motif models in more than 90% of the cases for metj and lexa, more than 80% for phop, and more than 75% for the fur motif.
on the other hand, adding y. pestis did not decrease the sensitivity of our motif models: motif instances that were only conserved in s. typhimurium and e. coli, but not in y. pestis were also recovered.
these results indicate that aligned blocks are not dominated by the sequences of the most related species and that adding a distantly related species helps delineating the true motifs without decreasing the sensitivity, even when motif instances are no longer conserved across all species.
comparison with other methodologies
we compared the performance of our methodology to that of two other motif detection algorithms: alignace, a gibbs sampling algorithm designed to detect overrepresented motifs in a set of coregulated genes and phylocon, an algorithm that uses information on coexpression and orthology for motif detection.
alignace was applied to our test data sets without taking orthology information into account.
execution parameters are described in methods.
as displayed in figure  <dig>  only two out of the four motifs could be detected by alignace with very low recovery rates.
in addition, the performance for those two motifs drops significantly when increasing the number of random genes .
while the number of false positives seems to be independent of the noise, it is clearly high ).
regarding the quality of the motifs recovered, fur and lexa, the sensitivity was always high, however, at the expense of a lower specificity.
no values for sensitivity and specificity were calculated for phop and metj as these motifs were not detected.
our methodology clearly outperformed alignace in three aspects: the number of true motifs recovered, the quality of the motifs and the robustness against noise.
this result is expected as alignace uses one source of information i.e.
genes from one species, while our methodology depends on two sources i.e.
single species genes and their orthologs.
in the case of phylocon, it also failed to recover metj and phop .
although it was previously reported that it is possible to detect the metj motif in a dataset containing only metj intergenic regions  <cit>  , phylocon clearly failed to do so in the noisy context of our study.
for lexa, phylocon recovered the motif at a rate comparable to that of our algorithm, and only marginally affected by the increasing noise in the data.
phylocon performed well in retrieving the fur motif, but with a recovery rate slightly sensitive to noise.
calculating the false positive discovery rate for phylocon illustrates that this algorithm is not sensitive to low signal to noise ratios  .
however, the absolute number of false positives is higher than that in the case of our methodology.
regarding the quality of the motif models, the fur motif model retrieved by phylocon seemingly outperforms our retrieved model both in sensitivity and specificity with hardly any effect for the noise in the data set.
for the lexa motif, an optimal specificity was obtained but with mediocre sensitivity, indicating that the motif model, although frequently recovered, is often based on just two or three lexa instances.
it is important to emphasize that all the values obtained for the performance assessment of phylocon are biased to its favor in this case.
one needs to note that in all the occasions when phylocon did not converge to a known motif, we retrieved the motif model from a cycle premature of convergence .
thus, slightly better sensitivities and recovery rates of phylocon over our methodology need to be interpreted in the light of this fact.
again, our methodology proved to be more robust to noise than similarly based algorithms as seen in its ability to recover all the true motif models in the data set with very few false positives.
evaluation of the analysis flow on expression data
besides the test data sets, we applied our methodology on two data sets derived from genome wide expression studies.
a first data set consisted of a list of  <dig> differentially expressed genes between a constitutive and a null pmra mutant of s. typhimurium  <cit> .
the pmrab two-component regulatory system is part of a multi-component feedback loop that acts as a major virulence regulator in s. typhimurium.
the system itself is responsive to fe3+ and mild acid and senses mg2+ indirectly by communicating with the mg2+ sensitive phopq system via pmrd.
applying our analysis flow on the intergenic sequences of these coexpressed genes  resulted in the detection of two potential motifs.
the first motif which was derived from the motif instances of the known pmra regulated genes udg, yfbe, yibd and yjdb, corresponded to the consensus of the biologically validated pmra motif   <cit> .
the motif logo is shown in figure  <dig> a  screening the intergenic regions of the remaining differentially expressed genes from the input set with this motif model, resulted in the detection of six additional potential pmra targets.
two of these six genes  did not contain an ortholog in e. coli or y. pestis, and in the four remaining genes  the pmra motif was not conserved in the orthologs of e. coli or y. pestis, explaining the reason these motif instances could not be recovered initially unless by screening.
the  regulation of eight of these reported ten genes by pmrab is supported by evidence from previous studies.
seven of these genes – ais , yjdb , yfbe , ugd , yibd, ybjg  and stm <dig>  – are known members of the pmrab regulon that were confirmed in different experiments  <cit> .
the last gene, yijp , was also discovered in an in silico screening of this same microarray data by tamayo et al.
<cit> .
we also report two new potential pmra targets, ygiw and yegh, that were not recovered by tamayo et al  <cit> .
this could be due to the more stringent threshold they used when defining differentially expressed genes, than ours .
in addition to the well known pmra motif, we predicted yet an uncharacterized motif aaggaana)  which was based on conserved instances present in tufa, yiht and stm <dig> .
screening the remaining differentially expressed genes with the motif model corresponding to this motif resulted in the discovery of motif instances in two additional genes .
no similarity between this motif and any of the motifs in the existing databases could be found .
the second data set was derived from the study of salmon et al.
<cit> .
e. coli and related species respond to oxygen depletion by switching to anaerobic respiration.
this transition is mainly controlled by the global regulator fnr  <cit> .
salmon et al.
<cit>  performed genome wide expression profiling experiments to identify genes differentially expressed in response to oxygen and controlled by fnr.
applying our methodology to  <dig> differentially expressed genes derived from their study resulted in the detection of a motif model corresponding to the well known fnr motif .
the model was based on conserved instances found in  <dig> known fnr regulated genes narx, nirb, ndh and cyda .
the instances present in three differentially expressed genes, marked as fnr regulated in regulondb  did not contribute to our fnr motif model.
it seems like the degree of conservation of the motif among the respective orthologs of these genes was too low to be detected by our analysis flow.
however, these genes could be retrieved in the screening step.
discussion
if we want to be able to get a complete view on the transcriptional network of an organism, revealing all regulatory motifs remains one of the main challenges  <cit> .
despite the fact that several motif detection algorithms have been developed and optimized, detection of regulatory motifs with low overrepresentation is still difficult using the common motif detection tools.
therefore we developed a tool that is able to retrieve regulatory motifs planted in a noisy environment i.e.
only a very small subset of submitted intergenic regions contains the motif.
in a first step of our method, large conserved regulatory regions  are identified in a set of orthologous intergenic regions .
after aligning all these conserved blocks with each other, blocks containing a shared regulatory motif are clustered.
in a final step, screening of all input intergenic regions permits for the detection of those target genes where the motif was not conserved in its orthologs .
to test its reliability, we applied our methodology on a "golden standard" consisting of a set of randomly selected, non-related genes among which known targets of the fur, metj, lexa and phop regulons were hidden.
although these known targets contained previously described motif instances for each of these regulators, their statistical overrepresentation in this test set was low ).
when applying our methodology we found that for  <dig> out of the  <dig> hidden motifs the recovery rate was above 90% even in the presence of a high amount of noisy genes.
for the fur motif it was slightly lower  because of the lower degree of conservation of the motif model .
notwithstanding this high recovery rate, the number of false positive motifs  remained low .
the achieved quality of the retrieved motif models, reflected by the motif model sensitivity  and specificity  depends on the characteristics of the motifs; well conserved, non-dyad motifs such as the lexa and metj motifs are seemingly easy to retrieve and have a high quality; dyad motifs , although having high specificity , their sensitivity was lower than in the case of non-dyad motifs, especially for the phop dyad.
in the case of the phop motif, the low sensitivity is due to the fact that it also occurs as a single half site.
the score of the alignment of the single half site with the dyad falls below the thresholds we used and therefore these single sites could not be recovered by our methodology.
to assess the influence of taking into account orthology information in addition to information from coexpression, we applied our methodology to a combined data set of orthologous and coexpressed genes and compared its results to those obtained by applying alignace, which is a motif detection tool based on gibbs sampling, to the coexpression data only.
our methodology clearly outperformed alignace in recovering the true motifs in the data set.
in addition, the performance of alignace was seriously influenced by increasing noise in the data, in contrast to what is observed with our methodology.
these results indicate that by the incorporation of orthology information, the retrieval of motifs with weak overrepresentation  becomes possible.
in addition to the above mentioned advantage of using the combined sources of information of coexpression and orthology, an extra value can be deduced.
when using phylogenetic footprinting alone on orthologous gene sets of closely related species sharing a large part of the regulatory mechanism, long conserved blocks are detected rather than small distinct motifs  <cit> .
because this complicates the delineation of specific motifs, the sequential use of blocksampler  and blockaligner  allows for an improved delineation of individual regulatory motifs from those long conserved regions across orthologs.
we also compared our methodology to phylocon, as it has a similar strategy as ours.
phylocon identifies conserved regulatory regions  in sets of orthologs based on the wconsensus program.
subsequently, these profiles are merged between different sets of orthologs using a greedy algorithm, in order to detect a common regulatory motif.
phylocon was originally developed to detect motifs in a set of coexpressed genes, containing only one motif.
the test sets used in the original paper usually contain a single motif per data set.
as was noted by the authors, phylocon would perform better on less conserved motifs.
indeed, our results show that phylocon had a better performance in retrieving the more degenerated fur motif than the well conserved lexa, metj and phop motifs.
despite this, the overall recovery rate was lower than that of our methodology in noisy data sets containing more than one motif.
the metj and phop motifs were not recovered at all.
although the authors stated that their methodology can retrieve regulatory regions present in only a small set of genes , in our experience phylocon fails to retrieve such motifs in a noisy context.
in addition, as phylocon proceeds cycle per cycle, where in each cycle a new motif instance is added to the motif model, the authors suggest that the motif model building process be stopped before convergence in order to detect more motifs in a single dataset.
however, they do not provide a clear stop criteria or heuristics to retrieve the optimal model.
in order not to bias our results towards a sub-optimal stop criterion, we checked at each cycle whether a motif model was found that matched our test data set.
if found during at least one cycle, the motif was considered "recovered".
note that this approach is feasible when one knows which motif to look for, but not in the case when a novel motif is searched for.
this approach led to the bias of the assessment results to the favor of phylocon, as seen in the higher recovery rate, sensitivity and specificity acquired for phylocon over our method.
as a final proof of concept, we also applied our methodology to two gene sets derived from genome wide expression profiling experiments.
firstly, out of  <dig> differentially expressed genes between constitutive and null pmra mutants of s. typhimurium  <cit> , we could retrieve the expected pmra motif model  <cit> , and predict the presence of two new putative pmra targets, ygiw and yegh.
we also predicted a yet uncharacterized motif of the consensus aaggaana that was based on conserved instances in the genes tufa, yiht and stm <dig>  in a second test, using a list of  <dig> fnr regulated genes  <cit> , we could retrieve the fnr motif model based on  <dig> genes containing a clear fnr regulatory motif.
CONCLUSIONS
conclusively, we have developed an approach that can reliably identify multiple regulatory motifs lacking a high degree of overrepresentation in a set of coexpressed genes  by exploiting the advantages of using both coexpression and phylogenetic information.
through comparing our methodology to two other motif detection programs, we show the robustness of our implementation.
as a proof of concept, analysis of genome wide expression data with our methodology successfully retrieves the present regulatory motifs.

 several motif detection algorithms have been developed to discover overrepresented motifs in sets of coexpressed genes. the rationale behind these methodologies is that a set of genes regulated by the same transcription factor should contain in their intergenic regions motifs that are statistically overrepresented as compared to their occurrences in unrelated sequences. these methodologies have proven to be useful in many applications. however, usually their performance rapidly drops as the signal to noise ratio in the data set decreases. this drop in performance is also evident in an assessment study of different computational de novo motif detection tools, where the number of correct motifs retrieved was very low in sets of noisy data. however, noisy data is mostly the case encountered in sequence sets derived from genome wide expression profiles, such as microarrays. the high noise level in such sequence sets comes as a result of the processing of the microarray data, as well as the nature of the biological processes in the cell itself. for instance, when comparing mrna expression between a wild type and a regulator knock out strain, besides the direct targets of the regulator, indirect targets are also affected in their mrna expression in the knock out. in such mutants the complete regulatory network acting downstream of the mutated regulator is disturbed. lists of genes derived from these experiments contain targets of more than one regulatory protein lowering the relative overrepresentation of a particular motif in order to get over this problem, we have developed an approach that exploits orthology information besides coexpression, to discover de novo motifs. orthology information is introduced by phylogenetic footprinting which is based on the assumption that among phylogenetically related species, the regulating sequences in the upstream regions of orthologous genes are selectively conserved by evolution. phylogenetic footprinting has been used for the detection of motifs with relative success. in these approaches, however, the orthology information is only used within a set of orthologous intergenic regions to create motif models. recently, a number of algorithms were developed that permit for the mutual comparison of the motif models derived from different sets of orthologous intergenic regions, followed by the clustering of the conserved regions that share the same regulatory motif. in one approach, jensen et al. applied phylogenetic footprinting using gibbs sampling and then grouped the conserved regions using a bayesian clustering algorithm. a similar way of clustering motif models derived from phylogenetic footprinting was developed by qin et al. and van nimwegen et al.. another approach is developed by wang and stormo, where conserved regulatory regions were detected using wconsensus and where the regions sharing the same regulatory motif were clustered by gradually merging motif models of different orthologous sets. in their recent paper, wang and stormo used a different clustering approach; they would first align the models and consequently cluster them according to their alignment scores. our methodology is a combination of gibbs sampling-based phylogenetic footprinting, with two-step clustering. for phylogenetic footprinting, we developed a new algorithm called blocksampler, which is an extension of the gibbs sampling-based motifsampler, optimized towards phylogenetic footprinting. for the alignment of the different motif models returned from blocksampler, we developed a second algorithm called blockaligner, which aligns matrices describing conserved regions using a smith-waterman approach. the methodology based on these two new algorithms is capable of detecting motifs with weak overrepresentation in a set of coregulated genes. by applying our procedure on gene lists derived from real genome wide expression studies, we show its ability to function effectively in noisy data. in this context, the use of orthology information compensates for a lower degree of motif overrepresentation we also compared its performance on a test data set, with that of two other motif detection tools: one that is exclusively based on coexpression information, alignace, and another that is most similar to our method, phylocon. with this comparison, we demonstrated the robustness of our method over the two mentioned. using our method on two real biological data sets proved its biological applicability.  general strategy several motif detection algorithms have been developed to discover overrepresented motifs in sets of coexpressed genes. however, in a noisy data set the motif might not be sufficiently overrepresented to allow detection by classical tools. to be able to recover motifs in such context, we developed a procedure in which we first use phylogenetic footprinting to delineate all potential motifs in each gene. then, we mutually compare all detected motifs and identify the ones that are shared by at least a few genes in the data set as potential candidates. the complete analysis flow is represented in figure and consists of the following steps: starting from a list of differentially expressed or coexpressed genes, we find the orthologs for each gene in a number of closely related species. the obtained data sets, consisting of the intergenic sequences of orthologous genes, are subjected to phylogenetic footprinting using a gibbs sampling tool called blocksampler. this yields a list of conserved regions for each of the orthologous data sets, corresponding to all potential motifs. searching for the motifs shared by at least some of the original list of coexpressed genes, we mutually align our blocks with blockaligner, and then we construct a multiple alignment using the pairwise alignment scores to delineate further the potential regulatory motifs. as our methodology only detects motifs in genes for which orthologous information is available, some motif hits in the initial gene list might escape detection. to recover these motifs, we use the motif models we obtained from the previous step to screen the intergenic sequences of the remaining genes. here we give an overview of the main tools we used in our flow. algorithmic details can be found in the methods section. blocksampler is used to detect conserved motifs in intergenic sequences of orthologous genes. the algorithm is an adapted version of motifsampler, a motif detection algorithm based on gibbs sampling. due to the specificities of the scoring scheme the algorithm does not require the motif to be present in each single orthologous sequence. although regions conserved in the entire set of sequences will receive a better score, the regions conserved in less than the entire set could still be retained. in contrast to the original implementation, blocksampler allows for scoring each orthologous intergenic sequence in the input data set with its corresponding species specific background model. since it is often the case with closely related species that big stretches around the motifs are conserved, blocksampler was adapted to look for long conserved sequence blocks. blocksampler also allows for the choice of a reference species, usually corresponding to the species of interest for which the experimental data are available. the consequence of using a reference species is that only the conserved regions that include the reference species will be retained. blockaligner performs a local ungapped pairwise alignment, based on dynamic programming for the mutual comparison of sequence blocks, represented as frequency matrices. the scoring scheme of blockaligner is based on the kullback-leiber distance. we used a graph clustering algorithm to group the blocks shared by multiple genes. this algorithm is optimized to cluster sequences based on pairwise alignment scores. evaluation of the analysis flow on test data we applied our analysis flow on test data sets with known motif instances. as shown in figure the data sets are made up of sequences with instances for the motifs phop, lexa, fur and metj, imbedded in a varying number of random sequences. five collections of data sets were created with an increasing number of random sequences, decreasing the signal to noise ratio from 18- 7% for fur and lexa and 11- 4% for metj and phop. for the purpose of evaluating the performance of the methodology, we adopted four measurements: recovery rate, number of false positives, specificity and sensitivity. the former two are a reflection of how well a true motif model is extracted, while the latter two are measurements of the extracted motif's quality. specifically, the recovery rate measures the number of times a motif model corresponding to a true motif is recovered by the algorithm; the number of false positives measures the average number of motif models not corresponding to the true motifs recovered by the algorithm; the sensitivity measures the ratio of true motif instances that contributed to the recovered motif model; the specificity measures the ratio of false motif instances that contributed to the recovered motif model. note that these values were calculated before the last screening step of the algorithm, so that all instances recovered by screening are not included in the calculations. as shown in figure and the supplementary table, our methodology performed well in retrieving the metj, lexa and phop motif models, with relatively low effect of the increasing noise in the data set. only for the fur motif the recovery rate was low, but with high resistance to noise. analysis of the results showed that during the run of the methodology, the fur motif instances were clustered in a single cluster, however, together with degenerated blocks lacking fur instances. the presence of such blocks in the subsequent motif delineation step causes the consensus score of the fur motif model to drop below the selected threshold, explaining why it was not frequently recovered using our stringent criteria. the number of false positives picked up by the algorithm was low, ranging between an average of in the low noise data sets to in the high noise sets. this shows the robustness of the algorithm against noise in the data. regarding the quality of the motif models recovered, figure shows that the algorithm achieved relatively high sensitivity and specificity for fur, metj and lexa, indicating that most true instances contributed to the model, and that few false ones did. in the case of phop, the sensitivity was low due to the fact that the model recovered by our algorithm was the dyad variant, while the two instances of the half site variant did not contribute to the model. importance of the selected species to assess the importance of adding a distantly related species to the analysis, we tested to what extent motif instances in this species contributed to the motif models returned by our algorithm. instances of y. pestis seemed to have contributed to the resulting motif models in more than 90% of the cases for metj and lexa, more than 80% for phop, and more than 75% for the fur motif. on the other hand, adding y. pestis did not decrease the sensitivity of our motif models: motif instances that were only conserved in s. typhimurium and e. coli, but not in y. pestis were also recovered. these results indicate that aligned blocks are not dominated by the sequences of the most related species and that adding a distantly related species helps delineating the true motifs without decreasing the sensitivity, even when motif instances are no longer conserved across all species. comparison with other methodologies we compared the performance of our methodology to that of two other motif detection algorithms: alignace, a gibbs sampling algorithm designed to detect overrepresented motifs in a set of coregulated genes and phylocon, an algorithm that uses information on coexpression and orthology for motif detection. alignace was applied to our test data sets without taking orthology information into account. execution parameters are described in methods. as displayed in figure only two out of the four motifs could be detected by alignace with very low recovery rates. in addition, the performance for those two motifs drops significantly when increasing the number of random genes. while the number of false positives seems to be independent of the noise, it is clearly high ). regarding the quality of the motifs recovered, fur and lexa, the sensitivity was always high, however, at the expense of a lower specificity. no values for sensitivity and specificity were calculated for phop and metj as these motifs were not detected. our methodology clearly outperformed alignace in three aspects: the number of true motifs recovered, the quality of the motifs and the robustness against noise. this result is expected as alignace uses one source of information i.e. genes from one species, while our methodology depends on two sources i.e. single species genes and their orthologs. in the case of phylocon, it also failed to recover metj and phop. although it was previously reported that it is possible to detect the metj motif in a dataset containing only metj intergenic regions, phylocon clearly failed to do so in the noisy context of our study. for lexa, phylocon recovered the motif at a rate comparable to that of our algorithm, and only marginally affected by the increasing noise in the data. phylocon performed well in retrieving the fur motif, but with a recovery rate slightly sensitive to noise. calculating the false positive discovery rate for phylocon illustrates that this algorithm is not sensitive to low signal to noise ratios. however, the absolute number of false positives is higher than that in the case of our methodology. regarding the quality of the motif models, the fur motif model retrieved by phylocon seemingly outperforms our retrieved model both in sensitivity and specificity with hardly any effect for the noise in the data set. for the lexa motif, an optimal specificity was obtained but with mediocre sensitivity, indicating that the motif model, although frequently recovered, is often based on just two or three lexa instances. it is important to emphasize that all the values obtained for the performance assessment of phylocon are biased to its favor in this case. one needs to note that in all the occasions when phylocon did not converge to a known motif, we retrieved the motif model from a cycle premature of convergence. thus, slightly better sensitivities and recovery rates of phylocon over our methodology need to be interpreted in the light of this fact. again, our methodology proved to be more robust to noise than similarly based algorithms as seen in its ability to recover all the true motif models in the data set with very few false positives. evaluation of the analysis flow on expression data besides the test data sets, we applied our methodology on two data sets derived from genome wide expression studies. a first data set consisted of a list of differentially expressed genes between a constitutive and a null pmra mutant of s. typhimurium. the pmrab two-component regulatory system is part of a multi-component feedback loop that acts as a major virulence regulator in s. typhimurium. the system itself is responsive to fe3+ and mild acid and senses mg2+ indirectly by communicating with the mg2+ sensitive phopq system via pmrd. applying our analysis flow on the intergenic sequences of these coexpressed genes resulted in the detection of two potential motifs. the first motif which was derived from the motif instances of the known pmra regulated genes udg, yfbe, yibd and yjdb, corresponded to the consensus of the biologically validated pmra motif. the motif logo is shown in figure a screening the intergenic regions of the remaining differentially expressed genes from the input set with this motif model, resulted in the detection of six additional potential pmra targets. two of these six genes did not contain an ortholog in e. coli or y. pestis, and in the four remaining genes the pmra motif was not conserved in the orthologs of e. coli or y. pestis, explaining the reason these motif instances could not be recovered initially unless by screening. the regulation of eight of these reported ten genes by pmrab is supported by evidence from previous studies. seven of these genes – ais, yjdb, yfbe, ugd, yibd, ybjg and stm – are known members of the pmrab regulon that were confirmed in different experiments. the last gene, yijp, was also discovered in an in silico screening of this same microarray data by tamayo et al.. we also report two new potential pmra targets, ygiw and yegh, that were not recovered by tamayo et al. this could be due to the more stringent threshold they used when defining differentially expressed genes, than ours. in addition to the well known pmra motif, we predicted yet an uncharacterized motif aaggaana) which was based on conserved instances present in tufa, yiht and stm. screening the remaining differentially expressed genes with the motif model corresponding to this motif resulted in the discovery of motif instances in two additional genes. no similarity between this motif and any of the motifs in the existing databases could be found. the second data set was derived from the study of salmon et al.. e. coli and related species respond to oxygen depletion by switching to anaerobic respiration. this transition is mainly controlled by the global regulator fnr. salmon et al. performed genome wide expression profiling experiments to identify genes differentially expressed in response to oxygen and controlled by fnr. applying our methodology to differentially expressed genes derived from their study resulted in the detection of a motif model corresponding to the well known fnr motif. the model was based on conserved instances found in known fnr regulated genes narx, nirb, ndh and cyda. the instances present in three differentially expressed genes, marked as fnr regulated in regulondb did not contribute to our fnr motif model. it seems like the degree of conservation of the motif among the respective orthologs of these genes was too low to be detected by our analysis flow. however, these genes could be retrieved in the screening step. discussion if we want to be able to get a complete view on the transcriptional network of an organism, revealing all regulatory motifs remains one of the main challenges. despite the fact that several motif detection algorithms have been developed and optimized, detection of regulatory motifs with low overrepresentation is still difficult using the common motif detection tools. therefore we developed a tool that is able to retrieve regulatory motifs planted in a noisy environment i.e. only a very small subset of submitted intergenic regions contains the motif. in a first step of our method, large conserved regulatory regions are identified in a set of orthologous intergenic regions. after aligning all these conserved blocks with each other, blocks containing a shared regulatory motif are clustered. in a final step, screening of all input intergenic regions permits for the detection of those target genes where the motif was not conserved in its orthologs. to test its reliability, we applied our methodology on a "golden standard" consisting of a set of randomly selected, non-related genes among which known targets of the fur, metj, lexa and phop regulons were hidden. although these known targets contained previously described motif instances for each of these regulators, their statistical overrepresentation in this test set was low ). when applying our methodology we found that for out of the hidden motifs the recovery rate was above 90% even in the presence of a high amount of noisy genes. for the fur motif it was slightly lower because of the lower degree of conservation of the motif model. notwithstanding this high recovery rate, the number of false positive motifs remained low. the achieved quality of the retrieved motif models, reflected by the motif model sensitivity and specificity depends on the characteristics of the motifs; well conserved, non-dyad motifs such as the lexa and metj motifs are seemingly easy to retrieve and have a high quality; dyad motifs, although having high specificity, their sensitivity was lower than in the case of non-dyad motifs, especially for the phop dyad. in the case of the phop motif, the low sensitivity is due to the fact that it also occurs as a single half site. the score of the alignment of the single half site with the dyad falls below the thresholds we used and therefore these single sites could not be recovered by our methodology. to assess the influence of taking into account orthology information in addition to information from coexpression, we applied our methodology to a combined data set of orthologous and coexpressed genes and compared its results to those obtained by applying alignace, which is a motif detection tool based on gibbs sampling, to the coexpression data only. our methodology clearly outperformed alignace in recovering the true motifs in the data set. in addition, the performance of alignace was seriously influenced by increasing noise in the data, in contrast to what is observed with our methodology. these results indicate that by the incorporation of orthology information, the retrieval of motifs with weak overrepresentation becomes possible. in addition to the above mentioned advantage of using the combined sources of information of coexpression and orthology, an extra value can be deduced. when using phylogenetic footprinting alone on orthologous gene sets of closely related species sharing a large part of the regulatory mechanism, long conserved blocks are detected rather than small distinct motifs. because this complicates the delineation of specific motifs, the sequential use of blocksampler and blockaligner allows for an improved delineation of individual regulatory motifs from those long conserved regions across orthologs. we also compared our methodology to phylocon, as it has a similar strategy as ours. phylocon identifies conserved regulatory regions in sets of orthologs based on the wconsensus program. subsequently, these profiles are merged between different sets of orthologs using a greedy algorithm, in order to detect a common regulatory motif. phylocon was originally developed to detect motifs in a set of coexpressed genes, containing only one motif. the test sets used in the original paper usually contain a single motif per data set. as was noted by the authors, phylocon would perform better on less conserved motifs. indeed, our results show that phylocon had a better performance in retrieving the more degenerated fur motif than the well conserved lexa, metj and phop motifs. despite this, the overall recovery rate was lower than that of our methodology in noisy data sets containing more than one motif. the metj and phop motifs were not recovered at all. although the authors stated that their methodology can retrieve regulatory regions present in only a small set of genes, in our experience phylocon fails to retrieve such motifs in a noisy context. in addition, as phylocon proceeds cycle per cycle, where in each cycle a new motif instance is added to the motif model, the authors suggest that the motif model building process be stopped before convergence in order to detect more motifs in a single dataset. however, they do not provide a clear stop criteria or heuristics to retrieve the optimal model. in order not to bias our results towards a sub-optimal stop criterion, we checked at each cycle whether a motif model was found that matched our test data set. if found during at least one cycle, the motif was considered "recovered". note that this approach is feasible when one knows which motif to look for, but not in the case when a novel motif is searched for. this approach led to the bias of the assessment results to the favor of phylocon, as seen in the higher recovery rate, sensitivity and specificity acquired for phylocon over our method. as a final proof of concept, we also applied our methodology to two gene sets derived from genome wide expression profiling experiments. firstly, out of differentially expressed genes between constitutive and null pmra mutants of s. typhimurium, we could retrieve the expected pmra motif model, and predict the presence of two new putative pmra targets, ygiw and yegh. we also predicted a yet uncharacterized motif of the consensus aaggaana that was based on conserved instances in the genes tufa, yiht and stm in a second test, using a list of fnr regulated genes, we could retrieve the fnr motif model based on genes containing a clear fnr regulatory motif.  conclusively, we have developed an approach that can reliably identify multiple regulatory motifs lacking a high degree of overrepresentation in a set of coexpressed genes by exploiting the advantages of using both coexpression and phylogenetic information. through comparing our methodology to two other motif detection programs, we show the robustness of our implementation. as a proof of concept, analysis of genome wide expression data with our methodology successfully retrieves the present regulatory motifs. 
we applied our methodology to a compiled test data set containing known regulatory motifs and to two biological data sets derived from genome wide expression studies. several motif detection algorithms have been developed to discover overrepresented motifs in sets of coexpressed genes. comparing our results with two other motif detection algorithms points out the robustness of our algorithm. by executing four consecutive steps of 1) identifying conserved regions in orthologous intergenic regions, 2) aligning these conserved regions, 3) clustering the conserved regions containing similar regulatory regions followed by extraction of the regulatory motifs and 4) screening the input intergenic sequences with detected regulatory motif models, our methodology proves to be a powerful tool for detecting regulatory motifs when a low signal to noise ratio is present in the input data set. we developed an approach that can reliably identify multiple regulatory motifs lacking a high degree of overrepresentation in a set of coexpressed genes by exploiting the advantages of using both coexpression and phylogenetic information. then we mutually compare all detected motifs and identify the ones that are shared by at least a few genes in the data set as potential candidates. to still recover motifs which are not significantly enriched but still present, we developed a procedure in which we use phylogenetic footprinting to first delineate all potential motifs in each gene.
 several motif detection algorithms have been developed to discover overrepresented motifs in sets of coexpressed genes. however, in a noisy gene list, the number of genes containing the motif versus the number lacking the motif might not be sufficiently high to allow detection by classical motif detection tools. to still recover motifs which are not significantly enriched but still present, we developed a procedure in which we use phylogenetic footprinting to first delineate all potential motifs in each gene. then we mutually compare all detected motifs and identify the ones that are shared by at least a few genes in the data set as potential candidates.  we applied our methodology to a compiled test data set containing known regulatory motifs and to two biological data sets derived from genome wide expression studies. by executing four consecutive steps of 1) identifying conserved regions in orthologous intergenic regions, 2) aligning these conserved regions, 3) clustering the conserved regions containing similar regulatory regions followed by extraction of the regulatory motifs and 4) screening the input intergenic sequences with detected regulatory motif models, our methodology proves to be a powerful tool for detecting regulatory motifs when a low signal to noise ratio is present in the input data set. comparing our results with two other motif detection algorithms points out the robustness of our algorithm.  we developed an approach that can reliably identify multiple regulatory motifs lacking a high degree of overrepresentation in a set of coexpressed genes by exploiting the advantages of using both coexpression and phylogenetic information. 