Question: Gap Continuation Penalty With Dynamic Programming ?
2
gravatar for User 5037
7.5 years ago by
User 5037290
User 5037290 wrote:

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?

• 5.0k views
ADD COMMENTlink modified 5.3 years ago by Biostar ♦♦ 20 • written 7.5 years ago by User 5037290
3
gravatar for Michael Kuhn
7.5 years ago by
Michael Kuhn5.0k
EMBL Heidelberg
Michael Kuhn5.0k wrote:

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).

ADD COMMENTlink written 7.5 years ago by Michael Kuhn5.0k

Iam interested in manualy performing it. On paper. Could you please explain it ?

ADD REPLYlink written 7.5 years ago by User 5037290

please look at the linked source code to see how it is done

ADD REPLYlink written 7.5 years ago by Michael Kuhn5.0k

somebody please help me

ADD REPLYlink written 7.5 years ago by User 5037290

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.

ADD REPLYlink written 7.3 years ago by Biomonika (Noolean)3.1k
3
gravatar for Haibao Tang
7.5 years ago by
Haibao Tang3.0k
Mountain View, CA
Haibao Tang3.0k wrote:

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.

ADD COMMENTlink written 7.5 years ago by Haibao Tang3.0k
0
gravatar for Peter Kovac
7.3 years ago by
Peter Kovac60
Bratislava, Slovakia
Peter Kovac60 wrote:

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).

ADD COMMENTlink written 7.3 years ago by Peter Kovac60
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1051 users visited in the last hour