木構造の比較: 無順序木

生物情報ソフトウェア特論
（6）木構造の比較：無順序木
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
講義予定












第１回: 文字列マッチング・データ構造
第２回：たたみ込みとハッシュに基づくマッチング
第３回：近似文字列マッチング
第４回：配列解析
第５回：木構造の比較：順序木
第６回：木構造の比較：無順序木
第７回：文法圧縮
第８回： RNA二次構造予測
第９回：タンパク質立体構造の予測と比較
第１０回：固定パラメータアルゴリズムと部分k木
第１１回：グラフの比較と列挙
第１２回：ニューラルネットワークの離散モデル
無順序木の編集距離
木の編集距離

編集距離： T1 を T2 に変換するのに要する編集
操作の最小回数
削除：頂点 v を削除し、v の子を v の親の子とする
 挿入：削除の逆
 置換：頂点 v のラベルを置き変える
（無順序木では、子の左右を入れ替えてもOK）

A
T1
A
Ｃを削除
B
D
B
A
C
A
B
B
D
D
A
Ｃを挿入
B
B
T2
B
D
A
B
木間写像と最大共通部分木

木間写像：以下を満たす写像 M  V (T1 ) V (T2 )
((v1 , w1 )  M )((v2 , w2 )  M )
 v1  v2  w1  w2
 v1がv2の先祖  w1がw2の先祖
 v1がv2の左  w1がw2の左 (順序木)

最大共通部分木

M id  {( v, w) | (v, w)  M , label (v)  label ( w)}
の要素数が最大となる Mid により誘導される部分木

編集距離と最大共通部分木の関係

編集距離 = | V (T1 ) |  | V (T2 ) |  | M |  | M id |
木間写像と最大共通部分木の例
T1
最大共通部分木
T2
一般の距離の場合の関係
一般の編集距離
γ(x,y)
:ラベル x をラベル y に置換
γ(x,ε) :ラベル x の頂点を削除
γ(ε,y) :ラベル y の頂点を挿入
最大共通部分木のスコア
score ( M ) 
 w(u, v)
( u ,v )M
w(u, v)   (l (u ),  )   ( , l (v))   (l (u ), l (v))
編集距離とスコアの関係
dist (T1 , T2 ) 
 (l (u),  )   ( , l (v))  score(M
uV (T1 )
vV (T2 )
OPT
)
無順序木の編集距離の
2h+2 近似アルゴリズム
[Akutsu et al.: Theoret. Comp. Sci., 2013]
無順序木の編集距離の近似
最大共通部分木（最大化）⇔編集距離（最小化）
 しかし、近似に関しては無関係
 編集距離： MAX SNP困難以外の結果が無い
⇒無順序木の編集距離の 2h+2近似

方法
 木 T を特徴ベクトル Φ（T）に変換
1
Φ(T1 )  Φ(T2 ) 1  dist (T1 , T2 )  Φ(T1 )  Φ(T2 ) 1
2h  2
特徴ベクトル


T(v) : v とその子孫から誘導される T の部分木
Φt(T)= #(T,t)= |{ v | T(v)≈t }|, Φ(Ti) = < Φt(Ti) | t∊{Ti(v)|i=1,2} >
特徴ベクトルの性質
T1
補題1
Φ(T1 )  Φ(T2 ) 1 
(2h  2)  dist (T1 , T2 )
証明：編集操作1に
より距離が高々
2h+2 増加
補題2
dist (T1 , T2 ) 
Φ(T1 )  Φ(T2 ) 1
証明：次のスライド
T2
r
r
c
a b
c
a
b
a
a c
b
Φ(T1)= ( 2, 2, 1, 1, 1, 0,
1, 0 )
Φ(T2)= ( 2, 1, 2, 1, 0, 1,
0, 1 )
a b c
a
b
c
c T
1
a b a c
T2
補題2 dist (T1, T2 )  Φ(T1 )  Φ(T2 ) 1
証明
T1 を T2 に変換する d=||Φ(T1)-Φ(T2)|| 回の編集操作系列（証明中で
は両方の木からの頂点の削除系列）を示す
d=0 の時、明らかに T1 ≈ T2
T1(u) ≈ T2(v) を満たす根の子のペア (u,v) が存在するなら、
T1(u) , T2(v) を両方の木から削除


編集操作ではなく、これらはマッチしたものとみなし、以降の対象から除く
このようにしても次式により d は不変
Φ(T1  T1 (u))  Φ(T2  T2 (v))  (Φ(T1 )  Φ(T1 (u)))  (Φ(T2 )  Φ(T2 (v)))  Φ(T1 )  Φ(T2 )
|Ti(v)|

