This is a common problem in bioinformatics. There are in general three different approaches to the problem
- Inexact string search via dynamic programming
- Inexact string search via text search
The filtering isn’t strictly speaking solving the problem – rather, it’s eliminating most of those regions in the string which are irrelevant. Still, it’s the most promising area: In modern-day sequencing projects, this is the go-to method, but it only makes sense if you search for lots of small strings, since you first need to create an index for the large string (the “reference”).
Still, a brief overview.
All the methods described in the following are implemented in the SeqAn library for C++. Unfortunately, the code uses some very special idioms to to implement highly efficient algorithms in a generic fashion but it’s still the best reference implementation that I know of.
The first method uses a dynamic programming local alignment algorithm (think Smith-Waterman), with one modification: for each column that we calculate, we stop once we find the second error (in your case; in general, we allow k errors and stop after we find k + 1).
Even though dynamic programming has a prohibitive O(n * m) complexity, this trick (called the “Ukkonen trick”) pushes runtime down to O(n * k) which, in your case, is linear. Combined with an efficient implementation of the dynamic programming table (Myers bit vector algorithm), this was fast enough to assemble reads at Celera during the Human Genome Project. There are some lecture notes which can serve as a basis for the implementation.
Caveat: this is pretty tricky, especially if you want to understand the correctness proof of the bit vector algorithm.
But actually, since you only allow mismatches instead of gaps this is overkill – it’s effectively the same as your method, albeit with a more efficient implementation.
The second approach uses modified exact string search, see cat_baxter’s answer for two excellent implementations. In particular, a modification of the suffix tree version (using a trie with backlinks due to Aho and Corasick) was used in some versions of the sequence search tool BLAST.
The third approach can be split again; I’m going to focus on two variants:
pigeonhole-based search. In your case, that’s incredibly easy: since you only allow one error, you can just split each potential hit location into two; now you know that one of those must match exactly – otherwise there’d be at least two errors in the match.
So you can just move a sliding window over the string and use an exact search algorithm to compare regions of the size m/2 against both halves of your pattern (of length m). This can be done very efficiently if you have an index for the reference string.
Alternatively, you can harness the q-gram lemma which tells you that (in your case), the pattern has t common q-grams with each equal-length match in the reference, where t = m - 2 q + 1. If you choose your q appropriately, you can build a collision-free hash table for all q-grams in the reference, and look up all matching positions in O(1).