輪講 第３回 Chapter 3 Exact Matching: A Deeper Look at Classical Methods 山田　崇 2002/10/25

Overview (1) Apostolico-Giancarlo の方法 (1986) BM 法の最悪の計算量に関するおはなし Cole による証明 (1994) 比較の回数は高々 4m 回． KMP 法の前処理 パターンが複数あるときのマッチング Aho-Corasick の方法 (1975)

Overview (2) マッチングの応用 正規表現を用いたパターンマッチ DNA，たんぱく質のマッチング ワイルドカードを含むマッチング 2 次元のマッチング 正規表現を用いたパターンマッチ

なぜ PowerPoint なのか? 論文構成法でプレゼンの講義がなくなった． 研究室の ノートPC，プロジェクタの使用方法の習得 「時間の制約」(マクドナルド先生) 人前でプレゼンする機会の減少 観衆がいらっしゃる中でプレゼンの練習をしたい 研究室の ノートPC，プロジェクタの使用方法の習得 アニメーション

Apostolico-Giancarlo 法

AG 法 概要 T 上のどの文字も，P 上のどれかの文字といったんマッチしたら，2 度比較されることはない 比較の回数は高々 2m すべての比較の結果は「マッチ」か「ミスマッチ」 ミスマッチは高々 m 回しか発生しない マッチも高々 m 回しか発生しない． 全体の計算量も O(m) ここでは AG 法をさらに改善したものを紹介 シフトの方法は BM 法をシミュレート BM 法がみつけるミスマッチはすべて発見 冗長なマッチを減らすことで比較回数を削減

Key Ideas アルゴリズムを phase ごとに分割(1) アルゴリズムを分割 分割したものを compare/shift phase と呼ぶ． 各 compare/shift phase には順番に 1, 2, …, q (≦ m) と番号をふる． それぞれのフェーズでの仕事 P の右端が T のある文字のところにある P と T を右から左に比較していく 「すべての P がマッチする」か「ミスマッチが見つかる」状態まで 2. を繰り返す P を BM 法のルールに従ってシフトし次 phase へ

Key Ideas アルゴリズムを phase ごとに分割(2) 先週導入した図を今回も利用 [Nakayama, 2002] compare/shift phase T の position 　　×○○○ 　　　　×○○○○ 　　　　　　　　×○○○ 1 2 3 ○：マッチ ×：ミスマッチ

Key Ideas BM 法からの修正(1) 長さ m の配列 M を用意する M( j ): P の suffix が T の [ j －M( j )＋1.. j ]の範囲に現れることを保証 各 phase ごとに M の要素は (少なくとも 1 つ) 書き換えられる P の suffix j ・K の決め方は後述 ・このあとのシフトはBM法といっしょ T × ○ ○ ○ ○ P M( j ) には k ≦ 4 を満たす k を代入

比較しなくても (過去の遺産から) 情報を得ることができる Key Ideas BM 法からの修正(2) N と M を利用してマッチ・ミスマッチを予測する 例: M( h ) = α，Ni = β，α > β のとき (下図) h j ここで× この範囲は○ α T i β P 比較しなくても (過去の遺産から) 情報を得ることができる

Key Ideas BM 法からの修正(3) さらにわかること Ni = i のとき Ni > i のとき ここに P が出現 h j 予測により○ 比較により○ ここで× j α T i β P h ミスマッチを予言できる 予測により○ 比較により○ ここで× j α T i β P

One phase in detail 詳細を述べるにあたっての準備 P の右端は T の j の位置にいるものとして，phase は始まる h = j i = n BM 法と同様に 右から左に向かって順番に比較する ミスマッチが見つかったら BM 法と同様にシフト P が T 中に見つかったら BM 法と同様にシフト シフトしたら その phase は終了

One phase in detail アルゴリズム(1) M(h) がまだ定義されていない，もしくは M(h) = Ni = 0 のとき T(h) と P(i) を下記に従って比較 T(h) = P(i) かつ i = 1 のとき T [h..j] に P が存在している M(j) = n としてシフトし，phase を終了する j T P みつかったぞー すでに○ ○

One phase in detail アルゴリズム(2) M(h) がまだ定義されていない，もしくは M(h) = Ni = 0 のとき T(h) と P(i) を下記に従って比較 T(h)=P(i) かつ i > 1 のとき h := h－1，i := i － 1 として同じ phase を繰り返す j T P ここはまだわからない すでに○ ○

