BACKGROUND: Low levels of oxygen in tissues, seen in situations such as chronic lung disease, necrotic tumors, and high altitude exposures, initiate a signaling pathway that results in active transcription of genes possessing a hypoxia response element (HRE). The aim of this study was to investigate whether a change in miRNA expression following hypoxia could account for changes in the cellular transcriptome based on currently available miRNA target prediction tools. METHODS: To identify changes induced by hypoxia, we conducted mRNA- and miRNA-array-based experiments in HT29 cells, and performed comparative analysis of the resulting data sets based on multiple target prediction algorithms. To date, few studies have investigated an environmental perturbation for effects on genome-wide miRNA levels, or their consequent influence on mRNA output. RESULTS: Comparison of miRNAs with predicted mRNA targets indicated a lower level of concordance than expected. We did, however, find preliminary evidence of combinatorial regulation of mRNA expression by miRNA. CONCLUSION: Target prediction programs and expression profiling techniques do not yet adequately represent the complexity of miRNA-mediated gene repression, and new methods may be required to better elucidate these pathways. Our data suggest the physiologic impact of miRNAs on cellular transcription results from a multifaceted network of miRNA and mRNA relationships, working together in an interconnected system and in context of hundreds of RNA species. The methods described here for comparative analysis of cellular miRNA and mRNA will be useful for understanding genome wide regulatory responsiveness and refining miRNA predictive algorithms.