DNA配列アラインメントと動的計画法（Needleman-Wunsch法）

Q: DNA配列アラインメントと動的計画法（Needleman-Wunsch法）とは何ですか？

2つの配列 A = a_1 a_2 \dots a_m と B = b_1 b_2 \dots b_n の類似度を最大化するアラインメント問題は、スコア行列 F(i, j)（0 \le i \le m, 0 \le j \le n）に対する動的計画法（Needleman-Wunschアルゴリズム）によって定式化される。 F(0, 0) = 0 F(i, 0) = i \cdot d, \quad F(0, j) = j \cdot d 漸化式： F(i, j) = \max \begin{cases} F(i-1, j-1) + S(a_i, b_j) & \text{(一致または置換)} \\ F(i-1, j) + d & \text{(配列Bにギャップ挿入)} \\ F(i, j-1) + d & \text{(配列Aにギャップ挿入)} \end{cases} ここで S(a_i, b_j) は類似度スコア（一致=+1, 不一致=-1など）、d はギャップペナルティ（負値）である。

Q: DNA配列アラインメントと動的計画法（Needleman-Wunsch法）は社会やプログラミングでどのように使われていますか？

バイオインフォマティクスにおける相同性検索（BLAST）とウイルス変異追跡: 次世代シーケンサー（NGS）が解読した数十億塩基のビッグデータから、既知の遺伝子や疾患変異を検索するエンジンで利用される。完全なDPは計算コストがかかるため、NCBIのBLASTでは短い一致シード（k-mer）をハッシュテーブルで高速検出し、その周辺のみを動的計画法で局所拡張するヒューリスティック手法が採用されている。

生命の暗号（塩基配列）の進化・変異を2次元グリッド上の最適経路問題として解き明かす数理

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 生物のDNAやアミノ酸配列の変異（置換・挿入・欠失）を比較する問題は、組み合わせ爆発を起こすため全探索が不可能である
2: 動的計画法（Needleman-Wunsch法）を用いることで、 $O(2^{m+n})$ の爆発的計算量を $O(mn)$ の多項式時間へと劇的に圧縮できる
3: BLASTや最新の新型コロナ・インフルエンザウイルスの系統樹追跡、がんゲノムの遺伝子変異特定はすべてこの数理が基盤となっている

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

生物のDNAやアミノ酸配列の変異（置換・挿入・欠失）を比較する問題は、組み合わせ爆発を起こすため全探索が不可能である

身につく武器・思考力

動的計画法（Needleman-Wunsch法）を用いることで、$O(2^{m+n})$ の爆発的計算量を $O(mn)$ の多項式時間へと劇的に圧縮できる

実社会・ITでの活躍現場

•バイオインフォマティクスにおける相同性検索（BLAST）とウイルス変異追跡
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

2つのDNA配列テキストボックスに好きな塩基（A, T, G, C）を入力してみよう。下のDPスコアマトリクスが瞬時に再計算され、黄色のハイライトで「右下から左上への最短・最高スコア経路（トレースバック）」が浮かび上がる。上のアライメント結果で、縦棒（|）で一致、ハイフン（-）でギャップ（変異の挿入・欠失）が綺麗に整列される様子を確認できる。

配列1（基準DNAシーケンス）:

配列2（比較対象シーケンス）:

プリセット例:

最適グローバルアラインメント（トレースバック結果）

配列1: G-ATTACA

| | |·|·

配列2: GCA-TGCU

最適アライメントスコア

Match=+1, Mismatch=-1, Gap=-1

動的計画法（DPスコアマトリクス）黄色ハイライト = 最適経路（トレースバック）

	ε	G	C	A	T	G	C	U
ε	0	-1	-2	-3	-4	-5	-6	-7
G	-1	1	0	-1	-2	-3	-4	-5
A	-2	0	0	1	0	-1	-2	-3
T	-3	-1	-1	0	2	1	0	-1
T	-4	-2	-2	-1	1	1	0	-1
A	-5	-3	-3	-1	0	0	0	-1
C	-6	-4	-2	-2	-1	-1	1	0
A	-7	-5	-3	-1	-2	-2	0	0

各セル $(i, j)$ は「左上からの斜め（置換）」「上からの移動（削除）」「左からの移動（挿入）」の最大値を取って決定

直感チェック！ミニクイズ

長さ100塩基の2つのDNA配列をギャップを入れて比較する場合、可能なアラインメントの総数は約どのくらいになるか？

Layer 2 — 定義・受験・証明

定義

2つの配列 $A = a_1 a_2 \dots a_m$ と $B = b_1 b_2 \dots b_n$ の類似度を最大化するアラインメント問題は、スコア行列 $F(i, j)$ （ $0 \le i \le m, 0 \le j \le n$ ）に対する動的計画法（Needleman-Wunschアルゴリズム）によって定式化される。

