# Smith-Waterman Pairwise Local Alignment Algorithm

I have written a R code for Smith-Waterman (SW) algorithm.

I wanted to check the results of my code with online examples. In all cases -except one- I found the same alignment. So there is this one example -let's say example A*- for which I found a quite different alignment result: in the example they give three equivally good alignments whereas I found only one that corresponds to no none of those three alignments (we have the same score, though).

I am now trying to understand whether example A is wrong or if my code is not working properly.

Therefore, I have two requests:

• Does anyone have a dataset of the result of SW used on two sequences? I could then compare these results with the output of my code.
• Does anyone have whatever way to compute SW algorithm? Then, I could give that person the example A, which could then try this example A, and give me the output.

This would be very helpful if someone could help, I have already spent so much time on my code, without finding anything that could explain those different outputs.

Thank you!

• Example A: Sequence A = "TGCTCTGT" and Sequence B = "TACTATCAT"

There are many implementations of the Smith-Waterman algorithm. However, they are not all guaranteed to give the same output because although it's an optimal local alignment algorithm, it still depends on the chosen scoring scheme (i.e. substitution matrix and gap penalties).

With this in mind, you could try EMBOSS Water online: https://www.ebi.ac.uk/Tools/psa/emboss_water/

Or in Biopython, the Align.PairwiseAligner() (which uses SW by default when aligner.mode is set to local): https://biopython.org/DIST/docs/api/Bio.Align.PairwiseAligner-class.html

In R, you can use pairwise Alignment in Biostrings.

## Nucleotide global, local, and overlap alignments
library(Biostrings)
s1 <- DNAString("ACTTCACCAGCTCCCTGGCGGTAAGTTGAT")
s2 <- DNAString("GTTTCACTACTTCCTTTCGGGTAAGTAAAT")
# needleman
pairwiseAlignment(s1,s2,type="global")
# smith-waterman
pairwiseAlignment(s1,s2,type="local")


I am not very sure how to implement it from scratch. If you face more problems with this example, I can have a go at it.

• are there faster methods to do this than the Biostrings implementation in R? Using R, are there hash or FFT methods?
– Vass
Sep 5, 2020 at 17:59
• it's not related to this question (which does smith-waterman) maybe you can try rdrr.io/rforge/NameNeedle/man/needles.html Sep 5, 2020 at 19:22