Fundamentals of Bioinformatics - Ogurtsov, A.N. 2013

Methods of Bioinformatic Analysis
Sequence Alignment Algorithms
Local Alignment Algorithm

The Smith-Waterman algorithm is used when it is necessary to find the optimal alignment of subsequences of original sequences x and y, for example, when searching for common Protein domains.

Local alignment is also an effective approach for detecting similarity when comparing highly divergent sequences.

The best local alignment is defined as the alignment of subsequences of x and y with the highest score.

In general, the local alignment algorithm is similar to the Global Alignment Algorithm, but it has two key differences.

The first difference is that to determine the score for each Cell of the dynamic programming matrix, the option of assigning a zero score F(i,j) = 0 is introduced whenever all other choices yield negative values.

Class="center">

If the best alignment at a given step has a negative score, it is better to start a new alignment than to continue the old one. Whenever the optimal score in a matrix cell turns out to be negative, a 0 is entered into The Cell along with a marker indicating a dead end and THE START OF a new alignment. Therefore, negative values never appear in the dynamic programming matrix during local alignment.

Due to The addition of this new "zero" choice, the elements of the top row and left Column in this algorithm are also set to zero, rather than -id and -jd as in global alignment.

As a result, any subsequence can "slide" along another before the alignment begins without incurring gap penalties (deletions) left behind.

The second difference is that the alignment can terminate anywhere in the table, rather than only in the bottom-right corner as in global alignment. Thus, instead of F(n, m), the best score in local alignment can be the maximum value of F(i, j) anywhere in the matrix, and the traceback Procedure must start precisely from that cell. Figure 57 shows an example of finding a local alignment

for the same sequences for which the global alignment was found in Figure 53. In this case, the local alignment turned out to be a subset of the global alignment. However, this is not always true.

Currently, software tools designed for local similarity search employ modified Smith-Waterman algorithms that utilize affine gap penalty Functions.

Figure 57 - Local alignment using the Smith-Waterman method



Last update: 11/08/2026

Editorial and Educational Adaptation: This material has been compiled based on the primary/original source text. The project team performed an editorial review, corrected technical inaccuracies, structured sections, and adapted the content for an educational format.

What was processed:

  • elimination of formatting defects (OCR errors, structural breaks, corrupted characters);
  • editorial organization of content;
  • standardization of terminology in accordance with academic sources;
  • verification of factual statements against the original source text.

All mentions of the author, publication year, and origin of the primary text have been preserved in accordance with the source.