Talk:Needleman–Wunsch algorithm

Note that everyone so far has failed to define the variable d in all their formulas. What is this? Also, I just backtracked up an edit distance matrix and the alignments generated definitely seemed fine to me (inserting "-" when you don't move diagonally). Is this formula a generalization of that? It seems like it. Should this be noted and explained in this page or the Levenshtein page? —Preceding unsigned comment added by 65.88.178.10 (talk) 18:17, 17 September 2007 (UTC)

i think there's an error in the formula for the iteration of the algorithm: it currently reads:

Fij = max(Fi − 1,j − 1 + S(Ai − 1,Bj − 1),Fi,j − 1 + d,Fi − 1,j + d)

i think it should read

Fij = max(Fi − 1,j − 1 + S(Ai,Bj),Fi,j − 1 + d,Fi − 1,j + d)

(the suffices in S(A,B) need changing) as i'm new to dynamic programming, i'm not sure about this.

any ideas anyone?

The section following this, starting with 'Basis':

As the algorithm progresses, the Fij will be assigned to be the optimal score for the alignment of the first i characters in A and the first j characters in B. The principle of optimality is then applied as follows.

Does this sequence begin at i=0? or i=1?

"To compute which alignment actually gives this score, you can start from the bottom left cell" - should this not be right?

Huge error with the initialization concept?

If you google search Needleman-Wunsch algorithm you will find one of the top matches is this: http://www.ludwig.edu.au/course/lectures2005/Likic.pdf

This shows that the initialization is based on something other than zeroes. In my solution I implemented this using the (Java) code:

// Initialize the 0,0 element
F[0][0] = 0;

// The top and left sides need to be assigned as if they were dashes
for (int i = 1; i <= A.length(); i++)
{
  F[i][0] = d * i;
}
for (int j = 1; j <= B.length(); j++)
{
  F[0][j] = d * j;
}

(Sorry about probably not following Wiki etiquette, I am a complete newbie here) —The preceding unsigned comment was added by Ravi Luthra (talk • contribs) .

Errors with the algorithm as it is presented here:

1) In the matrix calculation, the loop iterates from 1 to length(A) and length(B) where the sequences start from 0. Therefore, S(Ai,Bj) should be S(Ai-1, Bj-1) since S(Ai,Bj) would return an error.

2) As in the previous post ('huge error...'), the initialization needs to change according to the "Genomic Perl" book.

3) The code in which the alignments are calculated also gives wrong results. I am using the code in "Genomic Perl" book and it works fine.

Illustration ?

This article really needs a visual illustration of what a typical F matrix would contain. Can anyone provide ?