BACKGROUND: In eukaryotes, transcriptional regulation is usually mediated by 
interactions of multiple transcription factors (TFs) with their respective 
specific cis-regulatory elements (CREs) in the so-called cis-regulatory modules 
(CRMs) in DNA. Although the knowledge of CREs and CRMs in a genome is crucial to 
elucidate gene regulatory networks and understand many important biological 
phenomena, little is known about the CREs and CRMs in most eukaryotic genomes 
due to the difficulty to characterize them by either computational or 
traditional experimental methods. However, the exponentially increasing number 
of TF binding location data produced by the recent wide adaptation of chromatin 
immunoprecipitation coupled with microarray hybridization (ChIP-chip) or 
high-throughput sequencing (ChIP-seq) technologies has provided an unprecedented 
opportunity to identify CRMs and CREs in genomes. Nonetheless, how to 
effectively mine these large volumes of ChIP data to identify CREs and CRMs at 
nucleotide resolution is a highly challenging task.
RESULTS: We have developed a novel graph-theoretic based algorithm DePCRM for 
genome-wide de novo predictions of CREs and CRMs using a large number of ChIP 
datasets. DePCRM predicts CREs and CRMs by identifying overrepresented 
combinatorial CRE motif patterns in multiple ChIP datasets in an effective way. 
When applied to 168 ChIP datasets of 56 TFs from D. melanogaster, DePCRM 
identified 184 and 746 overrepresented CRE motifs and their combinatorial 
patterns, respectively, and predicted a total of 115,932 CRMs in the genome. The 
predictions recover 77.9% of known CRMs in the datasets and 89.3% of known CRMs 
containing at least one predicted CRE. We found that the putative CRMs as well 
as CREs as a whole in a CRM are more conserved than randomly selected sequences.
CONCLUSION: Our results suggest that the CRMs predicted by DePCRM are highly 
likely to be functional. Our algorithm is the first of its kind for de novo 
genome-wide prediction of CREs and CRMs using larger number of transcription 
factor ChIP datasets. The algorithm and predictions will hopefully facilitate 
the elucidation of gene regulatory networks in eukaryotes. All the predicted 
CREs, CRMs, and their target genes are available at 
http://bioinfo.uncc.edu/mniu/pcrms/www/.