- https://ja.wikipedia.org/wiki/%E5%A4%9A%E9%87%8D%E6%95%B4%E5%88%97 ## 概要 Multiple Sequence Alignment（多重配列アラインメント、MSA）とは、3本以上のDNA・RNA・タンパク質配列を並べ、相同性（共通祖先からの由来）や機能的・構造的な対応関係が縦に揃うようにギャップ（`-`）を挿入して整列させる手法。 ゴールは「文字をすべて同じにすること」ではなく、進化の過程で起きた抜け落ち（挿入・欠失＝インデル）や変化（置換）を考慮したうえで、最も尤もらしく並べ、どこが同じでどこが変わったかを浮き彫りにすること。 **例**: 共通祖先から分岐した3配列 ``` 配列1: A T G C C 配列2: A G C C (2文字目のTが欠失) 配列3: A C G C C (2文字目がTからCに変異) ``` 左詰めのままだと配列2のせいで後ろ全体がズレて比較できない。配列2にギャップを挿入すると： ``` 配列1: A T G C C 配列2: A - G C C 配列3: A C G C C ``` 4文字目以降が揃い、「違っている（変異）けれど同じ起源の位置」が分かる。 ## 主な活用分野 - **機能・活性部位の特定**: 生物種を超えて保たれている高保存領域は、酵素の触媒部位などの重要部位である可能性が高い - **分子系統樹の作成**: 配列の一致率・変異パターンから種や遺伝子の分岐順序を推定 - **タンパク質立体構造予測**: AlphaFold などは MSA から共進化（位置Aの変異と隣接位置Bの変異の相関）情報を抽出し、3次元構造予測の中核入力とする ## アルゴリズムと計算量 2配列のペアワイズアラインメントなら動的計画法（[[Needleman-Wunsch]]法）で厳密解を効率よく求められる。しかし配列数 $N$、配列長 $L$ の場合、厳密解の計算量は $O(L^N)$ となり NP困難。そのため近似アルゴリズムが使われる。 | 手法分類 | 特徴 | 代表的なツール | |---|---|---| | 漸進法（Progressive） | 全ペアの類似度からガイドツリーを作り、似た配列から順に束ねる高速な手法 | ClustalW, Clustal Omega | | 反復法（Iterative） | 暫定アラインメントを部分的に解体・再構築してスコアを段階的に改善。精度と速度のバランスが良い | MAFFT, MUSCLE | | プロファイルHMM | 配列ファミリーの特徴を隠れマルコフモデルとして学習し、新規配列を当てはめる | HMMER | 実務では数千〜数万本を高速・高精度に処理できる **MAFFT** や **MUSCLE** が広く使われる。 ## スコアリングの仕組み コンピュータは合計スコアが最大になる並びを探索する最適化問題として解く。 $S_{\text{total}} = \sum (\text{一致・置換スコア}) - \sum (\text{ギャップペナルティ})$ **一致・置換**: DNA/RNAでは単純に一致 $+2$ / 置換 $-1$ のような設定が多い。タンパク質は20種のアミノ酸の化学的性質の近さを反映した置換行列（[[BLOSUM]] や [[PAM]]）でスコアを決める（例: BLOSUM62で保存的置換 L→I は $+2$、非保存的置換 L→D は $-4$）。 **ギャップペナルティ**: ギャップを無制限に許すと不自然な整列になるため減点する。標準はアフィンギャップペナルティ。 $W_k = d + (k-1) \cdot e$ $d$=ギャップ開始ペナルティ（重い）、$e$=伸長ペナルティ（軽い）、$k$=ギャップ長。複製ミスで数文字まとめて抜ける方が、1文字欠失が独立して何度も起きるより現実的なため、開始と伸長を分けて重み付けする。 **例**: 配列A `GATTACA` と配列B `GATCA`（一致+2, 置換-1, 開始-3, 伸長-1）を末尾ギャップで揃えると ``` 配列A: G A T T A C A 配列B: G A T C A - - ``` スコア = $2+2+2-1+2-3-1 = +3$ 点。すべての置換・ギャップの組み合わせを点数化し、合計最大の並びを動的計画法で求める。 **Sum-of-Pairs (SP)**: 3本以上の整列では、各カラムで存在する全2配列ペアのスコアを合計し、それを全カラムで合算したものを目的関数とする。