Tai マッピングの根無し木への拡張

Tai

マッピングの根無し木への拡張

Enhanced Tai Mapping to Unrooted Trees

芳野拓也

1∗

_平田耕一

2

Takuya Yoshino

1

_{Kouichi Hirata}

2

1

_{九州工業大学情報工学府情報工学専攻}

1

_{Graduate School of Computer Science and Systems Engineering,}

Kyushu Institute of Technology

2

_{九州工業大学情報工学研究院}

2

_{Department of Artificial Intelligence, Kyushu Institute of Technology}

Abstract: In this paper, we enhance a Tai mapping to unrooted trees, motivated by the 4-point condition and the 3-4-point condition for phylogenetic trees. First, we introduce 4- 4-point-preserving mapping, rooted 4-point-4-point-preserving mapping and 3-point-4-point-preserving mapping, addi-tionally subtree-preserving mapping, center-preserving mapping and and path-preserving mapping as a bijection of nodes in two unrooted trees. Then, we show that, for rooted trees, a constrained mapping coincides with a 3-point-preserving mapping and a less-constrained mapping coincides with a 4-point-preserving mapping and a rooted 4-point preserving mapping. We also show that, for unrooted trees, a subtree-preserving mapping is always center-preserving, a center-preserving mapping is always 4-point-preserving and a 4-point-preserving mapping is always path-preserving, but no converse directions hold in general.

1

はじめに

2 つの根付き木 (rooted tree) 間の Tai マッピング (Tai mapping) [8] は, 単射であり, かつ, 先祖子孫関係 を保存する (根付き順序木の場合はさらに兄弟関係を保 存する) ノード間の対応付けである. この Tai マッピン グは, マッピングによる対応付けがあるノードを置換, 対応付けがない木のノードを削除と挿入とみなすこと で, 2 つの根付き木間の Tai マッピングの最小コストが 木編集距離 (tree edit distance) となることが知られて いる [8]. また, Tai マッピングに様々な制約を入れる ことで, 数多くの木編集距離の変種を導入することが でき [4, 5, 10, 11, 12], そのときの Tai マッピングが階 層を成すことも知られている [3, 9]. さらに, Tai マッ ピングは, 木カーネルの一種であるマッピングカーネ ル [2, 6] の定式化における数え上げの対象でもある. このように, 根付き木において Tai マッピングは木編 集距離や木カーネルとして重要な概念であるが, この Tai マッピングを根無し木 (unrooted tree) に拡張する ためには, 単射であることに加えて, 先祖子孫関係に代 わる条件を導入する必要がある. Zhang ら [12] は, 挿 ∗_{連絡先：九州工業大学情報工学府情報工学専攻}       〒 820-8502 福岡県飯塚市川津 680-4        E-mail: [email protected] 入と削除を次数 2 以下のノードに制限した次数 2 距離 (degree-2 distance) を根無し木に拡張する際, 根付き木 の LCA 保存マッピングの拡張として, 3 つのノードの 中心 (center) を保存する中心保存マッピング (center-preserving mapping) を導入した. ここで, 3 つのノー ドの中心とは, 2 つのノード間の 3 つのパスの共通ノー ドである. 本研究では, この中心に着目する. 生物種の進化を表す進化系統樹 (phylogenetic tree) [7] は, 葉に生物種のラベルが付いた根無し木もしくは根付 き木である. この進化系統樹の再構成とは, すべての生 物種 (葉) 間の距離が距離行列として与えらえれたとき, その距離がパス上の辺の重みの総和となる進化系統樹 を求める問題である. 距離行列から進化系統樹を再構成できるとき, 距離 行列は加法的である (additive) といい, 距離行列から 葉の高さがすべて等しい根付き進化系統樹を構成でき るとき, 距離行列は超計量的である (ultrametric) とい う [7]. このとき, 距離行列における任意の異なる 4 つ の生物種が 4 点条件 (4-point condition) [1] を満たす とき, そのときに限り, 距離行列は加法的となる [7]. ま た, 加法的距離行列における任意の異なる 3 つの生物 種が 3 点条件 (3-point condition) を満たすとき, その ときに限り, 距離行列は超計量的になる [7]. この 4 点条件と 3 点条件は, 辺の重みの総和としての 人工知能学会研究会資料 SIG-FPAI-B502-16

