集中講義（東京大学）「化学システム工学特論第３」 バイオインフォマティクス的手法による 化合物の性質予測（３） 配列アライメント 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

内容 配列アライメントとは？ ペアワイズ・アライメント 配列検索の実用プログラム マルチプル・アライメント 配列モチーフ 大域アライメント 局所アライメント アフィンギャップコスト 配列検索の実用プログラム マルチプル・アライメント SPスコア 多次元DP 実用的アライメント法 配列モチーフ

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

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

スコア行列の導出 基本的には頻度の比の対数をスコアとする BLOSUM行列 既存のスコア行列を用いて多くの配列のアライメントを求め、ギャップ無しの領域（ブロック）を集める 残基がL％以上一致しているものを同一クラスタに集める 同じクラスタ内で残基aが残基bにアラインされる頻度Aabを計算 qa=∑b Aab / ∑cd Acd, pab=Aab / ∑cd Acd　を求め、　　　ｓ（a,b)=log(pab/qaqb) としたのち、スケーリングし近傍の整数値に丸める

ペアワイズ・アライメント 配列が２個の場合でも可能なアラインメントの個数は指数オーダー しかし、スコア最大となるアライメント（最適アライメント）は動的計画法により、O(mn)時間で計算可能（m,n:入力配列の長さ）

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

動的計画法による大域アライメント(1) (Needleman-Wunschアルゴリズム) 入力文字列から格子状グラフを構成 アライメントと左上から右下へのパスが一対一対応 最長経路＝最適アライメント

動的計画法による大域アライメント(2) DP (動的計画法)による 最長経路(スコア)の計算 ⇒ O(mn)時間 行列からの経路の復元は、 F(m,n)からmaxで＝となっている F(i,j)を逆にたどることに行う （トレースバック）

動的計画法による大域アライメント(3)

局所アライメント(1) (Smith-Watermanアルゴリズム) 配列の一部のみ共通部分があることが多い 　　⇒共通部分のみのアライメント x1x2 … xm, y1y2 … yn を入力とする時、スコアが最大となる部分列ペア xixi+1 … xk, 　yjyj+1 … yh を計算 例えば、HEAWGEH　と　GAWED　の場合、 　　　　　　　　A W G E 　　　　　　　　A W －E 　　というアライメントを計算 大域アライメントを繰り返すとO(m3n3)時間 ⇒Smith-WatermanアルゴリズムならO(mn)時間

局所アライメント(2) 動的計画法 の式 （最大のF(i,j)から トレースバック）

局所アライメント(3) 局所アライメントの正当性の証明（下図） 局所アライメントの定義：x1x2 … xm, y1y2 … yn を入力とする時、スコアが最大となる部分列ペア xixi+1 … xk, yjyj+1 … yh を計算

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

配列検索の実用プログラム(1) O(mn):mは数百だが、nは数ＧＢにもなる ⇒実用的アルゴリズムの開発 　⇒実用的アルゴリズムの開発 FASTA:短い配列（アミノ酸の場合、1,2文字、DNAの場合、4-6文字）の完全一致をもとに対角線を検索し、さらにそれを両側に伸長し、最後にＤＰを利用。 BLAST:固定長（アミノ酸では3, DNAでは11）の全ての類似単語のリストを生成し、ある閾値以上の単語ペアを探し、それをもとに両側に伸長させる。ギャップは入らない。伸長の際に統計的有意性を利用。

配列検索の実用プログラム(2)

配列検索の実用プログラム(3) SSEARCH: 局所アラインメント（Smith-Watermanアルゴリズム）をそのまま実行 PSI-BLAST: ギャップを扱えるように拡張したBLASTを繰り返し実行。「BLASTで見つかった配列からプロファイルを作り、それをもとに検索」という作業を繰り返す。

マルチプルアライメント：意味 ３本以上の配列が与えられた時、全ての配列の長さが同じになるようにギャップを挿入 進化的、構造的に相同な残基（塩基）ができるだけ同じカラムに並ぶようにする 通常はスコアを用いて、最適化問題として定式化 理想的なアライメント 同一残基から派生した残基が同一カラムに並ぶ 構造的に重なり合う残基が同一カラムに並ぶ ⇒構造的に重なり合わない場所を無理に重ね合わせるのは、あまり意味がない

マルチプルアライメント：定式化 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＜ｌ s(mik,mil) （mik = i列, k行目の文字）

SP(Sum of Pairs)スコア S(mi)=∑k＜ｌ s(mik,mil) 問題点 mik = i列, k行目の文字 確率的な正当性が無い 同一カラムに a,b,c が並んだ場合、log(pabc/qaqbqc) とすべきだが、SPスコアでは　 log(pab/qaqb)+ log(pbc/qbqc)+ log(pac/qaqc)

多次元DPによる マルチプルアライメント N個の配列に対するマルチプルアライメント 例：N=3 N次元DPによりO(2NnN)時間（各配列の長さはO(n)を仮定） 例：N=3

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

実用的マルチプルアライメント法 ヒューリスティックアルゴリズムの開発 プログレッシブアライメント 逐次改善法 N次元DPは（N=4ですら） 　　　非実用的 一般にはNP困難 プログレッシブアライメント 近隣結合法などを用いて　案内木を作る 類似度が高い節点から低い節点へという順番で、配列対配列、配列対プロファイル、プロファイル対プロファイルのアラインメントを順次計算 逐次改善法 「配列を一本取り除いては、アラインメントしなおす」を繰り返す

プログレッシブアライメント

プロファイル-プロファイル・アライメント 各列を１文字のように扱うことにより、DPにより計算

逐次改善法 「配列を一本取り除いては、アラインメントしなおす」を繰り返す

配列モチーフ 似た性質を持つタンパク質配列などが持つ共通文字列パターン ロイシンジッパー（DNA結合） ATP/GTP結合部位 　配列モチーフ 似た性質を持つタンパク質配列などが持つ共通文字列パターン ロイシンジッパー（DNA結合） L-x(6)-L-x(6)-L-x(6)-L ATP/GTP結合部位 [AG]-x(4)-G-K-[ST] Cys-His Zinc Finger（DNA結合） C-x(2,4)-C-x(3)-[LIVMFYWC]-x(8)-H-x(3,5)-H

講義のまとめ（配列アライメントI） 動的計画法によるペアワイズアライメント マルチプルアライメント 配列モチーフ 参考文献 大域アライメント 局所アライメント(Smith-Watermanアルゴリズム) アフィンギャップコストを用いたアライメント マルチプルアライメント 多次元DP プログレッシブアライメント 配列モチーフ 参考文献 阿久津、浅井、矢田訳：バイオインフォマティクス –確率モデルによる遺伝子配列解析、医学出版、2001