情報生命科学特別講義

情報生命科学特別講義III
(3)たたみ込みとハッシュに
基づくマッチング
阿久津 達也
京都大学 化学研究所
バイオインフォマティクスセンター
講義予定















第1回: 文字列マッチング
第2回: 文字列データ構造
第3回: たたみ込みとハッシュに基づくマッチング
第4回: 近似文字列マッチング
第5回: 配列アラインメント
第6回: 配列解析
第7回: 進化系統樹推定
第8回: 木構造の比較:順序木
第9回: 木構造の比較:無順序木
第10回: 文法圧縮
第11回: RNA二次構造予測
第12回: タンパク質立体構造の予測と比較
第13回: 固定パラメータアルゴリズムと部分k木
第14回: グラフの比較と列挙
第15回: まとめ
たたみ込みによる
文字列マッチング
たたみ込みとFFT
ベクトル a=(a0,…,am-1) と b=(b0,…,bn-1) のたたみ込み a*b は
ck 
aib j を要素とするベクトル c=(c0,…,cn+m-1)

i  j k
(ただし、cn+m-1=0と定義)
2つの多項式
p( x)  a0  a1 x  a2 x 2    am1 x m1
q( x)  b0  b1 x  b2 x 2    bn 1 x n 1
p( x)q( x)  c0  c1x  c2 x2   cnm2 xnm2
の積
の各係数は、たたみ込みベクトルの各成分に等しい
(a0,…,am-1) と (b0,…,bn-1) のたたみ込みはFFTを用いて
(Real-RAM上で) O(n log n) 時間で計算可能(ただし、m≦n)
たたみ込みによる文字列マッチング: アイデア
(a0, a1,a2) と (b0,…,bn-1) のたたみ込みを考える
ここで、 a0, a1,a2 を逆順にすれば、以下のようになる
⇒ パターンを逆順にして、たたみ込みを行えば、
文字列マッチングに使えそう
(Fisher-Patersonアルゴリズム)
たたみ込みによる文字列マッチング
Σ={a,b}, T = abbabbab, P=abb, P-1=bba として、 χa(T)などを次
のように定義
 (T )  10010010,  (T )  01101101
,
a
 a ( P 1 )  001,
すると
b
 b ( P 1 )  110
 a (T )   a ( P 1 )  0010010010
 b (T )   b ( P 1 )  0121121110
この2個のベクトルの和は 0131131120 となり、
値が 3 となる桁がマッチしている場所に対応
定理:文字列マッチングは FFT により O(n log m) 時間で実行可能
(ただし、|Σ|は定数)
Don’t Care記号つき文字列マッチング
Don’t Care記号: 任意の1文字とマッチする記号 (`*’ で表す)
KMP, BM, ACアルゴリズムを Don’t Care記号つきに拡張するの
は困難。でも、たたみ込み法なら、以下の例のように簡単
T  ab * a * ba , P  a * ba
 a* (T )  1011101,  a ( P 1 )  1001
 b* (T )  0110110,  b ( P 1 )  0100
χa*(...) は、対象の文字が
a か * なら、1 に対応させる
定理:Don’t Care記号つき文字列マッチングは FFT により
O(n log m) 時間で実行可能
(ただし、|Σ|は定数)
Karp-Rabinアルゴリズム
ランダマイズド・アルゴリズム(乱拓アルゴリズム)
同じ入力を与えても、アルゴリズムの動作が内
部で用いた乱数の値により異なるアルゴリズム
 ラスベガス・アルゴリズム


常に正しい解を出力(ただし、計算時間は乱数に
より異なることがある)
モンテカルロ・アルゴリズム

誤った解を出力する可能性がある
Karp-Rabinアルゴリズム: アイデア
ハッシュ関数の利用
長さ m の各部分文字列に対し、以下の性質を満たす
整数値(ハッシュ値) h(ti ti m1 )
を計算
(i)
p1  pm  ti ti  m 1 ならば、
常に
h( p1  pm )  h(ti ti  m 1 )
(ii) p1  pm  ti ti  m 1 ならば、
高確率で h( p1  pm )  h(ti ti  m 1 )
Karp-Rabinアルゴリズム: ハッシュ関数
q を適当に大きな素数とし、b を適当な基数(例: b=2)とすると
h(ti tim1 )  (tibm1  ti 1bm2   ti m1 ) mod q
なお、h()は、毎回計算しなおさなくても、
h(ti 1 ti m )  ((h(ti ti m1 )  tibm1 )b  ti m ) mod q
により、1回あたり O(1) 時間で計算可能
定理: q を適当な範囲内でランダムに選ぶことにより、どのような
入力 P, T に対しても、高い確率で以下が成立
p1  pm  ti ti m1 ならば、 h( p1  pm )  h(ti ti m1 )
Karp-Rabinアルゴリズム
ハッシュ関数を計算し、一致している場所を出力
⇒ 線形時間モンテカルロ・アルゴリズム
Karp-Rabinアルゴリズム: 確率の解析
補題: 任意の N について、(異なる)素因数の個数は O(log N)
(証明) 素数は2以上なので、t 個の素因数を持てば N≧2t
補題: x,y (x≠y) をそれぞれ m ビットの数とする。τ 以下の素数 p

をランダムに選んだ時、(x = y) mod p となる確率はO( m log
 )
(証明) (x = y) mod p となるのは |x-y| が p の倍数の時のみ。
一方、|x-y| の素因数の個数は上記補題より O(m) 個。
τ 以下の素数の個数は素数定理より≈ τ/ln τ なので、
m log
(x = y) mod p となる確率は O(  ) 。
(Karp-Rabinの定理の証明)
τ = n2m log n2m とすれば、 p1  pm  ti ti m1 なのに、ハッシュ

1
値が一致してしまう i の存在確率は O(n  mlog
)

O
(

n)
ラスベガス・アルゴリズム化
方法1
 マッチが見つかったら O(m) 時間かけてチェック
 誤りであれば、単純なO(mn)時間アルゴリズムを
最初から実行
計算時間の期待値は O((m+n)+(1/n)(mn))=O(m+n)
方法2
 マッチが見つかったら O(m) 時間かけてチェック
 誤りであれば、異なる素数 p を用いて再実行
計算時間の期待値は O(m+n)
( O((m  n)((1  1n )  2  1n  (1  1n )  3  ( 1n )2  (1  1n )  )  O(m  n) )
注意: 素数生成のための時間は考慮していないが、考慮しても定理や解析は成立
まとめ

たたみ込みによる文字列マッチング


O(n log m) 時間
Karp-Rabinアルゴリズム


Don’t care 文字が扱える。
ハッシュ関数を用いたランダマイズド・アルゴリズム
補足



たたみ込みマッチングは、文字のミスマッチにも対応可
たたみ込みを用いずに don’t care つき文字列マッチングを効率的に
扱うのは(たぶん)研究課題
Karp-Rabinアルゴリズムは広くは利用されていないが、文字列などの
データをハッシュするという考え方は、第4回に説明する Locality
Sensitive Hashingや埋め込み(Embedding)などの名で盛んに研究・
応用されている
本講義で研究課題としたものはすべて「たぶん」です