Background: Given a set of DNA sequences s1,..., st, the (l, d) motif problem is to find an l-length motif sequence M, not necessary existing in any of the input sequences, such that for each sequence si, 1 ≤ i ≤ t, there is at least one subsequence differing with at most d mismatches from M. Many exact algorithms have been developed to solve the motif finding problem in the last three decades