Detection of generic spaced motifs using submotif pattern mining.
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.
Wijaya
Edward
E
Institute for Infocomm Research, Singapore.
Rajaraman
Kanagasabai
K
Yiu
Siu-Ming
SM
Sung
Wing-Kin
WK
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
D014157:Transcription Factors