阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
透過的データ圧縮 Transparent Data Compression
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
4.3 マージソート.
情報生命科学特別講義III (1) 文字列マッチング
LZ圧縮回路の設計とハード・ソフト 最適分割の検討 電子情報デザイン学科 高性能計算研究室 4回生 中山 和也 2009/2/27.
簡潔データ構造 国立情報学研究所 定兼 邦彦.
ヒープソートの演習 第13回.
アルゴリズムイントロダクション第2章 主にソートに関して
アルゴリズムとデータ構造 第8回 ソート(3).
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
情報生命科学特別講義III (8)木構造の比較: 順序木
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
On the Enumeration of Colored Trees
Problem G : Entangled Tree
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(3) + 数理談話会 木構造および画像データの文法圧縮
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
第10回 ソート(1):単純なソートアルゴリズム
データ構造とアルゴリズム 分割統治 ~ マージソート~.
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
エージェントを管理するボスの苦悩 問題 n人のエージェントを部下に持つボスがいる. エージェントは出張・帰還を頻繁に繰り返す.
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
データ構造とアルゴリズム論 第7章 探索のアルゴリズム
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
二分探索木によるサーチ.
データ構造とプログラミング技法 (第10回) ー文字列照合(KMP法、BM法)ー.
2009/10/16 いろいろなデータ構造 第3講: 平成21年10月16日 (金) 4限 E252教室 コンピュータアルゴリズム.
生物情報ソフトウェア特論 (1) 文字列マッチング・データ構造
k 個のミスマッチを許した点集合マッチング・アルゴリズム
情報工学概論 (アルゴリズムとデータ構造)
生命情報学入門 配列のつなぎ合わせと再編成
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
情報生命科学特別講義III (2)文字列データ構造
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
九州大学大学院 情報学専攻特別講義 (3) 配列解析
分子生物情報学(2) 配列のマルチプルアライメント法
アルゴリズムとプログラミング (Algorithms and Programming)
先進的計算基盤システムシンポジウム SACSIS2007併設企画 マルチコアプログラミングコンテスト 「Cellスピードチャレンジ2007」
情報生命科学特別講義III (13) 固定パラメータアルゴリズムと 部分k木
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
プログラミング 4 整列アルゴリズム.
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズム論 (第12回) 佐々木研(情報システム構築学講座) 講師 山田敬三
プログラミング 4 木構造とヒープ.
九州大学大学院 情報学専攻特別講義 (6) 固定パラメータアルゴリズムと 部分k木
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
文法と言語 ー文脈自由文法とLR構文解析ー
第16章 動的計画法 アルゴリズムイントロダクション.
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2011年6月28日
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 2013年7月2日
平面走査法を使った 一般線分の 交点列挙アルゴリズム
4.プッシュダウンオートマトンと 文脈自由文法の等価性
ヒープソート.
生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木
生物情報ソフトウェア特論 (4)配列解析II
プログラミング 4 文字列.
参考:大きい要素の処理.
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
Presentation transcript:

阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター 生命情報学特論 (2)文字列データ構造 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

接尾辞木

