FFTと文字列マッチングの楽しい組み合わせ

配列解析アルゴリズム特論 渋谷 配列解析アルゴリズム特論 渋谷

文字列探索・比較（２）

渋谷

東京大学医科学研究所ヒトゲノム解析センター （兼）情報理工学系研究科コンピュータ科学専攻 http://www.hgc.jp/~tshibuya

配列解析アルゴリズム特論 渋谷 はじめに

¦

前回の話題

¿文字列探索（照合）アルゴリズムのいろいろ uKMP, AC uBM, Horspool, Turbo-BM

¦

今回の話題

¿力任せ文字列マッチングの高度化 ¿誤りを考えた探索 uFFTとマッチング uアラインメント入門

配列解析アルゴリズム特論 渋谷 Rabin-Karp (1)

¦

ハッシュ関数によって判定

¿ひとつずらす時のハッシュ関数の変化の計算が簡単な ハッシュ関数である必要がある ¿余計なメモリはO(1)でよい たとえば modular hash: hash(x[0..n-1]) = (x[0]dn-1 _{+ x[1]d}n-2 _{+ x[2]d}n-3 _{+ … + x[n-1]) mod q} パタン p → hash(p) テキスト hash(T[0..|P|-1]) hash(T[1..|P|]) hash(T[2..|P|+1]) hash(p)と比較 同じなら、その場所をチェック 差分のみ を計算 qは大きな素数

配列解析アルゴリズム特論 渋谷 Rabin-Karp (2)

10111

(16+4+2+1) mod 5 = 3 Pattern

11001101110100101...

Text check → YES! check → NO (16+8+1) mod 5 = 0 ((0-1·16)·2+1) mod 5 = 4 ((4-1·16)·2+0) mod 5 = 1 ((1-0·16)·2+1) mod 5 = 3 ((3-0·16)·2+1) mod 5 = 2 ((2-1·16)·2+1) mod 5 = 3 O(1) O(1) O(1) O(1) O(1) ただし実際の計算は細かくmodをとる （オーバーフロー対策）

配列解析アルゴリズム特論 渋谷 Shift-And Method ¦ ビット演算による並列化 ¿ 文字の種類ごとに計算する ¿ bit演算で計算するので、３２個なり６４個なりの計算が同時にできる （32（６４）文字以下のパタンなら特に速い） ¿ アルファベットサイズが小さい時にはBoyer-Mooreより速いことも！ ACGT T 0001 T 0001 A 1000 T 0001 T 0001 G 0010 C 0100 G 0010 文字のビット表現 各列にはそ の位置までテ キストが一致 している場合 に１が入って いる。 X _{Xを1bitシフトして1とORした後、B} AとAND TTTACGTATTATTGCGTCC.. T 01110001011011000100.. T 00110000001001000000.. A 00001000000100100000.. T 00000000000010000000.. T 00000000000001000000.. G 00000000000000100000.. C 00000000000000010000.. G 00000000000000001000.. テキスト パ タ ン 0から開始

配列解析アルゴリズム特論 渋谷 Shift-Or Method

¦

Shift-And Methodの実装時における効率化

¿Shift-And での１とのORをなくすために、ビットを反転させた 状態ですべての計算を行う uシフトした時に０が入るので、１を考えなくてよい u反転させて計算するのでANDではなく、ORを用いる u一番下の行に０が現れたらパタン発見！ ((001001 << 1) OR 000001) AND 010010 vs. (110100 << 1 ) OR 101101 1.5倍速！

配列解析アルゴリズム特論 渋谷 Rabin-Karp / Shift-Orのより有用な活用方法

¦

Shift-Orはパタンの長さに制限がある

¦

パタンの先頭

k 文字のみに対してShift-Orを用い、足

りない部分はbrute-forceで計算する、という活用法が

あり得る

¿さすがに先頭６４文字が「たまたま」一致してしまうことは滅多 にないため、十分高速

¦

Rabin-Karpは索引化も可能

¿ハッシュ値のハッシュテーブルを持つ ¿ソートして二分探索する u長さ可変、としたい場合は、先頭k文字のハッシュ、などで