One phase in detail アルゴリズム(3) M(h) がまだ定義されていない，もしくは M(h) = Ni = 0 のとき T(h) と P(i) を下記に従って比較 T(h)≠P(i) のとき ミスマッチが発生していることに他ならない M(j) := j － h として BM 法と同様のシフトを行い phase 終了 P の suffix j T P すでに○ ×

One phase in detail アルゴリズム(4) M(h) < Ni のとき P は T と [i － M(h) + 1.. n] の範囲でマッチしていることが予測できる i := i － M(h)，h := h － M(h) として繰り返す 予測により○ h ここはまだわからない j T P M(h) すでに○ Ni i

One phase in detail アルゴリズム(5) M(h) ≧ Ni かつ Ni = i > 0 のとき 予測によりP は T と [i － Ni + 1.. j] の範囲でマッチしている(＝ T のその範囲で P が現れる)ことがわかる M(j) := j － h としてシフト，phase 終了 予測により○ h j T P M(h) みつかったぞー すでに○ Ni i

One phase in detail アルゴリズム(6) M(h) > Ni かつ Ni < i のとき 予測によりP は T と [i － Ni +1 .. n] の範囲でマッチし， i － Ni でミスマッチすることがわかる M(j) := j － h としてシフト，phase 終了 予測により○ h 予測により× j T P M(h) すでに○ Ni i

One phase in detail アルゴリズム(7) M(h) = Ni かつ 0 < Ni < i のとき 予測によりP は T と [i － Ni +1 .. n] の範囲でマッチすることがわかる h := h － M(h), i := i － M(h) として同じ phase を繰り返す 予測により○ h ここはまだわからない j T P M(h) すでに○ Ni i

BM 法の計算量 Cole による解析

概要 BM 法の計算量が worst-case で O(m) となることを示す シフトは good suffix rule のみ使い，かつ P が T に現れない場合に O(m) となることを示して P が T に現れる場合にも O(m) となることを示し そのあと bad character rule も使った場合にもO(m) となることを示す

準備(1) 新しい変数の導入 AG 法のときと同様に BM 法を compare/shift phase に分割 phase i で si : phase の最後でシフトする量 ti : 比較してマッチした T の substring gi : 以前のphaseで比較されたことのある文字の数 g’i : phase i で初めて比較した文字の数 Σi(gi + g’i ) : 比較した延べ文字数→この値が O(m) であることを示すことが goal

準備(2) string に関する補題 βi:=βββ…βとおく(β: string) i 個 Lemma 1 γ，δを空ではない string とする．このとき，γδ＝δγが成り立つならば，ある string ρとある整数 i， j が存在して，δ＝ρi，γ＝ρjとなる． Lemma 1 【証明】|δ|＋|γ| に関する帰納法により示す． |δ|＋|γ|＝2 のとき: δ＝ρ，γ＝ρ，i ＝ j ＝1 のとき，またそのときのみγδ＝δγが成り立つ． 以下 |δ|＋|γ| > 2 のときについて考える． |δ| < |γ| ならば γδ＝δγより，δはγの prefix となる．γ＝δδ’ とおけば，γδ＝δγよりδδ’δ＝δδδ’．両辺左からδを取り除いても等号が成立．すなわちδ’δ＝δδ’．ここで，|δ’|＋|δ|＝|γ| < |δ| +|γ| であるから，帰納法の仮定よりあるρ，i，j が存在してδ＝ρi，δ’＝ρj．このときγ＝ρi + j． |δ|＝|γ| ならばδ＝γ＝ρ，i ＝ j ＝ 1．|δ| > |γ| のときの証明は省略．□

準備(3) semiperiodic とは string α が period βについて semiperiodic であるとは… αが string βの (空ではない) suffix (β全体でもOK)を含み，その後ろに 1 個以上 β が続くこと 例 アルファベット Σ ＝ {今，井，浩} string α＝井浩今井浩今井浩 は， period β＝今井浩 に対してsemiperiodic 井 浩 今 α βのsuffix β β

