集中講義（九州大学数理学研究院） バイオ構造データに対する数理モデルと アルゴリズム（５） 木構造データ間の編集距離 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

内容 文字間の編集距離とアラインメント 木の編集距離 順序木に対する多項式時間アルゴリズム オイラー文字列による木の編集距離の近似 無順序木に対する固定パラメータアルゴリズム

背景

背景 配列のパターンマッチング 木構造のパターンマッチング バイオインフォマティクスの最重要基本技術の一つ バイオインフォマティクス RNA構造の比較、糖鎖構造の比較 XMLデータベース 類似XML文書の検索 画像理解

配列検索 バイオインフォマティクスにおける基本原理 配列検索の利用法 配列が似ていれば機能も似ている ただし、例外はある 実験を行い機能未知の配列が見つかった データベース中で類似の配列を検索 機能既知の類似の配列が見つかれば、その配列と似た機能を持つと推定

RNA二次構造 RNAでは一部の塩基対が結合している　 ⇒ RNA二次構造

RNA二次構造の木表現

文字間の編集距離と 配列アラインメント

文字列の編集距離 G C T A s1 = GCGTCGT s2 = CGATCCTC ー 編集操作 文字の追加 文字の削除 文字の置換 編集距離 ＝ 文字列 s1 を s2 に変換するための最小の編集操作回数 距離の公理を満たす s1 = GCGTCGT s2 = CGATCCTC G C ー T A ⇒　距離＝４ アラインメント

配列アラインメント バイオインフォマティクスの最重要技術の一つ ２個もしくは３個以上の配列の類似性の判定に利用 ２個の配列に対するアラインメントは編集距離とほとんど同じ 文字間の最適な対応関係を求める（最適化問題） 配列長を同じにするように、ギャップ記号（挿入、欠失に対応）を挿入

ペアワイズ・アラインメント 配列が２個の場合でも可能なアラインメントの個数は指数オーダー しかし、スコア最大となるアライメント（最適アライメント）は動的計画法により、O(n2)時間で計算可能（n:入力配列のうち長い方の長さ）

ギャップペナルティ 線形コスト -gd アフィンギャップコスト –d – e(g-1) g： ギャップ長 ｄ： ギャップペナルティ ｄ： ギャップ開始ペナルティ e： ギャップ伸張ペナルティ この図の例では、コスト= -d - 2e よく利用されるペナルティ　(d,e)=(12,2),(11,1)

スコア行列 残基間（アミノ酸文字間）の類似性を表す行列 PAM250, BLOSUM45 など

動的計画法による大域アラインメント（１） 入力文字列から格子状グラフを構成 アライメントと左上から右下へのパスが一対一対応 最長経路＝最適アライメント

動的計画法による大域アラインメント（２） ⇒ O(mn)時間 DP (動的計画法)による 最長経路(スコア)の計算 行列からの経路の復元は、 F(m,n)からmaxで＝となっている F(i,j)を逆にたどることに行う （トレースバック）

動的計画法による編集距離の計算 アラインメント： 配列が類似 ⇔ スコアは大 編集距離： 配列が類似 ⇔ 距離は小 アラインメント計算 アラインメント：　配列が類似　⇔　スコアは大 編集距離： 配列が類似　⇔　距離は小 アラインメント計算 編集距離計算

木の編集距離

