Presentation is loading. Please wait.

Presentation is loading. Please wait.

生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木

Similar presentations


Presentation on theme: "生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

12 最近接文字列問題: アイデア 命題: 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 を変えていく

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

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

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

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

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

18 木分解の性質 命題 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 木の定義は省略

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

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

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

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

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

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


Download ppt "生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木"

Similar presentations


Ads by Google