準備(4) prefix semiperiodic とは string αが period γ に関して prefix semiperiodic であるとは… αが 1 個以上の string γ のコピーを含み，その後ろには (空ではない) γの prefix (全体でもOK) が 1 つ続くこと 例 string α＝今井浩今井浩今井 は， period γ＝今井浩 に対して prefix semiperiodic

準備(5) semiperiodic と prefix semiperiodic ある string α が period βに関して semiperiodic ならば，また，そのときに限って，αはβと同じ長さを持つ period に関して prefix semiperiodic である． Lemma 例　string 今井今今井今今井今今井今今井 は，priod 今今井 に関して semiperiodic であり，period 今井今 に関して prefix semiperiodic である． text T において， pattern P が位置 p, p’(≧ p) の 2 箇所に出現するとき (ただし，p’ － p ≦ floor (n / 2))，P は period p’－p に関して semiperiodic である． Lemma

Cole の証明 (1) 本題に戻る Goal を再確認 Goal はΣi(gi + g’i ) が O(m) であることを示すこと Σi g’i ≦ m を示すのは簡単 どの文字も最初に比較できるのは 1 回限り Σi si ≦ m も定義より自明 シフト量の合計は高々m Σi gi ≦ 3m となることを今から示したい si ≧ gi /3 が各 phase i で成り立つことを示せばよい．

Cole の証明(2) T に P が現れない場合 i 番目の compare/shift phase を考える T の substring ti が P の suffix とマッチ P を si だけ右にシフト si ≧(| ti |＋1)/3のときは T のうち phase i で比較される文字すべてが過去に比較されたことのあるものだったとしても si ≧ gi /3 が成り立つ よって， si < (| ti |＋1)/3 のとき，すなわち | ti |＋1 > 3si のときのことについて以下で考える

Coleの証明(3) いくつかの約束ごと α: 長さsi の P の suffix β: ある j が存在して，α＝βj を満たすような最小の substring α＝β，j ＝1，というのもOK P:＝P[n－ |ti|＋1..n] 長さ|ti|＋1の P の suffix P のうち，phase i で比較される部分 (結果は問わない)

Coleの証明(4) good suffix rule のみ＋PはTにない場合 | ti |＋1 > 3si のとき，P，ti　はともにαに関して semiperiodic である． Lemma 2 【証明】 P を右端から順番に |α|＝si 個ずつ左側にはみ出るまで分けていく． |P|＝| ti |＋1 > 3si より，P には すくなくとも 3 つの区切りができるはずである(図)．phase i は si だけ P を右シフトすると終了する(次頁に続く) P α 区切り

Coleの証明(5) good suffix rule のみ＋PはTにない場合 (前頁から続く) si だけ右シフトしたあとの状態を考えると(図)， si とαの定義から，αは phase i の P から右シフトしたあとの(phase i + 1の) P の一部分となる． good suffix rule の定義より，図で phase i + 1 の P のうち，ti の下にある部分は，phase i において ti の下にある部分とマッチしなくてはならない． 以上の 2 つの事実から，si ごとに区切ったブロックは実は全部αであることがわかる． よって，P も ti もαに関して semiperiodic である．□ P α T ti × P

Coleの証明(6) 先の補題から言えること P と ti は αについて semiperiodic → βについても semiperiodic である． α＝βj より明らか

Coleの証明(7) さらに補題 | ti |＋1 > 3si のとき，各 phase h < i では，P の右端は ti 中のどのβの右端にもそろえられることはない． Lemma 3 【証明】ti はβに関して semiperiodic であることはすでに示した(図)．また，phase h ではP の右端が ti より右側に来ることはありえない．phase h で P の右端が ti中のあるβの右端にそろえられていると仮定して矛盾を導く． このとき，P の右側にあるβの数を q とおく．また，このとき，P は q|β|の位置にあると呼ぶことにする. (次頁に続く) T β ti

Coleの証明(8) 証明 (前頁から続く) phase h において，k’ を ti のジャスト左側の位置とし，その位置に対応するPの位置を k とする．このとき，P と T の比較は，ti の左側までマッチし，T(k’)とP(k)を比較したときにミスマッチする．なぜならば P と ti はβに関して semiperiodic である． 仮定より，phase h において P の右端はβのどらかの右端と位置がそろえられている． からである．(さらに続く) ここで× ここまで○ T β ti k’ P P k

