Identification of jointly correlated gene sets

Associations between expressions of genes play a key role in deciphering their functions. Correlation score between pairs of genes is often utilized to associate two genes. However, the relationship between genes is often more complex; multiple genes might collaborate to control the transcription of a gene. In this paper, we introduce the problem of searching pairs of genes, which collectively correlate with another gene. This problem is computationally much harder than the classical problem of identifying pairwise gene associations. Exhaustive search is infeasible for transcriptomic datasets also; since for [Formula: see text] genes, there are [Formula: see text] possible gene combinations. Our method builds three filters to avoid computing the association for a large fraction of the gene combinations, which do not produce high correlation. Our experiments on a synthetic dataset and a prostate cancer dataset demonstrate that our method produces accurate results at the transcriptome level in practical time. Moreover, our method identifies biologically novel results which classical pairwise gene association studies are unlikely to discover.