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

Slides:



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

A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
情報生命科学特別講義III (5)配列アラインメント
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
情報生命科学特別講義III (1) 文字列マッチング
Bipartite Permutation Graphの ランダム生成と列挙
極小集合被覆を列挙する 実用的高速アルゴリズム
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
ラベル付き区間グラフを列挙するBDDとその応用
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
情報生命科学特別講義III (8)木構造の比較: 順序木
    有限幾何学        第8回.
On the Enumeration of Colored Trees
An Algorithm for Enumerating Maximal Matchings of a Graph
Permutationグラフと Distance-Hereditaryグラフの 再構築アルゴリズム
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
Extremal Combinatrics Chapter 4
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(3) + 数理談話会 木構造および画像データの文法圧縮
Approximation of k-Set Cover by Semi-Local Optimization
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
列挙問題 列挙問題の定義 アルゴリズムの速度 バックトラッキング 分割法 逆探索.
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
宇野 毅明 国立情報学研究所 2002年3月 東北大大学院 情報科学研究科ワークショップ
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
Proper Interval Graphsの ランダム生成と列挙
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(5) 木構造データ間の編集距離
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
情報生命科学特別講義III (7)進化系統樹推定
情報生命科学特別講義III (11) RNA二次構造予測
k 個のミスマッチを許した点集合マッチング・アルゴリズム
情報生命科学特別講義III (4)近似文字列マッチング
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
九州大学大学院 情報学専攻特別講義 (9) ブーリアンネットワークの 解析と制御
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
第3回 アルゴリズムと計算量 2019/2/24.
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
第9回 優先度つき待ち行列,ヒープ,二分探索木
25. Randomized Algorithms
九州大学大学院 情報学専攻特別講義 (3) 配列解析
計算量理論輪講 chap5-3 M1 高井唯史.
分子生物情報学(2) 配列のマルチプルアライメント法
A Simple Algorithm for Generating Unordered Rooted Trees
情報生命科学特別講義III (13) 固定パラメータアルゴリズムと 部分k木
九州大学大学院 情報学専攻特別講義 (6) 固定パラメータアルゴリズムと 部分k木
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
情報知能学科「アルゴリズムとデータ構造」
列挙問題 列挙問題の定義 アルゴリズムの速度 バックトラッキング 分割法 逆探索.
第16章 動的計画法 アルゴリズムイントロダクション.
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造 2011年6月16日
九州大学大学院 情報学専攻特別講義 (8) ニューラルネットワークの 離散モデル
情報工学概論 (アルゴリズムとデータ構造)
擬似クリークを列挙する 多項式時間遅延アルゴリズム
アルゴリズムとデータ構造 第2章 リスト構造 5月24日分
情報生命科学特別講義III (14) グラフの比較と列挙
4.プッシュダウンオートマトンと 文脈自由文法の等価性
ヒープソート.
生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木
生物情報ソフトウェア特論 (4)配列解析II
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
グラフの列挙 中野 眞一    (群馬大学) 2019/9/14 列挙学校.
生物情報ソフトウェア特論 (10)固定パラメータアルゴリズムと 部分k木
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Presentation transcript:

阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター 生命情報学特論 (7)グラフの比較と列挙 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

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(v,{赤})=1 v w u1 u2 P(w,{赤,黄,青})=1 P(u1,{赤,黄,     青,緑})=1

計算量の解析 補題: 上記アルゴリズムの計算量は 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 倍増えるだけ。

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

デランダマイゼーション(脱乱択化) アイデア: ハッシュ関数族を用いる 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 の応用 ネットワークモチーフ [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個あたりにかかる時間をできるだけ少なくすることが目標となる 本講義では根つき順序木の列挙を紹介 頂点を1個1個追加していくことにより列挙

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

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

Family Treeの例(n=5)

列挙アルゴリズム 深さ優先で Family Tree をたどり、頂点数が n になれば出力して前に戻る r(T): 木 T の根 T(v,+): 木 T の頂点 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)および小さな部分グラフの検出に有向 列挙される構造1個あたりの計算時間を削減 逆探索および Family Tree の利用 補足 k-path 問題や小さな部分グラフの検出は多くの研究が行われ改良が続いている [Fomin: J. Comput. Syst. Sci. 2012] 部分k木などの効率的列挙は研究課題 [Horvath, Otaki, Ramon: ECML/PKDD 2013]