P(k) ＝ P(1) ＝ P(1＋|β|) ＝ … ＝ P(1＋q|β|) Coleの証明(9) さらに証明 (前頁から続く) もっと詳しく言うと，P はβに関して semiperiodic であること，P の右端がちょうど q|β| にあることから，次の式が成り立つ． P(k) ＝ P(1) ＝ P(1＋|β|) ＝ … ＝ P(1＋q|β|) しかし P(k) ＝ P(1) と T(k’) を比較したときにミスマッチするので， P(k) ＝ P(1) ≠ T(k’) 従って，T(k’) と P(k) を比較したときにミスマッチが発生し，このミスマッチをもって phase h は終わるはずである． 以下の証明ではこの事実を利用する．(まだまだ続く)

Coleの証明(10) まだまだ証明 phase h でシフトが終わったあと，P の右端がどこにあるか考えると，次の 2 通り P の右端は q|β|より右側のどれかのβの右端にそろう P の右端は どれかのβの右端ではないどれかの文字にそろう 前者に関しては，シフト後に T(k’) に対応する文字は，ある r を持ってきて P(k r|β|) とかける．ところが，P はβに関して semiperiodic なので，P(k － r|β|)＝P(k) が成り立つ．このことは good suffix rule に矛盾する． 後者の場合，下図のように β＝γδ とかける(もっと続く) T β ti γ δ P β

Coleの証明(11) もっと証明 (前頁から続く) γはβの prefix，δはβの suffix であるから |γ|＋|δ|＝|β|．よって，γδ＝δγが成立し，β＝ρj とかける．これはβの定義に矛盾． いずれの場合にも矛盾が生じることから，このようは phase h は存在しないことが示せた．□

Coleの証明(12) 補題はあと2つ Lemma 4 | ti |＋1 > 3si のとき，各 phase h < i では，P は T 中の ti と高々 |β|－1 文字マッチする． Lemma 4 【証明】|β| 文字以上マッチしたとすると，P の右端は先の補題によりどのβの右端にもそろえられていないから，P の右側の |β| 文字はβの prefix γ のあとにβの suffix δ が続く形となって，|γ|＋|δ|＝|β|となる．先ほどと同様，これはβの定義に矛盾する．□

Coleの証明(13) 最後の補題 | ti |＋1 > 3si のとき，各 phase h < i では，もし P の右端が ti に含まれる文字とそろっていたとすると，P の右端は ti の左側の |β|－1 文字 のうちのどれかか，ti の右側 |β| 文字 のどれかにそろえられる． Lemma 5 【証明】石関さんのレジュメを参照してください．

Coleの証明(14) そしてこれが求めていた定理 P が T に現れないと仮定するならば，任意の phase i において si ≧ gi /3 Theorem 【証明】 | ti |＋1 > 3si のときのみ示せば十分．Lemma 5 より，phase h < i では，P の右端は ti の左 |β|－1 文字もしくは 右|β|文字のどれかにそろえられる．また，Lemma 4 より， phase h では高々|β| 回の比較しか行われない． よって，phase i では以前の phase で比較された可能性のある ti 中の文字は，左の |β|－1 文字か右の 2|β|文字である．すなわち gi ≦ 3|β| ＝ 3si．□

Coleの証明(15) 以上のことよりいえること P が T に現れないと仮定するならば，BM 法の比較回数は最悪でも高々4m． Theorem 【証明】 ・Σi g’i ≦ m を示すのは簡単 どの文字も最初に比較できるのは 1 回限り ・Σi si ≦ m も定義より自明 シフト量の合計は高々m ・Σi gi ≦ 3m となることをさっき示した． よって，全体の比較回数は， Σi(gi + g’i ) ≦ 4m となる．□

Galilの方法(1) PがTに現れるときは? Pのn文字とTのm文字がすべて同じ文字であるとき，比較の回数はΘ(mn) O(m) で抑えられる方法を Galil が考案 phase i で P の右端が T の 位置 k に対応する位置にあるとする． P と T を右から左に比較していって，比較が位置 s で終わったとする (結果は不問) phase i のシフトで P の左端が s の右となるようにgood suffix rule に従って，移動すると，phase i＋1 では P の prefix が T(k)までマッチする phase i＋１ では T(k) まで比較すればよい．

Galilの方法(2) BM法の計算量 Theorem Galil の方法を使えば，BM 法の比較回数は P が T に現れるかどうかに関係なく O(m) となる． Theorem

