There are proprietary libraries (in C) that do this sort of thing in a couple milliseconds per query string. The basic idea is that you use your dictionary of sequences to construct a finite automaton, which either accepts or rejects your query string. This does require some cleverness to do fuzzy matching, and I'm afraid I don't know enough of the details to help you out there.