0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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) $\endgroup$
    – Ram RS
    May 25, 2021 at 19:41
  • 1
    $\begingroup$ 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? $\endgroup$
    – Ram RS
    May 25, 2021 at 19:59

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.