1. Transcription Factor Binding

Understanding the mechanisms that determine the regulation of gene expression is an important and challenging problem. A fundamental subproblem is to identify DNA-binding sites for unknown reg-ulatory factors, given a collection of genes believed to be coregulated, and given the noncoding DNA sequences near those genes. We present an enu-merative statistical method for identifying good candidates for such transcription factor binding sites. Unlike local search techniques such as Ex-pectation Maximization and Gibbs samplers that may not reach a global optimum, the method pro-posed here is guaranteed to produce the motifs with greatest z-scores. We discuss the results of experiments in which this algorithm was used to locate candidate binding sites in several well stud-ied pathways of S. cerevisiae, as well as gene clus-ters from some of the hybridization microarray ex-periments