A first approach to finding common motifs with gaps

Costas S. Iliopoulos, James Mchugh, Pierre Peterlongo, Nadia Pisanti, Wojciech Rytter, Marie France Sagot

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


We present three linear algorithms for as many formulations of the problem of finding motifs with gaps. The three versions of the problem are distinct in that they assume different constraints on the size of the gaps. The outline of the algorithm is always the same, although this is adapted each time to the specific problem, while maintaining a linear time complexity with respect to the input size. The approach we suggest is based on a re-writing of the text that uses a new alphabet made of labels representing words of the original input text. The computational complexity of the algorithm allows the use of it also to find long motifs. The algorithm is in fact general enough that it could be applied to several variants of the problem other than those suggested in this paper.

Original languageEnglish (US)
Pages (from-to)1145-1154
Number of pages10
JournalInternational Journal of Foundations of Computer Science
Issue number6
StatePublished - Dec 2005

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)


  • DNA
  • Gapped Motifs
  • Inference
  • Suffix tree


Dive into the research topics of 'A first approach to finding common motifs with gaps'. Together they form a unique fingerprint.

Cite this