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?
Yes, this is possible. For example, the gap extension penalty has been implemented in JAligner and you can check the source code to see how it's done (in the construct function).
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).
Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
version 2.3.6
Iam interested in manualy performing it. On paper. Could you please explain it ?
please look at the linked source code to see how it is done
somebody please help me
Introducing gap has to be more penalized than just extending already existing gap. For example, choosing gap instead of penalty for mismatch is much more important than extending 12 gaps into 13 gaps. Thats why the differentiation is made.