情報生命科学特別講義III （14）グラフの比較と列挙阿久津達也京都大学化学研究所バイオインフォマティクスセンター講義予定                第１回: 文字列マッチング第２回：文字列データ構造第３回：たたみ込みとハッシュに基づくマッチング第４回：近似文字列マッチング第５回：配列アラインメント第６回：配列解析第７回：進化系統樹推定第８回：木構造の比較：順序木第９回：木構造の比較：無順序木第１０回：文法圧縮第１１回： RNA二次構造予測第１２回：タンパク質立体構造の予測と比較第１３回：固定パラメータアルゴリズムと部分k木第１４回：グラフの比較と列挙第１５回：まとめ Color Coding [Alon et al.: J. ACM 1995] k-Path問題入力：無向グラフ G(V,E)、整数 k 出力： G 中の長さ k の点素（同じ頂点を二度通らない）パス（のどれか）   NP困難 ⇐ k=n(=|V|)とおけばハミルトンパス問題素朴なアルゴリズム：各頂点 v から初めて、隣接する頂点を調べ、さらに隣接する頂点を調べ・・・ ⇒ O(nk) 時間くらいかかるアイデア   V を k 個の集合に分割（頂点を k 色で塗り分ける）うまくいけば、パスの各頂点がすべて別の集合に入る（うまくいく確率を解析 ⇒ ランダマイズド（乱拓）・アルゴリズム）動的計画法アルゴリズム  指定された頂点 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(u, C { f (u)})  1  P(w, C )  1 and f (u)  C P(v,{赤})=1 v P(w,{赤,黄,青})=1 u1 w u2 P(u1,{赤,黄, 青,緑})=1 計算量の解析 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 へという順に実行） P(u, C { f (u)})  1  P(w, C )  1 and f (u)  C 補題：上記アルゴリズムの計算量は O(2k poly(n)) 証明： C の組み合わせの数は 2k 。よって、2kn 個の P(u,C) を計算すれば十分。すべての始点 v を試しても高々 n 倍増えるだけ。確率の解析補題： P をグラフ G の k-パスとし、各頂点に k 色のどれかをランダムに割り当てた時、P の各頂点が異なる色になる確率は e-k以上証明： P の頂点への色の割り当て方は kk 通り。一方、異なる色の割り当て方は k! 通り。よって、求める確率は Stirling の公式より k! 2k (k / e ) 2k k   k e k k k k e k k 定理：上記アルゴリズムを ek 回以上繰り返せば、（解をもつ場合に）少なくとも1回成功する確率は 1/2 以上証明：解があるのに、毎回、失敗する確率は  k ek (1  e )  e1  12 なお、解の有無に関係なく間違った解を出すことはないデランダマイゼーション（脱乱択化）アイデア：ハッシュ関数族を用いる 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) 時間で解ける Color Coding の応用 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] 順序木の列挙 [Nakano: Inf. Proc. Lett. 2002] グラフ構造の列挙        与えられた制約を満たすグラフ構造をすべて列挙漏れなく、かつ、重複なく列挙することが必要化合物の構造決定、データマイニングなどへの応用 1870年代から研究（アルカンの数え上げ）多くの場合、逆探索、family tree といった手法が使われる可能な構造は通常、指数オーダーあるため、出力される構造1個あたりにかかる時間をできるだけ少なくすることが目標となる本講義では根つき順序木の列挙を紹介  頂点を１個１個追加していくことにより列挙根つき順序木の列挙入力：頂点数 n 出力：頂点数が n の根つき順序木すべて（ただし、直前に出力した構造との差異のみの出力も可）例： n=4 次に頂点を追加する時は右端のパス（太線）中のどこかに追加 Family Tree     逆探索（reverse search）の実現法の一つグラフの標準形（同型なグラフの一意な表現）を利用 ⇒ 根付き順序木は考慮不要子グラフから親グラフを一意に定義親グラフに頂点を追加することにより子グラフを生成   重複して生成しないように定義することが重要根つき順序木の場合、最も右側の根から葉へのパスの最後の頂点（＝最も右にある頂点）を削除した木を親とする Family Treeの例（n=5）列挙アルゴリズム     深さ優先で Family Tree をたどり、頂点数が n になれば出力して前に戻る r(T): 木 T の根 T(v,+): 木 T の頂点 v に一番右の子を追加して得られる木 ε: 空頂点（頂点がないことを意味） P roc Enum Tree(T , i ) i f (i  n) outputT ; re tu rn; v  r (T ); wh i l e(v   ) do Enum Tree(T (v, ), i  1); v  rightmostchild of v 定理：頂点数 n の根つき順序木は1個あたり定数時間で列挙可能証明：正当性の証明は省略（宿題）し、時間計算量を解析する。 EnumTreeは再帰1回ごとに定数時間（T の出力に関する時間を除く）。 Family Tree の内部頂点の数は葉の数以下。よって、Family Tree の葉の数（＝出力木の数）に比例する時間で列挙可能。様々な構造の列挙    無順序木や他のクラスでは同型性が問題となる前のFamily Treeでは左下に示すように（無順序木として）同型な木が異なる木から生成されていた正規形や親子関係の定義が複雑になるが多くの研究       （ラベルつき）無順序木 [Nakano, Uno: Proc. WG 2005] 次数リストからの無順序木 [Zhuang, Nagamochi: Proc. ISAAC 2010] 外平面的グラフ [Wang, Nagamochi: KUAMP Tech. Rep. 2010-007] 極大クリーク [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] まとめ  Color Coding   短いパス(k-path)および小さな部分グラフの検出に有向構造の列挙   列挙される構造１個あたりの計算時間を削減逆探索および Family Tree の利用補足   k-path 問題や小さな部分グラフの検出は多くの研究が行われ改良が続いている [Fomin: J. Comput. Syst. Sci. 2012] 部分k木などの効率的列挙は研究課題