REGULATORY GENOMIC SEQUENCES A GIBBS SAMPLING ALGORITHM TO DETECT CLUSTERED CIS-ELEMENTS

Motivation: The DNA sequence binding preferences of individual transcription factors are generally not informative enough for detection of their binding sites (cis-elements) in large DNA sequences. However, in higher eukaryotes cis-elements are observed to occur in clusters in the sequence, and multiple transcription factors typically bind them cooperatively to form an enhanceosome. There has been increasing recent interest in computational detection of such clusters (Frith et al., 2001; Berman et al., 2002), but the main bottleneck in these approaches is the lack of knowledge of which cis-elements tend to cluster with one another. Results: We have implemented a novel Gibbs sampling technique to detect unknown cis-elements that cluster with a given sample of known cis-elements of one type. The program was tested on a range of increasingly difficult problem scenarios. In cases where it fails, we dissect which aspect of the technique (objective function or search algorithm) is the cause of failure. When the algorithm is allowed to make several alternative predictions, it succeeds in most test cases. Availability: The program is available from the authors on request