配列解析アルゴリズム特論 渋谷

Shift-And/Shift-Or

¦ 少し一般化すると Wild-card (Don't care) を扱うことが可能

¿パタン側もテキスト側も両方とも ¿（Ａ or Ｔ）といったことも可能 パタン

TT*TT*CG

B

_A

00100100

B

_C

00100110

B

_G

00100101

B

_T

11111100

B

_*

11111111

配列解析アルゴリズム特論 渋谷 ハミング重み（距離）でマッチング

¦

更に進めて一致している文字の数（ハミング重

み）を求めたい

¿

ナイーブにやると

O(nm)の計算時間がかかる。

AATGTCGCTACGTCGTCCAACGCATTAC

CTACATG → 0

CTAC

A

T

G → 5

CTAC

T

A

G

→ 2

ずらしながら、すべての位置で計算したい

（ハミング距離は２） （ハミング距離は７） （ハミング距離は５）

配列解析アルゴリズム特論 渋谷 掛け算と足し算で計算できる

¦

Shift-And/Orと似た計算で計算できる

→ 畳み込み！

文字 Cに着目 他の文字も同様に計算して、足し 合わせればハミング重みになる 掛け算と足し算で 同じ場所にＣがあ る場所の数を数 えられる

0000010100100100110010100001

1001000 → 0

1001000 → 2

1001000 → 0

AATGTCGCTACGTCGTCCAACGCATTAC

CTACATG → 0

CTACATG → 5

CTACTAG → 2

配列解析アルゴリズム特論 渋谷 高速フーリエ変換（ＦＦＴ） （１）

¦

準備

)

/

2

sin(

)

/

2

cos(

/ 2

n

i

n

e

i n n

π

π

ω

π

⋅

+

=

=

⋅

とすると以下の性質が成り立つ

1

=

n n

ω

'n-th root of unity' property � 𝑗𝑗=0 𝑛𝑛−1 𝜔𝜔𝑛𝑛𝑗𝑗 = 0 Cancellation property （2次元平面上で原点を中心とする円上にある等間隔なk点の重心が原点であることに相当）

i

1 θ

e

θ·i 複素平面 虚数単位

配列解析アルゴリズム特論 渋谷 高速フーリエ変換（ＦＦＴ） （２）

¦

Fourier 変換とは

¿周波数への分解のようなもの ¿逆フーリエ変換で元に戻すことが可能

dt

e

t

h

f

H

ift

∫

−∞∞

⋅

=

₍

₎

2π

)

(

df

e

f

H

t

h

ift

∫

−∞∞ −

⋅

=

₍

₎

2π

)

(

… 虚部（あるいは実部）をゼロとして ⇒ 周波数

配列解析アルゴリズム特論 渋谷 高速フーリエ変換（ＦＦＴ） （３）

∑

− =

⋅

=

1 0 / 2 N k N ikn k n

h

e

H

π

∑

− = −

⋅

=

1 0 / 2

1

N n N ikn n k

_N

H

e

h

π

¦

離散Fourier 変換はFourier変換の離散化

k N m N n N n k m i m N n N ikn N m N imn m N n N ikn n h N e h e e h e H ⋅ =       = ⋅       _⋅ = ⋅

∑

∑

∑ ∑

∑

− = − = − − = − − = − = − 1 0 1 0 / ) ( 2 1 0 / 2 1 0 / 2 1 0 / 2 π π π π 証明 Cancellation property から、m=k 以外の時は これが 0 になる！

配列解析アルゴリズム特論 渋谷

高速フーリエ変換（ＦＦＴ） （４）

¦

Fourier変換・逆変換は

O(n log n)

¿ナイーブにやれば、O(n2)かかる ¿偶数奇数を別々に計算するのを再帰的に行うだけで高速化できる odd n N in even n N k N n k i k N in N k N n k i k N k N ikn k n

H

e

H

e

h

e

e

h

e

h

H

⋅

+

=

⋅

⋅

+

⋅

=

⋅

=

∑

∑

∑

− = ′ ′ + ′ − = ′ ′ ′ − = / 2 2 / 1 0 / 2 2 1 2 / 2 2 / 1 0 / 2 2 2 1 0 / 2 π π π π π hからHを計算（逆もほぼ同様） • 半分のサイズの問題が２つ出てくる • それらの解がわかっていれば、そこか らH₁,H₂,…,H_nはO(n)で計算可能 • 部分問題は再帰的に解く（log n段） • 最後はO(n)で解ける単純な問題

配列解析アルゴリズム特論 渋谷 畳み込み（１）

¦

やりたいこと

¿ナイーブにやれば、O(N2)かかる 9 3 1 4 1 5 9 2 6 5 3 5 8 9 3 1 4 3 7 3 1 4 1 4 2 1 3 5 6 2 3 7 3 1 27 21 3 4 4 5 36 4 6 15 15 30 16 27 21 3 4

186

N通りのずらし方に対して、この値を求めたい 足し算 同じ長さ（長さN)の２つの巡回数列 これをずらしていって（N通り） 掛け算

