情報生命科学特別講義III （13） 固定パラメータアルゴリズムと 部分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) 時間で解ける 証明 アルゴリズムの正当性は明らか 再帰呼び出し１回にかかる手間は、グラフのサイズのオーダー（O(n2)時間） 再帰の深さは k 以下で、１回あたり2回の再帰呼び出しが行われるので、再帰呼び出しの回数は 2k+1 以下 よって、全体の時間計算量は O(2k n2)

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

カーネル化（２） 計算量の解析 G’の構成はグラフのサイズのオーダー（O(n2)時間） 全解探索は O(2^{(2k)2} k2) 時間 ある場合は、 それらも削除 |V’|≦2k2 計算量の解析 G’の構成はグラフのサイズのオーダー（O(n2)時間） 全解探索は O(2^{(2k)2} k2) 時間 ⇒ O(2^{(2k)2 }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 個を選べば明らかに少なくとも１個は s[j]=si[j] が成立。 アイデア： t=s1から始めて（この時は最大距離は補題1より 2d 以下）、d が１ずつ減るように補題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) 幅が最小となる木分解の幅

木分解の例 ⇒ 木の木幅は１ ⇒ サイクルの木幅は２

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

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