長さの制限付きギャップと 文字クラスを含むパタンに対する 照合アルゴリズムの改善 九州大学附属図書館 喜 田 拓 也
長さの制限付きギャップと文字クラス 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…]
これまでの手法 文字クラスに対する文字列照合アルゴリズム 正規表現パタンに対する文字列照合 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)
文字クラスを含んだパタン照合 Shift-And法のアイデア パタン a-a-b-a-[bc] を検出するNFA 1 2 3 4 5 b a c テキスト:= aababcaabacab
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) | 0m1) & B[ tj ]
ギャップ付き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 ba = 2 a = 1 b = 3
Gaps-Shift-And法における NFAの状態遷移の模倣 Shift-And法の状態更新 D ((D << 1) | 0m1) & B[ tj ] 遷移の模倣 D D | (( F ( D & I )) & F ) 1 2 4 8 c a b e d 7 5 3 6 f F: 00000100 I: 00100000 F I: 00111000
Gaps-Shift-And法改良のアイデア 5 の状態に注目！ 1 2 4 8 c a b e d 7 5 3 6 f D: 00111000 00011100 00001100 00000100
カウンタ Clk 整数 k1 を2進数で表現したビット列を反転したビット列で長さが l のものを Clk とする。 C85 = ( 0 0 0 0 0 1 0 1) = 1 1 1 1 1 0 1 0 k 回インクリメント （+ 5） 1 1 1 1 1 1 1 1 + 1 0 0 0 0 0 0 0 0 長さ log2(k+1) +1
LongGaps-Shift-And法の計算 Shift-And法の状態更新 D’ ((D << 1) | 0m1) & 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
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
まとめ NavarroとRaffinot[2001]が提案したGaps-Shift-And法を基に、長いギャップでも少ないビット列で計算可能なLongGaps-Shift-And法を開発した 実装・実験はこれから ・・・たぶん、遅い・・・（演算回数が2倍以上！） ギャップの下限a が上限b に近いと効果がない PROSITEパタンはギャップが短いのがほとんど (ToT)