Tweet
Gap open and extend penalties in Needleman-Wunsch algorithm
Hi guys, I made my own implementation of the Needleman-Wunsch algorithm in Python. This worked pretty well, but then I decided I wanted different penalties for opening a gap and extending a gap, because the algorithm kept opening small gaps in the middle of the alignment.
This is where I started to struggle and I may need some help:
I have two arrays, one for the score and another to keep track of the steps through the array. The second one stores three booleans for the directions (diagonal, up and left) for each position. When I calculate the scores for each position to find the max score, I look at the position before the one I'm at to see if there has been a deletion or insertion as well. If yes I only subtract the gap extension penalty, if not then the gap open penalty.
However this gives me false positive results from time to time.
Consider this example:
At position [7,5] the algorithm can branch off in continuing the gap to [6,5] or take the match to [6,4], however when continuing the algorithm the info, that the highest score came from the continuation of the gap was lost. At the end there are two possible ways through the matrix:
Here I show the two routes, the first number is the score for the next move. The two following numbers are the current coordinates. One of the routes is a false positive, as you can see because when you add up the scores one has the score of 5 and one has a score of 3, but both are viable backtracks through the matrix.
I hope someone can help me sort this out. Thank you.
This is where I started to struggle and I may need some help:
I have two arrays, one for the score and another to keep track of the steps through the array. The second one stores three booleans for the directions (diagonal, up and left) for each position. When I calculate the scores for each position to find the max score, I look at the position before the one I'm at to see if there has been a deletion or insertion as well. If yes I only subtract the gap extension penalty, if not then the gap open penalty.
However this gives me false positive results from time to time.
Consider this example:
At position [7,5] the algorithm can branch off in continuing the gap to [6,5] or take the match to [6,4], however when continuing the algorithm the info, that the highest score came from the continuation of the gap was lost. At the end there are two possible ways through the matrix:
Here I show the two routes, the first number is the score for the next move. The two following numbers are the current coordinates. One of the routes is a false positive, as you can see because when you add up the scores one has the score of 5 and one has a score of 3, but both are viable backtracks through the matrix.
I hope someone can help me sort this out. Thank you.