配列解析アルゴリズム特論 配列アライメントI 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義内容 講義予定 １１月５日 配列アライメントI（担当：阿久津） １１月１２日 配列アライメントII（担当：山口） Smith-waterman アルゴリズム Hash法を用いた高速検索 Gibbsサンプリング １１月１２日　配列アライメントII（担当：山口） マルチプルアライメント，E-Value PSI-BLAST １１月１９日　QTL解析（担当：中谷） 糖尿病モデル動物等での解析例等を用いた解説 １１月２６日　機械モデルと学習手法（担当：馬見塚） HMM、有限混合モデル、EMアルゴリズムなど １２月３日　文字列照合アルゴリズム（担当：坂内） 文字列照合アルゴリズム、索引構造、最適パターン探索 講義内容

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

スコア行列（置換行列） 残基間（アミノ酸文字間）の類似性を表す行列 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 (動的計画法)による 最長経路(スコア)の計算 行列からの経路の復元は、 F(m,n)からmaxで＝となっている F(i,j)を逆にたどることに行う （トレースバック）

局所アライメント(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アルゴリズムとの組み合わせが広く利用されている

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

ギャップコストと計算時間の関係 ギャップコストが凸の時： O(n 2α(n))時間 ただし、α(n)は 　　アッカーマン関数の逆関数（実用的には定数と同じ）

ペアワイズ・アライメントの計算量に 関するその他の結果 線形領域アライメント スコア計算だけなら簡単 トレースバックが難しい しかし、分割統治法によりO(n)領域が可能(右図) O(n2)時間の改善は可能か？ 　　⇒O(n2/logn)が可能 s(xi,yj)が疎(O(n)程度)な場合(Sparse DP) ⇒O(n logn)程度で可能

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

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

BLAT(The Blast-Like Alignment Tool) [Genome Res. 12:656] データベース配列のインデックスをメモリ上に配置⇒高速化 ただし、前処理が必要

BLATの確率解析：１ヒット完全一致 以下の二つを解析 記号の定義 (I) 相同領域を見逃さない確率 (II) 相同でない領域のワードがヒットする個数の期待値 記号の定義 K: ワード長(5-20程度) M: 相同領域中の塩基の一致率(>90%) H: 相同領域の長さ(50-200) G: データベース配列(ゲノム配列)の長さ(3Gbase) Q: 質問配列の長さ A: 塩基の種類(4)

BLATの確率解析：１ヒット近似一致 各ワード内で１文字までのミスマッチを許す 解析法は基本的に１ヒット完全一致の場合と同じ 計算時間が難点 (I) 相同領域を見逃さない確率 (II) 相同でない領域のワードがヒットする個数の期待値 解析法は基本的に１ヒット完全一致の場合と同じ MK、(1/A)K　を右図のように置き換える 計算時間が難点

BLATの確率解析：Nヒット完全一致 （DNA配列解析：K=11,N=2を利用）

計算式および実データによるBLATの評価

PatternHunter [Bioinformatics, 18:440] BLASTの精度かつMegaBlastの高速性を主張 連続した文字をseedとせず、飛び飛びの文字をseedとする 111010010100110111で1の位置のみを考慮

局所マルチプルアライメント (Local Multiple Alignment) 複数配列と長さLが与えられた時、スコア最大となるように各配列から長さLの部分列を抽出 モチーフ（共通の性質を持つ遺伝子などに共通の部分パターン）抽出などに有用

相対エントロピースコアのもとでの 局所マルチプルアライメント 相対エントロピースコアの定義 fj(a): （モチーフ領域の）j列目におけるaの出現頻度 p(a): aの出現頻度（背景確率） L: モチーフ領域の長さ 実用的アルゴリズム Gibbsサンプリング, EM NP困難

Gibbs サンプリング 各配列xjからランダムに部分配列tjを選ぶ 1個の配列xiをランダムに選ぶ xiの部分列ti’を　　　　 に比例する確率で選ぶ ti をti’ でおきかえる ステップ2-4を十分な回数だけ繰り返す ( ti[j]: 部分列ti のj列目の文字 )

講義のまとめ（配列アライメントI） 動的計画法によるペアワイズアライメント 高速配列検索アルゴリズム 大域アライメント 局所アライメント(Smith-Watermanアルゴリズム) アフィンギャップコストを用いたアライメント 線形領域アライメント 高速配列検索アルゴリズム BLAT と PatternHunter 局所マルチプルアライメント(Gibbsサンプリング)