A combinatorial optimization approach for diverse motif finding applications

Elena Zaslavsky, Mona Singh

Research output: Contribution to journalArticle

22 Scopus citations

Abstract

Background: Discovering approximately repeated patterns, or motifs, in biological sequences is an important and widely-studied problem in computational molecular biology. Most frequently, motif finding applications arise when identifying shared regulatory signals within DNA sequences or shared functional and structural elements within protein sequences. Due to the diversity of contexts in which motif finding is applied, several variations of the problem are commonly studied. Results: We introduce a versatile combinatorial optimization framework for motif finding that couples graph pruning techniques with a novel integer linear programming formulation. Our approach is flexible and robust enough to model several variants of the motif finding problem, including those incorporating substitution matrices and phylogenetic distances. Additionally, we give an approach for determining statistical significance of uncovered motifs. In testing on numerous DNA and protein datasets, we demonstrate that our approach typically identifies statistically significant motifs corresponding to either known motifs or other motifs of high conservation. Moreover, in most cases, our approach finds provably optimal solutions to the underlying optimization problem. Conclusion: Our results demonstrate that a combined graph theoretic andmathematical programming approach can be the basis for effective and powerful techniques for diverse motif finding applications.

Original languageEnglish (US)
Article number13
JournalAlgorithms for Molecular Biology
Volume1
Issue number1
DOIs
StatePublished - Aug 17 2006

All Science Journal Classification (ASJC) codes

  • Structural Biology
  • Molecular Biology
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A combinatorial optimization approach for diverse motif finding applications'. Together they form a unique fingerprint.

Cite this