Question: needleman-Wunch implementation with affine gap penalty model
1
gravatar for Fadel
2.8 years ago by
Fadel10
Malaysia
Fadel10 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:

Target: TGCTAGTATAAACCTTATGGTATCTGCAGCAGAGGTTTCTTTAATCTCTCAATAGTAGATGCTTTGAAAC

Read: TTATCTATAATTTGGTATTGTAATGACAGTTTGTGTTTGGTTTTTTCTTCAGTAT

Alignment:

TGC-TAG-TATAAACCT-TATGGTATCTG-CAGCA-GAGGTTTCTTTAATCTCTCAATAGTAGATGCTTTGAAAC ---TTATCTATAATTTGGTATTGTAA-TGACAGTTTGTGTTTGGTTTTTTCT-TCAGTAT---------------

score = 46

while using EMBOSS-needle

TGCTA-GTATAAACCTTATGGTATCTGCA--GCAGAG-----GTTT-CTTTAATCTCTCAATAGTAGATGCTTTGAAAC --TTATCTATAA----TTTGGTAT-TGTAATG-ACAGTTTGTGTTTGGTTTTTTCT-TCAGTAT---------------

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 = '|' ;


}

else     
{
    max = horizontal ;
    *figure = '-' ;
}
return  max ;
}

enter image description here

alignment • 1.9k views
ADD COMMENTlink modified 2.8 years ago • written 2.8 years ago by Fadel10
1

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 2.8 years ago by Jean-Karim Heriche18k

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

ADD REPLYlink modified 2.8 years ago • written 2.8 years ago by Fadel10
1

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

ADD REPLYlink written 2.8 years ago by Jean-Karim Heriche18k

thanks a lot Jean :))

ADD REPLYlink written 2.8 years ago by Fadel10
1

Hello mfb.bioinfo!

It appears that your post has been cross-posted to another site: http://stackoverflow.com/questions/38831040

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

ADD REPLYlink written 2.8 years ago by Pierre Lindenbaum120k
Please log in to add an answer.

Help
Access

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