九州大学大学院 情報学専攻特別講義 (6) 固定パラメータアルゴリズムと 部分k木

Slides:



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

A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム( 1 ) スケールフリーネットワーク 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター.
情報生命科学特別講義III (5)配列アラインメント
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
情報生命科学特別講義III (1) 文字列マッチング
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
極小集合被覆を列挙する 実用的高速アルゴリズム
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
ラベル付き区間グラフを列挙するBDDとその応用
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
情報生命科学特別講義III (8)木構造の比較: 順序木
    有限幾何学        第8回.
An Algorithm for Enumerating Maximal Matchings of a Graph
Permutationグラフと Distance-Hereditaryグラフの 再構築アルゴリズム
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(3) + 数理談話会 木構造および画像データの文法圧縮
Approximation of k-Set Cover by Semi-Local Optimization
宇野 毅明 国立情報学研究所 2002年3月 東北大大学院 情報科学研究科ワークショップ
京都大学 化学研究所 バイオインフォマティクスセンター
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(5) 木構造データ間の編集距離
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
情報生命科学特別講義III (7)進化系統樹推定
奈良女子大集中講義 バイオインフォマティクス (10) スケールフリーネットワーク
7.時間限定チューリングマシンと   クラスP.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
情報生命科学特別講義III (11) RNA二次構造予測
k 個のミスマッチを許した点集合マッチング・アルゴリズム
生物情報ソフトウェア特論 (8) RNA二次構造予測
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
遺伝的アルゴリズムへの 統計力学的アプローチ 大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
九州大学大学院 情報学専攻特別講義 (9) ブーリアンネットワークの 解析と制御
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
第3回 アルゴリズムと計算量 2019/2/24.
25. Randomized Algorithms
九州大学大学院 情報学専攻特別講義 (3) 配列解析
計算量理論輪講 chap5-3 M1 高井唯史.
分子生物情報学(2) 配列のマルチプルアライメント法
A Simple Algorithm for Generating Unordered Rooted Trees
離散数学 07. 木 五島.
情報生命科学特別講義III (13) 固定パラメータアルゴリズムと 部分k木
分子生物情報学(3) 確率モデル(隠れマルコフモデル)に 基づく配列解析
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
九州大学大学院 情報学専攻特別講義 (4) RNA二次構造予測
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
生物情報ソフトウェア特論 (8) RNA二次構造予測
第16章 動的計画法 アルゴリズムイントロダクション.
短い部分文字列の ミスマッチトレランスを 高速計算するアルゴリズム
直並列グラフの連続多重彩色 西関研究室 吉田進太郎.
Max Cut and the Smallest Eigenvalue 論文紹介
九州大学大学院 情報学専攻特別講義 (8) ニューラルネットワークの 離散モデル
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 第2章 リスト構造 5月24日分
奈良女子大集中講義 バイオインフォマティクス (7) 進化系統樹
情報生命科学特別講義III (14) グラフの比較と列挙
4.プッシュダウンオートマトンと 文脈自由文法の等価性
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木
卒業研究 Treedecompositionを生成するヒューリスティックアルゴリズムの幅に関する評価実験
卒業研究 木分解ヒューリスティック アルゴリズムの性能評価実験 ~アルゴリズムの改良の考察と そのプログラム作成~
生物情報ソフトウェア特論 (4)配列解析II
13.近似アルゴリズム.
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
生物情報ソフトウェア特論 (10)固定パラメータアルゴリズムと 部分k木
集中講義(東京大学)「化学システム工学特論第3」 バイオインフォマティクス的手法による化合物の性質予測(1) バイオインフォマティクス概観
分子生物情報学(0) バイオインフォマティクス
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Presentation transcript:

九州大学大学院 情報学専攻特別講義 (6) 固定パラメータアルゴリズムと 部分k木 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

講義内容 バイオインフォマティクス概論(資料なし) 配列アラインメント 配列解析 RNA二次構造予測 タンパク質立体構造の比較と予測 固定パラメータアルゴリズムと部分k木 グラフの比較と列挙 ニューラルネットワークの離散モデル ブーリアンネットワークの解析と制御 講義の進展状況によっては内容に変更の可能性あり