接尾辞木 (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$

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

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

接尾辞木の構成:単純な方法 接尾辞木の葉の数は n 個 ⇒ 接尾辞木の頂点数、枝数はO(n) 枝の文字列は S 中の位置で記憶 ⇒ 接尾辞木は O(n)領域 接尾辞木の構築法  (単純な方法) i が1から n まで S[i…n] を1個ずつ追加しながらトライを作成 子が1個しかない頂点を縮約 時間計算量 1個の追加にO(n)時間   ⇒全部の追加にO(n2)時間 縮約もO(n2)時間 ⇒ 全体でO(n2)時間

Ukkonenアルゴリズム [Ukkonen: Algorithmica 1995]

Ukkonenアルゴリズム:アイデア オンライン・アルゴリズム 接尾辞木の簡潔な表現 接尾辞リンクの活用(後で説明) S の最初の文字から始め、1文字ずつ文字を読み込む i 文字目を読み込む度に、 S[1..i] の接尾辞木に更新 接尾辞木の簡潔な表現 そのまま接尾辞木を保持すると更新のたびに多くの時間が必要   ⇒  $ のみからなる枝は持たない 接尾辞リンクの活用(後で説明) ⇒ 線形時間アルゴリズム

Ukkonenアルゴリズム:基本版 for i←1 to n-1 do for j←1 to i+1 do S[1] に対応する接尾辞木 T1 を構成; for i←1 to n-1 do for j←1 to i+1 do S[j..i] に一致する根からのパスをたどる; 次の位置に文字 S[i+1] がなければ枝を追加; (更新後の接尾辞木を Ti+1 とする) 1回の S[j..i] のチェックに O(n) 時間、全部で O(n2) 回のチェック ⇒ O(n3) 時間 S[i] の次が葉の場合は、枝を追加しない (葉は最後の文字に対応するので、枝につく文字が増えても何もしなくて良い)

Ukkonenアルゴリズム:文字追加の規則 S[i+1]の追加の規則 規則1: S[j…i] に対応する根からのパスが葉で終われば、その枝のラベルの最後に S[i+1] を追加 (ただし、実際は何もしない) 規則2: S[i+1] に対応する葉も枝もなければ、S[i+1]をラベルにもつ新たな枝と、新たな内部頂点を追加 規則3: S[i+1] に対応する枝があれば、何もしない 規則1 規則2 規則3

Ukkonenアルゴリズム:規則の性質 補題: 規則3が一度適用されたら、j’>j において S[j’..i] は調べる必要はない (S[j’..i] へのS[i+1]の追加は葉の伸長により自動的に対応) 証明: S[j’..i+1] は S[j..i+1] の接尾辞なので、 S[j..i+1] に対応する根からのパスがあれば、 S[j’..i+1] に対応するパスも存在 ⇒ 規則 3 が適用されたらステップiにおいて、それ以降のjをチェックしない 補題: S[j..i] のパスをたどって S[i+1] に対応する枝が新たに追加されたらば、i’>i において S[j..i’] を調べる必要はない 証明: 追加された枝の最後のラベルは常に S[i’+1] に対応 ⇒ 規則 2が適用されたら、以降のすべてのステップにおいて、そのjをチェックしない 上記補題から、S[j..i+1] のチェックは以下のように行えば十分 i: S[ji+1..i+1], S[ji+2..i+1], …, S[ji+1+1..i+1] i+1: S[ji+1+1..i+2], S[ji+1+2..i+2], …, S[ji+2+1..i+2] i+2: S[ji+2+1..i+3], S[ji+2+2..i+3], …, S[ji+3+1..i+3] i+3: S[ji+3+1..i+4], S[ji+3+2..i+4], …, S[ji+4+1..i+4]        …

Ukkonenアルゴリズム:改良版 1回の S[j..i] のチェックに for i←1 to n-1 do O(n) 時間、 空の接尾辞木 T1 を構成; j1←0; for i←1 to n-1 do すべての葉を延長; for j←ji+1 to i+1 do S[j..i] に一致する根からのパスをたどる; if 次の位置に文字 S[i+1] がある(規則3) then    ji+1←j-1; break; 規則2を適用; ji+1←j 1回の S[j..i] のチェックに O(n) 時間、 全部で O(n) 回のチェック ⇒ O(n2) 時間 葉がすべて先に延長されている ので、規則1の適用はない 規則3 規則2 規則2

Ukkonenアルゴリズム:接尾辞リンク 接尾辞リンク: x を文字、α を文字列とする。v をパスラベルが xα である内部頂点とする。パスラベルが α である内部頂点を w とする時、 v の接尾辞リンク s(v) は s(v)=w (αが空の時、s(v)は根) 補題: v を接尾辞木の内部頂点とすると、s(v) は必ず存在 証明: v が内部頂点なので、xαyβ と xαzγ という接尾辞があるはず(y≠z)。よって、αy、αz というパスラベルも存在し、α をパスラベルとする内部頂点が存在。 パスラベル: 根から頂点までのパスの枝のラベルを連結した文字列 接尾辞リンクは葉にも定義可能

Ukkonenアルゴリズム:接尾辞リンクの利用 接尾辞リンクをたどると、 S[j..i] を根から毎回たどらなくても、木の更新ができる。 枝を追加して新たな内部頂点ができる度に、接尾辞リンクを新たに追加。 例(下図): Ti の構築が終了した時点で、ピンクの d を参照。(ピンクの d は S[ji+1..i] に対応。実際には、直前の頂点を記憶(d の位置は ji から計算可能)) Ti+1 の構築のために、cada, ada, da, a を追加する(他は葉をのばせばよい)。 接尾辞リンクをたどりながら、d で終わる文字を見つけ、その下に頂点を挿入。 最後の a (ピンクの a)は規則3により追加の必要がない。 この a が次の S[ji+1+1..i+1] に対応。 Ti Ti+1

Ukkonenアルゴリズム:接尾辞リンクの利用 根まで至らずに接尾辞リンクをたどるのが終わる場合(規則3が適用)の例 S=bdbeabdabcabe (葉の伸長部分は省略)

Ukkonenアルゴリズム:枝の経由法 前の図では、各内部頂点から1文字たどるだけで目的の位置にたどりつけたが、場合によっては何文字もたどることが必要。 しかし、枝を1本たどるのは定数時間で可能(最初の文字だけ見てどの枝を選べばよいかわかれば、接尾辞の性質により他の文字は一致)。 もちろん、場合によっては複数の枝を経由することも必要であるが、計算量の ならし解析により、全部で O(n) 回の経由で済むことを示すことができる (詳細は省略)。

Ukkonenアルゴリズム:$の追加 定理: 接尾辞木は線形時間で構成可能 最後に $ を追加し、接尾辞木を完成させる。 $ の追加は(これまでに出現していない)新たな文字を最後尾に追加するのと全く同じ。 定理: 接尾辞木は線形時間で構成可能

Burrows-Wheeler変換 参照: [岡野原: 情報処理, 2012]

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 の 順番が保存される

BW変換: 部分文字列検索 S=abracadabra$ 以下の関数(高速に計算可能)を利用 C(x): ソート後の表における、文字 x を先頭とする最初の接尾辞の位置 rankx(B,i): B[1…i-1] 中に出現する文字 x の個数 B 接尾辞 検索アルゴリズム P=bra の場合の(sp,ep) の変化 (1,13) ⇒ a ⇒ (2,7) ⇒ r ⇒ (11,13)⇒b⇒(7,9) P=braa の場合の(sp,ep)の変化 (1,13) ⇒ a ⇒ (2,7) ⇒ a ⇒ (3,3) ⇒ none C(a)=2, C(b)=7, C(c)=9, C(d)=10, C(r)=11 行iにおいて、B [i]は接尾辞の1個前の文字

BW変換: 部分文字列検索の例 S=abracadabra$ (2,7) (7,9) (11,13) C(b)=7 C(c)=9 C(d)=10 (2,7) a の前の r は、B中で 「最初から2番目まで」 だけであることがわかる (7,9) C(r)=11 (11,13) P=bra の時の(sp,ep) の変化 sp ep (1,13) ⇒ C(a)+ranka(B,1)=2+0=2 C(a)+ranka(B,13)=2+5=7 (2,7) ⇒ C(r)+rankr(B,2)=11+0=11 C(r)+rankr(B,7)=11+2=13 (11,13) ⇒ C(b)+rankb(B,11)=7+0=7 C(b)+rankb(B,13)=7+2=9 出現順が保存されることも利用 (sp,ep-1) がS[i..m] とマッチしている範囲

接尾辞配列

接尾辞配列 (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)

接尾辞配列作成の線形時間アルゴリズム(1) DC3アルゴリズム[Karkkainen et al., JACM 2006] を説明 アイデア: マージソート 文字列 T SA ソートした接尾辞

接尾辞配列作成の線形時間アルゴリズム(2) 配列位置を3の剰余により B0,B1,B2 に分割し、C=B1∪B2とする 例: B1={1,4,7,10}, B2={2,5,8,11}, C={1,4,7,10,2,5,8,11} Rk=[tktk+1tk+2][tk+3tk+4tk+5]… とし、R=R1・R2 とする 必要に応じて、末尾に $ を追加($ < a)

接尾辞配列作成の線形時間アルゴリズム(3) R の各要素を(基数ソートで)順位づけしたものを R’ とする R’ の接尾辞配列 SAR’ を再帰的に構成 順位づけ R’=(1,2,4,6,4,5,3,7,$) R’ の 接尾辞配列

接尾辞配列作成の線形時間アルゴリズム(4) SAR’ により、 C=B1∪B2 の位置のソートが完了 残り B0 を Si ≦ Sj ⇔ (ti, rank(Si+1)) ≦ (tj, rank(Sj+1)) でソート Si : 入力文字列の i 番目文字から 始まる接尾辞 rank(Si): Si の接尾辞配列における順位 S12 < S6 < S9 < S3 < S0 上記規則でソート C の位置のソートが完了 S0 S3 S6 S9 S12

接尾辞配列作成の線形時間アルゴリズム(5) C のソート結果と B0 のソート結果を以下の規則でマージ B0 vs. B1 : Si ≦ Sj ⇔ (ti, rank(Si+1)) ≦ (tj, rank(Sj+1)) B0 vs. B2 : Si ≦ Sj ⇔ (ti, ti+1, rank(Si+2)) ≦ (tj, tj+1, rank(Sj+2)) S0 S3 S6 S9 S12 S12 < S6 < S9 < S3 < S0 S1 < S4 < S8 < S2 < S7 < S5 < S10 < S11 マージ S12 < S1 < S6 < S4 < S9 < S3 < S8 < S2 < S7 < S5 < S10 < S11 < S0 マージ規則の 適用例 S1 < S6 ⇔ (a, rank(S2)) < (a, rank(S7)) S3 < S8 ⇔ (b, a, rank(S5)) < (b, a, rank(S10))

接尾辞配列作成の線形時間アルゴリズム(6) S3 S6 S9 S12 定理: 接尾辞配列は線形時間で構成可能 証明: 上記アルゴリズムの正当性は明らか。また、再帰呼出し以外は線形時間。 再帰呼出しの際はデータのサイズが2/3になる。よって、DC3アルゴリズムの計算時間をT(n)とすると以下を得る。 T(n)=T(2n/3)+O(n)

まとめ 接尾辞木 BW変換 接尾辞配列 補足 接尾辞集合をコンパクトに表現 線形時間で構成可能 文字列をコンパクトに表現、圧縮にも有効、高速な検索が可能 接尾辞配列 接尾辞木と同様の目的、よりコンパクト 補足 UkkonenアルゴリズムはO(log |Σ|)時間のオーバーヘッドがあるが、一般のアルファベットに対して線形時間で動作するアルゴリズムも存在 [Farach: Proc. FOCS 1997] 近年ではコンパクトかつ検索その他を用意にする簡潔データ構造(succinct data structure)に関する研究が盛んに行われている