
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Open Access, Open Source, and Intellectual Property Policies at US Universities  Joann  General  0  03052015 05:17 AM 
NeedlemanWunsch perl script  pony2001mx  Bioinformatics  0  07152014 08:03 AM 
How to open one gap on reads with bowtie2 ?  remimaglione  Bioinformatics  2  04072014 03:17 PM 
extend sequence  mirex  Illumina/Solexa  2  08282012 11:59 AM 
How do I extend reads?  Martiniano  Bioinformatics  0  09152011 05:13 AM 

Thread Tools 
01152020, 10:36 AM  #1 
Junior Member
Location: Hannover Join Date: Sep 2018
Posts: 4

Gap open and extend penalties in NeedlemanWunsch algorithm
Hi guys, I made my own implementation of the NeedlemanWunsch 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. 
Tags 
algorithm, extension, gap, needleman, wunsch 
Thread Tools  

