Basic Applied Bioinformatics

CHAPTER 10Smith–Waterman Algorithm (Local Alignment)

CS Mukhopadhyay and RK Choudhary

School of Animal Biotechnology, GADVASU, Ludhiana

10.1 INTRODUCTION

The Smith–Waterman algorithm (Smith and Waterman, 1981) is a dynamic programming tool that is used for local alignment, to compare molecular sequences of any length with an aim to identify the conserved region(s). It is a modified form of the Needleman–Wunsch algorithm, where tracing back is stopped as soon as a score of zero (0) is encountered in the path. The scoring is done by replacing the negative values with zeroes in a cell.

10.2 OBJECTIVE

To align two sequences (nucleotide or amino acid) to find out the local region(s) of similarity, using the Smith–Waterman algorithm.

10.3 PROCEDURE

Two sequences will be utilized for local alignment using the Smith–Waterman algorithm:

• Seq1: CTAGTAG
• Seq2: CAGGTAGTG

The steps are similar to that of global alignment (Needleman–Wunsch algorithm):

1. Define a scoring scheme, as shown above.
2. Initiation of scoring matrix construction: Just like the NW algorithm, here we need to calculate three scores and select the highest when we move to the next cell (horizontally to right, vertically downward and diagonally towards bottom right).
3. Trace‐back step: to find out the local alignment.

In the matrix shown in Figure 10.1, three scores are shown in each cell (vertical, diagonal and horizontal, respectively). The highest numerical value is chosen to calculate the scores for the next cells (hence, ...