Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-07T05:03:07.470Z
Answers.Text: 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
Answers.UserDisplayName: M__
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-08T14:51:55.327Z
Answers.Text: 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?
Answers.UserDisplayName: marinegor
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-06T14:50:35.203Z
Answers.LastActivityDate: 2019-12-06T14:50:35.203Z
Answers.UserDisplayName: Stuber
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-22T02:22:04.560Z
Comments.Text: 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
Comments.UserDisplayName: marinegor
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-22T05:24:12.060Z
Comments.Text: 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.
Comments.UserDisplayName: gringer
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-01T23:46:19.797Z
Comments.Text: 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.
Comments.UserDisplayName: Alex Reynolds
Tags: <proteins><python><blast><software-recommendation>
Title: Is there any tool for fuzzy sequence matching?
ThreadText: # 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?  
  
  ---
  
  