序列比對是比較基因體學和功能基因體學的計算基石。從演算法設計到統計推論，它貫穿整個生物資訊學的理論體系。
動態規劃的數學形式
Needleman-Wunsch（1970）全域比對的遞迴關係：
F(i,j) = max{ F(i-1,j-1) + s(xi,yj), F(i-1,j) + d, F(i,j-1) + d }
其中 s(xi,yj) 是替代矩陣中的分數，d 是缺口罰分。Smith-Waterman（1981）局部比對增加一個 0 的選項，允許從任何位置重新開始。Gotoh（1982）將仿射缺口罰分引入動態規劃，使用三個矩陣（M, Ix, Iy）將時間複雜度維持在 O(mn)。
替代矩陣的理論基礎
PAM 矩陣（Dayhoff et al., 1978）基於 Markov chain 模型，從高相似度蛋白質對推導 1 PAM（1% 的胺基酸改變）的突變機率矩陣 M，再透過矩陣乘冪 M^n 推算任意演化距離。對數化後得到 log-odds 分數矩陣：S(a,b) = log(q(a,b) / (p(a)·p(b)))，其中 q(a,b) 是配對在真正同源序列中出現的機率，p(a) 和 p(b) 是背景頻率。
BLOSUM 矩陣（Henikoff & Henikoff, 1992）直接從保守蛋白質區塊（blocks）中的觀測頻率計算，不需要外推。BLOSUM62 因其在多數應用中的穩健表現而成為預設標準。兩個系列的關鍵差異：PAM 適合偵測遠距同源，BLOSUM 適合中等至高相似度比對。
統計推論：Karlin-Altschul 理論
Karlin & Altschul（1990）證明了無缺口局部比對的最高分數 S 服從 Gumbel 極值分布：P(S > x) ≈ 1 - exp(-Kmn e^(-λx))，其中 K 和 λ 是由替代矩陣和序列組成決定的統計參數。E-value = Kmn e^(-λS) 給出在隨機序列資料庫中得到同等分數的期望次數。有缺口比對的統計理論尚無封閉解，實務上透過經驗模擬估計參數。
進階演算法
- Banded alignment：限制動態規劃在對角線附近的帶狀區域，降低計算量至 O(kn)（k 為帶寬）
- 四俄羅斯人法（Four Russians Method）：預計算所有可能的小區塊結果，將 O(mn) 改進至 O(mn/log n)
- SIMD 向量化：利用 CPU 的 SSE/AVX 指令平行計算多個格子，Parasail 和 Striped Smith-Waterman 是代表實作
- Hirschberg 演算法：使用分治策略將空間複雜度從 O(mn) 降至 O(min(m,n))，同時維持時間複雜度 O(mn)
序列比對在基因體時代的角色
隨著定序成本驟降和長讀段技術（PacBio HiFi, Oxford Nanopore）成熟，序列比對面臨新挑戰：超長讀段（>10 kb）的比對需要特殊的種子延伸策略（如 minimap2 的 minimizer-based chaining）；基因體層級比對（whole-genome alignment）使用 anchor-based 方法（MUMmer 的 maximal unique matches）避免全動態規劃的計算瓶頸。