情報生命科学特別講義

情報生命科学特別講義III
（４）近似文字列マッチング
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
講義予定















第１回: 文字列マッチング
第２回：文字列データ構造
第３回：たたみ込みとハッシュに基づくマッチング
第４回：近似文字列マッチング
第５回：配列アラインメント
第６回：配列解析
第７回：進化系統樹推定
第８回：木構造の比較：順序木
第９回：木構造の比較：無順序木
第１０回：文法圧縮
第１１回： RNA二次構造予測
第１２回：タンパク質立体構造の予測と比較
第１３回：固定パラメータアルゴリズムと部分k木
第１４回：グラフの比較と列挙
第１５回：まとめ
近似文字列マッチング
近似文字列マッチング：問題の定義
入力： P  p1  pm , T  t1 tn , 許容誤差 k
出力：以下の条件を満たす T 中のすべての位置 j

P と T  ti t j は誤差 k 以内でマッチ
誤差の種類: (A) 文字が異なる (B) 1文字挿入 (C) 1文字削除
例： P=bcde, T=abcdfebde, k=1
例： P=bcdefgh, T=abxdyeghij, k=3
近似文字列マッチング：動的計画法アルゴリズム
for j  0 to n do D[0, j ]  0;
for i  0 to m do D[i,0]  i;
for i  0 to m do

D[i  1, j ]  1;

for j  0 to n do D[i, j ]  min
D[i, j  1]  1;
 D[i  1, j  1]  1   ( p , t );
i j

for j  0 to n do if ( D[m, j ]  k ) th e noutput j
ただし、
例： P=caab,
T=bccabac
⇒ O(mn)時間
1, x  y
0, x  y
 ( x, y )  
Landau-Vishkinアルゴリズム
Landau-Vishkinアルゴリズム：アイデア
アイデア：たてのものをななめに見る
対角線 d： j-i=d を満たす D[i,j] の集合
表 L[d,e]: L[d,e]=i ⇔
D[i,j]=e かつ j-i=d を満たす最大の行が i
例：下の表で、 L[3,0]=0, L[3,1]=3, L[3,2]=4
L[d,e]の性質
必要な記憶領域は


O(kn)
対角線の総数は O(n)
L[d,e] は e≦k までで十分
対角線に沿って単調増加
Landau-Vishkinアルゴリズム
アルゴリズム
の中心部分
for e  0 to k do
for d  e to n do
 L[d , e  1]  1;

row  max L[d  1, e  1];
 L[d  1, e  1]  1;

