長さの制限付きギャップと文字クラスを含むパタンに対する..ppt

《長さの制限付きギャップと文字クラスを含むパタンに対する..ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、長さの制限付きギャップと文字クラスを含むパタンに対する照合アルゴリズムの改善九州大学附属図書館喜田拓也長さの制限付きギャップと文字クラス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法（Abrahamson1987,Wu

2、-Manber1992）→O(m

3、

4、+m/wn)正規表現パタンに対する文字列照合DFAへ変換→O(2m+n)時間NFAへ変換→O(m×n)時間PROSITEパタンに対する文字列照合アルゴリズムGaps-Shift-And法（NavarroandRaffinot2001）→O(Pmax/w×n)文字クラスを含んだパタン照合Shift-And法のアイデアパタンa-a-b-a-[bc]を検出するNFA012345baabacaababcaabacabテキスト:=Shift-And法の動作10000aa

5、babcaabacababcパターン:=aba[bc]aテキスト:=a-a-b-a-[bc]11000001001001000001000001000011000001001001000001100000000011010001010000100100100101101010010&ビット列BD((D<<1)

6、0m1)&B[tj]ギャップ付きShift-And法のアイデアパタンa-b-[cd]-x(1,3)-e-fを検出するNFA01248cabed7536fa=1b=3ba=2Gaps-S

7、hift-And法におけるNFAの状態遷移の模倣Shift-And法の状態更新D((D<<1)

8、0m1)&B[tj]遷移の模倣DD

9、((F(D&I))&F)01248cabed7536fF:00000100I:00100000FI:00111000Gaps-Shift-And法改良のアイデア5の状態に注目！01248cabed7536fD:00111000000111000000110000000100カウンタClk整数k1を2進数で表現したビット列を反転したビット列

10、で長さがlのものをClkとする。C85=(00000101)=111110101111111100000000k回インクリメント（+5）+1長さlog2(k+1)+1LongGaps-Shift-And法の計算Shift-And法の状態更新D’((D<<1)

11、0m1)&B[tj]新たにアクティブになったギャップ開始地点の検出A(F(D’&I))&F)カウンタのリセットC&A（ここでCはカウンタの初期ビット列）インクリメントされるカウンタの検出Dc(GA)&D（Gはカウンタの位置をマスクす

12、るビット列）カウンタのインクリメント(Dc+((Dc>>(lmax1))&I))&G状態更新の式DD’&G

13、C&A

14、(Dc+((Dc>>(lmax1))&I))&GパタンGaps-SALongGaps-SAa-x(0,2)-ba-x(0,10)-ba-x(0,100)-ba-x(0,1000)-b412102100246911a-x(1,2)-ba-x(5,10)-ba-x(50,100)-ba-x(500,1000)-b412102100241058508LongGaps-Shift-And法とGa

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