F(0, 0) = 0

F(i, 0) = i \cdot d, \quad F(0, j) = j \cdot d

漸化式：

F(i, j) = \max \begin{cases} F(i-1, j-1) + S(a_i, b_j) & \text{(一致または置換)} \\ F(i-1, j) + d & \text{(配列Bにギャップ挿入)} \\ F(i, j-1) + d & \text{(配列Aにギャップ挿入)} \end{cases}

ここで $S(a_i, b_j)$ は類似度スコア（一致=+1, 不一致=-1など）、 $d$ はギャップペナルティ（負値）である。

公式・数理モデル

F(i, j) = \max \{ F(i-1, j-1) + S(a_i, b_j), \; F(i-1, j) + d, \; F(i, j-1) + d \}

証明・導出

ベルマンの最適性の原理（Principle of Optimality）による最適解の保証：

全体のアラインメントの末尾の列は、次の3パターンのいずれか1つに必ず分類される。 1. $(a_m, b_n)$ ：両方の末尾文字を対応させる（斜め遷移） 2. $(a_m, -)$ ： $b$ 側にギャップを空ける（垂直遷移） 3. $(-, b_n)$ ： $a$ 側にギャップを空ける（水平遷移）

もし全体のアラインメントが最適であるならば、末尾を取り除いたプレフィックス $a_{1..m-1}$ と $b_{1..n-1}$ のアラインメントもまた、その部分問題における最適解でなければならない（背理法：もしより高いスコアの部分解が存在するなら、末尾を繋げることで全体のスコアをさらに向上できてしまい、初期の仮定に矛盾する）。

この部分構造最適性により、 $(m+1) \times (n+1)$ の格子グラフ上の最長経路問題へと帰着され、計算量は全探索の指数時間 $O(3^{m+n})$ から、テーブルを左上から順に埋める $O(mn)$ の二乗時間へと劇的に削減される。最後に $F(m, n)$ から矢印を逆に辿るトレースバック（Backtracking）を行うことで、大域的最適アラインメントが厳密に復元される。

押さえておきたいポイント

DNA（A, T, G, C）の突然変異は、数理的には「文字列のレーベンシュタイン距離（編集距離）」の拡張重み付きバージョンである
全体を整列するグローバルアラインメント（Needleman-Wunsch）と、部分的に似ている領域を探すローカルアラインメント（Smith-Waterman）がある
タンパク質のアミノ酸配列比較では、変異の起こりやすさを統計的に集計したBLOSUM62やPAM250などのスコア行列が用いられる

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

バイオインフォマティクスにおける相同性検索（BLAST）とウイルス変異追跡

次世代シーケンサー（NGS）が解読した数十億塩基のビッグデータから、既知の遺伝子や疾患変異を検索するエンジンで利用される。完全なDPは計算コストがかかるため、NCBIのBLASTでは短い一致シード（k-mer）をハッシュテーブルで高速検出し、その周辺のみを動的計画法で局所拡張するヒューリスティック手法が採用されている。

1// Needleman-Wunsch グローバルアラインメントの実装
2export function needlemanWunsch(
3  seq1: string,
4  seq2: string,
5  match: number = 1,
6  mismatch: number = -1,
7  gap: number = -1
8) {
9  const m = seq1.length;
10  const n = seq2.length;
11  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
12
13  for (let i = 0; i <= m; i++) dp[i][0] = i * gap;
14  for (let j = 0; j <= n; j++) dp[0][j] = j * gap;
15
16  for (let i = 1; i <= m; i++) {
17    for (let j = 1; j <= n; j++) {
18      const score = seq1[i - 1] === seq2[j - 1] ? match : mismatch;
19      dp[i][j] = Math.max(
20        dp[i - 1][j - 1] + score,
21        dp[i - 1][j] + gap,
22        dp[i][j - 1] + gap
23      );
24    }
25  }
26
27  // トレースバック復元
28  let align1 = "";
29  let align2 = "";
30  let i = m, j = n;
31
32  while (i > 0 || j > 0) {
33    if (i > 0 && j > 0 && dp[i][j] === dp[i - 1][j - 1] + (seq1[i - 1] === seq2[j - 1] ? match : mismatch)) {
34      align1 = seq1[i - 1] + align1;
35      align2 = seq2[j - 1] + align2;
36      i--; j--;
37    } else if (i > 0 && dp[i][j] === dp[i - 1][j] + gap) {
38      align1 = seq1[i - 1] + align1;
39      align2 = "-" + align2;
40      i--;
41    } else {
42      align1 = "-" + align1;
43      align2 = seq2[j - 1] + align2;
44      j--;
45    }
46  }
47
48  return { score: dp[m][n], align1, align2 };
49}