配列解析アルゴリズム特論 渋谷 畳み込み（２）

¦

離散畳み込み定理

∑

− = −

⋅

=

1 0 / 2

1

N n N ikn n k

_N

S

e

s

π

∑

− = −

⋅

=

1 0 / 2

1

N n N ikn n k

_N

R

e

r

π 離散フーリエ変換













⋅

⋅

=





























⋅













⋅

=

⋅

=

∑

∑

∑

∑

∑

− = ⋅ − − − = − = + − − = ⋅ ⋅ − − = + 1 0 2 1 0 1 0 ) ( 2 1 0 2 2 1 0

1

1

N n j i n N n N k N n N n j k i n N n N n k i n N k k k j j

e

R

S

N

e

R

e

S

N

r

s

C

π π π Cancellation property から証明 逆離散 フーリエ変換！

配列解析アルゴリズム特論 渋谷 畳み込み（３）

¥

巡回していない有限数列の計算をするには？



0詰めする

u巡回して回り込まないように、それぞれの長さが二つ の数列の長さの和になるように。 uO((n+m) log (n+m)) ゼロでつめる必要

配列解析アルゴリズム特論 渋谷 片方の数列が非常に大きい場合には

¦

それぞれの長さを

n、 m （n>m）としてO(n log m)に

することが可能

テキストをm‒1ずつ重なったm+O(m)ごとの問題に分割する m m+O(m) n （たとえば 2m ）

配列解析アルゴリズム特論 渋谷 畳み込みを用いたハミング距離に基づく探索

¦

そんなわけでＦＦＴで

O(n log m)で探索可能。

¿ただし、文字の種類数が多い場合は効率は悪くなる これと他の文字に 着目して計算した 値を足し算する 文字 Cに着目

0000010100100100110010100001

1001000 → 0

1001000 → 2

1001000 → 0

AATGTCGCTACGTCGTCCAACGCATTAC

CTACATG → 0

CTACATG → 5

CTACTAG → 2

配列解析アルゴリズム特論 渋谷 重み行列（プロファイル）

¦

似た機能の配列を集めて並べ、各位

置における塩基の重み（頻度）を行列

としたもの

¦

データベース

¿PRINTS, BLOCKS （たんぱく質）, TRANSFAC（DNA・転写因子） ¿立体構造予測などでも活躍する 1 2 3 4 5 6 7 8 9 A 0.3 0.1 - 0.25 - - - 0.2 0.2 T 0.1 0.9 0.2 0.25 0.7 - 1.0 0.1 0.2 C 0.2 - 0.7 0.25 0.3 - - 0.5 0.3 G 0.4 - 0.1 0.25 - 1.0 - 0.2 0.3 [Krogh et al. 1994, …] GTCATGTCC GTCGCGTGC ATCGCGTCT ATCTTGTGG TTTATGTCT CACACGTCG CTCGCGTTG GTTGTGTTT ATTATGTGA AACATGTGG CTCCCGTAC CTCTCGTCT TTTTTGTCC GTCTTGTAC GTCCTGTCG GTGGTGTCG GTGCTGTAA ATCTTGTCC GTCCTGTCA ATCCTGTAA ２０本のサンプル

配列解析アルゴリズム特論 渋谷 プロファイル・マッチング ¦ 確率的な考え方からの重み計算 ¿ 配列AACTがランダムに出現する率は up = (1/4)4 u 文字の頻度によっては、この値は異なる可能性がある。 ¿ 同じ配列が下のプロファイルが存在した時に出現する率は uq = 0.3 · 0.1 · 0.7 · 0.5 ¿ そのモチーフの出現率を r とすると配列AACTがこのモチーフのものである確率は u_r·q / ((1–r)·p+r·q)

¿ 実際は掛け算は大変なのと、1≫r なので log q + log r – log p を計算してその重要 度とする ¦ この計算をテキストのすべての位置に関して計算するのもやはりFFTで可能！ 1 2 3 4 A 0.3 0.1 - 0.25 T 0.1 0.9 0.2 0.25 C 0.2 - 0.7 0.5 G 0.4 - 0.1

-配列解析アルゴリズム特論 渋谷 FFTによる探索

¦

FFTによる探索は他にもさまざまなところで使わ

れる

¿

類似数列探索

u音声検索 u画像検索 u動画検索

¿

立体構造探索

u類似探索 uドッキング探索

配列解析アルゴリズム特論 渋谷 数列検索の例

¦

数列同士の比較

3204993572452103212

2342661723

2651111331

この良し悪しを差の二乗和で計算する場合、FFTが使える

¥

頑張れば画像探索にも使える

O(N log M) Photo by T. Shibuya 探す

∑

∑

∑

∑

= + = + = = +

−

+

=

−

n i i i j n i i j n i i n i i i j

q

p

q

p

q

p

1 1 2 1 2 1 2

₂

)

