生物情報ソフトウェア特論 （３）近似文字列マッチング 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

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

近似文字列マッチング

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

近似文字列マッチング： 動的計画法アルゴリズム 例： 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$ についての接尾辞木を構成 P row+1 に相当する箇所 S[row+1..m+n+2] に対応する葉を x とする t row+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 ループの p row+1 =t row+d+1 を次のように変更 p row+1 = ＊ or t row+d+1 = ＊ or p row+1 =t row+d+1 ⇒ しかし、ループの実行が最悪で O(m) 時間かかる テーブルの 利用 ⇒ ループの実行が O(M) ⇒ 全体で O(kMn)

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

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

編集距離の埋め込み 埋め込み： X を距離 ρ 、 Y を距離 σ を有する距離空間とする時、以下を 満たす X から Y への関数 Φ を、 X から Y への歪み率 D の埋め込みとよ ぶ 定理： 長さ n の文字列に対する編集距離は O(n 2 ) 次元の L 1 空間 に歪み率 で埋め込み可能 [Ostrovsky, Rabani: J. ACM 2007] 定理： 長さ n の文字列に対する編集距離の L 1 空間への埋め込みの歪み率 は Ω(log n) [Krauthgamer, Rabani: Proc. SODA 2006] 定理： 長さ n の文字列に対する編集距離の log(n) O(1/ε) 近似は O(n 1+ε ) 時間 で計算可能 [Andoni et al.: Proc. FOCS 2010] 定理： 移動操作を許した場合、長さ n の文字列に対する編集距離は L 1 空 間に歪み率 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 ⊆ 2 d 、 b=(b 1,…,b d ) ∈ P とし、 F={h i | h i (b)=b i } とすると、 F は (r,r(1+ε),1-r/d,1-r(1+ε)/d)- LSH 関数族 証明： c と b の距離が r 以下なら、少なくとも d-r ビットは一致。 よって、 h i (c)=h i (b) となる確率は (d-r)/d=1-r/d 以上。 注意： 確率は h の選び方 のみについてとる

局所性鋭敏型ハッシュ： アルゴリズム F から k 個の関数の組合せを選ぶことにより G を構成 G={g | g(p)=(h i1 (p),…,h ik (p)), h ij ∈ F } G からランダムに τ 個選んだ関数を g 1,…,g τ とする 前処理： ハッシュテーブルの構成 g 1,…,g τ を用いて τ 個のハッシュテーブルを作成 各テーブルごとに、 P をハッシュ 探索： i=1 から i=τ まで以下を繰り返す バケット g i (q) の点をすべてチェックし、 d(p,q) ≦ r を満たす p があれば出力して終了 調べた点の合計が 4 τ を超えたら失敗して終了。 繰り返しが終了したら、 d(p,q) ≦ (1+ε)r を満たす点は無しと 出力。

局所性鋭敏型ハッシュ： アルゴリズムの 説明 探索： i=1 から i=τ まで以下を繰り返す バケット g i (q) の点をすべてチェックし、 d(p,q) ≦ r を満たす p があれば出 力して終了 調べた点の合計が 4 τ を超えたら失敗して終了。 繰り返しが終了したら、 d(p,q) ≦ (1+ε)r を満たす点は無しと出力。

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

d(p,q)>(1+ε)r を満たす p に対し、 g i (p)=g i (q) となる確 率は より、１個のバケットに入る、そのような（望ましく ない） p の個数の期待値は ((1/n)×n)=1 以下。 局所性鋭敏型ハッシュ： 誤検出確率 よって、 τ 個のバケットに入る、そのような p の個数 の期待値は τ 以下。 ⇒ 4τ 個以上の点を調べてしまう確率は (τ/4τ)=1/4 以下 。 ⇒ d(p,q) ≦ (1+ε)r を満たす p が存在しない場合に、 失敗してしまう確率は 1/4 以下。 (no を出力して欲しいのに失敗してしまう場合）

局所性鋭敏型ハッシュ： 計算量 領域計算量： O(dn+n 1+ρ ) 領域 点の情報： O(dn) 領域 ハッシュテーブル： O(τn)=O(n 1+ρ ) 領域 （点の情報は点へのポインタで記憶） 探索の時間計算量： O(dτ)=O(dn ρ ) 時間 （ハッシュ関数は O(d) 時間で計算可能と仮定） 定理： （ r,r(1+ε),α,β)- LSH 族が存在する問題に対し、 O(dn+n 1+1/(1+ε) ) 領域、 O(dn 1/(1+ε) ) 探索時間で （高確率で成功する）近似近傍探索が実行可能 O(log n) 個のコピーを作成すれば、失敗確率は O(1/n h ) に下げることが可能

実数データへの対応 ランダムな直線への射影 + 整数化 [Datar et al.: Proc. SoCG. 2004] R t 空間（ 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(nk 4 /m+m+k) 時間まで改善されている [Cole, Hariharan: SIAM J. Comput. 2002] 。編集距離は O(n+k 2 ) 時間で計算可能。 Steaming 型でも O(n+k 2 ) 時間らしい [Chakraborty et al., STOC 2016] k に関係なく O(nm 1-ε ) 時間でできるかは研究課題（ O(log 2 n) 程度の改善は既知 [Bille, Colton: TCS 2008] ）⇒ 最近、 Strong Exponential Time Hypothesis (SETH) のもとで否 定的に解決 [Backurs & Indik, STOC 2015] （第４回に解説） Don’t Care 文字つき近似文字列マッチングの改良は研究課題 編集距離の O(n) サイズ（もしくはそれに近いサイズ）の L 1 空間への低歪み埋め 込みは研究課題 LSH を利用しない近似近傍探索 [Andoni et al., SODA, 2014]