title: Detection of generic spaced motifs using submotif pattern mining.
abstract: BACKGROUND
  Identification of motifs is one of the critical stages in studying the regulatory interactions of genes. Motifs can have complicated patterns. In particular, spaced motifs, an important class of motifs, consist of several short segments separated by spacers of different lengths. Locating spaced motifs is not trivial. Existing motif-finding algorithms are either designed for monad motifs (short contiguous patterns with some mismatches) or have assumptions on the spacer lengths or can only handle at most two segments. An effective motif finder for generic spaced motifs is highly desirable.
  
  
  RESULTS
  This article proposes a novel approach for identifying spaced motifs with any number of spacers of different lengths. We introduce the notion of submotifs to capture the segments in the spaced motif and formulate the motif-finding problem as a frequent submotif mining problem. We provide an algorithm called SPACE to solve the problem. Based on experiments on real biological datasets, synthetic datasets and the motif assessment benchmarks by Tompa et al., we show that our algorithm performs better than existing tools for spaced motifs with improvements in both sensitivity and specificity and for monads, SPACE performs as good as other tools.
  
  
  BACKGROUND
  The source code is available upon request from the authors.
authors.affiliation: Institute for Infocomm Research, Singapore.
authors.forename: Edward
authors.initials: E
authors.lastname: Wijaya
authors.forename: Kanagasabai
authors.initials: K
authors.lastname: Rajaraman
authors.forename: Siu-Ming
authors.initials: SM
authors.lastname: Yiu
authors.forename: Wing-Kin
authors.initials: WK
authors.lastname: Sung
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D001483:Base Sequence; D001665:Binding Sites; D019295:Computational Biology / Q000379:methods*; D015233:Models, Statistical; D010363:Pattern Recognition, Automated; D011485:Protein Binding; D017434:Protein Structure, Tertiary; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA; D014157:Transcription Factors / Q000235:genetics
chemical_list: D014157:Transcription Factors