生物情報ソフトウェア特論 （１） 文字列マッチング・データ構造 生物情報ソフトウェア特論 （１） 文字列マッチング・データ構造 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義予定 第１回: 文字列マッチング・データ構造 第２回： たたみ込みとハッシュに基づくマッチング 第３回： 近似文字列マッチング 第１回:　文字列マッチング・データ構造 第２回：　たたみ込みとハッシュに基づくマッチング 第３回：　近似文字列マッチング 第４回：　配列解析 第５回：　木構造の比較：順序木 第６回：　木構造の比較：無順序木 第７回：　文法圧縮 第８回：　RNA二次構造予測 第９回：　タンパク質立体構造の予測と比較 第１０回：　固定パラメータアルゴリズムと部分k木 第１１回：　グラフの比較と列挙 第１２回：　ニューラルネットワークの離散モデル

講義目的、成績、教科書 講義目的 バイオインフォマティクスにおける主要な離散アルゴリズムについて理解する 乱拓アルゴリズム、近似アルゴリズム、固定パラメータアルゴリズムなど、現代的なアルゴリズム設計技法について理解する 計算時間および解の最適性もしくは近似精度に理論的保証のあるアルゴリズムを主対象とする 成績評価 出席5割、レポート5割 レポートは最終日の講義において出題 参考書（主に第4-9回） 主に第4-9回：　阿久津達也：バイオインフォマティクスの数理とアルゴリズム、共立出版、2007 第１,2回： Crochemore & Rytter: Jewels of Stringology, World Scientific, 2002 第12回： Anthony: Discerete Mathematics on Neural Networks, SIAM, 2001. その他は講義ノートにおいて該当トピックの最初に参考文献を記載

文字列マッチング問題

文字列マッチング問題（１） 例 入力 パターン文字列： テキスト文字列： 出力 を満たす、すべての j j=6 j=14 j=3 j=10

文字列マッチング問題（２） 単純アルゴリズム 一文字ずつ、ずらしながらチェック 例 全部で、4+1+1+2+4+1=13 回の比較

文字列マッチング問題（３） 命題： 単純アルゴリズムの時間計算量は Θ(mn) 証明： 時間計算量が O(mn) なのは明らか。 以下の例の場合、m(n-m+1) 回の比較が必要なので、Ω(mn) 時間。 ただし、平均的にはO(m+n)時間で動作することが知られている。

Knuth-Morris-Prattアルゴリズム

KMPアルゴリズム： アイデア アイデア： 以前の結果を利用 表 h[i]： 次を満たす最大の k （無い時は h[i]=0） アイデア：　以前の結果を利用 j=2 ではグレーのところだけをチェックすれば良い 表 h[i]： 次を満たす最大の k （無い時は h[i]=0）

KMPアルゴリズム： テキスト処理 KMPアルゴリズム （テキスト処理） 表 h[i]： 次を満たす最大の k （無い時は h[i]=0） 上記はマッチの有無のみを判定。すべての j の出力は宿題

KMPアルゴリズム： 実行例（１） 表 h[i]： 次を満たす最大の k （無い時は h[i]=0） a b p h[i] 1 2 3 4 i a b h[4]=3 a a a b h[4]=3 a a a b t a c b a c b a a a b h[3]=0 a c b

KMPアルゴリズム： 実行例（２） h[5]=0 Match! h[6]=2 h[2]=1 h[3]=0

KMPアルゴリズム： 実行例（３） h[12]=7 h[7]=4 h[4]=2 h[2]=1 h[1]=0