(

配列解析アルゴリズム特論 渋谷 畳み込みによる立体構造（物体）探索

¦

二つの立体構造（物体）の重なりをdetectできる。

¿うまく設計すればタンパク質のドッキング解析などにも応用 可能 ¿回転は考慮できない 平行移動した際の重なりの計算が畳み込みで可能

配列解析アルゴリズム特論 渋谷 立体構造マッチング（１）

¦

回転を考慮したタンパク質の立体構造（＝３次元座標列）

の探索でもFFTを利用した

O(n log m)アルゴリズムが存在

する

¿３次元に限らず同様の計算が可能 類似部分構造探索 端から順にチェック 回転、平行移動

配列解析アルゴリズム特論 渋谷

立体構造マッチング（２）

¦

RMSD (Root mean square deviation)

¿対応している原子、対応する回転、対応する平行移動がわかっ ている場合に、どれくらい近いかを計算する方法 ¿対応する原子さえわかっている場合、RMSDを最小化するため の最適な回転、平行移動を求めるのはO(n)で可能 ¿他の分野ではLSD (Least-square distance)と呼ばれることも u計算幾何、グラフィクス、ロボティクス、時系列データ解析、 etc.

n

v

b

R

a

B

A

RMSD

n i i i v R

|

(

)

|

/

min

)

,

(

1 2 ,

∑

₌

−

⋅

−

=

配列解析アルゴリズム特論 渋谷

URMSD: Unit-Vector Root Mean Square Deviation

¦

URMSD: Unit-Vector Root Mean Square Deviation

¿RMSDの変形 ¿いくつかのペアの距離が大きい場合でもさほど影響をうけない u₁ u₂ u₃ u₄ u₆ u₇ w₁ w₂ w₃ w4 w₅ w₆ w₇ u₅

n

w

R

u

B

A

URMSD

n i i i R

|

|

/

min

)

,