木構造の比較 部分グラフに基づく最大共通部分木 編集距離に基づく最大共通部分木 講義で示すアルゴリズム 順序木：O(n2)時間 無順序木： O(n2.5/log n)時間 編集距離に基づく最大共通部分木 順序木： O(n3)時間 無順序木：NP困難（MAX SNP困難） 講義で示すアルゴリズム 順序木に対するO(n4)時間アルゴリズム 順序木に対するO(n2)時間近似アルゴリズム 無順序木に対する固定パラメータアルゴリズム 　　　　　　　　　(O(f(k) poly(n))時間アルゴリズム） n: 二つの入力木のうち、大きい方の頂点数

順序木の編集距離計算 上限 下限 O(n6)時間 [K-C.Tai, 1979] O(n4)時間 [K. Zhang & D. Shasha, 1989] O(n3log n)時間 [P. N. Klein, 1998] O(n3)時間 [E. Demaine et al., 2007] 下限 Ω (n3)時間 [E. Demaine et al., 2007] （ただし、decomposition strategy algorithms の枠内）

無順序木の編集距離計算 編集距離 最大共通部分木 NP困難 [K. Zhang, R. Statman, D. Shasha, 1992] MAX SNP困難 [K. Zhang & T. Jiang, 1994] 高さが h の時、2h+2近似 [Fukagawa et al., 2009] 最大共通部分木 一方が高さ１の木で、もう一方が高さ２の木でも 　　　定数近似困難 [M. M. Halldorsson & K. Tanaka, 1996] O(log 2n)近似 [M. M. Halldorsson & K. Tanaka, 1996] 高さが h の時、2h 近似 [M. M. Halldorsson & K. Tanaka, 1996] 1.5h 近似に改良 [Akutsu et al., 2008]

木の編集距離 編集距離： T1 を T2 に変換するのに要する編集操作の最小回数 削除： 頂点 v を削除し、v の子を v の親の子とする 挿入： 削除の逆 置換： 頂点 v のラベルを置き変える （無順序木では、子の左右を入れ替えてもOK） A B C D T1 A B D T2 Ｃ　を削除 Ｃ　を挿入

木の編集距離 文字列間の編集距離の 根つき木への拡張 ３種類の編集操作 T1, T2 間の 編集距離 頂点ラベルの置換、頂点の削除、 頂点の挿入 T1, T2 間の 編集距離 T1 を T2 に変えるのに必要な 最小の編集 操作回数

木の編集距離と木間写像 T1, T2 間の写像 編集距離の計算 １対１、親子関係を保存 　木の編集距離と木間写像 T1, T2 間の写像 １対１、親子関係を保存 コスト： ラベルが異なる頂点数 ＋ 写像に含まれない頂点数 編集距離の計算 順序木（子の順序を保存）：　動的計画法により、多項式時間 無順序木：　NP困難

木間写像と最大共通部分木 木間写像： 以下を満たす写像 最大共通部分木 編集距離と最大共通部分木の関係 　の要素数が最大となる Mid により誘導される部分木 編集距離と最大共通部分木の関係 編集距離 =

木間写像と最大共通部分木の例 T1 T2 最大共通部分木

順序木に対する 多項式時間アルゴリズム

動的計画法アルゴリズム（１） D(F1,F2) 森 F1 と森 F2 の編集距離 森： 木の集合（ここでは木の順序集合） 森：　木の集合（ここでは木の順序集合） w（x,y）はラベル x から y への置換コスト　　（－ はギャップ）

動的計画法アルゴリズム（２）

動的計画法アルゴリズムの解析 各再帰ステップ１回あたりは定数時間で実行可能 よって、異なる D(F1,F2) の個数を見積もれば良い F1は、各頂点 v を根とする部分木から一番右上にある子頂点を繰り返し削除して得られる ⇒ v の選び方がO(n), 削除の回数がO(n)より、 　　異なる F1 の個数はO(n2) 異なる D(F1,F2) の個数は 　　O(n4) ⇒　O(n4) 時間

順序木の編集距離の O(h) 近似アルゴリズム

オイラー文字列 木を深さ優先探索 探索した順に頂点のラベルを並べる ただし、戻る時のラベルは の様に区別する ただし、戻る時のラベルは の様に区別する 命題：　T1 と T2 が同型 iff es(T1)=es(T2) ただし、根のラベルは無視

アルゴリズム 定理 T1, T2 をオイラー文字列 s1, s2 に変換 s1, s2間の編集距離 EDS(s1,s2) を計算して出力 h: 低い方の木の高さ

文字列の編集距離 G C T A s1 = GCGTCGT s2 = CGATCCTC ー 編集操作 文字の追加 文字の削除 文字の置換 編集距離 ＝ 文字列 s1 を s2 に変換するための最小の編集操作回数 距離の公理を満たす s1 = GCGTCGT s2 = CGATCCTC G C ー T A ⇒　距離＝４ アラインメント

命題 T1に対する１編集操作　⇒　s1 に対する２編集操作 B C D T1 T2 s2: s1: E

アラインメントからの写像の復元 アラインメントから両者において完全に保存されている部分木のみを抽出

上限の解析(1) 命題：途中に編集操作の入らない部分木どおしを対応させると正当な木間写像になる 証明：部分木どおしは親子関係に無く、かつ、オイラー文字列を利用しているので左右の関係が保存される A B

上限の解析(2) 文字列アライメントにおける１個のエラーが高さ×２個（T1と T2 ）の頂点の対応関係を損なう

定理 [Akutsu, IPL 2006]

無順序木に対する 固定パラメータアルゴリズム

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

補題 T1 , T2 の根を r1 , r2 とし、 dist(T1(u), T2(v))>0 がすべての u∊chd(r1), v∊chd(r2) について成立すると仮定する。 ここで、u を |Ti(u)| が最大となる r1 もしくは r2 の子とし、M を編集距離を与える写像とすると、以下の一つが成立（ u∊chd(r1) と仮定）。 ・ u は M に出現しない　（u を削除） ・ (u,v)∊M かつ dist(T1(u), T2(v))>0 が、 v∊chd(r2) に対して成立 ・ (u,v)∊M かつ dist(T1(u), T2(v))>0 が、 子以外の子孫に対して成立

補題 xi ∊chd(r1), yj ∊chd(r2)、かつ、T1 (xi) と T2 (yj) が同型なら、 dist(T1, T2) = dist(T1-T1(xi), T2-T2(yj ))

アルゴリズムの概要 根のペアから再帰的に実行 同型な子頂点ペアがあれば削除 それぞれの木の子頂点の個数が k 個以下の間は、大きい順に子頂点を１個ずつ追加 追加の際には、その子頂点の削除の場合も再帰的に考慮 子頂点を追加できなくなったらば、最小重みマッチングにより、子頂点間の対応関係を計算

計算量の解析 （2） FpDistは、すべての頂点ペアについてボトムアップに実行： O(n2)倍 計算量の解析　（2） FpDistは、すべての頂点ペアについてボトムアップに実行： O(n2)倍 距離は 0 から k のそれぞれについて実行: O(n)倍 よって、全体の計算時間は 定理: 二つの無順序木の編集距離が k 以内かどうかは O(2k・k!・n6)時間で判定可能 [Akutsu et al., SIGAL Tech. Rep., 2010]

まとめ 配列アラインメント 順序木の編集距離 無順序木の編集距離 バイオインフォマティクスの基本技術 動的計画法によるO(n2)時間アルゴリズム 順序木の編集距離 O(n4)時間動的計画法アルゴリズム 　　　　　　（O(n3)時間に改良可能） O(n2)時間O(h)近似アルゴリズム 無順序木の編集距離 固定パラメータアルゴリズム 　　　　　　（O(2.62k・poly(n))に改良可能）