固定パラメータ・アルゴリズム [Flum, Grohe: Parameterized Complexity Theory, Springer]

固定パラメータ・アルゴリズム NP困難問題への対処法 近似アルゴリズム 固定パラメータアルゴリズム 指数時間アルゴリズム(O(an)で底aを小さくする) 平均的に高速なアルゴリズム ヒューリスティックなアルゴリズム あるパラメータ k があり、O(f(k)poly(n)) 時間で動作 f(k) は指数時間、poly(n) は多項式時間 k に対しては指数時間(もしくは、超指数時間) n に対しては多項式時間

頂点被覆問題 入力: 無向グラフ G(V,E)、整数 k 出力: サイズ k 以下の V の部分集合 W で 、G のすべ ての辺の少なくとも一つの端点が W に属するもの 頂点被覆問題はNP困難

アイデア 再帰アルゴリズム 各辺の端点のいずれかは頂点被覆に属する よって、再帰呼び出しでそれぞれの可能性を調べる G-v: グラフ G から頂点 v、 および、v に接続するすべての辺を削除して得られるグラフ

再帰アルゴリズムの実行例

計算量の解析 定理: 頂点被覆問題は O(2k n2) 時間で解ける 証明 アルゴリズムの正当性は明らか 再帰呼び出し1回にかかる手間は、グラフのサイズのオーダー(O(n2)時間) 再帰の深さは k 以下で、1回あたり2回の再帰呼び出しが行われるので、再帰呼び出しの回数は 2k+1 以下 よって、全体の時間計算量は O(2k n2)

カーネル化(1) 固定パラメータアルゴリズム設計の別なアプローチ 解に必ず含まれる部分や含まれない部分を削除するなどして、多項式時間で入力データを小さなサイズ(パラメータにのみ依存するサイズ)のデータ(カーネル)に変換 カーネルに対して全解探索を実施 定理 固定パラメータアルゴリズムが存在 ⇔ カーネル化法が存在 頂点被覆問題に対するカーネル化 次数 k+1 以上の頂点は必ず被覆に含まれる    (そうでないと 、k+1 個以上の隣接頂点を被覆に含むことが必要) 次数 k+1 以上の頂点を削除した後で、k2 個より多くの辺が残ったら被覆不可能⇒(孤立頂点を削除すれば)残りの頂点は 2k2 個以下

カーネル化(2) 計算量の解析 G’の構成はグラフのサイズのオーダー(O(n2)時間) 全解探索は O(2^{2k2} k2) 時間 ある場合は、 それらも削除 |V’|≦2k2 計算量の解析 G’の構成はグラフのサイズのオーダー(O(n2)時間) 全解探索は O(2^{2k2} k2) 時間 ⇒ O(2^{2k2 }k2+n2)時間 (これと再帰型アルゴリズムの組み合わせも可)

最近接文字列問題に対する 固定パラメータ・アルゴリズム [Gramm et al.: Algorithmica, 2003]

最近接文字列問題 (Closest String) 入力: 同じ長さの文字列 s1,…,sk (|si|=L)、正整数 d 出力: すべての si に対しdH(s,si) ≦ d を満たす 長さ L の文字列 s dH(s,t): 文字列 s と t の間のハミング距離(ミスマッチの数) 例:  (d=3) この問題は NP困難

最近接文字列問題: アイデア 命題: dH(s,t) は三角不等式を満たす 補題1: dH(si,sj)>2d を満たす i≠j があれば、(∀si)(dH(s,si)≦d) を満たす s は存在しない 証明: そのような s が存在したとすると 2d≧dH(s,si)+dH(s,sj)≧dH(si,sj)>2d となり、矛盾 補題2: d<dH(t,si)≦2d 、 dH(s,si)≦d とすると、t[j]≠si[j] を満たす任意の j を d+1 個選べば、少なくとも1個の j について、s[j]=si[j] が成立 証明: もともと dH(s,si)≦d なので、任意の d+1 個を選べば明らかに少なくとも1個は s[j]=si[j] が成立。 アイデア: t=s1から始めて(この時は最大距離は補題1より 2d 以下)、d が1ずつ減るように補題2を用いて t を変えていく

