Confused about gap penalty for global alignment using dynamic programming?

Question

[junghyunjulie]

Hello, I have been struggling to understand about gap penalty. I learned how to use dynamic programming to align two sequences. In class, we use gap penalty as 0 including opening and extension gap.

Now I'm dealing with problem with internal gap penalty of -2 and opening/extension gap penalty of 0. I though all zeros in first column and row are opening and extension gap, but it didn't seems right when I tried to back trace.

So for example if I have a sequence called x (GTATTGA) and sequence y (AGTCCTATGCA), then how do I know where opening and extension gap are? I'm not asking you to solve my problem, but I'm confused about the concept.

Maybe somebody can help me understand clearly about this? I appreciate for your help in advance!

Answer 1

[Rob]

Hi,

Can you clarify a bit more the problem you're trying to solve? When you change the base case of the recurrence (i.e. setting the left-most column or bottom-most row to 0) this implies that you're actually trying to solve a semi-global alignment problem. However, semi-global alignment is still a somewhat ambiguous term, as there are many variants of semi-global alignment. There is the variant where we allow gaps for free before or after one of the strings (where we "fit" a smaller string into a larger one), and there is also the variant where we allow gaps before one string and after the other (where we find the best overlap between a suffix of one string and a prefix of the other). Which of these variants are you trying to solve?

Also, you use the term "opening" and "extension" gap penalties, but it seems like you're asking to solve the problem with a simple gap cost (i.e. all "internal" gaps cost -2, while the other gaps are free). The terms "opening" and "extension" usually refer to an affine gap cost model where there is one value --- the gap open penalty --- for starting a gap, and a different value --- the gap extension penalty --- for extending an existing gap.

To be able to answer your question, we need to clarify the precise problem you're trying to solve first because, for example, solving pairwise alignment with an affine gap penalty uses a different method (requiring 3 matrices) than solving pairwise alignment with a simple gap penalty.