The planted (l, d, q)-motif search problem aims at finding all strings of length l that appear in each of at least q input strings out of N with at most d differences.
[T14] S. Tanaka. Improved exact enumerative algorithms for the planted (l, d)-motif finding problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics 11(2), pp. 361-374, 2014. DOI: 10.1109/TCBB.2014.2306842
TraverString
[Note]
There was a bug in instances used in the paper. The mutated letters in occurrences were almost always "A", except when the original letter in the motif was "A" (in this case, the letter was mutated to the next letter of "A"). In other words, about d letters out of l in each occurrence were always "A". The algorithm becomes much faster for amino-acid sequences (|Σ|=20) if the instances are properly generated. Therefore, I strongly recommend not to use these instances, but to use your own instances.