最近接文字列問題: アルゴリズム アルゴリズム: ClosestString(s1,d) を実行 補題2

最近接文字列問題: 解析 定理: 最近接文字列問題は O((d+1)d poly(k,L))時間で解ける 証明: 正当性は補題1,2より明らか。 毎回 d+1 個の再帰呼び出しが行われるが、Δd が必ず1ずつ減少するため、再帰の深さは高々 d。 よって、計算量は O((d+1)d poly(k,L))。

木分解と部分k木 [Flum, Grohe: Parameterized Complexity Theory, Springer]

木分解 (tree decomposition) グラフ G(V,E) に対する木分解 以下を満たす根つき木と、(Vの部分集合からなる)集合族の組 すべての v∊V について、                は連結 すべての {u,v}∊E について、u, v∊Bt を満たす t∊VT が存在 木分解の幅 maxt |Bt|-1 グラフの木幅  (tree width) 幅が最小となる木分解の幅

木分解の例 ⇒ 木の木幅は1 ⇒ サイクルの木幅は2

木分解の性質 命題 T(VT,ET) における頂点 t の子を t1,…,th とすると、 任意の i≠j について 命題 T(VT,ET) における頂点 t の親を s 、子を t1,…,th とすると、 任意の i について ⇒ 多くの最適化問題が親と子の整合性を(個別に)考えるだけで解ける 定理 木幅が k であるグラフは部分 k 木であり、部分 k 木の 木幅は k である 定理 グラフの木幅の計算はNP困難 定理 k を定数とする時、部分 k 木に対し、幅が k で、かつ、|VT|≦n を満たす木分解を線形時間で計算可能 部分 k 木の定義は省略

部分k木に対する動的計画法アルゴリズム 例 頂点被覆問題 (ただし、最小の被覆を計算) 動的計画法アルゴリズム k を定数とする時、多くの NP困難問題が、部分k木に対しては、動的計画法アルゴリズムにより多項式時間で解ける 例 頂点被覆問題 (ただし、最小の被覆を計算) Ch(t): 木 T における頂点 t の子頂点の集合 動的計画法アルゴリズム ただし、Wt は Bt (による誘導されるGの部分グラフ)における頂点被覆。 r は T の根。

動的計画法アルゴリズムの説明 Bt Bs Bs’ OPTt(Wt): G(t) において、Bt 中の頂点被覆を Wt とした際の G(t) の頂点被覆の最小値 T(t): t とその子頂点から誘導される T の部分木 G(t): により 誘導される G の部分グラフ Bt Bs Bs’

計算量の解析 時間計算量の解析 kを定数とする。また、頂点数 n 以下の木分解をグラフ G のサイズの線形時間で計算可能(n は G の頂点数)。 T の各頂点 t∊VT ごとに高々 2k+1 個の Wt をテスト。 Σの中の min の計算のために、T の各辺ごとに高々 2k+1× 2k+1 =4k+1個の対をテスト。 よって、全体の計算量は、O(4k poly(n))。

木分解の バイオインフォマティクスへの応用

木分解の応用 タンパク質やRNAの高次構造のグラフ表現は比較的小さな木幅を持つと考えられる 応用例 タンパク質スレッディング 構造は3次元だが、平面で分割することができる 応用例 タンパク質スレッディング タンパク質側鎖構造予測 タンパク質立体構造アラインメント RNA二次構造比較

まとめ 固定パラメータアルゴリズム 木分解 補足 O(f(k)poly(n)) などの計算時間で動作 再帰呼び出し型アルゴリズム(でも、他のタイプもある) 木分解 木幅が定数のグラフに対しては、多くのNP困難問題が動的計画法により多項式時間で解ける タンパク質やRNAなどの構造解析・予測への応用 補足 固定パラメータアルゴリズム、木分解には数多くの研究 固定パラメータアルゴリズムに関する完全問題なども存在 詳細は以下の本などを参照 [Flum, Grohe: Parameterized Complexity Theory, Springer] [Fomin, Kratsch: Exact Exponential Algorithms, Springer]