k 個のミスマッチを許した点集合 マッチング・アルゴリズム 阿久津達也 京都大学 化学研究所 バイオインフォマティクスセンター 点集合合同性判定 P Q 最大共通部分点集合 P Q LCP k=7 研究の背景 (1) 合同性判定 O(n log n) (3次元以下) [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] 2次元で O(n3.2 log n) 3次元で O(n4.69 log n) ⇒ 二つの問題の時間計算量の間に大きな差 (両者ともパターン認識などにおける基本的問題) 研究の背景 (2) 文字列マッチング Exact マッチング: O(m+n) 近似マッチング: O(mn) k 個の誤りのみを許した場合: O(kn) ⇒ 点集合で誤りの個数を制限した場合は? Exact Matching ACGT AAA C G T C G Approximate Matching P k=3 AG - CAT Q AA C T C - T G 本研究の結果 最大共通部分点集合問題においてマッチしない点の個 数を k 以下とした場合の効率的アルゴリズム 数値列に対する近似マッチング 1次元 determ 本研究 inistic 既存研究 本研究 rando mized 既存研究 k3 n 2次元 3 1.34 k n kn 3次元 2 k n k n 4 1.8 2 n3 n 3 .2 n 4.69 k n k n1.34 n 2 k n1.8 n 2.5 2 n 2 n 2 .2 n 2.69 2.5 近似文字列マッチング 近似文字列マッチング 編集距離(edit distance)が最小のマッチを求める 距離=置換(substitution)+挿入(insertion)+削除(deletion) 動的計画法により O(mn)時間(|P|=m, |Q|=n) 距離がk以下の時、 O(kn)時間 [Landau & Vishkin 1989] 動的計画法+suffix tree Exact Matching ACGT AAA C G T C G Approximate Matching P k=3 AG - CAT Q AA C T C - T G 動的計画法による近似文字列マッチ D[i 1, j ] 1 D[i, j ] min D[i, j 1] 1 D[i 1, j 1] (1 ( p , q )) i j C A A T G C C A T A 0 0 0 0 0 0 0 1 1 0 0 1 1 1 2 2 1 1 0 1 1 3 3 2 2 1 1 1 4 4 3 3 2 1 2 A 1 0 A 0 1 2 1 1 C A A T GCC A - T A 距離がk以下の場合の近似文字列マッチ L[d,e]: D[i,j]=e かつ j-i=d となる最大の行 i for e 0 to k do for d e to n do L[d , e 1] 1 row max L[d 1, e 1] L[d 1, e 1] 1 while ( prow 1 t row 1 d ) do row row 1 L[d , e] row Suffix tree を用いて 定数時間で実行可能 ⇒ O(kn) 時間 C A A T G C C A T A 0 0 0 0 0 0 0 1 1 0 0 1 1 1 2 2 1 1 0 1 1 3 3 2 2 1 1 1 4 4 3 3 2 1 2 L[2,0]=2 L[2,1]=3 L[2,2]=4 d=2 点集合マッチング問題: LCP-kDIFF 入力 P d-次元空間上の点集合 P , Q (|P|=m, |Q|=n, m≦n) 非負整数 k 出力: 以下の等長変換 T (無い場合は No) Q LCP | Τ ( P) Q | は最大、かつ、 (m n k ) / 2 以上 (i.e., 共通部分に含まれない点 の個数が高々 k 個) k=7 1次元の場合(1): mmsp(pi,qj) mmsp(pi,qj) pi,qjから始まる合同な部分列組で最大長のもの 補題: O(n log n) 時間の前処理により、 |mmsp(pi,qj)|は O(1) 時間で計算可能 証明:Σ={ |pi+1 – pi|, |qj+1 – qj| }として suffix treeを構成 P p1 p2 p7 k=5 Q q1 q2 q7 q8 mmsp(p2, q1) 1次元の場合(2): アルゴリズム for all (i0 , j0 ) such thati0 j0 k do k ' i0 j0 2; i i0 ; j j0 ; Let T be a rigid motionsuch thatT ( pi0 ) q j0 ; while k ' k do h | m m sp( pi , q j ) |; find theminimumi such thati' i h and (j' )(T ( pi ' ) q j ' ); k ' k '(i 'i h) ( j ' j h); i i' ; P p1 p2 j j'; p7 k=5 Q q1 q2 q8 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| ) p5 p4 p3 θ p1 p6 q1 q8 q3 q2 q0 q7 p2 p0 p7 q4 q5 q6 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 の距離 p i3 pi q j3 p i2 p i1 q j2 q j1 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 の位置 ただし、pi と qj がマッチ ⇔ |pi-qj|<ε q2 p1 q1 q3 q4 q5 p2 q6 q7 p4 p3 1次元数値列の近似マッチング (2) 誤差としてミスマッチのみを許した場合 O(m1/2n log m)時間 [Amir, Farach, 1995] Convolution を利用 q2 p1 q1 q3 q4 p2 p4 q5 q6 p3 q7 1次元数値列の近似マッチング (3) Don’t careつき近似マッチング [Akutsu, 1995] Suffix tree が利用できないので、テーブルを利用 [Amir, Farach, 1995]との組合せで、以下が成立 定理4: 数値列の近似マッチング ⇒ O(k1/3m2/3 n log m) 時間 pi P Q qj 結論 1次元 determ 本研究 inistic 既存研究 本研究 rando mized 既存研究 k3 n 2次元 k 3 n1.34 k n2 k 4 n1.8 k 2 n2.5 n3 n 3 .2 n 4.69 k2 n k n1.34 n 2 k n1.8 n 2.5 n2 n 2 .2 n 2.69 課題 3次元 高次元の場合の検討 相似マッチの場合の検討 誤差を許した場合の検討
© Copyright 2025 ExpyDoc