bad character rule を許す場合 計算量はO(m) good suffix rule，bad character rule の両方のシフトを用いたとしても，BM 法の worst-case の計算量は O(m) となる． Theorem

KMP 法の前処理 オリジナル版

前回紹介された前処理 Z-based method spi の値を Zi を用いて計算していた Ziを用いる方法は 概念的にシンプル さまざまな手法の前処理に応用が効く

KMP 法の前処理 オリジナル版 概要 sp1 ＝ 0 spi (i = 2,3,4,…n)を計算 spi (i ≦ k) が既知であるとして spk+1 の値を計算 α: 長さ spk の P のprefix αは P [1..k] の suffix と等しい P の prefix のうち最長のもの α’ α P spk k

準備 βの導入 x ＝ P[k+1] とする β＝βx とは 長さ spk+1 の P のprefix まさにこれから計算しようとしているもの βは P[1..k] の suffix とマッチし，その後ろにP(|β|＋1) が続く最長の P の prefix spk+1 を見つけることは string β を見つけることにほかならない β x β x P k

The easy case αの次が x である場合 P(spk+1) ＝ x (＝ P(k+1)) である場合 String αx は P の prefix であり，P[1..k+1] の suffix でもある spk+1 ≧ |αx| ＝ spk+1 は明らか spk+1 ＝ spk+1 は成り立つのか？ α’ x α x P k spk

The easy case spk+1 ＝ spk+1 任意の k について， spk+1 ≦ spk ＋1．さらにいうと， spk+1 ＝ spk ＋1．iff. P(spk+1) ＝ P(k+1) Lemma 6 【証明】 spk+1 > spk ＋1 だったとすると，βはαよりも長くなる．ところが，定義より βもP[1..k] の suffix であるから spk の定義に矛盾．よって， spk+1 ≦ spk ＋1． 以上より明らかにαの次の文字が x ならば spk+1 ＝ spk ＋1である．逆も成り立つ．□

The general case αの次が x ではない場合 P(spk+1) ≠ x (＝ P(k+1)) である場合 Lemma 6 より spk+1 < spk ＋1，すなわち spk+1 ≦ spk βはαの suffix (β＝αはOK) βはαの proper suffix (β＝αはNG) βは位置 k+1 で終わって長さ高々spk のsubstring βはα’の suffix βはαの suffix でもある β α’ β x α y P k spk

The general case βはαの prefix でもある P(spk+1) ≠ P(k+1) のとき βはαの suffix としても，P[|β|+1]＝x となるようなαの proper prefix のうち最長のものとしても現れる β x β y α’ β α P 拡大 k spk α x β spk y 再帰的に spk+1 を計算できる

spk+1 を求めるアルゴリズム x = P(k+1); v = spk; while (P(v + 1) != x && v != 0) { v := spv; } if (P(v + 1) == x) spk+1 = v + 1; else spk+1 = 0;

例 アルファベット Σ＝ {い, ま, ひ, ろ, し} いまひいまろいまひいましいまひいまろいまひいまひ α α’ k k+1 spk+1

パターンが複数の場合 Aho-Corasick 法

概要 exact set maching problem P がいくつかあるときに，それぞれが T に存在するかどうか調べる P の数 z それぞれの pattern に対して それぞれ linear time にマッチングすると O(n + zm) Aho-Corasick 法を用いれば O(n + m + k) k: P が T に現れる回数

準備 P ＝ {P1, P2, … Pi} パターンの集合

keyword tree P のkeyword tree とは，次の条件を満たすrooted directed tree K のこと それぞれの edge はちょうど 1 文字のラベルがつけられている 同じ node から出る任意の 2 つの枝には違ったラベルがついている P 中のすべての pattern Pi は K のある node v にmap される K の root からの v への path を辿ることで，Pi をつづることができ， K のすべての leaf は，P のある pattern に対応する

例 P ＝ {potato, poetry, pottery, science, school} p s o c t i h e a h t 5 1 e y 2 4 3

