k 個のミスマッチを許した点集合マッチング・アルゴリズム 阿久津達也 京都大学　化学研究所 バイオインフォマティクスセンター

点集合合同性判定 最大共通部分点集合

研究の背景 （1） 合同性判定 最大共通部分点集合 [Akutsu,Tamaki,Tokuyama, 1998] 研究の背景　（1） 合同性判定 O(n log n) （３次元以下） [Atkinson, 1987] O(nd-2 log n) [Alt et al. 1988] O(n(d-1)/2 log n) (randomized) [Akutsu, 1998] O(nd/4+O(1) log n) (randomized) [Matousek, 1998] 最大共通部分点集合 [Akutsu,Tamaki,Tokuyama, 1998] ２次元で　O(n3.2 log n) ３次元で　O(n4.69 log n) ⇒　二つの問題の時間計算量の間に大きな差 (両者ともパターン認識などにおける基本的問題）

研究の背景 （2） ⇒ 点集合で誤りの個数を制限した場合は？ 文字列マッチング Exact マッチング： O(m+n) 研究の背景　（2） 文字列マッチング Exact マッチング：　O(m+n) 近似マッチング：　O(mn) k 個の誤りのみを許した場合： O(kn) ⇒　点集合で誤りの個数を制限した場合は？

本研究の結果 最大共通部分点集合問題においてマッチしない点の個数を k 以下とした場合の効率的アルゴリズム 数値列に対する近似マッチング

近似文字列マッチング 近似文字列マッチング 編集距離(edit distance)が最小のマッチを求める 距離＝置換(substitution)＋挿入(insertion)＋削除(deletion) 動的計画法により O(mn)時間（|P|=m, |Q|=n) 距離がk以下の時、 O(kn)時間 [Landau & Vishkin 1989] 動的計画法＋suffix tree

動的計画法による近似文字列マッチ

距離がk以下の場合の近似文字列マッチ L[d,e]： D[i,j]=e かつ j-i=d となる最大の行 i Suffix tree を用いて 　定数時間で実行可能 　⇒　O(kn) 時間

点集合マッチング問題: LCP-kDIFF 入力 d-次元空間上の点集合 P , Q (|P|=m, |Q|=n, m≦n) 非負整数 k 出力: 以下の等長変換 T （無い場合は No） （i.e., 共通部分に含まれない点の個数が高々 k 個）

1次元の場合（1）： mmsp(pi,qj) mmsp(pi,qj) 補題: O(n log n) 時間の前処理により、 |mmsp(pi,qj)|は O(1) 時間で計算可能 証明：Σ={ |pi+1 – pi|, |qj+1 – qj| }として suffix treeを構成

1次元の場合（2）： アルゴリズム

1次元の場合（3）： 計算量 定理1: 1次元 LCP-kDiff ⇒ O(k3 + n log n)時間 ランダムサンプリングの利用 各(pi0,qj0)あたり O(k)時間、 　全部で O(k2)個のペア　 ⇒ 　O(k3)時間 mmsp の前処理 ⇒　O(n log n)時間 ランダムサンプリングの利用 Pからランダムにサンプルすれば、その点は高確率でLCPに所属 ⇒ O(k)時間を節約可能 系1: 1次元 LCP-kDiff ⇒ 高確率で O((k2 + n) log n) 時間

2次元の場合（1）： 点の順序づけ 点に適切な順序 ⇒ suffix tree が利用可能 pi ≺ pi’ ⇔ θ(pi) < θ(pi’) or ( θ(pi) =θ(pi’) and | pi – p0| < | pi’ – p0| )

2次元の場合（2）： 計算量 定理2: 2次元LCP-kDiff ⇒ O(k3n4/3+ kn2 log n)時間 Pから O(k2) ペア　⇒ 一つのペアは LCP に所属 (p0,p1) と合同な Q のペア (q0,q1) の個数: O(n4/3) 各 ((p0,p1), (q0,q1)) あたり、O(k) 時間 ランダムサンプリングの利用 Pからペアをランダムにサンプルすれば、そのペアは高確率でLCPに所属 ⇒ O(k2)時間を節約可能 系3: 2次元 LCP-kDiff ⇒ 高確率で O(kn4/3 log n + n2log2n) 時間

3次元の場合（1）： 点の順序づけ 以下の情報を用いて順序づけ 平面 pi1, pi2, pi と、平面 pi1, pi2, pi3 のなす角度 pi - pi1 と pi2 - pi1 の内積 pi と直線 pi1 pi2 の距離

3次元の場合（2）： 計算量 定理3: 3次元LCP-kDiff ⇒ O(k4n1.8log n + k2n5/2 log2n) 時間 Pから O(k3) 個の三つ組　⇒ 一つは LCP に所属 (pi1, pi2 , pi3) と合同な Q の三つ組の個数: O(n1.8 log n) (pi1, pi2)と合同な Q のペアの個数: O(n3/2 log n) 各ペアについて suffix tree を構成: O(n log n) ランダムサンプリングの利用 Pから三つ組をランダムにサンプル ⇒ O(k3)時間を節約可能 系4: 3次元 LCP-kDiff ⇒ 高確率で O(k n1.8 log2n + n5/2 log3n) 時間

1次元数値列の近似マッチング (1) 入力： 数値列 P, Q 最大誤差 ε 出力： P との編集距離が k 以下の Q の位置 1次元数値列の近似マッチング　(1) 入力： 数値列 P, Q 最大誤差 ε 出力： P との編集距離が k 以下の Q の位置 　　　 ただし、pi と qｊ がマッチ ⇔ |pi-qj|<ε

1次元数値列の近似マッチング (2) 誤差としてミスマッチのみを許した場合 1次元数値列の近似マッチング　(2) 誤差としてミスマッチのみを許した場合 O(m1/2n log m)時間 [Amir, Farach, 1995] Convolution を利用

1次元数値列の近似マッチング (3) 定理４： 数値列の近似マッチング ⇒ O(k1/3m2/3 n log m) 時間 1次元数値列の近似マッチング　(3) Don’t careつき近似マッチング [Akutsu, 1995] Suffix tree が利用できないので、テーブルを利用 [Amir, Farach, 1995]との組合せで、以下が成立 定理４：　数値列の近似マッチング ⇒ 　　　　　　　　　O(k1/3m2/3 n log m) 時間

結論 課題 高次元の場合の検討 相似マッチの場合の検討 誤差を許した場合の検討