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

近似文字列マッチング

出力： 以下の条件を満たす 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=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) に下げることが可能

領域がO(τn)で済む理由（？） ハッシュテーブルをそのまま記憶すると大きな領域が必要 （ただし、出次数１の頂点を覚えずに済むように接尾辞木のように表現することが必要？）

拡張と応用 実数データへの対応 ランダムな直線への射影+整数化 [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]

編集距離計算量の下限

編集距離 入力： 出力： x を y に変換するのに必要な最小の編集操作数 （ペアワイズの全域配列アラインメントと本質的に等価） 編集操作: (A) 文字の置換 (B) 1文字挿入 (C) 1文字削除 ED(x,y): 文字列 x, y 間の編集距離 x=ATGAT A T G C ー ED(x,y)=3 y=ACTCT 挿入 置換 削除 定理：編集距離はSETHのもとでO(n2-ε)時間で計算不可 [Backurs & Indyk, STOC 2015] PT(x,y): 文字列 x と、 y の連続部分文字列との最小編集距離 （近似文字列マッチングの誤差と本質的に等価）

SAT(充足可能性問題) 用語 ＳＡＴ k-SAT: すべての節が k 個以下のリテラルの論理和 リテラル： 変数もしくは変数の否定(NOT) 節： リテラルの論理和(OR) 充足可能： 節(集合)を真とする変数への 0-1 割り当てが存在 ＳＡＴ 入力： 節集合　S 問題： S は充足可能(すべての節を真とする割り当てが存在する)か? k-SAT: すべての節が k 個以下のリテラルの論理和

SETH（Strong Exponential Time Hypothesis） SATに関する結果（乱拓アルゴリズムを含む） 3-SAT: O(20.388n) [Hertli, SCICOMP, 2014] 4-SAT: O(20.555n) [Hertli, SCICOMP, 2014] k-SAT： 2(1-1/O(k))n時間 [Paturi et al., JACM, 2005] 一般の場合： 2(1-1/O(log(m/n)))n 時間 （m：節の個数）[Calabro et al., Proc. CCC, 2006] SETH n 変数のSATは、どの定数 ε>0 に関しても、2(1-ε)n時間では解けない（という仮説） 直交ベクトル問題 入力：　d次元0-1ベクトルの集合A, B　(|A|=|B|=N) 出力: x・y=0（内積が0）となる (x,y)∊A×B はあるか？ SETHが成立⇒この問題は O(N2-εd) 時間では解けない

SATから直交ベクトル問題への還元 解析 SATの変数を XA={x1,…, xn/2}と XB={xn/2+1,…,xn}に２分割 XA（resp., XB）へのすべての0-1割り当てについて この割り当てで充足される節を０、充足されない節を１として、それらを並べた0-1ベクトルを作成し、 そのベクトルの集合をA（resp., B）とする (|A|=|B|=N=2n/2) 解析

証明の方針 直交ベクトル問題を編集距離問題に還元 直交ベクトルが存在 ⇔ P1 が P2 中で閾値以下でマッチ 直交ベクトルが存在 ⇔ 編集距離が閾値以下 A, B の要素（d次元0-1ベクトル）を文字列に変換 P1 = Aから変換した文字列をつなげたもの P2 = Bから変換した文字列をつなげたもの＋α 直交ベクトルが存在 ⇔ P1 が P2　中で閾値以下でマッチ 直交ベクトル（から変換した文字列）でちょうど重なるように、ずらしてマッチ

証明の概略（１）： 0-1の文字列化 Aのベクトル中の0,1 ⇒ CG1(0), CG1(1), g Bのベクトル中の0,1 ⇒ CG2(0), CG2(1) 1-1 間の距離は大きく（3l0)、他のビット間の距離は小さい（l0 ） g と、B の0,1 間の距離はほんの少し大きい（ l0 +1）

証明の概略（２）： ベクトルの文字列化 a∊A, b∊B に対し、VG1(a), VG2(b) を以下のように構成 証明の概略（２）：　ベクトルの文字列化 a∊A, b∊B に対し、VG1(a), VG2(b) を以下のように構成 a,bが直交すれば、ED(VG1(a),VG2(b))=l+2l2+dl0 :=Es 直交しなければ、 ED(VG1(a),VG2(b))=Es+d :=Eu 　　（直交すれば CG どうしがマッチ、それ以外は g…g とマッチ）

証明の概略（３）：ベクトル集合の文字列化 A, B に対し、P1, P2 を下図のように構成 （|A|≦|B|） 直交する (a,b) があれば、PT(P1,P2)≦(|A|-1) Eu + Es なければ、 PT(P1,P2) = |A| Eu ⇒ P’1=3 |P’2| P13 |P’2| , P’2= P2 として ED(P’1,P’2) を計算

編集距離計算下限に関するまとめ 編集距離計算、ペアワイズアラインメント 補足：多くの結果（下限）が前後して出現 SETHが成立 ⇒ （任意のε>0に対し）O(n2-ε） 時間では不可能 補足：多くの結果（下限）が前後して出現 局所アラインメント: O(n2-ε) [Abboud et al., ICALP 2014] Dynamic Time Warping Distance: O(n2-ε ) [Abboud et al., FOCS 2015] Longest Common Subsequence (for k strings): O(nk-ε ) [上と同じ] 部分木同型性： O(n2-ε） [Abboud et al., SODA 2016] 文脈自由文法解析, RNA二次構造予測： O(nω-ε ) [Abboud et al., FOCS 2015] クリーク問題を還元（ωは行列乗算に関する係数） 確率文脈自由文法解析： O(n3-ε ) [Saha, FOCS 2015] （all pairs）最短経路問題を還元 順序木の編集距離計算: O(n3-ε ) [Bringmann et al., SODA 2018] （all pairs）最短経路問題、および、クリーク問題を還元 SETH を（妥当な仮定のもとで）証明する、もしくは、否定するのは重要な研究課題