Sequence Alignment Algorithms
⭐ Dynamic Programming Core
6 Parameters
Sequence Alignment: Global (Needleman-Wunsch) vs Local (Smith-Waterman)
Comparative matrix of matrix initialization, traceback origin and termination, computational complexity, and biological use cases.
| Feature | Global Alignment (Needleman-Wunsch 1970) | Local Alignment (Smith-Waterman 1981) |
|---|---|---|
| Alignment Objective | Aligns sequences from end-to-end across their entire lengths | Finds the highest-scoring local conserved domain or motif within divergent sequences |
| Matrix Initialization (Row 0 & Col 0) | Penalized: F(i,0) = i · d and F(0,j) = j · d (cumulative gap penalties) | Initialized with zeros: F(i,0) = 0 and F(0,j) = 0 (no terminal gap penalty) |
| Negative Cell Scores Permitted? | Yes (scores can be negative if mismatches and gaps accumulate) | NO (values floored at 0: max(0, match, gap_i, gap_j)) |
| Traceback Start Position | Strictly begins at the bottom-right corner cell: F(M, N) | Begins at the cell containing the ABSOLUTE MAXIMUM score anywhere in matrix |
| Traceback End Position | Strictly terminates at top-left corner cell: F(0, 0) | Terminates as soon as any cell with a score of 0 is encountered |
| Ideal Biological Use Case | Comparing closely related, homologous genes/proteins of equal length | Identifying conserved catalytic domains, zinc fingers, or finding matches in long genomes |
Dynamic Programming Cell & Traceback
Key Point
Algorithm: Needleman-Wunsch (Global)
Zero Floor: No
Traceback Start: F(M,N) corner
Traceback Stop: F(0,0)
Key Point
Algorithm: Smith-Waterman (Local)
Zero Floor: YES (max >= 0)
Traceback Start: Max Matrix Cell
Traceback Stop: First 0 cell
Scoring Matrices & Substitution
⭐ Substitution Matrix Numbering Trap
5 Parameters
Protein Scoring Matrices: PAM vs BLOSUM
Comparative matrix of evolutionary models, numbering logic, training datasets, and target divergence levels.
| Feature | PAM (Point Accepted Mutation; Dayhoff) | BLOSUM (Blocks Substitution Matrix; Henikoff) |
|---|---|---|
| Theoretical Foundation | Evolutionary Markov model based on global alignments of closely related proteins (85% identity) | Empirical frequency counts directly observed in non-gapped local blocks (BLOCKS database) |
| Numbering Convention Rule | HIGHER numbers = MORE DIVERGENT sequences (e.g. PAM250 is for distant homologues) | HIGHER numbers = MORE CLOSELY RELATED sequences (e.g. BLOSUM80 is for close homologues) |
| Extrapolation Method | PAM1 is multiplied by matrix power (e.g. PAM250 = PAM1^250) mathematically | Directly measured from clustered sequences at defined identity percentage thresholds |
| Default Benchmark Matrix | PAM250 (roughly equivalent to BLOSUM45; 20% sequence identity) | BLOSUM62 (default for NCBI BLAST; optimal for ~62% clustered sequences) |
| Best For Distant Homology Detection | PAM250 (or PAM120) | BLOSUM45 (or BLOSUM50) |
Matrix Numbering Inversion Rule
Key Point
Divergence Level: Closely Related
Pam Matrix: PAM1 / PAM30
Blosum Matrix: BLOSUM80 / BLOSUM90
Key Point
Divergence Level: Default Standard
Pam Matrix: PAM120
Blosum Matrix: BLOSUM62 (NCBI Default)
Key Point
Divergence Level: Distant Homologues
Pam Matrix: PAM250
Blosum Matrix: BLOSUM45 / BLOSUM50