距離についての条件である. 本論文では, この 2 つの条 件を, 中心を用いることで木のトポロジーを特徴づける 条件に変更する. ノード u, v, w の中心を c(u, v, w) とす る. 根無し木のノード u, v, w, x が c(u, v, w) = c(u, v, x) かつ c(u, w, x) = c(v, w, x) を満たすとき, ノードの 2 つの組 (u, v) と (w, x) は 4 点条件を満たすという. ま た, 先祖子孫関係≤ に対して, 根 r を持つ根付き木の ノード u, v, w が c(u, w, r) ≤ c(v, w, r) = c(u, v, r) を 満たすとき, (u, v, w) は 3 点条件を満たすという. 根無し木 T1と T2に対して, M⊆ V (T1)× V (T2) を 単射とする. M に 4 点条件と 3 点条件を保存するとい う条件を加えることによって, 4 点保存マッピング (4-point-preserving mapping), 根付き 4 点保存マッピン グ (rooted 4-point-preserving mapping), 3 点保存マッ ピング (3-point-preserving mapping) を導入する. また, M が T1の部分木と T2の部分木を対応付ける とき M を部分木保存マッピング (subtree-preserving mapping) という. また, M が T1, T2のパスを対応付 けるとき, M をパス保存マッピング (path-preserving mapping) という. これらの準備の下で, 本論文では, M が根付き木の マッピングの場合, 以下が成り立つことを示す. M は制限 (constrained) マッピング [10, 11] ⇐⇒ M は 3 点保存マッピング. M は劣制限 (less-constrained) マッピング [4] ⇐⇒ M は 4 点保存マッピング ⇐⇒ M は根付き 4 点保存マッピング. また, M が根無し木のマッピングの場合, 以下の含意が 成り立つことを示す. ただし, 一般に逆は成り立たない. M は部分木保存マッピング =⇒ M は中心保存マッピング =⇒ M は 4 点保存マッピング =⇒ M はパス保存マッピング.

2

準備

閉路を持たない連結グラフを木という. 木 T = (V, E) に対して, v∈ V (T ) を単に v ∈ T と表す. 木 T のうち, 根ノード r ∈ T を 1 つ選んだものを根 付き木, そうでないものを根無し木という. 根付き木 T の根を r(T ) と表す. T = (V, E) を木とする. u, v ∈ T に対して, V′ = {v1, . . . , vn}, E′ = {(vi, vi+1) | 1 ≤ i ≤ n − 1}, v1 = u, vn = v を満たす木 (E′, V′) を u から v へのパスとい い, [u, v] で表す. u, v, w∈ T に対して, [u, v], [v, w], [w, u] に共通するノードを_{{u, v, w} の中心 [12] といい, c(u, v, w)} で表す. V′ _{⊆ V , E}′ _{⊆ E, T}′ _{= (V}′_{, E}′_{) とする. すべ} ての u, v∈ V′_{に対して u から v へのパスが T’ 中に存} 在するとき, T′を T の部分木という. 特に, 根付き木 T の根を r とするとき, ノード v(∈ T \ {r}) に対して, [r, v] 上の v に隣接するノードを v の親といい, par (v) で表す. また, [r, v]\ {v} のノード を v の先祖という. u, v∈ T に対して, v が u の親であ るとき, u を v の子という. 子を持たないノードを葉と いう. 本論文では, v が u の先祖であることを, u < v と表 し, u < v または u = v であることを, u ≤ v と表す. u, v ∈ T に対して, u ≤ w, v ≤ w であり, w′ < w な る w′が存在しないような w を u と v の最近共通先祖 (LCA) といい, u⊔ v で表す. 補題 1 根付き木 T の根ノードを r とし, u, v∈ T とす る. このとき c(u, v, r) = u⊔ v が成り立つ. ノード u, v ∈ T に対して, 先行走査順 pre に関し

て pre(u) ≤ pre(v) であり, 後行走査順 post に関して post (u)≤ post(v) であるとき, u を, v の左にあるとい

