DNA Sequence Alignment Scoring With Extended Gap and Similarity Matrix
Entering edit mode
2.6 years ago

Hey everyone! I am having a little difficulty trying to figure out how to align two sequences in Python using a Dynamic Programming algorithm. I've tried to take a look at the source code for jAligner, but I'm having issues understanding how it works.

Basically the problem is this:

Given two sequences, a scoring matrix given that gives scores between each nucleotide, a start gap penalty, and a continue gap penalty. For example:

   A   G   C   T
A  1  -2  -2  -1
G -2   1  -1  -2
C -2  -1   1  -5
T -1  -2  -2   1

openGap = -3
continueGap = -1

How do we compute the alignment of two sequences A and B (with length N and M) such that the score is maximized?

I've taken a look at This Wikipedia Page, but it doesn't mention anything about a continue/open gap, rather just one single gap score.

programming dynamic aligning needleman-wunsch • 740 views
Entering edit mode
2.6 years ago
Olli • 0

Hello there,

just change the gap score depending on the situation. If a new gap pops up you calculate with gap penalty (or single gap score) -3, if the gap was opened in the previous cell you take -1 instead. At the wiki page you linked the algorithm is quite well explained and I would suggest to look at this first before examine any source code ;)


Login before adding your answer.

Traffic: 1177 users visited in the last hour
Help About
Access RSS

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6