Conditional regulation of genes plays an important role in the response of organisms to their environment (e.g. disease, drought resistance, susceptibility to pests). Regulatory elements exert control over the increase or decrease of gene expression, making them an important target for future medical and agricultural research. Finding regulatory elements in sequences associated with co-expressed genes is called the Motif Discovery Problem, and is NP-complete.

I will present the framework of our exact algorithm for Motif Discovery, which is expected to run quickly on real-world biological data. The algorithm reduces to repeatedly solving a newly described problem, Motif Estimation. I will present linear-time algorithms for optimally solving the Motif Estimation problem for two special cases of input.

The work described is joint work with John Kececioglu.