い, u ⪯ v と表す. 根付き木に対して, 兄弟間の左右の 順序関係が与えられているものを順序木, そうでないも のを無順序木という. アルファベット Σ の要素が各ノードに割り当てられ ているような木をラベル付き木という. また各ノード に割り当てられた記号をラベルといい, v∈ T のラベル を l(v) で表す. 最後に, 進化系統樹 [7] における 4 点条件と 3 点条件 を導入する. 本来の 4 点条件と 3 点条件の定義は辺の 重みの和によって定義されるが, 本稿では中心を用いる ことによって, (根の有無に関わらず) 木のトポロジー に基づいて定式化する. 定義 1 (4 点条件) 木 T の 2 組のノードの対 (u, v) と (w, x) に対して, c(u, v, w) = c(u, v, x) and c(u, w, x) =

c(v, w, x) が成り立つとき, その 2 組のノード対は 4 点

条件を満たすという.

図 1 (左) は, 4 点条件のトポロジーである. ここで, 実線はパス, c(u, v, w) = c(u, v, x) = c, c(u, w, x) =

c(v, w, x) = d である. 中心と 4 点条件は, 根付き木でも定義できる. 図 1 (右) はノード r を根とする根付き木における 4 点条件 のトポロジーである. 定義 2 (3 点条件) T を根付き木とし, その根ノード r とする. T のノードの 3 つ組 (u, v, w) に対して, c(u, w, r)≤ c(v, w, r) = c(u, v, r), すなわち u⊔ w ≤ v ⊔ w = u ⊔ v が成り立つとき, その 3 つ組は 3 点条件を満たすという. 図 2 は根付き木の 3 点条件のトポロジーである. 進化系統樹の再構成では, 以下の補題が知られている.

u w d v x r u v d w x 図 1: 根無し木 (左) および根付き木 (右) における 4 点 条件のトポロジー. r u w v 図 2: 根付き木における 3 点条件のトポロジー. 補題 2 (cf. [7]) 根無し木の任意の 4 つの異なる葉に対 して, 4 点条件を満たすような 2 組の対の取り方が存在 する. 補題 3 (cf. [7]) 根付き木の任意の 3 つの異なる葉に 対して, 3 点条件を満たすような 3 つ組の取り方が存在 する.

3

マッピング

本節では, マッピングを 2 つの木のノード間の一対一 対応として定義する. 定義 3 (マッピング [8]) T1, T2を木とし, M ⊆ V (T1)× V (T2) とする. M が以下を満たすとき, 3 つ組 (M, T1, T2) を木 T1, T2間のマッピングという: ∀(u1, u2), (v1, v2)∈ M ( u1= v1 ⇐⇒ u2= v2 ) (一対一対応). 誤解の恐れがない場合, 3 つ組 (M, T1, T2) を, 単に M で表す. また, 根付き木 (根無し木) 間のマッピングを 単に根付き (根無し) マッピングという. 定義 4 (Tai マッピング [8]) T1, T2を根付き木, M を T1, T2間の根付きマッピングとする. M が以下を満た すとき, M を T1, T2間の順序 Tai マッピングという: 1. ∀(u1, u2), (v1, v2)∈ M ( u1≤ v1 ⇐⇒ u2≤ v2 ) (先祖子孫関係の保存). 2. ∀(u1, u2), (v1, v2)∈ M ( u1⪯ v1 ⇐⇒ u2⪯ v2 ) (兄弟関係の保存). また, M が上記条件の 1 を満たすとき, M を T1, T2間 の無順序 Tai マッピングという. M が順序 Tai マッ ピングまたは無順序 Tai マッピングであるとき, M ∈ MTai(T1, T2) と表記する. また, 根付き木に関して, Tai マッピングの変種を導 入する. 定義 5 (根付きマッピングの変種 (1)) M を T1, T2間 の根付きマッピングとする. 1. M が以下を満たすとき, M をトップダウンマッ ピング [5] といい, M ∈ MTop(T1, T2) と表す. ∀(v1, v2)∈ M ( (par (v1), par (v2))∈ M ) . 2. M が以下を満たすとき, M を LCA 保存マッピ ング [12] といい, M ∈ MLca(T1, T2) と表す. ∀(u1, u2), (v1, v2)∈ M ( (u1⊔ v1, u2⊔ v2)∈ M ) . 3. M が以下を満たすとき, M を孤立部分木マッピ ング [9], もしくは 制限マッピング [10, 11] とい い, M∈ MIlSt(T1, T2) と表す. ∀(u₍1, u2), (v1, v2), (w1, w2)∈ M, w1< u1⊔ v1 ⇐⇒ w2< u2⊔ v2 ) . 補題 4 根付き木 T1, T2と, A ∈ {Top,Lca,IlSt} に 対して, M ∈ MA(T1, T2) ならば, M ∈ MTai(T1, T2). 定義 6 (根付きマッピングの変種 (2)) M を T1, T2間 の根付きマッピングとする. 1. M が以下を満たすとき, M を劣制限マッピング [4] といい, M∈ MLess(T1, T2) と表す. ∀(u(1, u2), (v1, v2), (w1, w2)∈ M, u1⊔ v1< u1⊔ w1=⇒ v2⊔ w2= u2⊔ w2 ) . 2. M が Tai マッピングであり, 劣制限マッピングで あるとき, すなわち M ∈ M_Tai(T1, T2)∩ MLess(T1, T2) であるとき, M を劣制限 Tai マッピングといい, M ∈ M_LessTai(T1, T2) と表す. 次に, 根無しマッピングの変種と, 4 点条件と 3 点条 件に関連した根付きマッピングの変種を導入する. 定義 7 (根無しマッピングの変種) M を T1, T2間の根 無しマッピングとする. 1. M が以下のパス保存条件を満たすとき, M をパ ス保存マッピングといい, M∈ MPath(T1, T2) と 表す: ∀(u(1, u2), (v1, v2), (w1, w2)∈ M, w1∈ [u1, v1] ⇐⇒ w2∈ [u2, v2] ) .

