## Abstract

Motif discovery is the problem of finding local patterns or motifs from a set of unlabeled sequences. One common representation of a motif is a Markov model known as a score matrix. Matrix based motif discovery has been extensively studied but no positive results have been known regarding its theoretical hardness. We present the first nontrivial upper bound on the complexity (worst-case computation time) of this problem. Other than linear terms, our bound depends only on the motif width w (which is typically 5-20) and is a dramatic improvement relative to previously known bounds. We prove this bound by relating the motif discovery problem to a search problem over permutations of strings of length w, in which the permutations have a particular property. We give a constructive proof of an upper bound on the number of such permutations. For an alphabet size of a (typically 4) the trivial bound is n! ≈(n/e) ^{n},n = σ^{w}. Our bound is roughly n(σlog _{σ} n)^{n}. We relate this theoretical result to the exact motif discovery program, TsukubaBB, whose algorithm contains ideas which inspired the result. We describe a recent improvement to the TsukubaBB program which can give a speed up of nine or more and use a dataset of REB1 transcription factor binding sites to illustrate that exact methods can indeed be used in some practical situations.

Original language | English |
---|---|

Pages (from-to) | 219-228 |

Number of pages | 10 |

Journal | Lecture Notes in Computer Science |

Volume | 3537 |

Publication status | Published - 2005 Oct 17 |

Event | Ot16th Annual Symposium on Combinatorial Pattern Matching, CPM 2005 - Jeju Island, Korea, Republic of Duration: 2005 Jun 19 → 2005 Jun 22 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)