長さの制限付きギャップと 文字クラスを含むパタンに対する 照合アルゴリズムの改善

Presentation on theme: "長さの制限付きギャップと 文字クラスを含むパタンに対する 照合アルゴリズムの改善"— Presentation transcript:

1 長さの制限付きギャップと 文字クラスを含むパタンに対する 照合アルゴリズムの改善
九州大学附属図書館 喜 田 拓 也

2 長さの制限付きギャップと文字クラス PROSITEパタン 長さの制限付きギャップ 文字クラス（文字種） タンパク質検索で用いられるパタン
例： C-x(2,4)-C-x(3)-[LIVMFYWC]-x(8)-H-x(3,5)-H 長さの制限付きギャップ a以上、b以下のギャップ x(a, b), x(a)=x(a, a) 文字クラス（文字種） 文字の集合 [abc…]

3 これまでの手法 文字クラスに対する文字列照合アルゴリズム 正規表現パタンに対する文字列照合
Shift-And法 （Abrahamson 1987, Wu-Manber 1992） → O(m|| + m/w n) 正規表現パタンに対する文字列照合 DFAへ変換 → O(2m+n) 時間 NFAへ変換 → O(m×n) 時間 PROSITEパタンに対する文字列照合アルゴリズム Gaps-Shift-And法 （Navarro and Raffinot 2001） → O( Pmax/w×n)

4 文字クラスを含んだパタン照合 Shift-And法のアイデア
パタン a-a-b-a-[bc] を検出するNFA 1 2 3 4 5  b a c テキスト:= aababcaabacab

5 Shift-And法の動作 a-a-b-a-[bc] abc aababcaabacab a b [bc] 1 1 1 1 1 1 1 1
パターン:= abc テキスト:= aababcaabacab a b [bc] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ビット列 B & D  ((D << 1) | 0m1) & B[ tj ]

6 ギャップ付きShift-And法のアイデア
パタン a-b-[cd]-x(1,3)-e-f を検出するNFA 1 2 4 8  c a b e d 7 5 3 6 f  ba = 2 a = 1 b = 3

7 Gaps-Shift-And法における NFAの状態遷移の模倣
Shift-And法の状態更新 D  ((D << 1) | 0m1) & B[ tj ] 遷移の模倣 D D | (( F  ( D & I )) & F ) 1 2 4 8  c a b e d 7 5 3 6 f  F: I: F I:

8 Gaps-Shift-And法改良のアイデア
5 の状態に注目！ 1 2 4 8  c a b e d 7 5 3 6 f  D:

9 カウンタ Clk 整数 k1 を2進数で表現したビット列を反転したビット列で長さが l のものを Clk とする。 C85 =  ( ) = k 回インクリメント （+ 5） + 1 長さ log2(k+1) +1

10 LongGaps-Shift-And法の計算
Shift-And法の状態更新 D’  ((D << 1) | 0m1) & B[ tj ] 新たにアクティブになったギャップ開始地点の検出 A  ( F  ( D’ & I )) & F ) カウンタのリセット C & A （ここで C はカウンタの初期ビット列） インクリメントされるカウンタの検出 Dc  (G  A) & D （G はカウンタの位置をマスクするビット列） カウンタのインクリメント ( Dc + (( Dc >> (lmax  1)) & I )) & G 状態更新の式 D  D’ & G | C & A | (Dc + (( Dc >> (lmax  1)) & I )) & G

11 LongGaps-Shift-And法と Gaps-Shift-And法との要ビット数の比較
パタン Gaps-SA LongGaps-SA a-x(0, 2)-b a-x(0, 10)-b a-x(0, 100)-b a-x(0, 1000)-b 4 12 102 1002 6 9 11 a-x(1, 2)-b a-x(5, 10)-b a-x(50, 100)-b a-x(500, 1000)-b 10 58 508

12 まとめ NavarroとRaffinot[2001]が提案したGaps-Shift-And法を基に、長いギャップでも少ないビット列で計算可能なLongGaps-Shift-And法を開発した 実装・実験はこれから ・・・たぶん、遅い・・・（演算回数が2倍以上！） ギャップの下限a が上限b に近いと効果がない PROSITEパタンはギャップが短いのがほとんど (ToT)