が最大となる根の子 v を選び、v を Ti から削除
根の子が１個削除されるだけなので、特徴ベクトルは1か所１だけ減る
Φ(T1' )  Φ(T2 )  Φ(T1 )  Φ(T2 ) 1 1
1
最大でないと Φt (T1 )  Φt (T2 )
の場合にX
T1 ≈ T2 は、T1 と T2 が同型であることを意味
木に対する最大連結共通部分
グラフ計算アルゴリズム
木の最大連結共通部分グラフ
入力：二つの根つき無順序木 T1, T2
出力： T1, T2 の部分グラフに同型で、頂点数最大の木


簡単のため、根どうしは対応すると仮定
すべての頂点対を根の対として繰り返し解くことにより、根なし木にも対応可
T1
T2
アルゴリズム：動的計画法の利用


T(v): 頂点 v とその子孫から
構成される T の部分グラフ
D[u,v]： T1(u) と T2(v) の最大
連結共通部分グラフのサイ
ズ（頂点数）


ただし、 u と v は対応すること
が必要
動的計画法の適用


例
D[2,b] = 1, D[2,c]=1, D[2,d]=1
D[3,b] = 3, D[3,c]=3, D[3,d]=2
D[4,b] = 3, D[4,c]=2, D[4,d]=2
D[u,v] を葉から根へ
と計算
D[u,v] を計算する時
には、その子のペア
(u’,v’) の D[u’,v’] は
すべて計算済み
2
b
4
3
5
a
T1
1
6
7 e
8
9
T2
c
f g
j
d
h
i
アルゴリズム：二部グラフマッチングの利用

D[u,v]の計算



1
2
二部グラフ


子のペアに対する D[…] から二
部グラフを構成
二部グラフの最大重みマッチン
グを計算
U と W の間にしか辺が無いよう
に、頂点集合を (U,W) に分割可
能なグラフ
マッチング


5
端点を共有しない辺の集合
最大重みの場合も含め、多項
式時間で計算可能
5
4
1
7
2
U
W
マッチング
アルゴリズム：例

D[1,a] の計算
 D[1,a] = 最大重みマッチン
グの重み＋ 1 = 8
 (2,d), (3,c), (4,b) が対応
2
b
4
3
5
a
T1
1
6
8
D[2,b] = 1, D[2,c]=1, D[2,d]=1
D[3,b] = 3, D[3,c]=3, D[3,d]=2
D[4,b] = 3, D[4,c]=2, D[4,d]=2
c
f g
7 e
9
T2
j
h
d
2
i
3
1
1
1
b
3
3
c
2
3
4
2
2
ラベルの対にスコア（重み）が割り当てられる場合にも対応可能
d
無順序木の編集距離に対する
O(1.26n1+n2)時間アルゴリズム
[Akutsu et al.: J. Disc. Alg., 2014]
指数時間アルゴリズム

NP困難問題への対処法






近似アルゴリズム
固定パラメータアルゴリズム
指数時間アルゴリズム（O(an)で底aを小さくする）
平均的に高速なアルゴリズム
ヒューリスティックなアルゴリズム
指数時間アルゴリズム
タンパク質などでは n は有限（多くの場合、n≦1000で十
分）
⇒ 例えば 1.021000 で他のオーバーヘッドが少ないなら十
分計算可能
⇒ 小さな底の指数時間アルゴリズムの開発

基本アイデア



編集距離と同値なので最大共通部分木を計算
前述と同様の動的計画法の利用 ⇒ ただし、挿入・削除がある
ので、各頂点ペアごとに子頂点集合の探索が必要（指数時間）
⇒ ここをできるだけ改善
候補頂点集合 R （relevant set、先祖・子孫関係がない頂点集
合）どうしのみのチェック
(x, y  R)( x  des( y )  y  des( x))
二部グラフの構成



アイデア：葉を特別扱いする
R が分岐頂点のみを含む場合、候補分岐頂点集合とよぶ
二部グラフの頂点集合＝候補分岐頂点集合＋その子孫以外の
葉の集合
アルゴリズム


内部頂点が2個以上の子を持つと以下のように簡単
この仮定は除去可能（ただし、省略）
for all pairs (u , v)  V (T1 )  V (T2 ) do
(in a bottom - up way)
smax  0;
for all relevant branching sets Ru for T1 (u ) do
for all relevant branching sets Rv for T2 (v) do
s  BPscore ( Ru , Rv );
if s  smax then smax  s;
S[u, v]  w(u, v)  smax
w(u,v): u と v がマッチした時の頂点間の重み（この和を最大化）
S[u,v]: T1(u) と T2(v) の最大共通部分木のスコア（ただし、u,v が対応）
BPscore: 前述のように構成した二部グラフのスコア
アルゴリズムの解析
補題：頂点数 n の木における候補分岐頂点集合の個
数は Θ(2⌈(n−1)/3⌉) （ <O(1.26n)）
⇒ O(1.26n1+n2 ) 時間アルゴリズム
for all pairs (u , v)  V (T1 )  V (T2 ) do
(in a bottom - up way)
smax  0;
for all relevant branching sets Ru for T1 (u ) do
for all relevant branching sets Rv for T2 (v) do
s  BPscore ( Ru , Rv );
if s  smax then smax  s;
S[u, v]  w(u, v)  smax
n1, n2: 入力木の頂点数
最大次数とラベルに制約がある場合の改良

最大次数とラベルの種類が制約された場合、（高さ K 未満の）小
さな部分木の多くは同型（葉のかわりに小さな部分木を考える）
⇒ 多くの候補頂点集合は本質的に同じ ⇒ 本質的に異なる候補頂点集合
のみについて計算すればよい ⇒ O((1+ε)n1+n2) 時間 (εは任意の正定数）
アルゴリズムと解析
定理：以下のアルゴリズムは O(((2K) (1/K))n1+n2 poly) 時間で動作
任意の ε に対し、十分大きな K をとれば、 (((2K) (1/K))≦1+ε
R H  {v  R height (v)  K }, R L  {v  R height (v)  K }
R 0  {v  T height (v)  K , v  des(u ) for any u  R H }
無順序木の編集距離に対する
固定パラメータ・アルゴリズム
[Akutsu et al.: Theoret. Comp. Sci. 2011]
固定パラメータ・アルゴリズム

NP困難問題への対処法






近似アルゴリズム
固定パラメータアルゴリズム
指数時間アルゴリズム（O(an)で底aを小さくする）
平均的に高速なアルゴリズム
ヒューリスティックなアルゴリズム
固定パラメータアルゴリズム

あるパラメータ k があり、O(f(k)poly(n)) 時間で動作



f(k) は指数時間、poly(n) は多項式時間
k に対しては指数時間（もしくは、超指数時間）
n に対しては多項式時間
⇒編集距離が k 以内かどうかを判定する固定パラメータアルゴリズム
補題
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 個以下の間は、大
きい順に子頂点を１個ずつ追加


追加の際には、その子頂点の削除の場合も再帰的に考慮
子頂点を追加できなくなったらば、最小重みマッチング
により、子頂点間の対応関係を計算
アルゴリズム（前半部）
一方の木が空の場合
両方とも根だけの木の場合
同型な子がある場合
アルゴリズム（後半部）
同型な子頂点はないので、k 個までの
子頂点の対応関係をチェックすれば十分
サイズが最大の頂点 w を選択
対応する子頂点の個数は同じはず
最小重みマッチングの計算
T1 から w を削除
T2 から w を削除
w を子頂点集合に追加
計算量の解析（１）


再帰回数の見積もり
 レベルk-1の再帰を
高々2k回
再帰１回あたりの時間
 マッチングに O(n3)
分岐なし
合計で高々 2k 回
f ( k , n) 
2k  f (k  1, n)  O(n3 )
計算量の解析（2）
f (k , n)  2k  f (k  1, n)  O(n )
3

 O(n )  (1  2

   2 )  k!  O(n )  2
f (k , n)  O(n3 )  1  2k  2k  2(k  1)    2k  k!
3



2
k
3
k 1

 k!
FpDistは、すべての頂点ペアについてボトムアップ
に実行： O(n2)倍
距離は 0 から k のそれぞれについて実行: O(n)倍
k
6
よって、全体の計算時間は O(2  k!n )
定理: 二つの無順序木の編集距離が k 以内かどう
かは O(2k・k!・n6)時間で判定可能
まとめ
無順序木の編集距離

O(2h+2) 近似：特徴ベクトルを用いた埋め込みの利用

O(1.26n1+n2) 時間アルゴリズム：頂点数の削減
O(2k・k!・n6) 時間アルゴリズム：固定パラメータ・アルゴリズム


O(2.62k poly(n)) 時間に改善可能 [Akutsu et al.: Theoret. Comp. Sci. 2011]
補足
 編集操作に制約（木アラインメント、Tree Inclusion）


最大共通部分木の近似



次数固定なら多項式時間（参照： [Bille: Theoret. Comp. Sci. 2005]）
O(log n) 近似 [Akutsu et al.: Theoret. Comp. Sci., 2013]]
この近似率の改善、および、編集距離の高さに依存しない近似は研究課題
木の編集距離の高さに依存しない埋め込みは研究課題

Move を許した順序木の場合は可能 [Garofalakis, Kumar: ACM Trans. Database System 2005]

Download Report