Proximity-based cis-regulatory module detection using constraint programming for itemset mining
Tias Guns, Hong Fei Sun, Siegfried Nijssen, Aminael Sánchez Rodríguez, Luc De Raedt, Kathleen Marchal · Lirias · 2010
cis-regulatory modules (CRMs) are combinations of Transcription Factor Binding Sites involved in the regulation of genes. The detection of CRMs is key in developing a better understanding of gene regulation. Identifying significant combinations of binding sites is a difficult computational problem. Existing techniques use heuristic methods or strong restrictions to make the problem tractable, and are not very extendible. We present an extendible technique for enumerating all potential CRMs using only a biologically well-motivated restriction on the proximity of the binding sites involved. Our method consists of 3 phases: First, the genomic sequences under investigation are screened using an existing library of motif models, namely, position weight matrices. This screening identifies Transcription Factor Binding Site (TFBS) hits. Secondly, we use constraint programming for itemset mining to efficiently enumerate all combinations of TFBS hits that co-occur within a pre-defined distance, while avoiding undesirable redundancies. This results in an exhaustive list of potential CRMs. Lastly, the CRMs are ranked using statistical methods