We have described a combined graph-theoretic and mathematical programming framework for the motif finding problem that provides a flexible approach to tackle many important issues in motif finding. We have successfully applied it to a variety of problems, including discovering statistically significant DNA and protein motifs, and have been able to incorporate phylogenetic information in the context of cross-species motif discovery. A major advantage of our approach for motif finding is the ability to find optimal solutions for many practical problems.