Conclusion
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.
In related follow up work, we have shown how to improve the ILP formulation in the case where there are only a small number of distinct edge weights [47]; while this is not the case with the similarity scores considered here, it comes up in some applications (e.g., when considering scores based on just the total number of exact base-pair or amino acid matches). Further improvements and extensions to the ILP formulation for motif finding may be possible – for example, by incorporating constraints that model cooperative binding of transcription factors by looking for motifs within some distance of one another. While mathematical programming has not traditionally been applied to the motif discovery problem, our work demonstrates that it provides us a powerful alternative to successfully tackle a diverse set of applications.