text: user12311: 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
  
  (6,6)
  (5,5)
  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.
  
  user12311: 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.
  
original_text: 12311: <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>
   12311: <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>
  