(

1 1 2

∑

− =

⋅

−

=

i i i i i

a

a

a

a

u

=

₍

₊₁

−

₎

_/

₊₁

−

i i i i i

b

b

b

b

w

=

₍

₊₁

−

₎

_/

₊₁

−

where

配列解析アルゴリズム特論 渋谷 RMSDにおける平行移動の最適化（１）

¦

Rを考えないで最適化してみる。

∑

∑

∑

−

−

=

⋅

+

−

⋅

+

−

= n i i i n i t i i n i i i

b

a

v

b

a

v

n

v

b

a

2 2 1 2

₂

₍

₎

|

)

(

|

∑

−

−

=

n i i i

n

b

a

v

(

)

/

これは の時に最小値をとる。 ということは…？

n

v

b

R

a

B

A

RMSD

n i i i v R

|

(

)

|

/

min

)

,

(

1 2 ,

∑

₌

−

⋅

−

=

R=I だと仮定して、√の中を変形すると、

配列解析アルゴリズム特論 渋谷 RMSDにおける平行移動の最適化（２）

¦

較べたい２つの構造の重心が原点に来るように、それ

ぞれの構造を移動しておけば、回転の最適化をする際

に平行移動は考えなくてよい！

¿そうすれば、回転によって原点は移動しない

配列解析アルゴリズム特論 渋谷 回転の最適化

¦

というわけで、解きたい問題は

2 1

|

|

∑

=

⋅

−

n i i i

q

R

p

minimize

回転行列 R 比べたい平行移動済ベクトル

¥

もう少し展開すると

)} ( 2 { )} ( { )} ( { | | 1 1 1 2 1

∑

∑

∑

∑

= = = = ⋅ ⋅ − + = + − + = ⋅ − n i T i i n i i T i i T i n i i T T i i T i i T i i T i n i i i p q R trace q q p p p R q Rq p q q p p q R p Hとおく

配列解析アルゴリズム特論 渋谷 というわけで

¦

求めるべきものは

maximize trace(RH)

回転行列 R

¥

ところで、

3x3行列 H をよく見ると、、、

位置をずらしながらすべての位置関係についてHを計算 することが（平行移動を考えても）FFTを用いてO(n log n) で可能

∑

= n i T i i

q

q

1 T i n i i

p

q

∑

=₁

∑

= n i T i i

p

p

1

∑

= n i i

q

1

∑

= n i i

p

1 こちらは自明に線形時間で可能 こちらは畳み込み！ H が与えられれば、特異 値分解を使ってO(1)で計 算可能！

配列解析アルゴリズム特論 渋谷 この問題に対して便利な定理 ¦ 定理： ¿ 正定値対称行列M および 直交行列Qに対して trace(M) ≥ trace(Q·M) が成り立つ ¦ 簡単な証明 ¿ M = RSR-1 （対角化） u_{RはMの固有ベクトルからなる行列} ’ 固有ベクトルは正規直交 （←Mは対称行列） ’ R–1=R T が成り立つ （←正規直交性から） u_{SはMの固有値（正の値をとる）からなる対角行列 （←正定値性）} ’ すなわち、S の対角要素(S_ii )は正 ¿ θ_i ： 以下のq_i と r_i がなす角度 uq_i : Q·Rの第 i 列ベクトル r_i : R の第 i 列ベクトルを r_i

配列解析アルゴリズム特論 渋谷 回転を決めるためのTips ¦ 先ほどの定理 ¿ Mが正定値対称で、Qが直交ならば trace(M) ≥ trace(QM) ¦ ということは？ ¿ RHが正定値対称の場合に、trace(RH) は最大値をとる！ u適当な直交行列R''を用いてR'H = R'' ·RH と表すことができるため。 uただし直行行列は回転行列とは限らない。鏡像変換の可能性あり ¿ H=UΣVT（特異値分解）としてR=VUT （直交行列）とおけば uRH=VΣVT _{：正定値対称} ¿ Hは３×３（コンスタントサイズ）なのでこの計算はコンスタントタイム！ um×n行列ならばO(m2_n+nm2_+n3_{)で特異値分解が可能} ¦ 鏡像のチェックが必要 ¿ R のdeterminantが1だったら正解。-1だったら鏡像 ¿ 鏡像行列が得られてしまった場合の修正は実はO(1)で簡単にできる [Umeyama '91] u 「たまたま」鏡像が似ている、などという可能性は低い、と考えられる場合には、無視し てもよいかもしれない（応用による）

配列解析アルゴリズム特論 渋谷 特異値分解

¦

特異値分解

¿ 変換が簡単になるような正規直交基底を見つける手法 ¿ 計算時間： O(n3) (nxnの行列に対して) 1 1 orthonormalなベクトルv₁, v₂, ... _{変換されたものをorthonormalになるように長さを} 変えたベクトルu₁, u₂, ... 線形変換A

























=

n

u

u

v

v

A

σ

σ

σ



2 1 2 1 2 1

,

,...)

