配列アラインメント (I): 大域アラインメント http://www.lab.tohou.ac.jp/sci/is/nacher/eaching/bioinformatics/ week.pdf 08/4/0 08/4/0 基本的な考え方 バイオインフォマティクスにはさまざまなアルゴリズムがありますが その多くにおいて基本的な考え方は 配列が類似していれば 機能も類似している というものである 例えば : 機能が未知のヒトのタンパク質のアミノ酸配列が実験によって決定できたとしよう そのタンパク質の機能を計算機を用いて予測したい場合 最初にすべきことは 計算既知の配列からなるデータベースを検索して 類似した配列をみつけることである 08/4/0 3 基本的な考え方 その結果 非常に類似したアミノ酸配列をもつマウスのタンパク質が検出されたとすると ヒトのタンパク質もそのマウスのタンパク質と類似の機能をもつと予測することができる 機能の予測ができれば 的をしぼった実験をおこなうことができ 効率的にその機能を確認することが期待できる 08/4/0 4
重要な問題 配列アラインメント よって 配列の類似性の検出は バイオインフォマティクスにおけるもっとも基本的なかつ重要な問題であるといえる 類似した配列を検索するためには 個の配列の類似性を適切に評価することが必要になる そのための基本となるのが 配列アラインメントである 配列アラインメントとは 複数の配列が入力されたときに文字間の対応関係を計算すること もしくは その計算結果のことである 08/4/0 5 08/4/0 6 個の配列 3 個以上の配列 配列アラインメントは 個の配列に対するものと 3 個以上の配列に対するものとに大きく分けられるが 個の配列に対するペアワイズアラインメント (pairwise alignment) は比較的簡単な動的計画法 (dynamic programming) に基づくアルゴリズムによって効率よく計算することができる ヒューリスティクスや 3 個以上の配列 時々 生物学的に妥当アラインメントの計算や大量の配列データに対する検索のためには ヒューリスティクスや統計的手法が必要である 一方 3 個以上の配列に対するマルチプルアラインメント (multiple alignment) は 一般に NP( 困難 )(NP-Hard) であるため 近似アルゴリズムやヒューリスティクスなアルゴリズムが開発されている 08/4/0 7 08/4/0 8
ヒューリスティクスなアルゴリズム ヒューリスティクスなアルゴリズムとは 理論的保証はないが実験的に有効とされるアルゴリズム 方法 規則などを言う ペアワイズアラインメント : 大域アラインメント この講義では 動的計画法により ペアワイズアラインメントを説明します Σ を文字の集合とする Σは具体的には塩基の集合か アミノ酸の集合ということになる つまり Σ={,,,}, もしくは Σ={,,D,E,F,,H,I,K,L,M,N,P,Q,R,S,,V,W,Y} のいずれかとなる 08/4/0 9 08/4/0 0 ギャップ記号 Σ 上の文字列 s に対し s で s の長さ ( 文字の個数 ) を表し s[ i ] で s の i 番目の文字を表すものとする つまり s = n のとき s=s[]s[] s[n] となる また s[i j] で s の i 番目から j 番目の文字からなる部分文字列を表すものとする ギャップ記号 (gap symbol) - を Σ に現われない文字とする すると 配列ペア s s に対する大域アラインメント (global alignment) は それぞれの配列にギャップ記号 - を挿入して 長さを同じにそろえた配列の対 (s, s ) である すなわち s[i j] = s[i]s[i+] s[j] 08/4/0 08/4/0 3
入力配列 アラインメント 入力配列 : s[] s[] s[3] s[4] s[5] s s アラインメント s [] s [] s [3] s [4] s [5] s [6] s [7] s ー ー s ー s [] s [] s [3] s [4] s [5] s[6] s [] s [] s [3] s [4] s [5] s [6] s [7] 長さが同じになりました 08/4/0 3 08/4/0 4 なお 文字列の最初もしくは最後にギャップ記号を加える場合も大域アラインメントに含めるが 同じ位置にギャップ記号が並んではいけないものとする S [ i ] = S [ i ] = ー これはありえない 配列ペアに対応する可能なアラインメントは指数オーダー個あるので 数あるアラインメントから妥当なアラインメントを選び出すことが必要である そのために 個々アラインメントに対するスコアを次のように定義し スコアが最大となるアラインメントをもっとも妥当なアラインメントとして選び出す 08/4/0 5 08/4/0 6 4
スコア関数 スコア関数 スコア関数 (score function) w(y) を (Σ U {-}) x (Σ U {-}) から実数集合への関数とする アラインメントにおけるスコア関数はスコア行列 (score matrix) とよばれる ここで w(y) は任意の y Σ に対し w(y)=w(y,x), w(-)=w(-,y)= - d d は正の定数であり ギャップ 文字に対して - d というペナルティがつくことを意味する このスコア関数を 同じ列に並んだ文字に対して適用することにより 各列のスコアが決まる そして アラインメント全体のスコアは各列のスコアを合計したものとして定義され ペアワイズアラインメント問題は全体のスコアを最大とするアラインメントを求める問題として次のように定義される : 08/4/0 7 08/4/0 8 定義 ペアワイズアラインメント問題 入力 : 個の配列 s, s スコア関数 w(y). 出力 : 以下の定義されるスコアが最大となるアラインメント (s, s ) : S L ( s, s ) i w( s[ i], s[ i]) ( ただし l s s ) l スコアが最大となるアラインメントは 最適なアラインメント (optimal alignment) とよばれる よって ペアワイズアラインメント問題は 個の配列に対する最適なアラインメントを求める問題となる 08/4/0 9 08/4/0 0 5
例 s, s 例 L の場合 いかのそれぞれはアラインメントとなる ( 以降 L, L, L3 とする ) ここで x yのときにはw( y), x yのときにはw( y) そして d で定義されるスコア関数を考える L L3 L,L,L3のスコアは, 0となる L, L は最適アラインメントとなっていることが確認できる 08/4/0 08/4/0 アラインメントと編集距離 例 今まで 配列アラインメントは 入力配列にギャップを挿入して同じ長さにそろえたものとして定義してきたが 配列の進化を考えるうえでは 配列 s に文字の挿入 削除 置換が起きて s に変化した結果として解釈するほうが適切な場合がある たとえば s, s に対する次のアラインメントがあったとする (a) (b) (c) (d) 08/4/0 3 08/4/0 4 6
動的計画法による最適なアラインメント計算 (a) (b) (c) (d) 例 (a) は s にあった という文字が削除されたものと解釈する 例 (b) は s の 間に文字 が挿入されたものと解釈する 例 (d) も同様に文字 が挿入されたものと解釈する 例 (c) は s 中の文字 が 文字 に置換されたものと解釈する ここには 削除が 回 挿入が 回 置換が 回行われて 計 4 回の編集操作によって s になったことをあらわすことになる 最適なアラインメントを計算するには すべての可能性なアラインメントを生成し その中でスコアが最大となるものを選ぶ というアルゴリズムが考えられる しかしながら 可能なアラインメントの個数は指数オーダーであることが知られているので このアルゴリズムでは指数時間がかかります 08/4/0 5 08/4/0 6 動的計画法による最適なアラインメント計算 そこで 効率よく最適アラインメントを計算するためにさまざまなアルゴリズムが開発されてきた それらのほとんどにおいて基本となるのが 次に示す動的計画法に基づくアルゴリズムである 動的計画法による最適なアラインメント計算 入力配列を s s とし それぞれの長さを m, n とする また s[ i] と s[ j] に対する最適アラインメントのスコアを D[j] とする すると D[j] は次の再帰式 (recurrence) により計算できる 08/4/0 7 08/4/0 8 7
動的計画法による最適なアラインメント計算 この動的計画法アルゴリズムの意味は 以下に示すアラインメントグラフ (alignment graph) を考えると理解しやすい まず (m+) x (n+) 個の頂点を座標 ( に配列する (i=0,,m, j=0,,n) 08/4/0 9 j 動的計画法による最適なアラインメント計算 0,0) + + - - - +++= + = - 6 最適アラインメント最適でないアラインメント 08/4/0 30 i + m,n) 初期化 0,= j x (-d), 0)=i x (-d) d はギャップのペナルティ ( スコア ) 0, j ( d) 0) i ( d) i, j ) w( s[i],s[j]) max i, d j ) d w( x) x yのときw( y) j 0,..., n i 0,..., m 最適アラインメントのスコアを計算することは グラフにおいて頂点 (0,0) から (m,n) に至る最大重みパスを計算することと等価となる さらに s[ i] と s[ j] に対する最適アラインメントのスコアが 頂点 (0,0) から ( に至る最大重みパスの重みと等しくなることもわかる 08/4/0 3 08/4/0 3 8
頂点 ( に至るパスは どのパスにおいても ( に至る直前に (, ( j), ( j) のいずれかを通過しなくてはならない j) w(s(i),s() j) -d また (j) を通過した場合には (j) に至るまでの重みに w(s(i), s() を加えたものが ( までの重みになる j) w(s(i),s() j) -d 例えば :( を通過した場合には ( に至るまでの重みに d を加えたものが ( までのパスの重みになる (j) の場合は同様です -d -d 08/4/0 33 08/4/0 34 よって ( に至る最大重みパスの重みが再帰式で計算できる 0, j ( d) 0) i ( d) i, j ) w( s[i],s[j]) max i, d j ) d w( x) x yのときw( y) j 0,..., n i 0,..., m 08/4/0 35 再帰式により最適アラインメントのスコアが計算できることが分かったが 再帰式をそのまま実行したのでは 同じ がなんども出てきて 結局 指数時間かかってしまう そこで j が小さいほうから大きいほうへという順に を計算し その値をデーブルに覚えておくようにする 08/4/0 36 9
Procedure Pairwise lignment(s [,..., m],s [.,..., n], w) for i 0 to m do 0) i ( d) ; for j 0 to n do 0, j ( d); for i to m do for j to n do i, j ) w( s[i],s[j]) max i, d j ) d return m,n); よって 全体で O(mn) 時間で計算できることになる また を覚えるために O(mn) の記憶領域が必要となる 例 3: 全域的アラインメント Needleman-Wunsch 以下のように配列を考え る s: m=6 t: n=6 マッチの重み + ミスマッチの重み ギャップの重み - で評価 j (+) i (+) 0 (-) (+) () 0 (-) (+) - 08/4/0 37 例 4: 垂直変位 Needleman-Wunsch アルゴリズム大域アライメントのアルゴリズム () D [i, j ] が s[], s[],,s [ i ] と t[], t[],, t[ j ] の最適アライメントのスコアです 水平変位 () 初期化 0,0)=0, 0,= -j x d, 0)=- i x d d はギャップのペナルティ ( スコア ) 0
Needleman-Wunsch アルゴリズム大域アライメントのアルゴリズム (II) (3) 再帰式で Iteratively computation 0, jd, 0) id i, j ) w( s[i], t[j]) max i, d j ) d w( x) x yのときw( y) d ギャップスコア Needleman-Wunsch アルゴリズム大域アライメントのアルゴリズム (4) m,n) が s と t の最適アライメントのスコアです (5) アライメントを求めるには 0,0) から m,n) に至ったパスを m,n) からトレースバック (m=) (n=) (0,0) 0 d= (m=) (n=) (0,0) 0 d= (0,0) 0 - -4 - - (m=,n=) (m=,n=) (m=,n=) 08/4/0 43 08/4/0 44
Example: 対角 0 - -4 - -4 MX?? 0 + = - - = - 4 - - = - 4 0 - -4 MX 対角 - -4?? - = -3-4 - = -6 + = マッチの重さ + ミスマッチの重さ ギャップの重さ d= 0 - -4 - -4 Dynamic programming: example aps d = - Dynamic programming: example Dynamic programming: example
Dynamic programming: example Dynamic programming: example Dynamic programming: example 矢印の方向 : : : : - +-++ = 3