This is a test version of Biostars. For the public version, visit https://www.biostars.org.
DNA Sequence Alignment Scoring With Extended Gap and Similarity Matrix

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
• 1,419 views • link
updated by Olli • Olli • written by anonymouspenguin • anonymouspenguin

1 answer

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

• 0 views • link
written by Olli • Olli

Log in to answer this question.

More posts like this