2. M が以下の中心保存条件 [12] を満たすとき, M を中心保存マッピングといい, M ∈ MCnt(T1, T2) と表す: ∀(u₍1, u2), (v1, v2), (w1, w2)∈ M, (c(u1, v1, w1), c(u2, v2, w2))∈ M ) . 3. 集合{u ∈ T1| (u, v) ∈ M} と {v ∈ T2| (u, v) ∈ M} が, それぞれ T1= (V1, E1) と T2= (V2, E2) の部分木を誘導し, 任意の (u1, u2), (v1, v2)∈ M に対して, (u1, v1)∈ E1 ⇐⇒ (u2, v2)∈ E2を満たすとき, M を部分 木保存といい, M ∈ MSubt(T1, T2) と表す. 4. M が以下の 4 点保存条件を満たすとき, M を 4 点保存マッピングといい, M ∈ M4Pnt(T1, T2) と 表す: 任意の (u1, u2), (v1, v2), (w1, w2), (x1, x2) ∈ M に対して, 以下を満たすように ui, vi, wi, xi (i = 1, 2) を置き換えることができる. c(u1, v1, w1) = c(u1, v1, x1) かつ c(u1, w1, x1) = c(v1, w1, x1) ⇐⇒ c(u2, v2, w2) = c(u2, v2, x2) かつ c(u2, w2, x2) = c(v2, w2, x2). また, 根付き木の 4 点保存条件を以下の通りに導入 する. 定義 8 (根付き 4 点保存条件) T1, T2をそれぞれ, r1, r2 を根とする根付き木, M を T1, T2間の根付きマッピン グとする. M が以下の根付き 4 点保存条件を満たす とき, M を根付き 4 点保存マッピングといい, M ∈ Mr4Pnt(T1, T2) と表す: 任意の (u1, u2), (v1, v2), (w1, w2) ∈ M に対して, 以下を満たすように ui, vi, wi(i = 1, 2) を置き換える ことができる. c(u1, v1, w1) = c(u1, v1, r1) かつ c(u1, w1, r1) = c(v1, w1, r1) ⇐⇒ c(u2, v2, w2) = c(u2, v2, r2) かつ c(u2, w2, r2) = c(v2, w2, r2). M が Tai マッピングであり, 根付き 4 点保存マッピ ングでもあるとき, すなわち, M ∈ MTai(T1, T2)∩ Mr4Pnt(T1, T2) であるとき, M を根付き 4 点保存 Tai マッピングといい, M∈ Mr4PntTai(T1, T2) と表す. 定義 9 (3 点保存条件) T1, T2をそれぞれ, r1, r2 を根 とする根付き木, M を T1, T2間の根付きマッピングと する. M が以下の 3 点保存条件を満たすとき, M を 3 点保存マッピングといい, M ∈ M3Pnt(T1, T2) と表す: 任意の (u1, u2), (v1, v2), (w1, w2) ∈ M に対して, 以下を満たすように ui, vi, wi(i = 1, 2) を置き換える ことができる. c(u1, w1, r1)≤ c(v1, w1, r1) = c(u1, v1, r1) (u1⊔ w1≤ v1⊔ w1= u1⊔ v1と等価) ⇐⇒ c(u2, w2, r2)≤ c(v2, w2, r2) = c(u2, v2, r2) (u2⊔ w2≤ v2⊔ w2= u2⊔ v2と等価).

