Question: needleman-Wunch implementation with affine gap penalty model
gravatar for Fadel
3.6 years ago by
Fadel20 wrote:

Im trying to implement Neeedleman-Wunch with affine penalty model.

According to Algorithm in Bioinformatic: Practical Introduction (Slides) I have to initialize four tables and back-trace them,

to do back-tracing, another table is initialized and filled up with the help of a maximum function, which returns the maximum value to be added to table V(i,j) plus the associated figure ( \, | or -) to be added to back-tracing table

this approach works with simple queries, but once the the strings become complicated, things go out of control. like the following example:





score = 46

while using EMBOSS-needle


score = 52

My question, is this the right approach to implement NW with affine gap penalty model ?
here is my implementation in C++ Github.

int max(int diagonal,  int vertical, int horizontal, char *figure) {
int  max = 0 ;
if( diagonal > vertical && diagonal > horizontal )
    max = diagonal ;
    *figure = '\\' ;

else if (vertical > horizontal)
    max = vertical ;
    *figure = '|' ;


    max = horizontal ;
    *figure = '-' ;
return  max ;

enter image description here

alignment • 2.5k views
ADD COMMENTlink modified 3.6 years ago • written 3.6 years ago by Fadel20

This is the standard approach (not checking your code though). The difference between your implementation and EMBOSS could be due to the difference in scoring. Did you use the same scoring matrix, gap open and gap extension penalties in both cases ?

ADD REPLYlink written 3.6 years ago by Jean-Karim Heriche21k

yes, I do use DNAFULL scoring matrix and the same values for gap open and gap extension.

ADD REPLYlink modified 3.6 years ago • written 3.6 years ago by Fadel20

So it could be something in your code. Compare it to other implementations e.g. in C, C#, java, perl.

ADD REPLYlink written 3.6 years ago by Jean-Karim Heriche21k

thanks a lot Jean :))

ADD REPLYlink written 3.6 years ago by Fadel20

Hello mfb.bioinfo!

It appears that your post has been cross-posted to another site:

This is typically not recommended as it runs the risk of annoying people in both communities.

ADD REPLYlink written 3.5 years ago by Pierre Lindenbaum126k
Please log in to add an answer.


Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1547 users visited in the last hour