Motif matching using gapped patterns

Abstract. 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 gener-alized versions of the Position Weight Matrix model to describe tran-scription factor specificities. We present a simple practical algorithm, based on bit-parallelism, that, given a text of length n, runs in time O(n(log σ + gw-spandk-len(P)/we) + occ), where occ is the number of occurrences of the patterns in the text, k-len(P) is the total num-ber of strings in the patterns and 1 ≤ gw-span ≤ w is the maximum number of distinct gap lengths that span a single word of w bits in our encoding. We then show how to improve the time complexity to O(n(log σ + log2 gsize(P)dk-len(P)/we) + occ) in the worst-case, where gsize(P) is the size of the variation range of the gap lengths. Finally, by parallelizing in a different order we obtain O(dn/welen(P)+n+occ) time, where len(P) is the total number of alphabet symbols in the patterns. We also provide experimental results which show that the presented algo-rithms are fast in practice, and preferable if all the strings in the patterns have unit-length.