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

Get Basic Applied Bioinformatics now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.