Smith–Waterman algorithm

Smith–Waterman is a dynamic programming algorithm for local alignment. The main difference to the Needleman–Wunsch algorithm is that negative scores are set to zero in the SW algorithm.

$$M_{i,j} = \max\left\{0, M_{i−1,j−1}+S(a_i,b_j), M_{i−1,j}+d, M_{i,j−1}+d\right\}$$

Algorithm

• Two sequences are arranged in a matrix form
• Calculating $M_{i,j}$ for each cell
• Tracing back from the lower-right corner to the upper-left corner

 R code