title: RecMotif: a novel fast algorithm for weak motif discovery.
abstract: BACKGROUND
  Weak motif discovery in DNA sequences is an important but unresolved problem in computational biology. Previous algorithms that aimed to solve the problem usually require a large amount of memory or execution time. In this paper, we proposed a fast and memory efficient algorithm, RecMotif, which guarantees to discover all motifs with specific (l, d) settings (where l is the motif length and d is the maximum number of mutations between a motif instance and the true motif).
  
  
  RESULTS
  Comparisons with several recently proposed algorithms have shown that RecMotif is more scalable for handling longer and weaker motifs. For instance, it can solve the open challenge cases such as (40, 14) within 5 hours while the other algorithms compared failed due to either longer execution times or shortage of memory space. For real biological sequences, such as E.coli CRP, RecMotif is able to accurately discover the motif instances with (l, d) as (18, 6) in less than 1 second, which is faster than the other algorithms compared.
  
  
  CONCLUSIONS
  RecMotif is a novel algorithm that requires only a space complexity of O(m²n) (where m is the number of sequences in the data and n is the length of the sequences).
authors.affiliation: School of Computer Engineering, Nanyang Technological University, 639798, Singapore. Sunh0013@e.ntu.edu.sg
authors.forename: He Quan
authors.initials: HQ
authors.lastname: Sun
authors.forename: Malcolm Yoke Hean
authors.initials: MY
authors.lastname: Low
authors.forename: Wen Jing
authors.initials: WJ
authors.lastname: Hsu
authors.forename: Jagath C
authors.initials: JC
authors.lastname: Rajapakse
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D011336:Probability; D017422:Sequence Analysis, DNA / Q000379:methods*