By lliu | Fri, 04/23/2021 - 15:43

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