Talk:Smith–Waterman algorithm

Wrong formula for matrix?

Referring back to the 1981 paper of Smith and Waterman (http://www.cmb.usc.edu/papers/msw_papers/msw-042.pdf, formula (1)), the definition formula for the cells of the matrix H is not the same as in this article. The gap scores do not only depend on the row above and the column to the left; they depend on all rows above and all columns to the left. There are examples where this makes a difference to the final score, so the definition here is not correct.

An example: Reference: AACCCGAGTGGAATGGAATGGAATGGAATGGAATGGAATGGAATGGAATGGAATGGAAAGCAATGGCAAGAATTGGAATGGAAAGGAATC Read: GAATGGAATGGAATGCAATGGAATGGAATCATCCGTAATGGAATGGAAAGCAATGGAATG

Scoring +2 for match, -6 for mismatch, -5 for gap open, -3 for gap extend, the overall score is 66 by Smith-Waterman's algorithm and 62 by the algorithm presented here. — Preceding unsigned comment added by 217.33.180.66 (talk) 13:15, 17 March 2014 (UTC)

WPMED

I am not sure this article falls within the scope of WP:MED. Anyone who agrees, please delete the WPMED tag on this page. --Una Smith (talk) 04:29, 29 December 2007 (UTC) Biology - Yes, Medicine - well, there is very remote connection - but no. Crenshaw (talk) 02:03, 19 January 2010 (UTC)

Pseudocode of Algorithm and Remarks to Code are missing

There is the simple but efficient pseudocode of the algorithm missing. It is tailored to fit to the properties of genes in common genomes. Maybe someone can link the properties of common (for example eucaryotic cell) genes having introns and exons to the properties of Smith-Waterman or pairwise Smith-Waterman pSW --84.157.243.81 (talk) 09:32, 24 July 2008 (UTC)

Eq. -- why the 0?

Shouldn't $H(i,j)=\max {\begin{Bmatrix}0&\\H(i-1,j-1)+\ w(a_{i},b_{j})&{\text{Match/Mismatch}}\\H(i-1,j)+\ w(a_{i},-)&{\text{Deletion}}\\H(i,j-1)+\ w(-,b_{j})&{\text{Insertion}}\end{Bmatrix}},\;1\leq i\leq m,1\leq j\leq n$ be $H(i,j)=\max {\begin{Bmatrix}H(i-1,j-1)+\ w(a_{i},b_{j})&{\text{Match/Mismatch}}\\H(i-1,j)+\ w(a_{i},-)&{\text{Deletion}}\\H(i,j-1)+\ w(-,b_{j})&{\text{Insertion}}\end{Bmatrix}},\;1\leq i\leq m,1\leq j\leq n$

What's that zero doing in the B-matrix? —Preceding unsigned comment added by 129.170.215.143 (talk) 23:38, 18 June 2009 (UTC)

Smith-Waterman is for local alignment, which means that if H(i, j) is 0, then it's best for the alignment to start there. I think the example is really confusing, because it doesn't illustrate this fact, so you get an optimum local alignment that is also a global alignment. 69.218.212.242 (talk) 17:20, 8 August 2009 (UTC)

Performance reports

I find this article similar to post with "me faster" signs. As someone who actually takes part in "competition" of speeding up Smith-Waterman for different architectures I think it's a bit NPOV. (disclaimer: i haven't add mine implementation yet to the article but I intend to do so).

Performance results should be reported not as a single value but a graph with performance plotted against query size and database used. For example Fastflow implementation achieves 35GCUPS for __very__ long queries that are barely if ever used in practice. I think it's a bit misleading.

I guess that I'll rewrite this article and put pefrormance graph for different algorithms. But it would be nice if someone reviewed the article afterwards (coz I'll add my own work on SW too) to eliminate potential NPOV.

Crenshaw (talk) —Preceding undated comment added 22:20, 30 January 2010 (UTC).

Agree. The "754x speedup" is meaningless - compared to what? Ketil (talk) 21:32, 11 December 2011 (UTC)

Example needs to totally be redone

As a commenter above points out, this example is not good. The example in the article currently results in a local alignment which is also a global alignment. As the whole point of Smith-Waterman is to find the best local alignment, the example should find the best alignment of the best matching substring(s) in the 2 strings. I don't have time to fix this right now, but wanted point that out. --Rajah (talk) 03:46, 23 March 2010 (UTC)

Acceleration

It seems to me that "shows considerable promise for both speed of the algorithm and a more accessible programming model" is just marketing with no numbers and no substance.

en-dashes

Please: As you see, and en-dash rather than a hyphen is used in the title of this article, and of course should also be used in the body of the article. I just cleaned up a lot of that. Similarly, "Needleman-Wunsch" is wrong and "Needleman–Wunsch" is right. (Also in ranges of pages, years, etc., e.g.: pp. 305–42. See WP:MOS. Michael Hardy (talk) 17:25, 7 August 2012 (UTC)

Dead reference

The first reference to the paper in PDF seems to be dead, it looks like the university blocked it. There is another copy in here http://www.cmb.usc.edu/papers/msw_papers/msw-042.pdf but I'm not sure if putting that (or for that matter the link to the PDF that was here before) would involve copyright infringement. Can somebody enlighten me about this? Jorgeng87 (talk) 19:21, 13 November 2012 (UTC)