Is there any tool for fuzzy sequence matching? Note: this question was also asked on biostars

are you aware of any tool that is able to perform error-tolerant pattern-matching search on protein FASTA files?

For example, I want to know, which proteins in my fasta file to matchADNG..C.G regexp (which represents ADNGCG pattern). However, I want to be tolerant to matching errors, meaning that I'm good with any protein that differs in any 1 letter in the motif: ADNG..C.D, ADNG..D.G, MDNG..C.G, etc are all good. Running all possible variants through grep is possible, but exponentially long for longer patterns (I usually have 15-20 letters in pattern, and scan ~10e6-7 sequences).

I am aware of the tool agrep (docs. As far as I know, it's not supported anymore, and also does not distinguish letters in which it's allowed to make error. Also, it does not support long enough patterns (with more than 9 errors -- and yes, I tried to recompile it with myself from here and could not get it work). Also, it's not designed for proteins specifically.

I am also aware of ScanProsite and Protein Pattern Find services. The first one is not error-prone, the second one is seems to be a web interface for grep.
Python solution:
e&lt;=2 will allow up to 2 insertions, 2 deletions, or 2 SNPs in any 2 combinations

import regex
seq_list=["GGGAGGG", "GGGAAGGG", "GGGAAAGGG", "TTTATTT", "TTTAATTT", "TTTAAATTT", "GGGG", "GGG"]
for sequence in seq_list:
    if regex.search("(GGGGGG|TTTTTT){e&lt;=2}", sequence):
        print(sequence)


GGGAGGG
GGGAAGGG
TTTATTT
TTTAATTT
GGGG  

Can also include a wildcard

seq_list=["GGGAAAAAGGG", "GGGAAAAATGG", "GGGAAAAATTG", "GGGAAAAATTT"]
for sequence in seq_list:
    if regex.search("(GGG.*GGG|TTTTTT){e&lt;=2}", sequence):
        print(sequence)


GGGAAAAAGGG
GGGAAAAATGG
GGGAAAAATTG