keyword tree の作り方 root だけの tree を用意する 1. に root から 長さ|P1|の path をのばす．これをK1とする path の最後には 「1」と書く Ki から Ki+1を作る Ki の root から始まる path で，Pi+1 の prefix にマッチするものを探す Pi+1 と完全にマッチした path があれば，path の終点となった node に 「i+1」 とかく path がなければ，最後にマッチしたところから新たに枝を伸ばして path をつくり，終点の node に 「i+1」 とかく 木の構築にかかる時間はO(n)

Naïve use of keyword trees for set matching 初期状態 T の位置は最初の文字 K の位置は root T の prefix にマッチするだけ 木を辿っていく 番号がついている node にたどり着いたら P 発見 行き場がなくなったら or T の最後まで行き着いたら 発見できなかったことを意味する 次の状態 T の位置は 2 文字目 最後まで繰り返す O(mn) 時間で結果が出る

例 P ＝ {potato, poetry, pottery, science, school} T＝potpotato p s o c t 5 1 e y 2 4 3

The speed-up: generalizing KMP Naïve method では T の初期位置 l を毎回 1 ずつ increment していくのみ 無駄な検索は省きたい spi をpattern が増えても対応できるように一般化 Aho-Corasick 法 O(n + k + m) P のどの pattern も P のほかの pattern の proper substring を持たないという仮定のもとでの方法 仮定を取り除いても計算量が変わらないことを示す

準備(1) node にラベルをつける K の各 node v にラベルをつける K の root から node v に至る path についている文字を順番につなげたもの L(v): node v につけられたラベル

例 P ＝ {potato, poetry, pottery, science, school} p s o c t i h e a h t v e n r o h c r y 5 1 e y 2 4 L(v) = pott 3

準備(2) lp(v) K 上の各 node v について， lp(v): P に属する，ある pattern の prefix となっている L(v) の proper substring のうち，最長のものの長さ 例: 石関さんの資料の p.8 P＝{potato, tattoo, theater, other}

準備(3) failure link K 上の各 node v について， 例: 石関さんの資料 p.8 nv: 長さ lp(v) の L(v) の suffix でラベル付けされた K 上の node directed edge v→nv を failure link と呼ぶ． 例: 石関さんの資料 p.8

The failure links speed up the search j :これから pattern 探そうとしている文字列の最初の位置 k: まさに今から調べようとしている文字の位置

