SEQanswers

Go Back   SEQanswers > Bioinformatics > Bioinformatics



Similar Threads
Thread Thread Starter Forum Replies Last Post
Open Access, Open Source, and Intellectual Property Policies at US Universities Joann General 0 03-05-2015 05:17 AM
Needleman-Wunsch perl script pony2001mx Bioinformatics 0 07-15-2014 08:03 AM
How to open one gap on reads with bowtie2 ? remimaglione Bioinformatics 2 04-07-2014 03:17 PM
extend sequence mirex Illumina/Solexa 2 08-28-2012 11:59 AM
How do I extend reads? Martiniano Bioinformatics 0 09-15-2011 05:13 AM

Reply
 
Thread Tools
Old 01-15-2020, 10:36 AM   #1
bheida
Junior Member
 
Location: Hannover

Join Date: Sep 2018
Posts: 4
Question 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.
bheida is offline   Reply With Quote
Reply

Tags
algorithm, extension, gap, needleman, wunsch

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off




All times are GMT -8. The time now is 06:15 AM.


Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.
Single Sign On provided by vBSSO