情報生命科学特別講義III （5）配列アラインメント 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義予定 第１回: 文字列マッチング 第２回： 文字列データ構造 第３回： たたみ込みとハッシュに基づくマッチング 第１回:　文字列マッチング 第２回：　文字列データ構造 第３回：　たたみ込みとハッシュに基づくマッチング 第４回：　近似文字列マッチング 第５回：　配列アラインメント 第６回：　配列解析 第７回：　進化系統樹推定 第８回：　木構造の比較：順序木 第９回：　木構造の比較：無順序木 第１０回：　文法圧縮 第１１回：　RNA二次構造予測 第１２回：　タンパク質立体構造の予測と比較 第１３回：　固定パラメータアルゴリズムと部分k木 第１４回：　グラフの比較と列挙 第１５回：　まとめ

配列アラインメントとは？

配列検索 バイオインフォマティクスにおける基本原理 配列検索の利用法 配列が似ていれば機能も似ている ただし、例外はある 実験を行い機能未知の配列が見つかった データベース中で類似の配列を検索 機能既知の類似の配列が見つかれば、その配列と似た機能を持つと推定

配列アラインメント バイオインフォマティクスの最重要技術の一つ ２個もしくは３個以上の配列の類似性の判定に利用 文字間の最適な対応関係を求める（最適化問題） 配列長を同じにするように、ギャップ記号（挿入、欠失に対応）を挿入 ２個の配列に対するアラインメント：　　　　ペアワイズ・アラインメント ３個以上の配列に対するアラインメント：　マルチプル・アラインメント

ペアワイズ・アラインメント

… ペアワイズ・アラインメント ２本の配列に対するアラインメント 大域アラインメント： 配列全体にわたるアラインメント 列ごとにスコアが定義され、各列のスコアの和が最大となる最適アラインメントを計算 入力配列 ACGT ATCCT アラインメント … A C G T ー ー A ー C G T A C ー G T ー A T C C T A T C C T A T C C T －6 1 －1 スコア スコアの定義 同じ文字： １ 違う文字： －１ ギャップ： －１

大域アラインメントと格子状グラフ C A G T 入力文字列から格子状グラフを構成 アライメントと左上から右下へのパスが一対一対応 最長経路＝最適アラインメント C A G T -1 1 ー 最適アラインメント 非最適アラインメント

アラインメントの個数 漸化式による解析 組み合わせ的解析 アラインメントの個数＝格子状グラフにおけるパス数 ギャップ文字が現れない列の個数を k とすると アラインメント全体の長さは m+n-k (si,-) という型の列の個数は m-k (-,tj) という型の列の個数は n-k よって、アラインメントの個数は m+n-k 個の要素をk個、m-k個、n-k個に分割する組み合わせの数 Delannoy数として知られている 入力配列： s, t (|s|=m, |t|=n)

動的計画法による最適アラインメントの計算 アラインメントの個数：指数関数のオーダー 動的計画法を用いれば O(mn) 時間 D[i,j] は始点(0,0)から(i,j)までの最適パスの長さ アラインメントの復元（トレースバック） D[m,n] から再帰式で＝となっている頂点を逆にたどる D[i,j] D[i-1,j] D[i-1,j-1] D[i,j-1] -d w(s[i],t[j])

スコア行列 残基間（アミノ酸文字間）の類似性を表す行列 PAM250, BLOSUM45 など

局所アラインメント

局所アラインメント というアラインメントを計算 配列の一部のみ共通部分があることが多い ⇒共通部分のみのアラインメント 問題の定義 　　⇒共通部分のみのアラインメント 例えば、AATGCATE　と　GATCG　の場合、 　　　　　 　　　A T G C 　　　　　 　　　A T － C 　 　というアラインメントを計算 問題の定義 入力： 2個の配列 s, t スコア関数 w(x,y) 出力： Sopt(s[h…k],t[h’…k’]) が最大となる部分文字列の 　　組（s[h…k],t[h’…k’])に対する最適アラインメント 大域アラインメントを繰り返すとO(m3n3)時間 ⇒Smith-WatermanアルゴリズムならO(mn)時間

局所アラインメントに対する動的計画法 大域アラインメントに対する動的計画法を少し修正するだけでOK

局所アラインメント・アルゴリズムの正当性 証明のアイデア 始点と終点を表す２個の頂点を格子状グラフに追加 始点から終点へのパスと局所アラインメントが１対１対応

ギャップコスト

ギャップペナルティ 線形コスト -gd アフィンギャップコスト –d – e(g-1) g： ギャップ長 ｄ： ギャップペナルティ ｄ： ギャップ開始ペナルティ e： ギャップ伸張ペナルティ この図の例では、コスト= -d - 2e よく利用されるペナルティ　(d,e)=(12,2),(11,1)

アフィンギャップコストによるアラインメント 三種類の行列を用いる動的計画法によりO(mn)時間 Smith-Watermanアルゴリズムとの組み合わせが広く利用されている ⇒ Smith-Waterman-Gotoh アルゴリズム

