情報生命科学特別講義III （14） グラフの比較と列挙

Presentation on theme: "情報生命科学特別講義III （14） グラフの比較と列挙"— Presentation transcript:

1 情報生命科学特別講義III （14） グラフの比較と列挙
阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

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

3 Color Coding [Alon et al.: J. ACM 1995]

4 k-Path問題 入力： 無向グラフ G(V,E)、整数 k 出力： G 中の長さ k の点素（同じ頂点を二度通らない） パス（のどれか）
　　　　　パス（のどれか） NP困難 ⇐ k=n(=|V|)とおけばハミルトンパス問題 素朴なアルゴリズム： 各頂点 v から初めて、隣接する頂点を調べ、さらに隣接する頂点を調べ・・・　 　　⇒ O(nk) 時間くらいかかる アイデア V を k 個の集合に分割　（頂点を k 色で塗り分ける） うまくいけば、パスの各頂点がすべて別の集合に入る　 　　（うまくいく確率を解析 ⇒ ランダマイズド（乱拓）・アルゴリズム）

5 動的計画法アルゴリズム 指定された頂点 v から始まる k パスの有無を調べる すべての v について同様の作業を繰り返せばよい
トレースバックによりパスは復元可能 P(u,C): C の各色をちょうど1回使う v から u へのパスがあれば 1、 そうでなければ 0 （C は {1,2,…,k}の部分集合） 初期化： P(v,{f(v)})←1, 他はすべて 0 (f(v) は v の色） 再帰式： （|C|=1 から |C|=k-1 へという順に実行） {u,w}∈E P(v,{赤})=1 v w u1 u2 P(w,{赤,黄,青})=1 P(u1,{赤,黄, 　　　　青,緑})=1

6 計算量の解析 補題： 上記アルゴリズムの計算量は O(2k poly(n))
P(u,C): C の各色をちょうど1回使う v から u へのパスがあれば 1、 そうでなければ 0 （C は {1,2,…,k}の部分集合） 初期化： P(v,{f(v)})←1, 他はすべて 0 (f(v) は v の色） 再帰式： （|C|=1 から |C|=k-1 へという順に実行） 補題： 上記アルゴリズムの計算量は O(2k poly(n)) 証明： C の組み合わせの数は 2k 。よって、2kn 個の P(u,C) を計算すれば十分。 すべての始点 v を試しても高々 n 倍増えるだけ。

7 確率の解析 補題： P をグラフ G の k-パスとし、各頂点に k 色のどれかをランダムに割り当てた時、P の各頂点が異なる色になる確率は e-k以上 証明： P の頂点への色の割り当て方は kk 通り。一方、異なる色の割り当て方は k! 通り。よって、求める確率は Stirling の公式より 定理： 上記アルゴリズムを ek 回以上繰り返せば、（解をもつ場合に）少なくとも1回成功する確率は 1/2 以上 証明： 解があるのに、毎回、失敗する確率は なお、解の有無に関係なく間違った解を出すことはない

8 デランダマイゼーション（脱乱択化） アイデア： ハッシュ関数族を用いる
k-完全ハッシュ関数族： F を V={1,2,…,n} から {1,2,…,k} への関数 f の族（集合）とする。V の任意の k 個の要素からなる部分集合に対し、1対1写像を与える f∊F が存在する時、F は k-完全ハッシュ関数族とよばれる 定理： 任意の n,k に対し、2O(k)・log2n 個の関数からなる k-完全ハッシュ関数族を 2O(k)・n・log2n 時間で構成可能 ⇒　ランダムな割り当ての代わりに、この定理による関数 f を 　　　すべて試せばよい 系： k-Path問題は　2O(k)・poly(n)　時間で解ける

9 Color Coding の応用 ネットワークモチーフ [Alon et al.: Bioinformatics , 2008]
シグナルパスウェイ解析 [Huffner et al.: Bioinformatics 2007 & Algorithmica 2008] ネットワークマーカー [Dao et al.: Bioinformatics 2011] パスウェイ検索・アラインメント [Shlomi et al.: BMC Bioinformaics 2006]

10 順序木の列挙 [Nakano: Inf. Proc. Lett. 2002]

11 グラフ構造の列挙 与えられた制約を満たすグラフ構造をすべて列挙 漏れなく、かつ、重複なく列挙することが必要
化合物の構造決定、データマイニングなどへの応用 1870年代から研究（アルカンの数え上げ） 多くの場合、逆探索、family tree といった手法が使われる 可能な構造は通常、指数オーダーあるため、出力される構造1個あたりにかかる時間をできるだけ少なくすることが目標となる 本講義では根つき順序木の列挙を紹介 頂点を１個１個追加していくことにより列挙

12 根つき順序木の列挙 入力： 頂点数 n 出力： 頂点数が n の根つき順序木すべて （ただし、直前に出力した構造との差異のみの出力も可）
次に頂点を追加する時は右端のパス（太線）中のどこかに追加

13 Family Tree 逆探索（reverse search）の実現法の一つ グラフの標準形（同型なグラフの一意な表現）を利用
　　　　　⇒　根付き順序木は考慮不要 子グラフから親グラフを一意に定義 親グラフに頂点を追加することにより子グラフを生成 重複して生成しないように定義することが重要 根つき順序木の場合、最も右側の根から葉へのパスの最後の頂点（＝最も右にある頂点）を削除した木を親とする

14 Family Treeの例（n=5）

15 列挙アルゴリズム 深さ優先で Family Tree をたどり、頂点数が n になれば出力して前に戻る r(T): 木 T の根
T(v,+): 木 T の頂点 v に一番右の子を追加して得られる 木 ε: 空頂点（頂点がないことを意味） 定理： 頂点数 n の根つき順序木は1個あたり定数時間で列挙可能 証明： 正当性の証明は省略（宿題）し、時間計算量を解析する。 EnumTreeは再帰1回ごとに定数時間（T の出力に関する時間を除く）。 Family Tree の内部頂点の数は葉の数以下。 よって、Family Tree の葉の数（＝出力木の数）に比例する時間で列挙可能。

16 様々な構造の列挙 無順序木や他のクラスでは同型性が問題となる
前のFamily Treeでは左下に示すように（無順序木として）同型な木が異なる木から生成されていた 正規形や親子関係の定義が複雑になるが多くの研究 （ラベルつき）無順序木 [Nakano, Uno: Proc. WG 2005] 次数リストからの無順序木 [Zhuang, Nagamochi: Proc. ISAAC 2010] 外平面的グラフ [Wang, Nagamochi: KUAMP Tech. Rep ] 極大クリーク [Makino, Uno: Proc. SWAT 2004], [Tomita et al. Theoret. Comp. Sci. 2006] 配列モチーフ [Arimura, Uno: Proc. ISAAC 2005] （外平面的グラフの）立体異性 　　　　　　　　　　　　　　　　　　　　　　　　　 [Imada et al.: J. Chem. Inf. Model., 2011]

17 まとめ 補足 Color Coding 構造の列挙 短いパス(k-path)および小さな部分グラフの検出に有向
列挙される構造１個あたりの計算時間を削減 逆探索および Family Tree の利用 補足 k-path 問題や小さな部分グラフの検出は多くの研究が行われ改良が続いている [Fomin: J. Comput. Syst. Sci. 2012] 部分k木などの効率的列挙は研究課題