- The Smith–Waterman algorithm is a fundamental dynamic programming method used for local sequence alignment in bioinformatics. It was introduced by Temple F. Smith and Michael S. Waterman in 1981 to identify the most similar regions within two biological sequences. Unlike global alignment methods, which attempt to align sequences across their entire lengths, the Smith–Waterman algorithm identifies the highest-scoring local regions and does not require the complete sequences to be aligned. It is widely used to compare DNA, RNA, and protein sequences, particularly when the sequences may share similarity in only a portion of their lengths.
- Local sequence alignment is especially important when comparing sequences that contain conserved regions separated by unrelated or highly divergent segments. For example, two proteins may share a conserved functional domain even though their remaining regions have different sequences. Similarly, genes from different organisms may contain conserved coding regions alongside variable segments. A global alignment may be unsuitable in these situations because it attempts to align the entire sequences. The Smith–Waterman algorithm avoids this problem by identifying the region or regions that provide the highest alignment score under a specified scoring system.
- The Smith–Waterman algorithm uses dynamic programming to construct a scoring matrix. It evaluates possible matches, mismatches, and gaps while retaining only alignments with positive cumulative scores. The algorithm calculates the best local alignment ending at each matrix position and records the direction from which the optimal score was obtained. Unlike the Needleman–Wunsch algorithm, which permits cumulative scores to remain negative during matrix construction, Smith–Waterman introduces a zero-score option. This allows an alignment to restart at any position whenever extending an existing alignment would produce a negative score.
- Suppose two sequences are represented as (A) and (B), with lengths (m) and (n), respectively. The algorithm creates a scoring matrix (H) containing (m+1) rows and (n+1) columns. Each matrix position (H(i,j)) represents the highest possible local alignment score involving the prefixes ending at positions (i) and (j). The additional first row and first column are initialized to zero. This initialization allows the algorithm to begin a local alignment at any position in either sequence without imposing a penalty for unaligned leading residues.
- The matrix is filled by evaluating three possible operations at each position. A diagonal movement aligns the current residues from both sequences and adds a match or mismatch score. A vertical movement introduces a gap in one sequence, while a horizontal movement introduces a gap in the other. The algorithm also considers zero, which represents starting a new local alignment at the current position. It selects the largest of these four values.
- The standard Smith–Waterman recurrence with a linear gap penalty is:
[
H(i,j)=\max
\begin{cases}
0\
H(i-1,j-1)+s(A_i,B_j)\
H(i-1,j)+g\
H(i,j-1)+g
\end{cases}
]
- Here, (H(i,j)) is the optimal local alignment score at the current matrix position, (s(A_i,B_j)) is the substitution score for aligning residues (A_i) and (B_j), and (g) is the gap penalty, normally represented by a negative value. The zero term prevents negative-scoring alignment segments from being retained. As a result, the algorithm can identify a high-scoring region even when the sequences contain unrelated regions before or after it.
- The first step is to initialize the scoring matrix. Every cell in the first row and first column is assigned zero. The algorithm then calculates the scores for the remaining cells using the recurrence relation. At each position, it compares the diagonal, vertical, horizontal, and zero alternatives. The highest score is stored in the matrix, and the corresponding traceback direction is recorded. If several alternatives have the same maximum score, multiple optimal traceback paths may exist.
- After the matrix has been completed, the algorithm identifies the highest value anywhere in the matrix. Unlike global alignment, where traceback begins at the bottom-right cell, Smith–Waterman traceback begins at the cell containing the maximum score. This cell represents the endpoint of the highest-scoring local alignment. The algorithm then follows the recorded directions backward. A diagonal movement aligns two residues, while a vertical or horizontal movement introduces a gap in one of the sequences. Traceback continues until a cell containing zero is reached. This point marks the beginning of the selected local alignment. The aligned sequences are then reversed to restore their normal reading order.
- The following example illustrates the basic idea. Consider two DNA sequences:
Sequence 1: GGTTGACTA
Sequence 2: TGTTGAC
- The sequences share a highly similar region, GTTGAC, even though their complete lengths and surrounding regions differ. A local alignment method can identify this shared segment without requiring the unrelated terminal regions to be included in the alignment. The exact alignment and score depend on the match, mismatch, and gap parameters.
- The following Python implementation demonstrates the basic Smith–Waterman algorithm using a linear gap penalty and simple match and mismatch scores.
def smith_waterman(seq1, seq2, match=2, mismatch=-1, gap=-2):
m = len(seq1)
n = len(seq2)
# Create scoring and traceback matrices
score = [[0] * (n + 1) for _ in range(m + 1)]
traceback = [[None] * (n + 1) for _ in range(m + 1)]
max_score = 0
max_position = (0, 0)
# Fill the scoring matrix
for i in range(1, m + 1):
for j in range(1, n + 1):
if seq1[i – 1] == seq2[j – 1]:
substitution_score = match
else:
substitution_score = mismatch
diagonal = (
score[i – 1][j – 1] + substitution_score
)
up = score[i – 1][j] + gap
left = score[i][j – 1] + gap
best_score = max(0, diagonal, up, left)
score[i][j] = best_score
# Record traceback direction
if best_score == 0:
traceback[i][j] = None
elif best_score == diagonal:
traceback[i][j] = “diagonal”
elif best_score == up:
traceback[i][j] = “up”
else:
traceback[i][j] = “left”
# Record the highest-scoring cell
if best_score > max_score:
max_score = best_score
max_position = (i, j)
# Traceback from the highest-scoring cell
i, j = max_position
aligned1 = []
aligned2 = []
while i > 0 and j > 0 and score[i][j] > 0:
direction = traceback[i][j]
if direction == “diagonal”:
aligned1.append(seq1[i – 1])
aligned2.append(seq2[j – 1])
i -= 1
j -= 1
elif direction == “up”:
aligned1.append(seq1[i – 1])
aligned2.append(“-“)
i -= 1
elif direction == “left”:
aligned1.append(“-“)
aligned2.append(seq2[j – 1])
j -= 1
else:
break
aligned1.reverse()
aligned2.reverse()
return (
“”.join(aligned1),
“”.join(aligned2),
max_score
)
# Example sequences
sequence1 = “GGTTGACTA”
sequence2 = “TGTTGAC”
alignment1, alignment2, alignment_score = smith_waterman(
sequence1,
sequence2,
match=2,
mismatch=-1,
gap=-2
)
print(“Sequence 1:”, alignment1)
print(“Sequence 2:”, alignment2)
print(“Alignment score:”, alignment_score)
- This implementation performs matrix initialization, calculates local alignment scores, records traceback directions, and reconstructs one highest-scoring local alignment. It uses a simple linear gap penalty and returns one optimal alignment when ties occur. It does not enumerate all possible optimal alignments. The example is intended to demonstrate the algorithm’s main principles rather than replace optimized alignment software.
- The Smith–Waterman algorithm can also be implemented using Biopython’s PairwiseAligner. This provides a convenient way to perform local alignment with configurable scoring parameters and substitution matrices.
from Bio.Align import PairwiseAligner
sequence1 = “GGTTGACTA”
sequence2 = “TGTTGAC”
aligner = PairwiseAligner()
aligner.mode = “local”
aligner.match_score = 2
aligner.mismatch_score = -1
aligner.open_gap_score = -2
aligner.extend_gap_score = -2
alignments = aligner.align(sequence1, sequence2)
print(“Alignment score:”, alignments.score)
print(alignments[0])
- The local mode instructs the aligner to identify the highest-scoring local region rather than align the entire sequences. Setting the gap-opening and extension scores to the same value represents a linear gap-cost scheme under the usual affine convention. For more realistic biological comparisons, different gap-opening and extension penalties can be used. Protein alignments can also use substitution matrices such as BLOSUM62 or PAM250 instead of simple match and mismatch scores.
- In protein sequence alignment, substitution matrices are particularly important because amino acid substitutions differ in their evolutionary likelihood and biochemical consequences. Matrices such as BLOSUM and PAM assign different scores to amino acid pairs, allowing the algorithm to recognize conservative substitutions. For example, replacing leucine with isoleucine may receive a more favourable score than replacing leucine with a strongly charged amino acid. This improves the ability to detect related proteins even when their sequences are not identical.
- The following example demonstrates local protein alignment using BLOSUM62.
from Bio.Align import PairwiseAligner
from Bio.Align import substitution_matrices
protein1 = “MKTAYIAKQRQISFVKSHFSRQ”
protein2 = “GGTAYIAKQRIISFVKSHF”
aligner = PairwiseAligner()
aligner.mode = “local”
aligner.substitution_matrix = substitution_matrices.load(“BLOSUM62”)
aligner.open_gap_score = -10
aligner.extend_gap_score = -0.5
alignments = aligner.align(protein1, protein2)
print(“Alignment score:”, alignments.score)
print(alignments[0])
- This example uses BLOSUM62 to evaluate amino acid substitutions and affine gap penalties to distinguish gap opening from gap extension. The algorithm identifies the most favourable local protein alignment under these settings. The resulting alignment score depends on the substitution matrix, gap penalties, and sequence composition.
- The original Smith–Waterman algorithm uses a linear gap penalty. It can be extended to support affine gap penalties, which are widely used in modern sequence alignment. An affine gap model distinguishes between the cost of opening a new gap and the cost of extending an existing gap. A commonly used gap-cost expression is:
[
G(k)=g_o+(k-1)g_e
]
- Here, (G(k)) is the cost of a gap of length (k), (g_o) is the gap-opening cost, and (g_e) is the gap-extension cost. Under this convention, a gap of one position receives the opening cost, while each additional position receives the extension cost. The affine extension of Smith–Waterman uses additional dynamic programming states to track alignments ending in gaps in either sequence. This allows the algorithm to model longer insertions and deletions more realistically. Software packages may use different gap-cost conventions, so parameter definitions should be checked when reproducing an alignment.
- The Smith–Waterman algorithm has several important applications in bioinformatics. In protein research, it is used to identify conserved domains, functional motifs, and related regions in proteins that may differ substantially in overall length. It is useful for identifying possible homologous regions between proteins and supporting functional annotation. In DNA and RNA analysis, it can detect conserved sequence segments, compare gene fragments, and identify matching regions within longer genomic sequences. In pathogen genomics, it can help identify similar regions among viral or bacterial sequences. In molecular biology, it can support the comparison of primers, probes, and other short sequences against larger reference sequences, although specialised search and mapping tools may be more suitable for large-scale tasks.
- The algorithm is also an important foundation for understanding sequence similarity search methods. BLAST and other heuristic search tools use related scoring principles to identify high-scoring local alignments efficiently. However, BLAST is not simply the Smith–Waterman algorithm. It uses heuristic methods to reduce computational requirements and may not identify the exact optimal local alignment that exhaustive Smith–Waterman dynamic programming would produce. Smith–Waterman is therefore useful when an exact optimal local alignment is required for a pair of sequences, while heuristic methods are often preferred for searching very large biological databases.
- One of the main advantages of Smith–Waterman is its ability to identify optimal local alignments under a specified scoring model. It is especially valuable when sequences contain conserved regions surrounded by unrelated or highly variable regions. Its dynamic programming approach ensures that the highest-scoring local alignment is identified rather than relying on a greedy selection of matches. It can also accommodate different substitution matrices and gap-penalty schemes, making it applicable to nucleotide and protein comparisons.
- However, the algorithm has computational limitations. For two sequences of lengths (m) and (n), the conventional time complexity is (O(mn)), and storing the complete scoring and traceback matrices requires (O(mn)) memory. This can become expensive when aligning long genomic sequences or searching large databases. Optimized implementations can reduce memory usage or improve computational performance, but exhaustive local alignment remains more demanding than many heuristic search methods.
- Another limitation is that the resulting alignment depends on the scoring parameters. A high match score, severe mismatch penalty, or inappropriate gap penalty may favour alignments that do not reflect the biological relationship of interest. Repetitive regions and low-complexity sequences can also produce high-scoring local matches that are not biologically meaningful. A high alignment score alone does not establish homology, shared function, or evolutionary ancestry. Interpretation should consider sequence coverage, percentage identity, statistical significance, conserved domains, organism information, and other biological evidence.
- It is also important to distinguish the highest-scoring local alignment from every possible local similarity between two sequences. Standard traceback from the single highest-scoring cell produces one optimal local alignment, although multiple alignments may share the same score. Identifying additional distinct local regions requires additional procedures, such as masking an already identified region or using methods designed to report multiple local alignments.
- The Smith–Waterman algorithm is a central method in bioinformatics because it provides a mathematically rigorous approach to local sequence alignment. Its dynamic programming framework identifies the highest-scoring matching regions by evaluating substitutions and gaps while allowing alignments to begin and end at internal positions. It is particularly useful for detecting conserved domains, motifs, and related regions in sequences that differ in length or overall composition. Understanding Smith–Waterman, together with global alignment methods such as Needleman–Wunsch, provides an essential foundation for sequence comparison, protein analysis, database searching, and modern computational biology.