多項式時間計算可能な根無しラベル付き木の編集距離
Edit Distance Computable in Polynomial Time
between Unrooted Labeled Tree
芳野 拓也
1∗平田 耕一
1,2Takuya Yoshino
1Kouichi Hirata
1,21
九州工業大学大学院情報工学府
1
Graduate School of Computer Science and Systems Engineering,
2
九州工業大学情報工学研究院
2
Department of Artificial Intelligence,
Kyushu Institute of Technology
Abstract: In this paper, we formulate an edit distance for unrooted tree as the minimum cost transforming from a tree to another tree by using unrooted edit operations and an confluent mapping between unrooted trees extended the Tai mapping. This is a revised of the path-preserving mapping introduced in SISA’16 [7]. We also formulate an isolated-subtree mapping for unrooted trees and investigate whether it is the minimum of rooted isolated-subtree mapping for every pair of nodes in 2 trees.
1
はじめに
2つの根付き木 (rooted tree) 間の Tai マッピング (Tai mapping ) [4]は, 単射であり, かつ, 先祖子孫関係を保 存するノード間の対応付けである. この Tai マッピン グは, マッピングによる対応付けがあるノードを置換 (あるいは未操作), 対応付けがない木のノードを削除と 挿入とみなすことで, 2 つの根付き木間の Tai マッピン グの最小コストが木編集距離 (tree edit distance) とな ることが知られている [4]. また, Tai マッピングに様々 な制約を入れることで, 数多くの木編集距離の変種を 導入することができ [9, 10, 12], そのときの Tai マッピ ングが階層を成すことも知られている [3, 5]. さらに, Taiマッピングは, 木カーネルの一種であるマッピング カーネルの定式化における数え上げの対象でもある. このように, 根付き木において Tai マッピングは木編 集距離や木カーネルとして重要な概念であるが, この
Taiマッピングを根無し木 (unrooted tree) に拡張する
ためには, 単射であることに加えて, 先祖子孫関係に代 わる条件を導入する必要がある. Zhang ら [12] は, 挿 入と削除を次数 2 以下のノードに制限した次数 2 距離 (degree-2 distance)を根無し木に拡張する際, 根付き木 の LCA 保存マッピングの拡張として, 3 つのノードの 中心 (center ) を保存する中心保存マッピング (center-∗連絡先： 九州工業大学大学院情報工学符 〒 820-8502 福岡県飯塚市河津 680-4 E-mail: [email protected] preserving mapping)を導入した. ここで, 3 つのノー ドの中心とは, 2 つのノード間の 3 つのパスの共通ノー ドである. また中心保存マッピングの最小コストとして 定義される中心保存距離 (center-preserving distance) は, 2 つの木の任意のノードを根とみなした根付き木間 の次数 2 距離の最小値として求めることができる [12]. 本論文では, 編集操作を根無し木に拡張し, 根無し木 の編集距離を定式化する. また,孤立部分木マッピング (isolated-subtree mapping)を根無し木に拡張する.
2
準備
閉路を持たない連結グラフを木という. 木 T = (V, E) に対して, V, E をそれぞれ V (T ), E(T ) で表し, v ∈ V (T )を単に v∈ T と表す. また, |V (T )| を T の大き さ (size) といい, |T | で表す. 簡単のため, v ∈ V を単 に v∈ T で表し, 空の木を ∅ で表す. 木 T のうち,根ノード r∈ T を 1 つ選んだものを根 付き木, そうでないものを根無し木という. 根付き木 T の根を r(T ) と表し, 根ノード r∈ T を根として選んだ 根付き木を Trで表す. T = (V, E)を木とする. u, v ∈ V に対して, V′ = {v1, . . . , vn}, E′ = {(vi, vi+1)| 1 ≤ i ≤ n − 1}, v1 = u, vn = v を満たす木 (E′, V′)を u から v へのパスといい, [u, v] で表す. また, [u, v]\ {u, v} を [[u, v]] で表 す. u, v, w ∈ V に対して, [u, v], [v, w], [w, u] に共通す
人工知能学会研究会資料 SIG-FPAI-B506-14
るノードを{u, v, w} の中心 [12] といい, c(u, v, w) で表 す. V′ ⊆ V , E′ ⊆ E, T′ = (V′, E′)とする. すべて の u, v∈ V′に対して u から v へのパスが T’ 中に存在 するとき, T′を T の部分木という. v ∈ V に対して, {u ∈ T | (u, v) ∈ E} を v の隣接ノードといい, N(v) で 表す. 特に, 根付き木 T の根を r とするとき, ノード v(∈ T\ {r}) に対して, [r, v] ∩ N(v) のノードを v の親とい い, par (v) で表す. また, [r, v]\ {v} のノードを v の先 祖という. u, v∈ T に対して, v が u の親であるとき, u を v の子といい, v が u の先祖であるとき, u を v の子 孫という. 子を持たないノードを葉という. v∈ T に対 して, v および v の子孫からなる Trの部分木を Trの vを根とした完全部分木といい, Tr[v]で表す. 本論文では, 根付き木 Trにおいて, v が u の先祖で あることを, u <rvと表し, u <rvまたは u = v であ ることを, u ≤r vと表す. また, u≤r v, v ≤r uを共 に満たさないことを, u #r vと表す. u, v ∈ T に対し て, u≤rw, v≤rwであり, w′ <r wなる w′が存在し ないような w を u と v の最近共通先祖 (LCA) といい, u⊔rvで表す. 以上より, 以下の自明な補題を得る. 補題 1 根付き木 T の根ノードを r とし, u, v∈ T とす る. このとき c(u, v, r) = u⊔rvが成り立つ. アルファベット Σ の要素が各ノードに割り当てられ ているような木をラベル付き木という. また各ノード に割り当てられた記号をラベルといい, v∈ T のラベル を l(v) で表す. ε̸∈ Σ を空文字とし, Σ ∪ {ε} = Σεと する. 本論文ではラベル付き木を単に木として扱う. 定義 1 (編集操作 [4]) 根付き木 T の編集操作 (edit op-erations)を以下のように定義する. 1. 置換 (Substitution): T のノード v のラベルを変 更する. 2. 削除 (Deletion): v′ ∈ T を親に持つ v を削除し, vの子を v′の子とする. 3. 挿入 (Insertion): 削除の逆操作. ノード v を v′ ∈ Tの子として挿入し, v′の子の部分集合を v の子 とする. ここで, ラベルの組 (l1, l2)∈ (Σε× Σε\ {(ε, ε)}) に 対して, 編集操作を (l17→ l2)と書き, l1̸= ε かつ l2̸= ε のときに置換を, l2= εのときに削除を, l1= εのとき に挿入をそれぞれ表す. さらに, ラベルの組に, コスト関数 (cost function) γ : (Σε× Σε\ {(ε, ε)}) → R+ を定義する. 多くの 場合, コスト関数 γ はメトリック (metric) の制約をつ ける. すなわち, γ(l1, l2)≥ 0, γ(l1, l2) = 0 iff l1 = l2, γ(l1, l2) = γ(l2, l1)および γ(l1, l3)≤ γ(l1, l2)+γ(l2, l3) を満たすようなコスト関数をもちいる. l1̸= l2のとき, γ(l1, l2) = 1となるコスト関数を単一コスト関数 (unit cost function)といい, µ で表す. 定義 2 (編集距離 [4]) γ をコスト関数とする. 編集操 作 e = (l1 7→ l2)に対して, γ(e) = γ(l1, l2)で与えら れる値を, 編集操作 e のコストという. また, 編集操作 列 E = e1, . . . , ek に対して, γ(E) = ∑k i=iγ(ei)で与 えられる値を, 編集操作列 E のコストという. そして, 根付き木 T1と T2に対して, 以下のように定義される τr
Tai(T1, T2)を, T1と T2間の編集距離 (edit distance)
という. τr Tai(T1, T2) = min { γ(E) Eは T1から T2を得る ための編集操作列 } . 定義 3 (Tai マッピング [4]) Tur 1 と T vr 2 を根付き木と し, M ⊆ V (T1)× V (T2)とする. このとき, 任意の (u1, v1), (u2, v2)∈ M が以下の条件を満たすとき, 3 つ
組 (M, T1, T2)を Taiマッピング (Tai mapping) という.
1. u1= u2 iff v1= v2 (一対一対応). 2. u1≤ur u2 iff v1≤vrv2(先祖関係保存). 誤解のない限り, (M, T1, T2)を単に M と書く. また, T1, T2間のすべての Tai マッピングの集合をMrTai(T1, T2) で表す. 集合{v ∈ T1 | (v, w) ∈ M} と {w ∈ T2 | (v, w) ∈ M} を, それぞれ M|1, M|2で表す. M ∈ MrTai(T1, T2) に対して, M のコスト (cost) γ(M ) を以下のように与 える. γ(M ) = ∑ (v,w)∈M γ(v, w) + ∑ v∈T1\ M|1 γ(v, ε) + ∑ w∈T2\ M|2 γ(ε, w).
定理 1 (Tai [4]) τTaiγ (T1, T2) = min{γ(M) | M ∈
MTai(T1, T2)}. 定義 4 (孤立部分木マッピング [5]) Tur 1 , T vr 2 を根付 き木とし, M ∈ MrTai(T1, T2)とする. 任意の (u1, v1), (u2, v2), (u3, v3)∈ M が以下の条件を満たすとき, M を孤立部分木マッピング (isolated-subtree mapping) [5] (あるいは制限マッピング (constrained mapping) [10, 11])といい, M∈ MrIlst(T1, T2)で表す. u1⊔uru2= u1⊔uru3 ⇐⇒ v1⊔vr v2= v1⊔vrv3. 定理 1 と同様に, 孤立部分木距離 (isolated-subtree distance) [5] τr (T 1, T2)を以下のように定める.
τIlstr (T1, T2) = min{γ(M) | M ∈ MrIlst(T1, T2)}. さらに, 以下の定理が知られている. 定理 2 T1, T2 を木とし, n = |T1|, m = |T2|, D = max{d(T1), d(T2)}, d = min{d(T1), d(T2)} とする. 1. ([3]) MrIlst(T1, T2) ⊆ MrTai(T1, T2). すなわち, τr Tai(T1, T2)≤ τ r Ilst(T1, T2). 2. ([1, 11]) τr Tai(T1, T2)の計算問題は, T1, T2が二 分木であっても MAX SNP 困難である. 3. ([6]) τIlstr (T1, T2)は O(nmd) 時間で計算可能で ある. 編集操作や編集距離を根無し木に拡張するため, 根無 し木におけるノードの削除, 挿入を定式化する. 定義 5 (根無し木の編集操作) 根無し木 T の編集操作を 以下のように定義する. 1. 置換: 根付き木同様, T のノード v のラベルを変 更する. 2. 削除: ノード v′ ∈ N(v) を選択したのち, ノード vを削除し N (v)\{v′} を N(v′)に追加する. 言い 換えると, 各 u∈ N(v) と v をつなぐ辺 (u, v), お よびノード v を削除し, すべての u∈ N(v) \ {v′} に対して, 辺 (u, v′)を追加する. 図 1 (上) に操作 の模式図を示す. 3. 挿入: 削除の逆操作. ノード v′ に対して N ⊆ N (v′)を選んだ後, ノード v を挿入し N∪ {v′} を N (v)とする. 言い換えると, ノード v を追加し, すべての u ∈ N に対して辺 (u, v′)を削除, その 後すべての u∈ N ∪ {v′} に対して辺 (u, v) を追 加する. 図 1 (下) に操作の模式図を示す. 削除 v v 0 v1 vm vi 7→ v 0 v1 vm vi 挿入 v 0 u w vm v 1 7→ v v 0 u w vm v 1 図 1: 根無し木における削除 (上) と挿入 (下). 定義 6 (根無し木編集距離) γ をコスト関数とする. そ して, 根無し木 T1と T2に対して, 以下のように定義 される τTai(T1, T2)を, T1と T2間の根無し編集距離と いう. τTai(T1, T2) = min { γ(E) Eは T1から T2を得るた めの根無し編集操作列 } . 定義 7 (根無し Tai マッピング (合流マッピング)) T1, T2を根無し木とする. M ⊆ V (T1)× V (T2)が以下の条 件を満たすとき, 3 つ組 (M, T1, T2)を Taiマッピング
(Tai mapping),あるいは根付き木間の Tai マッピング
との区別のため,合流マッピング (confluent mapping) という. 1. ∀(u1, v1), (u2, v2)∈ M, u1= u2 iff v1= v2(一対 一対応). 2. 任意の (u1, v1), (u2, v2), (u3, v3)∈ M が [[u1, u2]]̸= ∅ かつ [[v1, v2]] ̸= ∅, c(u1, u2, u3) ∈ [[u1, u2]] ⇔ c(v1, v2, v3) ∈ [[v1, v2]] を満たすように取り換え ることができる (合流条件). 誤解のない限り, (M, T1, T2)を単に M と書く. また, T1, T2間のすべての合流マッピングの集合をMCnfl(T1, T2) で表す. SISA’16 [7]では, パス保存マッピングを導入したが, パ ス保存マッピングの最小コストが編集距離と一致しな いことが判明した. そのため, 上記合流マッピングを もって, パス保存マッピングの代替とする. 定理 3 T1, T2を根無し木とする. τTai(T1, T2) = min{γ(M) | M ∈ MCnfl(T1, T2)} . 定義 8 (中心保存マッピング [12]) M が以下の条件を 満たすとき, M を中心保存マッピング (center-preserving mapping)という. 任意の (u1, v1), (u2, v2), (u3, v3)∈ M に対して, (c(u1, u2, u3), c(v1, v2, v3))∈ M.
3
根無し孤立部分木距離
本節では, 根付き木の孤立部分木マッピングおよび孤 立部分木距離を根無し木に拡張する. 定義 9 (根無し孤立部分木マッピング) T1, T2を根無し 木とし, M ∈ MCnfl, (ur, ur) ∈ M とする. 任意の(u1, v1), (u2, v2), (u3, v3) ∈ M が以下の条件を満たす
とき, M を (ur, vr)孤立部分木マッピングという.
c(ur, u1, u2) = c(ur, u2, u3) = c(ur, u3, u1)
⇔ c(vr, v1, v2) = c(vr, v2, v3) = c(vr, v3, v1). また, すべての (u, v)∈ M が (u, v) 孤立部分木マッピ ングとなるような M を,孤立部分木マッピングといい, M ∈ MIlst(T1, T2)と表す. 定義 10 (根無し孤立部分木距離) 孤立部分木距離 τIlst(T1, T2)を以下のように定義する.
τIlst(T1, T2) = min{γ(M) | M ∈ MIlst(T1, T2)} .
以下は, 孤立部分木マッピングに関する予想である. 推測 1 T1, T2を根無し木とする. このとき, 以下は等 価である. 1. M ∈ MIlst(T1, T2) 2. 任意の (u1, v1), (u2, v2), (u3, v3), (u4, v4)∈ M に 対して, 以下が成り立つ.
c(u1, u2, u3) = c(u1, u2, u4) = c(u1, u3, u4)
⇔ c(v1, v2, v3) = c(v1, v2, v4) = c(v1, v3, v4). 推測 2 T1, T2を根無し木とする. このとき, 以下が成 り立つ. τIlst(T1, T2) = min { γ(M ) M ∈ MrIlst(Tur 1 , T vr 2 ), (ur, vr)∈ V (T1)× V (T2) } . 推測 2 の確認のため, 2 つの根無し木の, すべてのノー ドの組を根とした根付き木として孤立部分木距離を計 算し最小値を取ったものと, 中心保存距離の比較を行う. ここで, コスト関数は常に単一コスト関数 µ とする. 本論文では, KEGG [2] の提供する N 型糖鎖データ を用いる. 木の総数は 2, 142 であり, 総当たりの組数 は 2, 293, 011 となる. ノードと葉の数の平均はそれぞ れ 11.0696, 3.2876 であり, 高さと次数の平均はそれぞ れ 5.3838, 2.0724 である. 距離の分布を図 2 に示す. また, 距離の大小関係のみ の比較結果を表 1 に示す. 表 1: 根付き孤立部分木距離の最小値と中心保存距離 の大小関係 不等式 組数 % 中心保存距離=最小孤立部分木距離 2078529 90.6463 中心保存距離>最小孤立部分木距離 214482 9.3537 中心保存距離<最小孤立部分木距離 0 0.0000 表 1 より, 根付き孤立部分木距離の最小値が中心保 存距離を下回るものはなかった. これは, 次数 2 距離と 根付き孤立部分木距離の関係と同様であるため, 推測 2 を否定しえない. 0 5 10 15 20 25 30 35 40 45 0 5 10 15 20 25 30 35 40 45 Center-preserving distance
Minimum of isolated-subtree distance
図 2: 根付き孤立部分木距離の最小値と中心保存距離 の分布.
4
まとめと今後の課題
本論文では, 根付き木の編集距離を根無し木に拡張 し, Tai マッピング, 孤立部分木マッピングも同様に根 無し木への拡張を行った. また, N 型糖鎖をもちいて, 根無し孤立部分木距離と等価であると予想される任意 のノードの組を根と考えた根付き孤立部分木距離の最 小値と, 中心保存距離との比較を行った. N 型糖鎖で は, 推測 2 を否定する要素, すなわち, 中心保存距離を 上回る最小根付き孤立部分木距離は見つからなかった. よって, 推論 2 の証明が今後の課題として挙げられる.参考文献
[1] K. Hirata, Y. Yamamoto, T. Kuboyama: Im-proved MAX SNP-hard results for finding an edit distance between unordered trees, Proc. CPM 2011, LNCS 6661, 402–415, 2011.
[2] KEGG: Kyoto Encyclopedia of Genes and Genomes, http://www.kegg.jp/.
[3] T. Kuboyama: Matching and learning in trees, Ph.D thesis, University of Tokyo, 2007.
[4] K.-C. Tai: The tree-to-tree correction problem, J. ACM 26, 422–433, 1979.
[5] J. T. L. Wang, K. Zhang: Finding similar consensus between trees: An algorithm and a distance hierar-chy , Pattern Recog. 34, 127–137, 2001.
[6] Y. Yamamoto, K, Hirata, T. Kuboyama: Tractable and intractable variations of unordered tree edit dis-tance, Internat. J. Found. Comput. Sci. 25, 307–329, 2014.
[7] T. Yoshino, K. Hirata: Enhanced Tai Mapping for Unrooted Trees, Proc. SISA’16, 6–11, 2016.
[8] T. Yoshino, K. Hirata: Tai mapping hierarchy for rooted labeled trees through common subforest , The-ory of Comput. Sys (to appear).
[9] K. Zhang: Algorithms for the constrained editing dis-tance between ordered labeled trees and related prob-lems, Pattern Recog. 28, 463–474, 1995.
[10] K. Zhang: A constrained edit distance between un-ordered labeled trees, Algorithmica 15, 205-222, 1996. [11] K. Zhang, T. Jiang: Some MAX SNP-hard results concerning unordered labeled trees, Inform. Process. Lett. 49, 249–254, 1994.
[12] K. Zhang, J. Wang, D. Shasha: On the editing dis-tance between undirected acyclic graphs, Internat. J. Found. Comput. Sci. 7, 43-58. 1996.
