I am trying to compile a code for running Needleman Wunsch algorithm using PHP. I could come up to matrix construction and filling. I don't understand how to write the logic for back tracking so that we can get all (not only one) of the possible optimal alignments from the two sequences.
Does anybody know the logic and may provide me any (pseudo)code if you have from any language?
Korf et al. have an O'reilly book called BLAST that has Needleman-Wunsch in Perl. I was able to find that part of the book with the traceback code here: http://etutorials.org/Misc/blast/Part+II+Theory/Chapter+3.+Sequence+Alignment/3.1+Global+Alignment+Needleman-Wunsch/
Korf et al. have an O'reilly book called BLAST that has Needleman-Wunsch in Perl. I was able to find that part of the book with the traceback code here: http://etutorials.org/Misc/blast/Part+II+Theory/Chapter+3.+Sequence+Alignment/3.1+Global+Alignment+Needleman-Wunsch/
Thanks for the link sir. I have actually read that before. I find two issues in this code, one is when there are both diagonal and left or up arrows from a cell they are considering it only as diagonal, which prevents us from exploring the other possible alignments. The second is that in this way we will get only one alignment, and even that might not be an optimal one because of the first issue. This is what I understand from my knowledge. If there is anything wrong please correct me.
Because of these limitations only, I am working on code which will give all the possible optimal alignments from the given two sequences.
See slide align.ppt at http://www.imtech.res.in/raghava/slides/
Am really happy to get your help Raghava Sir. Have heard a lot about you from the starting of my work in Bioinformatics. Here is the link to the pdf which has what I understood of it from various books and what I teach to my students also sir: http://dl.dropbox.com/u/27959322/Dynamic_Programming_Ravi_Kanth.pdf.
I am looking or the logic to write in a programme sir to get all the possible optimal alignments from the sequences. Thanks a lot again for the help...
In the code if u give "if" in the place of "elsif" , hope it may provide all the alignment..
Thanks for showing that mistake. I have made a comment there at the bottom of that e-tutorials link. If anyone could, please give it a thought. The issue with that code is that it gives us one good alignment which might be the optimal and it only gives one of the best possible alignments....
During the backtracking, the naïve approach gives you the first path you encounter (as in, "this path is possible, let's go down it"). Instead, you must make you backtracking function recursive, such that at each cell, it will spawn a new path, inheriting the known path, for each valid outcome from the cell.
Thanks for putting it in words. I am trying to do the same but unable to get it working so far. Will let you know if there is any progress.
Ravi I would advice you to scan or put this issue at http://biostar.stackexchange.com/ or even at allied "stackexchange" forums.Try...
I could do the trace back step successfully. But need to make a few final changes. Once done with them will create an online tool for sequence alignment. Thanks to all for the opinions, suggestions and advice.
- Badges
- Science topic
- Similar topics
- Bioinformatics
- Bioinformatics and Computational Biology