KMPアルゴリズム： 解析 定理： KMPアルゴリズム（テキスト処理）の時間計算量は O(n) 証明： 明らかに (#) にかかる時間が問題。その時間は ・ j が１増えた時のみ、i も１増える ・ i←h[i] を１回実行すると、i は少なくとも１減る ・ i は増えた回数以上に減ることはない より、O(n)。よって、全体の計算量も O(n) 解析のアイデア： 計算量のならし解析（amortized analysis） 　　　　　　　　　ここでは「稼いだ分しか使えない」が基本的アイデア

KMPアルゴリズム： パターン処理 表 h[i] の作り方 テキスト処理と似た手続き 自分自身とのマッチをとりながら、h[i] を作っていく 　　　　問題を O(m+n) 時間で解く

Boyer-Moore アルゴリズム

BMアルゴリズム： アイデア、例 例 KMPではテキスト中の文字を全て１回は調べている まず、c と d を比較。d は P 中には現れないので、P が d と重なることはない。 よって、次のようにずらして、最後の文字を比較。 P 中の c の位置に T 中の a があるので、P 中の最後の a が重なるようにずらす

BMアルゴリズム： 計算量 詳細を工夫することにより、最悪の場合を O(m+n) とすることができる 平均的には KMP よりずっと速い BM と似たアルゴリズムでは、平均的に O((n/m) logkm) 時間を達成（ただし、k はアルファベットのサイズ（文字種の個数））

Aho-Corasick アルゴリズム

複数文字列マッチング問題 入力 キーワード集合： テキスト文字列： 出力 を満たす、すべての j KMPやBMを k 回実行　⇒ O(kn) 時間 Aho-Corasick アルゴリズムなら、O(m+n) 時間 これ以降の講義では、アルファベットΣ（文字種の集合）は固定と仮定

Aho-Corasick アルゴリズム アイデア キーワード集合からDFA（決定性有限オートマトン）を構成 例：　W={ he, she, his, hers } 実線：　前方遷移関数 f 点線：　失敗関数 g 0 に戻る失敗関数 は省略

Aho-Corasick アルゴリズム： 実行例 W={ he, she, his, hers }, T = ushers u s h e r s 0 0 3 4 5 8 9 2 0 に戻る失敗関数は省略

Aho-Corasickアルゴリズム： テキスト処理 O(n)時間 W={ he, she, his, hers } T = ushers

Aho-Corasick アルゴリズム： 例題 W={ he, she, his, hers }, T = rhishers r h i s h e r s 0 0 1 6 7 4 5 8 9 3 2 0 に戻る失敗関数は省略

Aho-Corasick アルゴリズム： DFAの構成(1) パターン集合からトライを構成 前方遷移関数 g を作成 幅優先探索を用いて失敗関数 f を作成 最適化された失敗関数 h を作成（これは無くてもOK）

Aho-Corasick アルゴリズム： DFAの構成(2) O(m)時間 定理 Aho-Corasickアルゴリズムは 複数文字列マッチング問題を O(m+n) 時間で解く

接尾辞木

接尾辞木 (suffix tree) 文字列 S[1..n] の接尾辞(suffix) 接尾辞木 S[1..n], S[2..n], S[3..n], ・・・, S[n-1..n], S[n..n] 接尾辞木 文字列のすべての 接尾辞から構成されるトライ（trie） S[n+1]=$ を追加し最後尾を表す （以降は $ を追加後に n 文字とする） ただし、子が1個しか ない頂点は縮約 S=aabbccdabbca$ の接尾辞 $ a$ ca$ bca$ . abbccdabbca$ aabbccdabbca$

接尾辞木の応用： パターン検索 テキスト文字列の接尾辞木を構成（１回のみ） パターン文字列の入力の毎に、根から一致する文字を順にたどる パターン文字列長に比例する時間（O(m)時間）で検索が終了 テキスト文字列長に無関係　⇒ データベース検索に有用

接尾辞木の応用： Longest Common Substring ２個の文字列 S1, S2 に共通に出現する最長の連続部分文字列の検出 「k文字ずらしては一致する部分をチェックする」というアルゴリズムではO(|S1|・|S2|)時間 接尾辞木を用いれば 線形時間（なお、接尾辞木も線形時間で構築可能） S=S1#S2$ の接尾辞木を作成 ⇒ #を含む葉へのパスと含まない葉へのパスを持つ頂点をマーク ⇒ 根からの文字数最大のマークつき頂点を探す S1=aabbcc S2=abbdd S=aabbcc#abbdd$

接尾辞配列 (suffix array) 接尾辞木と似た情報をより簡潔に表現 もとの文字列の接尾辞をソートし、接尾辞の開始位置のみを格納した配列（図中のSA） 文字列 S SA ソートした接尾辞

接尾辞配列の性質 接尾辞木があれば簡単に構成できるが、接尾辞木を作らなくても O(n) 時間で直接構成可能 部分文字列検索を、単純な二分探索法で O(m log n)時間で実行可。より精密な方法を使えば、O(m+log n）時間で実行可。 その他、接尾辞木でできる多くの操作が接尾辞配列でも可能（ただし、配列以外に付加的な情報が必要になる場合もある） 部分文字列検索の例： P=abraca a: (10,7,0,3,5) ⇒ ab: (7,0) ⇒ abr: (7,0) ⇒ abra (7,0) ⇒ abrac (0)

Burrows-Wheeler（BW）変換 例で示す：　S=abracadabra$ （$は終端を意味） この文字列を巡回させた文字列をすべて生成し、ソートし、終端の文字を並べたものが変換後の文字列 ソート ard$rcaaaabb

BW変換： 逆変換 変換後の文字列 逆変換：アイデア S=abracadabra$ 逆変換：方法 この作業を繰り返す 同じ文字が連続して並ぶことが多い ⇒ データ圧縮に有利 もとの文字が（同じ回数だけ）出現 終端 始端 逆変換：アイデア ソート後の巡回文字列の終端（BW変換）と始端の文字を並べる（文字には順番に番号を付加） 同じ行の（終端、始端）はS中で連続して出現 S=abracadabra$ 逆変換：方法 始端を並べた文字列を、BW変換後の文字をソートして作成 左側が$である行を探す⇒右側（a3）がSの1番目 左側がa3である行を探す⇒右側（b2）がSの2番目 左側がb2である行を探す⇒右側（r2）がSの3番目 この作業を繰り返す

始端と終端で順番が保存される理由 終端 始端 これをソートしたもの の末尾が a になる ので、 始端と終端で a の 順番が保存される

まとめ（１） 文字列マッチング： 線形時間で可能 補足 KMPアルゴリズム： 失敗関数の利用 文字列マッチング：　線形時間で可能 KMPアルゴリズム： 失敗関数の利用 Boyer-Mooreアルゴリズム：パターンの最後から検索 Aho-Corasickアルゴリズム：オートマトンを構成 補足 平均的には線形時間より高速に可能 近年では圧縮文字列の検索が盛んに研究 Aho-Corasick では O(log |Σ|)だけアルファベットサイズに依存していたが、前処理（DFAの構成）に関しては依存しないアルゴリズムも存在 [Dori & Landau: Inf. Proc. Lett. 2006]

まとめ（２） 接尾辞木 BW変換 接尾辞配列 補足 接尾辞集合をコンパクトに表現 線形時間で構成可能 文字列をコンパクトに表現、圧縮にも有効、高速な検索が可能 接尾辞配列 接尾辞木と同様の目的、よりコンパクト 補足 近年ではコンパクトかつ検索その他を用意にする簡潔データ構造(succinct data structure)に関する研究が盛んに行われている