A cost-aggregating integer linear program for motif finding

Carl Kingsford, Elena Zaslavsky, Mona Singh

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


In the motif finding problem one seeks a set of mutually similar substrings within a collection of biological sequences. This is an important and widely-studied problem, as such shared motifs in DNA often correspond to regulatory elements. We study a combinatorial framework where the goal is to find substrings of a given length such that the sum of their pairwise distances is minimized. We describe a novel integer linear program for the problem, which uses the fact that distances between substrings come from a limited set of possibilities allowing for aggregate consideration of sequence position pairs with the same distances. We show how to tighten its linear programming relaxation by adding an exponential set of constraints and give an efficient separation algorithm that can find violated constraints, thereby showing that the tightened linear program can still be solved in polynomial time. We apply our approach to find optimal solutions for the motif finding problem and show that it is effective in practice in uncovering known transcription factor binding sites.

Original languageEnglish (US)
Pages (from-to)326-334
Number of pages9
JournalJournal of Discrete Algorithms
Issue number4
StatePublished - Dec 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Computational biology
  • Integer linear programming
  • Sequence motif finding


Dive into the research topics of 'A cost-aggregating integer linear program for motif finding'. Together they form a unique fingerprint.

Cite this