A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Pairwise sequence alignment finds the best way to line up two biological sequences (DNA, RNA, or protein) to identify regions of similarity that may reflect functional, structural, or evolutionary relationships. Global alignment (Needleman-Wunsch) aligns sequences end-to-end, while local alignment (Smith-Waterman) finds the highest-scoring subsequence match. Both use dynamic programming with a scoring matrix for matches/mismatches and penalties for gaps. The resulting alignment reveals conserved residues and informs homology inference.
Manually fill in a small Needleman-Wunsch scoring matrix for two short DNA sequences (6-8 nucleotides). Then repeat with Smith-Waterman, noting how the zero-floor changes the traceback. Compare how different gap penalties change the alignment output.
Comparing two biological sequences is one of the most fundamental operations in bioinformatics. If two sequences from different organisms share significant similarity, they likely descended from a common ancestral sequence — making them homologs. Sequence alignment is the tool that makes this comparison rigorous by finding the arrangement of the two sequences, including gaps, that maximizes similarity according to a defined scoring system.
The Needleman-Wunsch algorithm (1970) performs global alignment: it aligns two sequences from start to finish. The algorithm builds a matrix where each cell represents the best alignment score up to that pair of positions, considering three possibilities at each step — match/mismatch (diagonal move), gap in sequence 1 (move down), or gap in sequence 2 (move right). The scoring uses a substitution matrix (like BLOSUM62 for proteins or a simple match/mismatch score for DNA) and gap penalties. After filling the entire matrix, a traceback from the bottom-right corner recovers the optimal alignment. This is a direct application of dynamic programming: the problem has optimal substructure (the best alignment up to position i,j builds on best alignments at earlier positions) and overlapping subproblems.
Smith-Waterman (1981) modifies this for local alignment by adding one rule: no cell can score below zero. This means the algorithm effectively "resets" when similarity breaks down, allowing it to find the highest-scoring island of similarity within two otherwise dissimilar sequences. The traceback starts from the highest-scoring cell (not the corner) and stops when it hits a zero. Local alignment is essential for finding shared domains in multi-domain proteins or detecting conserved regions between distantly related sequences.
The choice of scoring parameters profoundly affects results. Substitution matrices like BLOSUM62 encode the empirically observed rates at which amino acids replace each other during evolution — a leucine-to-isoleucine change (both hydrophobic, similar size) scores positively, while a glycine-to-tryptophan change (tiny to bulky) scores negatively. Gap penalties are typically affine: a larger cost to open a gap (modeling the rarity of insertion/deletion events) and a smaller cost to extend an existing gap (modeling that indels tend to be contiguous). These parameters are not arbitrary numbers; they encode biological knowledge about how sequences actually diverge.
Both algorithms run in O(nm) time and space for sequences of length n and m, which is exact but can be slow for large-scale searches. This computational cost motivated the development of faster heuristic methods like BLAST, which sacrifice guaranteed optimality for speed by pre-filtering candidate regions before applying full alignment. But understanding Needleman-Wunsch and Smith-Waterman is essential because they define what "optimal alignment" means — every heuristic is measured against them.