Smith-Waterman traceback with large gaps 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 =&gt; 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.
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.