4

マッピングの階層

根付きマッピングには以下の階層が知られている.

MTop(T1, T2)⊂ MLca(T1, T2)⊂ MIlSt(T1, T2)⊂

MLessTai(T1, T2)⊂ MTai(T1, T2). まず, 根付きマッピングの改装について議論する. 以 下, T1, T2を根付き木とする. 定理 1 M3Pnt(T1, T2) =MIlSt(T1, T2). [証明] M ∈ M_IlSt(T1, T2) と仮定すると, M は w1 ≤ u1⊔ v1 ⇐⇒ w2≤ u2⊔ v2を満たす. このとき, M は 図 3 で示す M1, M2, M3のどれかの形をとる. このう ち, 3 点保存条件を満たすのは M1と M3である. また, uiを viと置き換えることにより, M2もまた, 3 点保存 条件を満たす. したがって, M ∈ M3Pnt(T1, T2) が成 り立つ. 一方, M ∈ M3Pnt(T1, T2) と仮定すると, M は u1⊔ w1≤ v1⊔w1= u1⊔v1 ⇐⇒ u2⊔w2≤ v2⊔w2= u2⊔v2 を満たす. このとき, M は M1, M2′, M3のどれかの形 をとる. M2′について, w1≤ u1⊔v1 ⇐⇒ w2≤ u2⊔v2 が成り立つ. したがって, M ∈ MIlSt(T1, T2) が成り立 つ. 2 補題 5 M ∈ MTai(T1, T2)\ Mr4Pnt(T1, T2) となる根 付きマッピング M が存在する. 補題 6 M ∈ Mr4Pnt(T1, T2)\ MTai(T1, T2) となる根 付きマッピング M が存在する. 定理 2 M4Pnt(T1, T2) =Mr4Pnt(T1, T2) =MLess(T1, T2). [証明] M_4Pnt(T1, T2) =Mr4Pnt(T1, T2) は自明に成り 立つ. 補題 1 より, 根付き 4 点保存条件を以下のように 書き換えることができる. c(u1, v1, w1) = u1⊔ v1かつ u1⊔ w1= v1⊔ w1 ⇐⇒ c(u2, v2, w2) = u2⊔ v2かつ u2⊔ w2= v2⊔ w2.