任意ギャップコストによるアラインメント 動的計画法（下式）により、O(n 3 )時間 　　（ただし、m=O(n)とする）

ギャップコストと計算時間の関係 線形： O(n2)時間 アフィン：O(n2)時間 凸： O(n2α(n))時間 任意： O(n3)時間

線形領域アラインメント

線形領域アラインメント スコアの計算だけならO(m+n)領域で簡単に可能 トレースバックが難しい アイデア：　分割統治法を利用

配列検索の実用的アルゴリズム

配列検索の実用的アルゴリズム データベース検索： O(mn): m は数百だが、n は数ＧＢにもなる ⇒実用的アルゴリズムの開発 　⇒実用的アルゴリズムの開発 FASTA: 短い配列の完全一致（アミノ酸の場合、1,2文字、DNAの場合、4-6文字）をもとに対角線を検索し、さらにそれを両側に伸長し、最後にＤＰを利用 BLAST: 固定長（アミノ酸では3, DNAでは11）の全ての類似単語のリストを生成し、ある閾値以上の単語ペアを探し、それをもとに両側に伸長させる。ギャップは入らない。伸長の際に統計的有意性を利用 SSEARCH: 局所アラインメント（Smith-Waterman-Gotohアルゴリズム）をそのまま実行 PSI-BLAST: ギャップを扱えるように拡張したBLASTを繰り返し実行。「BLASTで見つかった配列からプロファイルを作り、それをもとに検索」という作業を繰り返す PatternHunter: 穴あきシードを用いる（連続した文字ではなく飛び飛びの文字の完全一致をもとに検索）

マルチプル・アラインメント

マルチプル・アラインメント：定式化 S(mi) = -∑cia log pia （cia= i列におけるaの出現回数, ３本以上の配列が与えられた時、長さが同じで、かつ、スコアが最適となるように各配列にギャップを挿入したもの スコアづけ　（全体スコアは基本的に各列のスコアの和:∑S(mi)） 最小エントロピースコア S(mi) = -∑cia log pia　　　（cia= i列におけるaの出現回数, pia = i列におけるaの生起確率） SPスコア(Sum-of-Pairs) S(mi)=∑k＜lw(mk[i],ml[i]) 　　　　　　　　　　　　　　　　　　（ mk[i]= アラインメント後のi列, k行目の文字）

多次元DPによるマルチプル・アラインメント N個の配列に対するマルチプル・アラインメント N次元DPによりO(2NnN)時間 （各配列の長さはO(n)を仮定） 例：N=3 一般の N に対しては NP困難 (i,j,k) (i-1,j,k) (i,j-1,k) (i,j-1,k-1)

マルチプル・アラインメントの実用的計算手法 プログレッシブ・アラインメント CLUSTAL-W（広く利用されているソフト）などで採用 逐次改善法との組み合わせが、より有効 逐次改善法 シミュレーテッドアニーリング 遺伝的アルゴリズム HMMによるアラインメント 分枝限定法 １０配列程度なら最適解が計算可能

近似アルゴリズム NP困難問題への対処法 近似アルゴリズム 固定パラメータアルゴリズム 指数時間アルゴリズム（O(an)で底aを小さくする） 平均的に高速なアルゴリズム ヒューリスティックなアルゴリズム 最適解との比率の最悪の場合の上限を理論的に保証 最適解がわからないのにどうやって保証するか？ 最適解の下限を理論的に見積もる（最小化問題の場合） 近似解の上限を理論的に見積もる 「近似解の上限／最適解の下限」が比率になる

近似アルゴリズム アルゴリズム ∑k≠iS(sk,si)が最小となる sk を計算 スコアに三角不等式を仮定し、最小化問題として定義 SPスコアを使用 アイデア： 中心となる配列を定め、それと各配列とのアラインメント結果をまとめる アルゴリズム ∑k≠iS(sk,si)が最小となる sk を計算 S(sk,si)をもとにギャップを適切に挿入し、マルチプルアラインメントA を構成 図中の xi はsi を表す

近似アルゴリズムの解析 定理 A のSPスコア ≦ (2-2/N)・最適解の SPスコア 証明 N・Starのスコア ≦2・最適解のスコア 　 (図2でx1に（=s1）接続しない辺のスコアの合計はスター(N-2)個分以下) 図中の xi はsi を表す

まとめ ペアワイズ・アラインメント マルチプル・アラインメント 補足 動的計画法で O(n2) 時間、線形領域も可能 局所アラインメント、線形ギャップスコアでも同様 マルチプル・アラインメント NP困難だが、距離で定義した場合、2近似が可能 補足 ペアワイズ・アラインメントは O(n2/log n) 時間で可能 [Crochemore et al.: Proc. SODA 2002] 様々なギャップスコアや疎行列の場合の動的計画法についても多くの研究 [Galil, Park: Theoret. Comp. Sci. 1992] マルチプル・アラインメントの近似率は 2-K/N まで改善（K は 任意の定数） [Bafna et al.: Theoret. Comp. Sci. 1997] N に関係なく 2 より良くできるかは研究課題