Smith-Waterman Pairwise Local Alignment Algorithm

Question

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"

Answer 1

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

Answer 2

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.