情報生命科学特別講義III （４）近似文字列マッチング 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義予定 第１回: 文字列マッチング 第２回： 文字列データ構造 第３回： たたみ込みとハッシュに基づくマッチング 第１回:　文字列マッチング 第２回：　文字列データ構造 第３回：　たたみ込みとハッシュに基づくマッチング 第４回：　近似文字列マッチング 第５回：　配列アラインメント 第６回：　配列解析 第７回：　進化系統樹推定 第８回：　木構造の比較：順序木 第９回：　木構造の比較：無順序木 第１０回：　文法圧縮 第１１回：　RNA二次構造予測 第１２回：　タンパク質立体構造の予測と比較 第１３回：　固定パラメータアルゴリズムと部分k木 第１４回：　グラフの比較と列挙 第１５回：　まとめ

近似文字列マッチング

出力： 以下の条件を満たす T 中のすべての位置 j 近似文字列マッチング： 問題の定義 入力： 出力： 以下の条件を満たす T 中のすべての位置 j P と　　　　　　　は誤差 k 以内でマッチ 誤差の種類: (A) 文字が異なる (B) 1文字挿入 (C) 1文字削除 例： P=bcde, T=abcdfebde, k=1 例： P=bcdefgh, T=abxdyeghij, k=3

近似文字列マッチング： 動的計画法アルゴリズム 例： P=caab, T=bccabac ⇒ O(mn)時間

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アルゴリズム の中心部分 定理： 近似文字列マッチングは 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]： を満たす最大の h テーブル W[r,j] の構成 テーブル全体のサイズは O((m/M)n) 構成はたたみ込み法により O((m/M)n log m）時間 テーブル作成とマッチングのバランス 定理： Don’t Care記号つき近似文字列マッチングは 　　　　　　　　　　　　　時間で実行可能

編集距離の埋め込みと 局所性鋭敏型ハッシュ [Andoni, Indyk: CACM 2008]

編集距離の埋め込み 埋め込み： X を距離 ρ、Y を距離 σ を有する距離空間とする時、以下を満たす X から Y への関数 Φ を、X から Y への歪み率 D の埋め込みとよぶ 定理： 長さ n の文字列に対する編集距離は O(n2) 次元の L1 空間 に歪み率　　　　　　　　　　　　で埋め込み可能 [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） 以下が満たされる d(p,q)≦r ならば、Pr[h(p)=h(q)]≧α d(p,q)＞(1+ε)r ならば、 Pr[h(p)=h(q)]≦β 命題：　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 を満たす点は無しと出力。

局所性鋭敏型ハッシュ： 検出確率 パラメータの設定 d(p,q)≦r が満たす p が存在する時に、gi(p)=gi(q) となる確率は

局所性鋭敏型ハッシュ： 誤検出確率 d(p,q)>(1+ε)r を満たす p に対し、gi(p)=gi(q) となる確率は より、１個のバケットに入る、そのような（望ましくない）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)時間で計算可能と仮定） 定理： （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]

まとめ 近似文字列マッチング Don’t Care 記号つき近似文字列マッチング 局所性鋭敏型ハッシュ 補足 動的計画法により 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]