Answers.Body: <p>I believe mafft can align degenerate sequences.  From the documentation for version 7 at: <a href="https://mafft.cbrc.jp/alignment/software/anysymbol.html" rel="nofollow noreferrer">https://mafft.cbrc.jp/alignment/software/anysymbol.html</a></p>
  
  <pre><code>Acceptable nucleotide symbols in the default mode:
  a, c, g, t, u
  Ambiguous nucleotides (r, y, w, s, k, m, d, v, h, b; IUPAC-IUB codes) can be used and are scored as:
  score(r,a) = ( score(a,a) + score(g,a) ) / 2 
  score(r,g) = ( score(a,g) + score(g,g) ) / 2 
  score(r,t) = ( score(a,t) + score(g,t) ) / 2 
  score(r,c) = ( score(a,c) + score(g,c) ) / 2 
  ... 
  score(r,y) = ( score(r,t) + score(r,c) ) / 2 
  ... 
  score(r,r) = ( score(a,a) + score(g,g) ) / 2 
  score(y,y) = ( score(c,c) + score(t,t) ) / 2 
  </code></pre>
  
  <p>MAFFT is designed for multiple sequence alignment, so will attempt to find a local alignment of homologous segments (using FFT), and then attempt to make a global alignment between the input sequences.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-11T14:30:09.160Z
Answers.Text: Can you expand your answer to include some support material?
Answers.UserDisplayName: Bioathlete
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-12T01:06:48.820Z
Answers.Text: I thought that a nucleotide blast could do the same. Just wondering if these tools also support querying against variable-width subsequences, or if wrappers around such tools can do this more efficiently in generalized cases. I have worked on parallelized analysis of combinations of substrings, in the meantime. It is brute-force but the scope of the problem seems tractable.
Answers.UserDisplayName: Alex Reynolds
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-12T08:52:14.650Z
Answers.Text: I'm not sure I quite understand your point about variable-width subsequences - as far as I understand, these tools tend to find the longest alignable subsequences they can from the two input sequences, so I guess if you want to test lost of different widths a wrapper would be the way to go.
Answers.UserDisplayName: Jay Moore
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-12T09:58:09.973Z
Answers.Text: @AlexReynolds I don't see why this isn't a 'normal' alignment problem where you could use blast or similar but with relaxed parameters (maybe permissive gap penalties to handle "variable-width" subsequences etc.). Perhaps a little more biological context would help us understand better too
Answers.UserDisplayName: Chris_Rands
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-10T13:40:54.617Z
Answers.LastActivityDate: 2019-08-12T08:48:41.763Z
Answers.LastEditDate: 2019-08-12T08:48:41.763Z
Answers.UserDisplayName: Jay Moore
Body: <p>I have an optimization problem where I have a degenerate nucleotide sequence I want to align against subsets of a reference genome (exons, specifically, to make the problem more tractable). </p>
  
  <p>The sequence itself contains subregions of variable length.</p>
  
  <p>The sequence looks like this, containing degenerate bases:</p>
  
  <pre><code>           L           C           R
  5' - SSS......SSS|NNN.....NNN|WWW......WWW - 3'
  </code></pre>
  
  <p>Per IUPAC notation, <code>S</code> denotes <code>C</code> or <code>G</code>, <code>N</code> denotes any base, and <code>W</code> denotes <code>A</code> or <code>T</code>. </p>
  
  <p>I am marking each block <code>L</code>, <code>C</code>, and <code>R</code> to broadly denote "left", "center", and "right" regions, oriented from 5' to 3' ("forward"-strand oriented).</p>
  
  <p>The widths of the <code>L</code> and <code>R</code> blocks can be from 20 to 25 bases long. The width of the <code>C</code> block can be 14 to 16 bases long.</p>
  
  <p>One programmatic way I could think to do this would be to brute-force a solution, generating all combinations of sequences of varied lengths, <code>blastn</code>-aligning each of such combinations to the sequence for the exon, and then looking for the best alignments among such sequences.</p>
  
  <p>The output would be the scores for regions from sequences that align, to be able to say, from point X to point Y of the genome, a sequence here aligns better than other candidate sequences.</p>
  
  <p>To avoid reinventing tools, and avoid brute-force methods, I'd like to know if there is a tool or even a wrapper around tools, which does this, in case it is already written, or another approach that is more elegant/efficient.</p>
  
