<p>Python solution:<br>
e&lt;=2 will allow up to 2 insertions, 2 deletions, or 2 SNPs in any 2 combinations</p>

<pre><code>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)
</code></pre>

<p>GGGAGGG<br>
GGGAAGGG<br>
TTTATTT<br>
TTTAATTT<br>
GGGG  </p>

<p>Can also include a wildcard</p>

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

<p>GGGAAAAAGGG<br>
GGGAAAAATGG<br>
GGGAAAAATTG</p>

CC BY-SA 4.0
2019-12-07T05:03:07.470Z
Agreed on the approach, it can be solved with an outer loop forcing s floating wildcard [AGTC] or [A-Z]  across the regex search term
M__
CC BY-SA 4.0
2020-01-08T14:51:55.327Z
Thanks for the solution.
The problem is, it is unadequately slow -- e.g. matching whole uniprot with that is very slow. 

Also, I am not aware of it's computational complexity for python regex fuzzy matching -- are you aware of its description?
marinegor
CC BY-SA 4.0
2019-12-06T14:50:35.203Z
2019-12-06T14:50:35.203Z
Stuber
<p><em>Note: this question was also asked on <a href="https://www.biostars.org/p/409111/#409142" rel="nofollow noreferrer">biostars</a></em></p>

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

<p>For example, I want to know, which proteins in my fasta file to match<code>ADNG..C.G</code> regexp (which represents <code>ADNGCG</code> 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: <code>ADNG..C.D</code>, <code>ADNG..D.G</code>, <code>MDNG..C.G</code>, etc are all good. Running all possible variants through <code>grep</code> is possible, but exponentially long for longer patterns (I usually have <code>15-20</code> letters in pattern, and scan <code>~10e6-7</code> sequences).</p>

<p>I am aware of the tool <code>agrep</code> (<a href="https://en.wikipedia.org/wiki/Agrep" rel="nofollow noreferrer">docs</a>. 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 <a href="https://github.com/Wikinaut/agrep" rel="nofollow noreferrer">here</a> and could not get it work). Also, it's not designed for proteins specifically.</p>

<p>I am also aware of <a href="https://prosite.expasy.org/scanprosite/" rel="nofollow noreferrer">ScanProsite</a> and <a href="https://www.bioinformatics.org/sms2/protein_pattern.html" rel="nofollow noreferrer">Protein Pattern Find</a> services. The first one is not error-prone, the second one is seems to be a web interface for <code>grep</code>.</p>

CC BY-SA 4.0
2019-11-22T02:22:04.560Z
As correctly mentioned on biostars, where I cross-posted it, I should add cross reference to that topic: https://www.biostars.org/p/409111/#409142
marinegor
CC BY-SA 4.0
2019-11-22T05:24:12.060Z
Thanks for the link. I personally have no problem with cross-posting, especially if you're linking to other sites and acknowledging the source of any gained knowledge that's added here.
gringer
CC BY-SA 4.0
2020-09-01T23:46:19.797Z
Have you tried using `blastp` with input containing IUPAC ambiguous bases, and post-filter results to match your criteria? I'm uncertain how ambiguous bases are treated for proteins, as opposed to nucleotide searches, but that might be an avenue to explore.
Alex Reynolds
<proteins><python><blast><software-recommendation>
Is there any tool for fuzzy sequence matching?
# Is there any tool for fuzzy sequence matching?

(Asked by: username_0 on 2019-11-21)

*Note: this question was also asked on [biostars](https://www.biostars.org/p/409111/#409142)*

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 match`ADNG..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](https://en.wikipedia.org/wiki/Agrep). 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](https://github.com/Wikinaut/agrep) and could not get it work). Also, it's not designed for proteins specifically.

I am also aware of [ScanProsite](https://prosite.expasy.org/scanprosite/) and [Protein Pattern Find](https://www.bioinformatics.org/sms2/protein_pattern.html) services. The first one is not error-prone, the second one is seems to be a web interface for `grep`.

**Tags:** proteins, python, blast, software-recommendation
> **Comments:**
> **username_0**: As correctly mentioned on biostars, where I cross-posted it, I should add cross reference to that topic: https://www.biostars.org/p/409111/#409142  
> **username_1**: Thanks for the link. I personally have no problem with cross-posting, especially if you're linking to other sites and acknowledging the source of any gained knowledge that's added here.  
> **username_2**: Have you tried using `blastp` with input containing IUPAC ambiguous bases, and post-filter results to match your criteria? I'm uncertain how ambiguous bases are treated for proteins, as opposed to nucleotide searches, but that might be an avenue to explore.  

---

## 1 answers

### Answer by username_3 on 2019-12-06. Score: 2

Python solution:
e<=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<=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<=2}", sequence):
        print(sequence)

GGGAAAAAGGG
GGGAAAAATGG
GGGAAAAATTG

> **Comments:**
> **username_4**: Agreed on the approach, it can be solved with an outer loop forcing s floating wildcard [AGTC] or [A-Z]  across the regex search term  
> **username_0**: Thanks for the solution. The problem is, it is unadequately slow -- e.g. matching whole uniprot with that is very slow.   Also, I am not aware of it's computational complexity for python regex fuzzy matching -- are you aware of its description?  

---

