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

講義予定 第１回: 文字列マッチング・データ構造 第２回： たたみ込みとハッシュに基づくマッチング 第３回： 近似文字列マッチング 第１回:　文字列マッチング・データ構造 第２回：　たたみ込みとハッシュに基づくマッチング 第３回：　近似文字列マッチング 第４回：　配列解析 第５回：　木構造の比較：順序木 第６回：　木構造の比較：無順序木 第７回：　文法圧縮 第８回：　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 と T の距離が k ⇔ P と T の誤差が k

近似文字列マッチング： 動的計画法アルゴリズム 例： P=caab, T=bccabad ⇒ 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={gi | gi(p)=(hi,1(p),…,hi,k(p)), hi,j∈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] 。編集距離はO(n+k2)時間で計算可能。Steaming型でもO(n+k2)時間らしい[Chakraborty et al., STOC 2016] k に関係なく O(nm1-ε) 時間でできるかは研究課題（O(log2n)程度の改善は既知 [Bille, Colton: TCS 2008]）⇒Strong Exponential Time Hypothesis (SETH)のもとで否定的に解決[Backurs & Indik, STOC 2015]（第４回に解説） Don’t Care文字つき近似文字列マッチングの改良は研究課題 編集距離の O(n)サイズ（もしくはそれに近いサイズ）のL1空間への低歪み埋め込みは研究課題 LSH を利用しない近似近傍探索 [Andoni et al., SODA, 2014]