Answers.Body: <p>This question is based on a misunderstanding. The Smith-Waterman algorithm calculates the best <code>local</code> segment. You have to start at the <span class="math-container">$max(H_{i,j})$</span> point and run the traceback as described. It will (most likely) return only a local segment that, however, has the maximum value in terms of alignment score.</p>
  <p>To get a <code>global</code> alignment, another algorithm has to be used. Needleman-Wunsch would be an example.</p>
  <p>The difference between <code>local</code> and <code>global</code> is that a <code>local</code> alignment only alignes a subsequence of the provided sequences whereas a <code>global</code> alignment gives the best alignment of the whole sequences.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-26T09:25:03.057Z
Answers.LastActivityDate: 2021-05-26T09:25:03.057Z
Answers.UserDisplayName: Sim
Body: <p>I am currently trying to understand how the traceback algorithm is supposed to work for the smith-waterman algorithm as my current understanding breaks down in case of a large alignment gap.</p>
  <p>Assume the sequences</p>
  <pre><code>3GA12CA
  GA56CA
  </code></pre>
  <p>The obvious best alignment would be (or some other variation thereof)</p>
  <pre><code>3GA12-CA
  -GA--6CA
  </code></pre>
  <p>However, assuming an affine gap penalty function of <code>x =&gt; x + 2</code> and a binary similarity score (i.e., if equal then 1 else -1) would lead to a scoring matrix</p>
  <pre><code>    3 G A 1 2 C A
    0 0 0 0 0 0 0 0
  G 0 0 1 0 0 0 0 1
  A 0 0 0 2 0 0 0 0
  6 0 0 0 0 0 0 0 0
  C 0 0 0 0 0 0 1 0
  A 0 0 0 1 0 0 0 2
  </code></pre>
  <p>When doing the traceback I would start with the largest value towards the lower right corner of the matrix</p>
  <ol>
  <li>(6,6)</li>
  <li>(5,5)</li>
  <li>Now I do not know how to find the next best alignment (in this example at (3,2)) as neither going up nor going to the left nor going diagonal is going to lead to a score greater 0 meaning I have no next best value to go on.</li>
  </ol>
  <p>How is the traceback function supposed to continue here?</p>
  <p>Additionally, I read that the traceback should start at the highest score in the matrix itself. However, if we would extend the first subsequence match length by one, this would mean we miss the right alignment option completely.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-25T19:41:39.520Z
Comments.Text: Before we get started, remember that mismatches are often preferred over gaps, so the "obvious" best alignment would treat one of the `12` in seq1 as a mismatch and the other as a gap, not introduce gaps in both sequences unless your mismatch penalty >> the gap open penalty (which makes no sense)
Comments.UserDisplayName: Ram RS
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-25T19:59:46.667Z
Comments.Text: I'm still trying to understand your problem statement. Affine gap penalties make expanding gaps less expensive than opening new ones, they do not make gaps cheaper than mismatches. "Gaps" are biological sequence insertions/deletions, and those are serious changes, you do understand that, right?
Comments.UserDisplayName: Ram RS
Tags: <phylogenetics>
Title: Smith-Waterman traceback with large gaps
ThreadText: # Smith-Waterman traceback with large gaps
  
  (Asked by: username_0 on 2021-05-25)
  
  I am currently trying to understand how the traceback algorithm is supposed to work for the smith-waterman algorithm as my current understanding breaks down in case of a large alignment gap.
  
  Assume the sequences
  
  ```
  3GA12CA
  GA56CA
  
  ```
  
  The obvious best alignment would be (or some other variation thereof)
  
  ```
  3GA12-CA
  -GA--6CA
  
  ```
  
  However, assuming an affine gap penalty function of `x => x + 2` and a binary similarity score (i.e., if equal then 1 else -1) would lead to a scoring matrix
  
  ```
      3 G A 1 2 C A
    0 0 0 0 0 0 0 0
  G 0 0 1 0 0 0 0 1
  A 0 0 0 2 0 0 0 0
  6 0 0 0 0 0 0 0 0
  C 0 0 0 0 0 0 1 0
  A 0 0 0 1 0 0 0 2
  
  ```
  
  When doing the traceback I would start with the largest value towards the lower right corner of the matrix
  
  1. (6,6)
  2. (5,5)
  3. Now I do not know how to find the next best alignment (in this example at (3,2)) as neither going up nor going to the left nor going diagonal is going to lead to a score greater 0 meaning I have no next best value to go on.
  
  How is the traceback function supposed to continue here?
  
  Additionally, I read that the traceback should start at the highest score in the matrix itself. However, if we would extend the first subsequence match length by one, this would mean we miss the right alignment option completely.
  
  **Tags:** phylogenetics
  
  > **Comments:**
  > **username_1**: Before we get started, remember that mismatches are often preferred over gaps, so the "obvious" best alignment would treat one of the `12` in seq1 as a mismatch and the other as a gap, not introduce gaps in both sequences unless your mismatch penalty >> the gap open penalty (which makes no sense)  
  > **username_1**: I'm still trying to understand your problem statement. Affine gap penalties make expanding gaps less expensive than opening new ones, they do not make gaps cheaper than mismatches. "Gaps" are biological sequence insertions/deletions, and those are serious changes, you do understand that, right?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-05-26. Score: 1 | Accepted answer
  
  This question is based on a misunderstanding. The Smith-Waterman algorithm calculates the best `local` segment. You have to start at the $max(H\_{i,j})$ point and run the traceback as described. It will (most likely) return only a local segment that, however, has the maximum value in terms of alignment score.
  
  To get a `global` alignment, another algorithm has to be used. Needleman-Wunsch would be an example.
  
  The difference between `local` and `global` is that a `local` alignment only alignes a subsequence of the provided sequences whereas a `global` alignment gives the best alignment of the whole sequences.
  
  
  ---
  
  