Simple DNA sequence finder w/ mismatch tolerance
This is a solved problem in bioinformatics and there are specific algorithms depending on your specific use-case:


Do you allow gaps?
How many mismatches do gaps incur?
… etc.


In the general case, this is a global pairwise alignment which is computed by the Needleman–Wunsch algorithm. If you are just interested in the score of the alignment, rather than the complete alignment, this can be simplified by not performing the backtracking.

Now, if you have a threshold and are only interested in finding matches below said threshold, then a more efficient variant employs the Ukkonen trick – unfortunately, references for this are hard to find online, and the print literature is quite expensive. But what it does is essentially break the recurrence in the above-mentioned algorithm once the score exceeds the threshold chosen before (using the insight that the error score can only increase, never decrease in a given column).

But all this is unnecessary if you don’t allow gaps. In that case, the algorithm is as straightforward as walking over both strings at once and looking whether the current positions match.

And this can be expressed in a single line:

def distance(a, b):
    return sum(map(lambda (x, y): 0 if x == y else 1, zip(a, b)))


and:

def distance_less_than(k, a, b):
    return distance(a, b) &lt; k