w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
Traceback in dynamic programming implementation of Needleman-Wunsch algorithm

As you alluded to with your comment about arrow color, the fundamental problem is that the second horizontal arrow is getting labeled as being a movement in M (black arrow) when it is really a movement in Ic (green arrow). This seems to be happening because the prevMatrix variable indicates the best matrix at (i-1, j-1), (i-1, j) or (i, j-1). This is the matrix in the previous cell from the forward perspective. Since you are doing trace*back* at this point, the cell that you are "coming from" in the trace is really (i, j) - the one that you are currently in. That determines the direction that you are moving in and thus whether you are aligning to a gap or not. Your best option is probably to have a variable that keeps track of the current matrix from loop iteration to loop iteration, and use this to determine what character to append to your alignment string. On each iteration you can update it after determining what cell you're going to next.

I think that making these changes will clarify the problem that you are running into with your re-written traceback_col_sequence function, but preliminarily it looks like you aren't taking into account the information that you have gained by tracing back. You're reusing score_cell(), which looks like it was designed to calculate scores going forward. When you are tracing back, you already know the ending, so you don't want to choose the maximum score for the previous cell. You want to choose the maximum score that could have lead to the location in the matrix that you are currently at. For instance, if you know that the matrix you are in in your traceback is M, then you know you didn't get there by extending a gap, so you shouldn't consider those options.

© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.