r 1 1 u1 w1 v 1 r 2 2 u2 w2 v 2 r 1 u 1 d 1 w1 v1 r 2 u 2 d 2 w2 v2 M1 M2 r1 v 1 d 1 w 1 u 1 r2 v 2 d 2 w 2 u 2 r 1 u1 w1 v1 r 2 u2 w2 v2 M2′ M3 図 3: 定理 1 の証明に用いる根付きマッピング Mi. M ∈ M_r4Pnt(T1, T2) と仮定する. もし, u1⊔ v1 < u1⊔w1, ならば T1中の u1, v1, w1のトポロジーは, 図 4 (1), (2), (3) に示す通りになる. このとき (2), (3) では u1 < v1 or v1 < u1のどちらか一方が成り立つ. よっ て, c(u1, v1, w1) = u1⊔ v1 < u1⊔ w1 = v1⊔ w1が 成り立つ. 根付き 4 点保存条件より, c(u2, v2, w2) = u2⊔ v2及び u2⊔ w2 = v2⊔ w2が成り立つ. ゆえに, M ∈ M_Less(T1, T2) が成り立つ. r1 d 1 1 u 1 v 1 w1 r1 d 1 v1 u 1 w1 r1 w 1 v1 u 1 r2 d 2 2 u 2 v 2 w2 (1) (2) (3) (4) r2 2 v 2 u 2 w 2 r2 w 2 v 2 u 2 r 2 2 u 2 v 2 w 2 (5) (6) (7) 図 4: 定理 2 の証明に用いる木のトポロジー. 逆に, M ∈ MLess(T1, T2) を仮定する. u1⊔ v1 < u1⊔w1とすると, 図 4 (1), (2), (3) より, c(u1, v1, w1) = u1⊔ v1及び u1⊔ w1= v1⊔ w1が成り立つ. 一方,M は 劣制限マッピングであるため, v2⊔ w2= u2⊔ w2が成 り立つ. そのため, c(u2, v2, w2) = u2⊔ v2を示せばよ いことになる. もし, u2⊔ v2< u2⊔ w2ならば, T2中での u2, v2, w2 のトポロジーは図 4 (4), (5), (6) に示す通りになり, c(u2, v2, w2) = u2⊔v2= c2が成り立つ. もし, u2⊔v2= u2⊔w2ならば, T2中での u2, v2, w2のトポロジーは図 4 (7) に示す通りになり, c(u2, v2, w2) = u2⊔ v2 = c2が 成り立つ. したがって, M∈ Mr4Pnt(T1, T2) が成り立つ. 2 注意 1 定理 2 のMr4PntTai(T1, T2) =MLessTai(T1, T2) を示すには, T1, T2のトポロジーを図 4 の (1), (4), (7) と比較すればよい. 次に, 根無しマッピングの階層について議論する. 以 下, T1と T2は根無し木とする. 補題 7 MSubt(T1, T2)⊂ MCnt(T1, T2). [証明] M ∈ M_Subt(T1, T2) とし, (u1, u2), (v1, v2), (w1, w2)∈ M とする. このとき, T1の [u1, v1] ([v1, w1], [w1, u1]) と, T2の [u2, v2] ([v2, w2], [w2, u2]) は同型で あるので, (c(u1, v1, w1), c(u2, v2, w2)) ∈ M が成り立 つ. ゆえに, M ∈ MCnt(T1, T2) が成り立つ. 一方, 図 5 のようなマッピング M ∈ MCnt(T1, T2)\ MSubt(T1, T2) が存在する. 2 u 1 Æ u 2 Æ 1 Æ w 1 2 Æ w 2 v 1 Æ v 2 Æ 図 5: 補題 7 の根無しマッピング M . 補題 8 MCnt(T1, T2)⊂ M4Pnt(T1, T2). [証明] M ∈ M_Cnt(T1, T2) とし, (u1, u2), (v1, v2), (w1, w2), (x1, x2)∈ M とする. 補題 1 より, c1 = c(u1, v1, w1) = c(u1, v1, x1) かつ d1 = c(u1, w1, x1) = c(v1, w1, x1) を満たすように, u1, v1, w1, x1を置き換えることができる. もし (c1, c2)∈ M なる ノード c2 ∈ T2が存在するなら, c1 = c(u1, v1, w1) = c(u1, v1, x1) であり M が中心保存マッピングであるこ とから, c2 = c(u2, v2, w2) = c(u1, v1, x1) が成り立つ. また, (d1, d2)∈ M なるノード d2 ∈ T2が存在するな ら, d1= c(u1, w1, x1) = c(v1, w1, x1) であり M が中心 保存マッピングであることから, d2 = c(u2, w2, x2) = c(v2, w2, x2) が成り立つ. ゆえに, M ∈ M4Pnt(T1, T2) となる. 一方, 図 6 のようなマッピング M ∈ M4Pnt(T1, T2)\ MCnt(T1, T2) が存在する. 2 補題 9 M4Pnt(T1, T2)⊂ MPath(T1, T2). [証明] M ∈ M_4Pnt(T1, T2) とする. このとき, すべ ての (u1, u2), (v1, v2), (w1, w2), (x1, x2)∈ M のトポロ ジーは T1, T2中で図 7 の通りになる. (y1, y2) ∈ M となる, y1 ∈ [c1, d1], y2 ∈ [u2, c2] を 仮定する. このとき, c(u1, v1, y1) = c(u1, v1, w1) = c1,

1 1 2 2 1 d 1 2 d 2 v 1 x 1 v 2 x 2 図 6: 補題 8 の M . u 1 w 1 1 d 1 v 1 x 1 u 2 w 2 2 d 2 v 2 x 2 T1 T2 図 7: 補題 9 の証明で用いる M のトポロジー. c(u2, v2, y2) = y2, c(u2, v2, w2) = c2が成り立つ. ゆえ に, y2= c2となる. (y1, y2) ∈ M となる, y1 ∈ [u1, c1], y2 ∈ [v2, d2] を 仮定する. このとき, c(y1, v1, x1) = c(y1, v1, w1) = c1, c(y2, v2, x2) = c(y2, v2, w2) = y2が成り立つ. ま