アルゴリズム AC 法 j:= 1; k:= 1; w := K の root do { while (there is an edge (w, w’) labeled char. T(c)) { if (w’ is numbered by pattern i) { report that Pi occurs in T starting at position l; } w:= w’; c++; w:= nw; l:= c – lp(w); } while (c <= m);

アルゴリズム 補足 root で mismatch したら node v まで探索して行き場がなくなったら 例: 石関さんの資料 p.8 c を increment して root からやり直す node v まで探索して行き場がなくなったら string L(v) は nv の定義よりT[c－lp(v)..c－1]までマッチすることを保証 nvに飛んでnvから出る edge とT(c) を比較 例: 石関さんの資料 p.8 時間計算量 O(m) ← KMP 法のときと同様に示せる

Linear Preprocessing for the failure function K 上の各 node v について nv を見つける v が root から 1 文字分しか離れていないとき nv ＝ root ある k について，root から k 文字はなれた node まですべての nv がすでに計算されているとする v’: v の親 x: edge v’ → v についているラベル KMP 法の解析のときと同様に再帰的に調べる O(n) 時間ですべての探索が終了

The full Aho-Corasick algorithm: relaxing the substituting assumption P のどの pattern も P のほかの pattern の proper substring を持たないという仮定を取り払う． 次の lemma が成立 keyword tree K が node v から pattern i の番号がついた failure link を持っているとき，AC 法で node v に到着したら，pattern Pi が T に存在し，その出現の最後尾の位置は T[c] となる． Lemma 7

アルゴリズムを改良 j:= 1; k:= 1; w := K の root do { while (there is an edge (w, w’) labeled char. T(c)) { if (w’ is numbered by pattern i || there is a directed path of falure links from w’ to a node numbered with i) { report that Pi occurs in T starting at position l; } w:= w’; c++; w:= nw; l:= c – lp(w); } while (c <= m);

さらに改良 前処理に付け加え Output link を付け加えた場合 ある node v について， v からいくつかの failure link を辿ると番号がついた node に行き着くことがわかる場合には，v から直接リンクをはる このリンクを output link と呼ぶ Output link を付け加えた場合 全体で O(n + m + k) 時間

マッチングの応用 o Matching against a DNA or protein library of known patterns o Exact matching with wild cards o Two-dimensional exact matching

Matching against a DNA or protein library of known patterns (1) Sequence-tagged-site (STS) Human Genome Project が開発 200 から 300 の長さをもった DNA の両端 (それぞれ 20-30 の長さ) は，ゲノム全体で 1 度しか現れない STSs: STS の複数形 100,000 以上の長さを持つゲノムの任意の substring をみたときに STSs の中の少なくとも 1 つを含んでいる，そういう STS の組を見つけたい

Matching against a DNA or protein library of known patterns(2) expressed sequence tags (EST) 遺伝子から得られる STS ｍRNA，cDNA から 得られる 遺伝子の sequence の一部分からコーディングされるたんぱく質を見つけることができる． EST や STS には keyword tree, AC 法が有効 速い (DNA の長さに比例) 実際にはエラーが存在するので考える必要あり 詳しいはなしは16 章で

Exact Matching with wild cards 任意の 1 文字とマッチ pattern に wild card が入っていても T 中に出現する pattern をすべて検索可能 例: abφφcφ は，テキスト xabvcbababcax に2 度マッチする

DNA transcription factor DNA の特定の場所に bind するたんぱく質を transcription factor(転写因子)と呼ぶ DNA を RNA に転写 enhancing suppressing Zinc Finger: transcription factor のひとつ 例: CYS**CYS*************HIS**HIS CYS: アミノ酸 シスチン(1文字) HIS: アミノ酸 ヒスチジン(1文字) Leucine Finger: これも transcription factor

アルゴリズム Exact Matching with wind cards wild card を含まない P の substring の集合P＝{P1,P2,…Pk}，各 Pi の出現位置の左端を li とおく． AC 法を用いて, P の各Pi を探す T に Pi が位置 j を開始位置として出現するときは，C(j－li＋1)++ C の中で値が k になっているものを探す C(p) ＝k iff. P が T[p..] に出現している

Two-dimensional exact matching こんなときに使います 長方形の絵 T T より小さな長方形の絵 P T, P ともにデジタル化されている T 中の P の出現をすべて見つけたい 準備 m: T の総ポイント数 例: 640*480＝307,200 n: P の点の数 n’: P の列の数 それぞれの列は異なっていると仮定 のちにこの仮定は取り払う

アルゴリズム(1) 2 つの phase に分ける T の列(複数)の中のPの列(単数)の出現を探索 列ごとに終端記号をくっつけてTを1列にする．これをT’ とする AC 法で P の各列がT’ に出現するか探索 O(m+n)時間 P の i 列目 がT’中から発見されたら 開始位置(p, q) T と同じ次元の配列 Mの位置(p, q)にi を書き込む 仮定より，M の各要素には高々1回しか値が書き込まれない

アルゴリズム(2) 仮定を取り払う M を 行ごとに scan 重複のある行は同じ行だとみなしてラベルをつければ解決 linear exact matching algorithm を各行に対して適用 O(n’+m)＝O(n+m) 仮定を取り払う 重複のある行は同じ行だとみなしてラベルをつければ解決

正規表現のマッチング

Formal definitions 正規表現とは(アルファベット Σ) *のことを Kleene closure と呼ぶ Σに属する文字1文字は正規表現 εは正規表現 正規表現のあとに他の正規表現が続く表現は正規表現 ＋で正規表現をくっつけたものも正規表現 regexp*は正規表現 これ以外のものは正規表現ではない *のことを Kleene closure と呼ぶ

正規表現のマッチング 正規表現 R にマッチするT中の部分文字列を求めたい 有向グラフG(R)を作る 例 土井さんの資料 p.3 s が始点，終点は t R の文字数を n とすれば G(R) の枝数は高々 2n．

考え方 N(i): N(i－1)からラベルT(i)の枝1本と0回以上のε遷移でいくことのできるnode の集合 N(0) s s からε遷移可能なノード T のprefix T[1..i] が R とマッチ iff. N(i) が Node t を含む

計算量(結果のみ) N(i) i=0..mを計算する G(R) の枝数を e とすれば，O(me)時間 全体の計算量はO(mn)

後ろの部分も調べたい R にマッチする T の non-prefix substring を調べたい場合には，

おしまい