(

,

,...)

(

V U T

V

U

A

=

∑

正値、対角行列

配列解析アルゴリズム特論 渋谷

というわけで結論

¦

立体構造においても

O(n log m)で類似構造探索が

可能

¿O(n log n) から O(n log m) にするのは文字列の時と同じ

テクニックで可能

類似部分構造探索

配列解析アルゴリズム特論 渋谷

Edit Distance (Levenstein Distance)

¦

ここまで

¿ハミング重み（距離）で計算＝比較する文字の位置は不変 uＦＦＴ、ビット演算等の高速化が可能

¦

生物配列等では

¿文字の脱落、挿入がありえる

¦

Edit distance

¿ある文字列ＡからＢへ何回の操作で変換できるか？ u挿入 u削除 u置換

AT

C

GGCTA

AT

T

GG

CT

A

ATTGGA

A

TT

TTGGA

変異 他にもより複雑な操作を導入す ることもあるが、ここではこの３つ を考える

配列解析アルゴリズム特論 渋谷 Dot Plot

¦

最も簡単な比較方法

¿DNAでは相補配列のプロットも考慮 uA-T uG-C u(G-T) G C T A

配列解析アルゴリズム特論 渋谷 アラインメントによる表現

¦

２つの文字列間の操作はアラインメントによって表

現できる。

¿

ハミング距離との違いはギャップの存在

MI-AMIBEACH---|| MI-AMIBEACH---|||: MI-AMIBEACH---|||

MINAMIM-ACHIDA

match mismatch

internal gap external gap

変異１ 挿入4 削除１

配列解析アルゴリズム特論 渋谷 Edit Distanceの解法（１）

¦

グラフ上での最短路を求める問題に帰着できる

¿格子状グラフ u一致している文字に相当している枝の長さを 0 uそれ以外の長さを 1 とする ¿正負を逆転させれば最長路問題 A T G C A C T

ATGC-A--CT

0 0 0 0と書いてある枝の長さは0 それ以外は1 →最短路を求める

配列解析アルゴリズム特論 渋谷 Edit Distanceの解法（２）

¦

動的計画法

¿始点から④までの最短路は、 u始点から①、②、③までの最短路がすべてわかっていればそれら＋1 本の枝の長さを比較することでO(1)で計算できる！ ¿すなわち、グラフを左から（あるいは上から）順番に最短路を計算 していけば、O(nm)で最短路を計算することが可能！ ¿パスを得るには、終点から、その最短路長を得られた枝をたどっ て行けばよい（トレースバック(trace back)という） A T G C A C T

ATGC-A--CT

① ② ③ ④ 始点 終点

配列解析アルゴリズム特論 渋谷 Edit Distanceの解法（３）

¦

編集距離に上限

kがある場合には O(kn)

¿ただし、２本の配列の長さが異なる場合には、あまり効果はない

¦

kがわからない場合は？

¿k=1 から初めて、成功するまで k を倍々に増やしていけばよい。 u全体でも O(kn) ’ 1+2+4+...+ 2d (2d < 2k) はO(k) となる！ A T G C A C T

ATGC-A--CT

k 0 0 0 0と書いてある枝の長さは0 それ以外は1 →最短路を求める

配列解析アルゴリズム特論 渋谷 アラインメント・スコア

¦

Edit distanceの一般化

¿スコア ～ 重み付きedit distance uただし、通常、似ているものが高いスコアになるようなスコアとすることが 多い u文字-文字のスコア uギャップに対するペナルティー的なスコア

¦

特殊な設定例

¿Longest Common Subsequence

u一致文字：１、不一致・ギャップ：０

MI-AMIBEACH---MINAMIM-ACHIDA

B-Mのスコア ギャップのスコア

配列解析アルゴリズム特論 渋谷

アラインメントのスコアテーブル（１）

¦

PAM (Point-Accepted-Mutation） Matrix

[Dayhoff '78]

¿

類似配列を収集（変異１％以下）

¿

変異から変異確率行列

Mを計算→n乗する

uPAM-250, PAM-300...

¿

log (q

_ij

/p

_i

p

_j

)に比例したスコア

up_iはその文字の出現率、q_ijは同時出現率

¿

近い配列のアラインメントは小さい

n で計算するの

がよい

¿

ギャップに関してはそれほど統計的な裏づけはない

経験値を使用することが多い

u使っている収集データにギャップが殆どないため

配列解析アルゴリズム特論 渋谷 アラインメントのスコアテーブル（２）

¦

スコア行列

¿アミノ酸文字間の類似性を表す行列 C S T P A G N D E Q H R K M I L V F Y W C 12 S 0 2 T -2 1 3 P -3 1 0 6 A -2 1 1 1 2 G -3 1 0 -1 1 5 N -4 1 0 -1 0 0 2 D -5 0 0 -1 0 1 2 4 E -5 0 0 -1 0 0 1 3 4 Q -5 -1 -1 0 0 -1 1 2 2 4 H -3 -1 -1 0 -1 -2 2 1 1 3 6 R -4 0 -1 0 -2 -3 0 -1 -1 1 2 6 K -5 0 0 -1 -1 -2 1 0 0 1 0 3 5 M -5 -2 -1 -2 -1 -3 -2 -3 -2 -1 -2 0 0 6 I -2 -1 0 -2 -1 -3 -2 -2 -2 -2 -2 -2 -2 2 5 L -6 -3 -2 -3 -2 -4 -3 -4 -3 -2 -2 -3 -3 4 2 6 V -2 -1 0 -1 0 -1 -2 -2 -2 -2 -2 -2 -2 2 4 2 4 F -4 -3 -3 -5 -4 -5 -4 -6 -5 -5 -2 -4 -5 0 1 2 -1 9 Y 0 -3 -3 -5 -3 -5 -2 -4 -4 -4 0 -4 -4 -2 -1 -1 -2 7 10 W -8 -2 -5 -6 -6 -7 -4 -7 -7 -5 -3 2 -3 -4 -5 -2 -6 0 0 17 PAM-250

配列解析アルゴリズム特論 渋谷

アラインメントのスコアテーブル（３）

¦

BLOSUM (Blocks Substitution Matrix)

¿

類似配列を収集

¿

ギャップなしの局所的な保存部位（Block）を収集

uBLOCKS database

¿

P%以上一致しているものは一つの配列として扱う

uBLOSUM-62 (P=62)

¿

log (q

_ij

/p

_i

p

_j

)に比例したスコア

up_iはその文字の出現率、q_ijは同時出現率

¿

考え方はほぼPAMと同じだが、遠縁、あるいは全く系

統的な関係のないタンパク質の比較に使うためのもの。

u系統的な関係のほとんどないにも関わらず類似している配列を「保存さ れている」配列、という。 ’ 生物一般の生存に重要なものだと考えられる u言い換えると、このテーブルを用いて系統樹を作ってはいけない！ ’ かわりに「機能」の「クラスタリング」はやってよい

配列解析アルゴリズム特論 渋谷 最適解解法

¦

まったく同じ動的計画法で計算すれば良い

¿

格子状グラフにおける最長（短）路

¿

O(nm) - n, m: 配列長

A T G C A C T

ATGC-A--CT

配列解析アルゴリズム特論 渋谷 まとめ ¦ 力任せマッチング・FFTマッチング ¦ アラインメント（初級編） ¦ 次回の話題 ¿文字列比較（上級編）