た, c(u2, y2, w2) = c(u2, y2, x2) = c2, c(u1, y1, w1) =

c(u1, y1, x1) = y1が成り立つ.

(y1, y2) ∈ M となる, y1 ∈ [u1, c1], y2 ∈ [w2, d2]

を仮定する. このとき, c(y1, v1, x1) = c(y1, v1, w1),

c(y2, v2, x2) = d2, c(y2, v2, w2) = y2が成り立つ. また,

c(u2, v2, y2) = c(u2, v2, x2), c(u1, v1, y1) = y1,

c(u1, v1, x1) = c1が成り立つ. ゆえに, y1= c1, y2= d2 となる. 上記の議論を組み合わせることにより, (y1, y2)∈ M に対して以下が成り立つ. ここで, k ∈ {u, v}, l ∈ {w, x} である. 1. y1∈ [c1, d1] iff y2∈ [c2, d2]. 2. y1∈ [u1, v1] iff y2∈ [u2, v2]. 3. y1∈ [w1, x1] iff y2∈ [w2, x2]. 4. y1∈ [k1, c1] かつ y2∈ [l2, d2] ならば, y1= c1 か つ y2= d2. 5. y1∈ [l1, d1] かつ y2∈ [k2, c2] ならば, y1= d1か つ y2= c2. したがって, M∈ MPath(T1, T2) となる. 一方, 図 8 のようなマッピング M ∈ MPath(T1, T2)\ M4Pnt(T1, T2) が存在する. 2 補題 7, 8, 9 をまとめると以下の通りになる. 定理 3 根無し木 T1, T2に対して, 以下が成り立つ. MSubt(T1, T2)⊂ MCnt(T1, T2)⊂ M4Pnt(T1, T2)⊂ MPath(T1, T2). 1 1 2 2 1 d 1 2 d 2 v 1 x 1 w 2 x 2 図 8: 補題 9 の M . 注意 2 操作的には,MTop[5] とMSubtは, 挿入と削除 を次数 1 のノード (根付き木の場合は葉, 根無し木の場 合は端点) に制限したものと対応する. また,MLca[12] と _MCnt [12] は, 挿入と削除を次数 2 以下のノードに 制限したものと対応する.

参考文献

[1] P. Buneman: A note on the metric properties of trees, J. Comb. Theory (B) 17, 48–50, 1974.

[2] K. Hirata, T. Kuboyama, T. Yoshino: Mapping

ker-nels between rooted labeled trees beyond orderd trees,

New Frontier in Artificial Intelligence, LNAI 9067, 317–330, 2015.

[3] T. Kuboyama: Matching and learning in trees, Ph.D thesis, University of Tokyo, 2007.

[4] C. L. Lu, Z.-Y. Su, C. Y. Yang: A new measure of edit distance between labeled trees, Proc. CO-COON’01, LNCS 2108, 338–348, 2001.

[5] S. M. Selkow: The tree-to-tree editing problem, In-form. Process. Lett. 6, 184–186, 1977.

[6] K. Shin, M. Cuturi, T. Kuboyama: Mapping kernels

for trees, Proc. ICML 2011, 2011.

[7] W.-K. Sung: Algorithms in bioinformatics: A

prac-tical introduction, Chapman & Hall/CRC, 2009.

[8] K.-C. Tai, The tree-to-tree correction problem,

J. ACM 26, 422–433, 1979.

[9] J. T. L. Wang, K. Zhang: Finding similar consensus

between trees: An algorithm and a distance hierar-chy , Pattern Recog. 34, 127–137, 2001.

[10] K. Zhang: Algorithms for the constrained editing

dis-tance between ordered labeled trees and related prob-lems, Pattern Recog. 28, 463–474, 1995.

[11] K. Zhang: A constrained edit distance between

un-ordered labeled trees, Algorithmica 15, 205-222, 1996.

[12] K. Zhang, J. Wang and D. Shasha: On the editing

distance between undirected acyclic graphs, Internat.