wh il e( prow 1  t row 1 d ) do row  row  1;
L[d , e]  row
定理：近似文字列マッチングは O(kn) 時間で実行可能
（略証）計算量の解析で問題となるのは while ループ。
しかし、suffix tree を用いれば、while ループは1回あたりO(1)時間
で実行可能。
接尾辞木の利用
while ループ（極大伸長部分列検出）のO(1)時間での実行方法
S=P#T$ についての接尾辞木を構成
Prow+1 に相当する箇所 S[row+1..m+n+2] に対応する葉を x とする
trow+1+dに相当する箇所 S[row+m+2+d..m+n+2] に対応する葉を y と
する
x と y のLCA（lowest
common ancestor）が
該当部分列に対応
LCAの計算はO(log n)
ビット長ワードの定数
時間演算を仮定する
と定数時間で可能
Don’t Care記号つき
近似文字列マッチング
[Akutsu: Inf. Proc. Lett. 1995]
Don’t Careつき近似文字列マッチング：問題の定義
問題： P,T のどちらにも Don’t Care記号（＊：任
意の１文字とマッチ可能）が入って良いとした近
似文字列マッチング
例： P=bc*eghi, T=a*cdefgij, k=2
Don’t Careつき近似文字列マッチング：アイデア
アイデア：二つの方法を組み合わせてバランスをとる
Landau-Vishkinアルゴリズムの利用
while ループの prow+1=trow+d+1 を次のように変更
prow+1=＊ or trow+d+1=＊ or prow+1=trow+d+1
⇒ しかし、ループの実行が最悪で O(m) 時間かかる
テーブルの
利用
⇒ ループの実行が O(M) ⇒ 全体で O(kMn)
Don’t Careつき近似文字列マッチング：テーブルの構成
W[r,j]： Pr Pr h1  t j t j hM 1 を満たす最大の h
テーブル W[r,j] の構成
テーブル全体のサイズは O((m/M)n)
構成はたたみ込み法により O((m/M)n log m）時間
テーブル作成とマッチングのバランス
kMn  ( Mm )nより M  m / k 。よって、 O(kMn)  O( Mm  n logm)  O( kmn logm)
定理： Don’t Care記号つき近似文字列マッチングは
O( kmn log m) 時間で実行可能
編集距離の埋め込みと
局所性鋭敏型ハッシュ
[Andoni, Indyk: CACM 2008]
編集距離の埋め込み
埋め込み： X を距離 ρ、Y を距離 σ を有する距離空間とする時、以下を満たす
X から Y への関数 Φ を、X から Y への歪み率 D の埋め込みとよぶ
(r )(x, y)(r   ( x, y)   ( ( x), ( y))  D  r   ( x, y))
定理：長さ n の文字列に対する編集距離は O(n2) 次元の L1 空間
に歪み率
2O( lognloglogn ) で埋め込み可能 [Ostrovsky, Rabani: J. ACM 2007]
定理：長さ n の文字列に対する編集距離の L1 空間への埋め込みの歪み率は
Ω(log n) [Krauthgamer, Rabani: Proc. SODA 2006]
定理：長さ n の文字列に対する編集距離の log(n)O(1/ε) 近似はO(n1+ε) 時間で計
算可能 [Andoni et al.: Proc. FOCS 2010]
定理：移動操作を許した場合、長さ n の文字列に対する編集距離は L1 空間に
歪み率 O(log n ・log*n) で埋め込み可能 [Cormode, Muthukrishnan: ACM Trans. Alg. 2007]
埋め込んだ後では高次元空間での探索が必要 ⇒ 局所性鋭敏型ハッシュ
局所性鋭敏型ハッシュ (Locality Sensitive Hashing)
高次元データの探索
Kd木などが使われるが、一般に次元が高いと難しい
⇒アイデア：多少のあいまい性を許す
近似近傍探索
(Approximate Neighbor Search)
入力： d次元の点集合 P (|P|=n),
質問点 q, 距離 r
出力： d(p,q) ≦r を満たす点が
あれば、yes (p も出力)
d(p,q)≦(1+ε)r を満たす点が
なければ、no
それ以外はどちらでもOK
局所性鋭敏型ハッシュ関数族
F が (r,r(1+ε),α,β)-局所性鋭敏型ハッシュ関数族 ⇔
h を F からランダムに選んだ時、（∀p）以下が満たされる
ならば、Pr[h(p)=h(q)]≧α
d(p,q)＞(1+ε)r ならば、 Pr[h(p)=h(q)]≦β
d(p,q)≦r
命題： P⊆2d、b=(b1,…,bd)∈P とし、F={hi | hi (b)=bi} とすると、F は
(r,r(1+ε),1-r/d,1-r(1+ε)/d)-LSH関数族
証明： c と b の距離が r 以下なら、少なくとも d-r ビットは一致。
よって、hi (c)=hi (b) となる確率は (d-r)/d=1-r/d 以上。
注意：確率は h の選び方
のみについてとる
局所性鋭敏型ハッシュ：アルゴリズム
F から k 個の関数の組合せを選ぶことにより G を構成
G={g | g(p)=(hi1(p),…,hik(p)), hij∈F }
G からランダムに τ 個選んだ関数を g1,…,gτ とする
前処理：ハッシュテーブルの構成
g1,…,gτ を用いて τ 個のハッシュテーブルを作成
各テーブルごとに、P をハッシュ
探索： i=1 から i=τ まで以下を繰り返す
バケット gi(q) の点をすべてチェックし、d(p,q)≦r を満たす p があ
れば出力して終了
調べた点の合計が 4τ を超えたら失敗して終了。
繰り返しが終了したら、 d(p,q)≦(1+ε)r を満たす点は無しと出力。
局所性鋭敏型ハッシュ：アルゴリズムの説明
探索： i=1 から i=τ まで以下を繰り返す
バケット gi(q) の点をすべてチェックし、d(p,q)≦r を満たす p があれば出力して
終了
調べた点の合計が 4τ を超えたら失敗して終了。
繰り返しが終了したら、 d(p,q)≦(1+ε)r を満たす点は無しと出力。
局所性鋭敏型ハッシュ：検出確率
パラメータの設定

ln(1/  )
ln(1/  )
k
ln(n)
ln(1/  )
  2n
d(p,q)≦r が満たす p が存在する時に、gi(p)=gi(q) となる
確率は
Pr[gi ( p)  gi (q)]   k   ln(n) / ln(1/  )  n(ln(1/ ) / ln(1/  ))  n 
上記を満たす gi が存在（つまり、p を検出）する確率は
Pr[(i)(gi ( p)  gi (q))]  1  (1  n  )  1 1/ e2  54
(1  1x ) x  1e
局所性鋭敏型ハッシュ：誤検出確率
d(p,q)>(1+ε)r を満たす p に対し、gi(p)=gi(q) となる確率は


Pr[gi ( p)  gi (q)]   k  exp ln( )  ln(ln(1/n) )  1n
より、１個のバケットに入る、そのような（望ましくない）p の
個数の期待値は ((1/n)×n)=1 以下。
よって、τ 個のバケットに入る、そのような p の個数の期待
値は τ 以下。
⇒ 4τ 個以上の点を調べてしまう確率は (τ/4τ)=1/4以下。
⇒ d(p,q)≦(1+ε)r を満たす p が存在しない場合に、
失敗してしまう確率は 1/4 以下。
(no を出力して欲しいのに失敗してしまう場合）
局所性鋭敏型ハッシュ：計算量
領域計算量： O(dn+n1+ρ) 領域
点の情報： O(dn)領域
ハッシュテーブル： O(τn)=O(n1+ρ) 領域
（点の情報は点へのポインタで記憶）
探索の時間計算量： O(dτ)=O(dnρ)時間
（ハッシュ関数はO(d)時間で計算可能と仮定）
ln(1 /  )
ln(1  r / d )
1



ln(1 /  ) ln(1  (1   )(r / d )) 1  
定理：（r,r(1+ε),α,β)-LSH族が存在する問題に対し、
O(dn+n1+1/(1+ε))領域、O(dn1/(1+ε))探索時間で
（高確率で成功する）近似近傍探索が実行可能
O(log n)個のコピーを作成すれば、失敗確率は O(1/nh) に下げることが可能
拡張と応用
実数データへの対応
ランダムな直線への射影+整数化 [Datar et al.: Proc. SoCG. 2004]
Rt 空間（tは定数）の球への射影（ほぼ最適） [Andoni, Indyk:
Proc. FOCS 2006]
バイオインフォマティクスへの応用
配列比較 [Buhler: Bioinformatics 2001]
モチーフ検出 [Buhler, Tompa: J. Comp. Biol. 2002]
化合物検索 [Cao et al.: Bioinformatics 2010]
質量分析スペクトル検索 [Dutta, Chen: Bioinformatics 2007]
まとめ
近似文字列マッチング
動的計画法により
O(mn) 時間
対角線に注目し、接尾辞木を用いると O(kn) 時間（k は許容誤差）
Don’t Care 記号つき近似文字列マッチング
テーブル+たたみ込み+動的計画法
局所性鋭敏型ハッシュ
近似と乱拓性の導入により次元への指数依存性を回避
補足
近似文字列マッチングは
O(nk4/m+m+k) 時間まで改善されている[Cole,
Hariharan: SIAM J. Comput. 2002] が、k に関係なく O(nm1-ε) 時間でできるかは研
究課題（O(log2n)程度の改善は既知 [Bille, Colton: TCS 2008]）
Don’t Care文字つき近似文字列マッチングの改良は研究課題
編集距離の O(n)サイズ（もしくはそれに近いサイズ）のL1空間への低歪み埋
め込みは研究課題
LSH
を利用しない近似近傍探索 [Andoni et al., Proc. SODA, 2014]

Download Report