Tags: <phylogenetics><blast><sequence><blastn>
Title: Appropriate tool or algorithm for sloppy alignment of degenerate bases
ThreadText: # Appropriate tool or algorithm for sloppy alignment of degenerate bases
  
  (Asked by: username_0 on 2019-08-09)
  
  I have an optimization problem where I have a degenerate nucleotide sequence I want to align against subsets of a reference genome (exons, specifically, to make the problem more tractable).
  
  The sequence itself contains subregions of variable length.
  
  The sequence looks like this, containing degenerate bases:
  
  ```
             L           C           R
  5' - SSS......SSS|NNN.....NNN|WWW......WWW - 3'
  
  ```
  
  Per IUPAC notation, `S` denotes `C` or `G`, `N` denotes any base, and `W` denotes `A` or `T`.
  
  I am marking each block `L`, `C`, and `R` to broadly denote "left", "center", and "right" regions, oriented from 5' to 3' ("forward"-strand oriented).
  
  The widths of the `L` and `R` blocks can be from 20 to 25 bases long. The width of the `C` block can be 14 to 16 bases long.
  
  One programmatic way I could think to do this would be to brute-force a solution, generating all combinations of sequences of varied lengths, `blastn`-aligning each of such combinations to the sequence for the exon, and then looking for the best alignments among such sequences.
  
  The output would be the scores for regions from sequences that align, to be able to say, from point X to point Y of the genome, a sequence here aligns better than other candidate sequences.
  
  To avoid reinventing tools, and avoid brute-force methods, I'd like to know if there is a tool or even a wrapper around tools, which does this, in case it is already written, or another approach that is more elegant/efficient.
  
  **Tags:** phylogenetics, blast, sequence, blastn
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-08-10. Score: 1
  
  I believe mafft can align degenerate sequences. From the documentation for version 7 at: <https://mafft.cbrc.jp/alignment/software/anysymbol.html>
  
  ```
  Acceptable nucleotide symbols in the default mode:
  a, c, g, t, u
  Ambiguous nucleotides (r, y, w, s, k, m, d, v, h, b; IUPAC-IUB codes) can be used and are scored as:
  score(r,a) = ( score(a,a) + score(g,a) ) / 2 
  score(r,g) = ( score(a,g) + score(g,g) ) / 2 
  score(r,t) = ( score(a,t) + score(g,t) ) / 2 
  score(r,c) = ( score(a,c) + score(g,c) ) / 2 
  ... 
  score(r,y) = ( score(r,t) + score(r,c) ) / 2 
  ... 
  score(r,r) = ( score(a,a) + score(g,g) ) / 2 
  score(y,y) = ( score(c,c) + score(t,t) ) / 2 
  
  ```
  
  MAFFT is designed for multiple sequence alignment, so will attempt to find a local alignment of homologous segments (using FFT), and then attempt to make a global alignment between the input sequences.
  
  > **Comments:**
  > **username_2**: Can you expand your answer to include some support material?  
  > **username_0**: I thought that a nucleotide blast could do the same. Just wondering if these tools also support querying against variable-width subsequences, or if wrappers around such tools can do this more efficiently in generalized cases. I have worked on parallelized analysis of combinations of substrings, in the meantime. It is brute-force but the scope of the problem seems tractable.  
  > **username_1**: I'm not sure I quite understand your point about variable-width subsequences - as far as I understand, these tools tend to find the longest alignable subsequences they can from the two input sequences, so I guess if you want to test lost of different widths a wrapper would be the way to go.  
  > **username_3**: @username_0 I don't see why this isn't a 'normal' alignment problem where you could use blast or similar but with relaxed parameters (maybe permissive gap penalties to handle "variable-width" subsequences etc.). Perhaps a little more biological context would help us understand better too  
  
  ---
  
  