Hi. When there is a match score, mismatch score and gap penalty the problem of aligning sequences can be done using dynamic programming. Is it possible to use gap continuation penalty in aligning two sequences under the dynamic programming method?
See the introductory slides here. I think you understand how to fill the DP matrix. For each cell in the DP matrix, we pick the max of three directions from three adjacent cells: UP, LEFT, DIAGONAL. UP and LEFT give you one gap, DIAGONAL give you match/mismatch.
Now the affine gap penalty makes the calculation more difficult. For each cell, we still pick the max of the three directions. But now since the gap score is not linear anymore (i.e.
Two gaps != 2 x one gap), you'll have to consider all the cells on LEFT, all the cells on UP, rather than just the immediate neighbor.
This also increase the computational complexity from squared to cubic.
If you can read Java code, here is a clear implementation of affine gap scores for the Needleman-Wunsch algorithm (and some other versions too). You can find more material on the author's site. That implementation comes straightforward from explanations in the Biological sequence analysis textbook.
BTW, the computational complexity is still squared (although you have to keep three DP matrices in the memory).