One of the major challenges in the post-genomic era is to determine all DNA-binding transcription factors (TFs) and their regulatory binding sites (motifs) within the genomes. To discover the relationship between the motifs and changes in gene expression, we propose a new algorithm, Co-Miner (Correlation Miner). Correlation rules are generated based on the expression profiles of genes with significant expression change through the time course of gene expression. Thus, we may consider the change in gene expression to be causatively associated with the transcription binding sites in the upstream sequences. In addition, we introduce partition and constraint pushing techniques to improve the performance and demonstrate their effectiveness by our experiments. By applying Co-Miner to a yeast dataset, the relationships between motifs and gene expression revealed by Co-Miner are confirmed in the literature.