  We present new algorithms for the problem of multiple string matching of
gapped patterns, where a gapped pattern is a sequence of strings such that
there is a gap of fixed length between each two consecutive strings. The
problem has applications in the discovery of transcription factor binding sites
in DNA sequences when using generalized versions of the Position Weight Matrix
model to describe transcription factor specificities. In these models a motif
can be matched as a set of gapped patterns with unit-length keywords. The
existing algorithms for matching a set of gapped patterns are worst-case
efficient but not practical, or vice versa, in this particular case. The novel
algorithms that we present are based on dynamic programming and
bit-parallelism, and lie in a middle-ground among the existing algorithms. In
fact, their time complexity is close to the best existing bound and, yet, they
are also practical. We also provide experimental results which show that the
presented algorithms are fast in practice, and preferable if all the strings in
the patterns have unit-length.
