整数計画法による木間距離の計算を高速化するための新しい定式化

整数計画法による木間距離の計算を高速化するための

新しい定式化

洪 恩平

1

_{小林 靖明}

2

_{山本 章博}

2∗

Eunpyeong Hong

1

,

Yasuaki Kobayashi

2

,

Akihiro Yamamoto

2

1

_{京都大学 工学部 情報学科}

1

_{Undergraduate School of Informatics and Mathematical Science, Faculty of Engineering,}

Kyoto University

2

_{京都大学 情報学研究科}

2

_{Graduate School of Informatics, Kyoto University}

Abstract: Kondo et al.(DS 2014) have proposed the method for computing distances between unordered rooted trees by transforming an instance of the distance computing problem into an instance of an integer programming problem. Kondo et al. showed that the tree edit distance, segmental distance, and bottom-up segmental distance problem can be respectively transformed into an integer programming problem which has O(n1n2) variables and O(n21n22) constraints. In this paper, we divide the tree edit distance problem into O(n1n2) subproblems each of which has only O(n1+ n2) constraints. In case of segmental distance and bottom-up segmental distance problem, each subproblem can be reduced to a maximum weighted matching problem which can be solved in polynomial time. In order to evaluate our method, we compare our method to the previous one which Kondo et al. have proposed. The experimental results show that the performance of our method has been improved remarkably compared to that of the previous method.

1

序論

XML や HTML などの半構造化データやバイオイン フォマティクスで使われる糖鎖データなどはラベル付 き根付き木として扱われる．これらのデータに対して データマイニングや機械学習の手法を適用するために はデータ間の距離を測る必要がある．木の距離として 代表的なものは木の編集距離 [1] という概念である．木 の編集距離のバリエーションとして断片距離，ボトム アップ断片距離 [2] なども定義されている． 木の編集距離は，２つの木が与えられたとき，一方 の木に編集操作を行って他方の木に変換するために必 要な最小コストと定義される．編集操作とはノードの 挿入，削除，置換の 3 つの操作をいう． ラベル付き根付き無順序木の編集距離の計算は NP 困難 [3] であるだけでなく，MAX SNP 困難である [4] ことが示されており，P=NP でない限り，多項式時間 近似スキームは存在しない．しかし，木はかなり頻繁 に現れるデータ構造であるため，木間距離の計算効率 を向上するために様々な手法が提案されている． ∗_{連絡先：京都大学 情報学研究科} 〒 606-8501 京都府京都市左京区吉田本町 E-mail: [email protected] Akutsu ら [5] は２つの木のノード数がそれぞれ n1， n2で，次数が 2 以上であるノードの数がそれぞれ b1， b2のとき O(min(1.26n1+n2, 2b1+b2poly(n1, n2))) 時間 で解く指数時間アルゴリズムを提案した．Horesh ら [6] はヒューリスティック探索アルゴリズムである A*ア ルゴリズムを用いてラベルなし根付き無順序木間の距 離を求めるアルゴリズムを提案し，Higuchi ら [7] がそ れをラベル付き根付き無順序木に対するアルゴリズム へ拡張した．Fukagawa ら [8] はラベル付き根付き無順 序木間距離の計算問題を最大重みクリーク問題に還元 した．Mori ら [9] はこの方法を動的計画法を用いて改 良した．Kondo ら [10] は整数計画問題へ還元し，整数 計画ソルバで解く方法を提案した．整数計画問題とは， 線形計画問題に，変数が全て整数値をとるという条件 を加えたものである．整数計画法を用いる方法は以下の ２つの利点があると考えられる．IBM ILOG CPLEX や Gurobi などの多様な整数計画ソルバが開発されて おり，木間距離計算問題を整数計画問題に定式化すれ ば効率の良い整数計画ソルバを用いて解くことができ る．さらに，編集距離を計算する整数計画問題の制約 式にさらに幾つかの制約式を加えることにより，編集 距離のバリエーションに対しても容易に整数計画問題 人工知能学会研究会資料 SIG-FPAI-B506-15

に定式化できる．Kondo らは断片距離とボトムアップ 断片距離を整数計画問題に定式化できることを示した [10]． 本稿では，Kondo らの方法を動的計画法を用いて改 良する．2 つの木がそれぞれ n1，n2だけのノードを持 つとき，それらの編集距離を計算する問題は O(n2 1n22) 個の制約式を持つ整数計画問題に還元することができ る．この整数計画問題を O(n1n2) 個の部分問題に分割 する．ここで，部分問題とは 2 つの各ノードを根とす る部分木間の編集距離を計算することである．そうす ると，各部分問題は O(n1+ n2) 個の制約式を持つ整数 計画問題として定式化することができ，元の整数計画 問題より制約式の数が削減される．特に断片距離とボ トムアップ断片距離においては最終解を求める問題を 除き，各部分問題が二部グラフの最大重みマッチング 問題に還元される．二部グラフにおける最大重みマッ チング問題は多項式時間で解けることが知られている [11]． 我々のアルゴリズムを説明するために第２節で諸定 義を与える．第３節では木間距離を計算する問題を整 数計画問題へ定式化する方法を説明し，それを動的計 画法を用いて改良する方法を紹介する．第４節では第 ３節で紹介したアルゴリズムと既存のアルゴリズムで 実験を行い，結果を比較する．実験では生物データで ある KEGG の糖鎖データ [12] をを用いた．第５節で 結論を述べる．

2

準備

2.1

ラベル付き根付き木

木 (tree) とは連結で閉路を持たないグラフである．木 の中で１つのノードを選んで，それを根 (root) と定め たものを根付き木 (rooted tree) という．根を定めるこ とにより，ノード間に半順序関係 < を与えることがで きる．すなわち，木 T の任意の２つのノード x と y を 考えたとき，x と y が辺で結ばれており，y が x より 根に近いとき，x < y と書く．このとき，y は x の先祖 (ancestor)，x は y の子孫 (descendant) であるという． x と辺で直接繋がっている先祖を x の親 (parent) とい う．y と辺で直接繋がっている子孫を y の子 (child) と いう．ノード x とノード y が同じ親を持つとき，x と y は兄弟 (siblings) であるという．ノード x とノード y が x < y，あるいは x = y であれば，x≤ y と書く． 本稿では木 T のノード集合を表すとき，単に T と書 くことにする．ノード x のすべての子供の集合を ch(x) と書く．ch(x) の要素数|ch(x)| を x の次数 (degree) と いい，木 T の次数を，maxx∈Tdeg(x) と定義する．次 数が 0 であるノードを T の葉 (leaf) といい，T のすべ ての葉の集合を leaves(T ) と書く．T の根を root(T ) と 書く．ノード x の親を par(x) と表す． 兄弟同士に順序付けがない木を無順序木 (unordered tree) という． 木 T にラベル関数 lT : V → Σ を付けたもの (T, lT) をラベル付き木 (labeled tree) という（ただし，Σ は， アルファベット集合である). 木 T の部分グラフで連結なものを T の部分木 (sub-tree) という．

2.2

木の編集距離

木の編集距離は一方の木に編集操作を行って他方の 木に変換するために必要な最小コストと定義する． 定義 1 (編集操作) 木 T に対する以下の３つの操作を 編集操作 (edit operation) という． 削除 (deletion)：T のノード t を削除し，t が親と子 供を持つなら t の子供を par(t) の子供にする． 挿入 (insertion)：削除の反対である． 置換 (substitution)：T のノードのラベルを別のラ ベルに書き換える． ノード s を挿入する操作，削除する操作，ラベルを書 き換えノード t にする操作のコストを，コスト関数 d を用いて，それぞれ d(ε, s), d(s, ε), d(s, t) と書く．こ こで ε は空白記号で，ノードがない状態を表す．編集 操作 e のコストを cost(e) と表記する．編集操作の列 E = ⟨e1, e2, ..., en⟩ のコストを cost(E) = ∑ icost(ei) とするとき，以下のように編集距離を定義する． 定義 2 (編集距離) 木 S と木 T において，E(S, T ) を S を T に変換するすべての編集操作列の集合とする． このとき，S，T 間の編集距離 D(S, T ) は次のように 定義する． D(S, T ) = min E_{∈E(S,T )}cost(E) マッピングという概念を導入すると木の編集距離を 組合せ的に説明することができる．マッピングとは木 S と木 T のノード集合の直積 S× T の部分集合であり， 2 つの木のノード間の対応付けを表す． 定義 3 (Tai マッピング) 木 S と木 T におけるマッピ ング M が Tai マッピングであるとは，任意の２つの要 素 (s1, t1), (s2, t2)∈ M について以下の条件を満足する ものとする． 1 対 1 対応：s1= s2 ⇐⇒ t1= t2 先祖子孫関係保存：s1< s2 ⇐⇒ t1< t2 － 79 －

Tai マッピングはノード間の対応付けであるが，意味的 には編集操作列に対応する．すなわち，Tai マッピング に含まれるノードには置換操作のみを行い，Tai マッピ ングに含まれないノードには削除，挿入を行うことに より一方の木を他方の木に変換することができる．こ れは Tai マッピングによって編集操作列のコストを計 算できることを意味する．以下のように Tai マッピン グのコストを定義すればその Tai マッピングに対応す る編集操作列のコストと一致し，定理 1 が成り立つ． 定義 4 (Tai マッピングのコスト) 木 S と木 T 間のあ るマッピング M ⊆ S × T において，M(1) _{={s ∈ S |} (s, t)∈ M}, M(2) _{={t ∈ T | (s, t) ∈ M} とする．コ} スト関数 d が与えられたとき，マッピング M のコスト を cost(M ) と書き，次のように定義する． cost(M ) = ∑_(s,t)∈Md(s, t) +∑_s∈S\M(1)d(s, ε) +∑_{t∈T \M}(2)d(ε, t) 定理 1 ([1]) 木 S と木 T 間のすべてのマッピングの集 合を_MTai_{(S, T ) とする．このとき，編集距離 D(S, T )} は， D(S, T ) = min M∈MTai_{(S,T )}cost(M )

2.3

Tai マッピングのバリエーション

定義 5 (断片マッピング [2]) 木 S と木 T を考える．マ ッピング M ∈ S × T が Tai マッピングであり，かつ， 以下の条件を満たすとき， M を断片マッピング (seg-mental mapping) であるという． ∀(s1, t1)∈ M s.t. s1̸= root(S) ∧ t1̸= root(T ), ∀(s2, t2)∈ M, (s1< s2∧ t1< t2) =⇒ (par(s1), par(t1))∈ M. 例えば，ノード s2とその子孫 s1がマッピングの端点 であれば par(s1) もマッピングの端点である．すなわ ち，s1から s2へのパスを考えると，そのパス上のすべ てのノードはマッピングの端点である． 定義 6 (ボトムアップ断片マッピング [2]) 木 S と木 T において，以下の条件を満たすマッピング M をボトム アップ断片マッピングという． ∀(s1, t1)∈ M, ∃(s2, t2)∈ M, s2≤ s1∧ t2≤ t1∧ s2∈ leaves(S) ∧ t2∈ leaves(T ) 断片マッピングの中で，マッピングの端点がなすパス が必ず葉を含むようなマッピングである． 定義 7 (断片距離とボトムアップ断片距離 [2]) 断片マ ッピングとボトムアップ断片マッピングの最小コスト をそれぞれ断片距離とボトムアップ断片距離と呼ぶ．

3

本論

3.1

既存の手法

以下では Kondo ら [10] が提案した手法を説明する． Tai マッピングのコストを最小化する問題を整数計画 問題に定式化する．そのためにマッピングのコストを 以下のように変形する． cost(M ) = ∑ (s,t)_∈M d(s, t) + ∑ s∈S\M(1) d(s, ε) + ∑ t∈T \M(2) d(ε, t) = ∑ (s,t)∈S×T d(s, t)ms,t+ ∑ s_∈S d(s, ε) { 1−∑ t_∈T ms,t } +∑ t∈T d(ε, t) { 1−∑ s∈S ms,t } = ∑ (s,t)∈S×T {d(s, t) − d(s, ε) − d(ε, t)}ms,t+ ∑ s∈S d(s, ε) +∑ t∈T d(ε, t) ここで，ms,tは (s, t) がマッピング M の要素であれば 1，そうでなければ 0 の値を持つ変数である．ws,t = d(s, ε) + d(ε, t)− d(s, t) とすれば以下のように書くこ とができる． cost(M ) =∑ s∈S d(s, ε) +∑ t∈T d(ε, t)− ∑ (s,t)∈M ws,tms,t 次に，Tai マッピングの制約条件を定式化する． ∀s ∈ S, ∑t∈Tms,t≤ 1 ∀t ∈ T, ∑s∈Sms,t≤ 1 ∀(s1, t1), (s2, t2)∈ S × T s.t. s1< s2⇎ t1< t2, ms1,t1+ ms2,t2≤ 1 上の 2 つの式は 1 対 1 対応，最後の式は先祖子孫関係 保存条件を表す．以上の式をまとめると以下のような 整数計画問題になる． IP 問題 1 (木の編集距離における整数計画問題) minimize ∑_s∈Sd(s, ε) +∑_t∈Td(ε, t) −∑(s,t)∈Mws,tms,t subject to m_∑s,t∈ {0, 1} (∀(s, t) ∈ S × T ) t∈Tms,t≤ 1 (∀s ∈ S) ∑ s∈Sms,t≤ 1 (∀t ∈ T ) ms1,t1+ ms2,t2 ≤ 1 (∀(s1, t1), (s2, t2)∈ S × T s.t. s1< s2⇎ t1< t2)

断片距離の制約条件を定式化すると以下のようになる． ∀(s1, t1), (s2, t2)∈ S × T

s.t s1̸= root(S), t1̸= root(T ), s1≤ s2, and t1≤ t2, ms1,t1+ ms2,t2 ≤ mpar(s1),par(t1)+ 1

この制約式を IP 問題 1 に追加することで断片距離に 対する整数計画問題が定式化できる．ボトムアップ断 片距離の制約条件は以下のように定式化できる．

∀(s1, t1)∈ S × T s.t s1∈ leaves(S) and t/ 1∈ leaves(T ),/ ms1,t1≤ ∑ s_{∈leaves(S),t∈leaves(T ),s<s}1,t<t1ms,t

3.2

改良方法

3.2.1 編集距離における改良 Tai マッピングのコストを最小化する問題は ∑ (s,t)∈S×T ws,tms,t を最大化する問題と一致する．この問題を部分問題に 分け，再帰的に解いていく方法を紹介する．まず，s と その子孫からなる部分木を S(s) とする．同様に，t と その子孫からなる部分木を T (t) とする．部分問題とは s∈ S, t ∈ T において，それぞれを根とする部分木間 の最適なマッピング M で (s, t)∈ M であるような最 大コストを求めることである．その最適値を Ws,tとす れば，ある条件を満たすマッピング M∗を用いて，再 帰式を以下のように書くことができる． Ws,t= max M∗    ∑ (s′,t′)∈M∗ Ws′,t′   + ws,t ここで，マッピング M∗を変数 m∗s′,t′ ∈ {0, 1} を用い て表すことができる．すなわち，m∗s′,t′ = 1⇔ (s′, t′)∈ M∗とする．このマッピングが満たすべき条件を以下 に示す． ∑ s′∈S ∑ t′∈Pl m∗s′,t′ ≤ 1 (∀l ∈ leaves(T )) ∑ t′∈T ∑ s′∈Pl m∗_s′,t′ ≤ 1 (∀l ∈ leaves(S)) ここで Plとは葉 l から根までのパスで，根のノードを 除いたものを表す．上の制約条件が必要な理由を以下 に述べる．この問題は部分木の最適な組み合わせを探 す問題である．部分木間の組み合わせを部分木の根の 間のマッピング M∗_{で表している．そのため，M}∗の 2 つの要素 (s1, t1), (s2, t2) が先祖子孫関係を持つこと は各ノードが表す部分木が重なる部分が生じることを 意味する．従って，M∗の任意の 2 つの要素は先祖子 孫関係を持たない．この条件を m∗s′,t′ で表すと，任意 の葉 l において，Pl上にあるマッピングの端点は高々1 個しかないということになる．以上を整数計画問題に 定式化すると以下のようになる． IP 問題 2 (編集距離における部分問題) maximize ∑_(s′,t′)∈S(s)\{s}×T (t)\{t}Ws′,t′m∗s′,t′+ ws,t subject to m_∑∗_s′,t′ ∈ {0, 1} (∀(s, t) ∈ Ts× Tt) s′_∈Ts ∑ t′_∈Plm ∗ s′,t′ ≤ 1 (∀l ∈ leaves(Tt)) ∑ t′∈Tt ∑ s′∈Plm ∗ s′,t′ ≤ 1 (∀l ∈ leaves(Ts)) 上の整数計画問題を再帰的に解いていけばすべての部 分木間の最適なマッピングのコストが得られる．従っ て，得られた部分問題の最適値をうまく組み合わせる ことで最終的な解が得られる．それは以下の整数計画 問題を解くことである． IP 問題 3 (最終解を求める問題) maximize ∑_(s,t)∈S×TWs,tm∗s,t subject to m∗_s,t∈ {0, 1} (∀(s, t) ∈ S × T ) ∑ s_∈S ∑ t_∈Plm ∗ s,t≤ 1 (∀l ∈ leaves(T )) ∑ t_∈T ∑ s_∈Plm ∗ s,t≤ 1 (∀l ∈ leaves(S)) 3.2.2 断片距離とボトムアップ断片距離における改良 次に，断片距離を改良する方法を紹介する．編集距 離と同じように部分問題を再帰的に解いていく方法で ある．断片マッピングも Tai マッピングの一種である ので，編集距離の場合と同じような部分問題を考える． 断片マッピングの制約条件より，木 S の部分木の根 s の子孫 s1がマッピングの端点であれば，s1から s への パス上にあるすべてのノードはマッピングの端点であ る．ここで，木 T のあるノード t1において m∗s1,t1 = 1 であれば，IP 問題 2 の制約条件より s1から s までの パス上でマッピングの端点となるノードは s と s1の 2 つしかない．s1が s の子でなければ，これは断片マッ ピングの制約条件に反する．従って，ある t1において m∗_s 1,t1 = 1 となる s1は必ず s の子である．従って，部 分木 S(s) と T (t) に関する部分問題を考えたとき，最 適なマッピングを求めることは，s と t それぞれの子供 の集合 A と B を考え，A と B の間の最適なマッチン グを求めることとなる．ただし，A の元 s1と B の元 t1間のマッチングの重みは Ws1,t1である．すなわち，2 部グラフの最大重みマッチング問題に変換できる．そ の例を図 1 に示す．2 部グラフの最大重みマッチング 問題はハンガリアン法 [11] を用いれば多項式時間で解 かれる．すべての部分木間の最適マッピングが得られ れば，編集距離の場合と同様に IP 問題 3 を解くことで 最終的な距離が得られる． － 81 －

2017. 2. 24. 오전 11:49

Preview

s

₁

s

₂

t

₁

t

₂

Ws1,t1 Ws1,t2 Ws2,t1 Ws2,t2 Ws1,t1 Ws1,t2 Ws2,t1 Ws2,t2

s

1

s

₂

t

₁

t

₂

図 1: 断片距離の部分問題を最大重みマッチング問題に変換する例 ボトムアップ断片距離の場合は断片距離とほぼ同じ であるが，部分問題の中で，葉のノード s と葉でない ノード t 間のマッピングを考えるとき，Ws,tは必ず 0 にしなければならない．なぜなら，ボトムアップ断片 距離の制約条件より，t の子孫の中で葉であるノードの 1 つ以上がマッピングに含まれなければならないが，s が葉であるため，Tai マッピングの制約より，不可能で ある．Ws,tを 0 にすれば断片マッピングの中でボトム アップ断片マッピングでないものは全て排除されるの でボトムアップ断片マッピングのみを計算できる．

4

実験結果

本研究で提案した手法を既存の手法と比較するため に計算機実験を行った．生物データである KEGG の Glycan データに対して実験を行い，2 つの木のノード 数の和ごとに区間を分け，平均実行時間を比較した．計 算機環境は 3.7GHz Quad-Core Intel Xeon E5，RAM 12GB である．Java でプログラムを実装し，整数計画 ソルバとして IBM ILOG CPLEX 12.6 を使用した．

Glycan データに対して編集距離計算を実行した結果 を表 1 に示す．本実験では根同士が必ずマッピングに 含まれるようにした．もちろん，そうでない場合も同 じ手法で解ける．[50,54] はノード数の和が 50 以上 54 以下であるインスタンスを意味する．IP Ted は既存の 手法，DpIP Ted は本稿で提案した手法である．Avg. は平均実行時間，t.o. はタイムアウトしたインスタン ス数を表す．タイムアウトは 30,000 ミリ秒と設定した． 平均実行時間の単位はミリ秒とした． 同じデータセットに対して断片距離とボトムアップ 断片距離の計算を行った結果を表 2 に示す．IP Sg と IP BotSg はそれぞれ断片距離とボトムアップ断片距離 を計算する既存の方法を表し，DpIP Sg と DpIP BotSg はそれぞれの距離を計算する改良した方法である．*は すべてのインスタンスがタイムアウトしたことを意味 する． 実験結果より，本稿で提案した手法が既存の手法よ り性能が大幅に改善されたことが確認できる．

5

結論

本稿では整数計画法を用いて木間距離を計算する手 法を動的計画法を用いて改良し，より効率の良い定式 化を提案した．その結果，制約式の数が大幅に減少し た．計算機実験を行って既存の手法との比較を行った 結果，糖鎖データに対して提案手法の実行時間が既存 の手法より速いことが確認された．本稿では編集距離， 断片距離，ボトムアップ断片距離の 3 つの距離におけ る定式化を提案したが，他の距離に対しても効率の良 い定式化を与えることが今後の課題である．

参考文献

[1] Tai, K.: The Tree-to-Tree Correction Problem, Journal of ACM, Vol. 26, pp. 422–433 (1979) [2] Kan, T., Higuchi, S., Hirata, K.:

Segmen-tal Mapping and Distance for Rooted Labeled Ordered Trees, Algorithms and Computation, Vol. 7676, pp. 486–494 (2012)

[3] Zhang, K., Statman R., Shasha, D.: On the editing distance between unordered labled trees, Information Processing Letters, Vol. 42, No. 3, pp. 133–139 (1992)

[4] Zhang, K., Jiang, T.: Some MAX SNP-hard results concerning unordered labeled trees, In-formation Processing Letters, Vol. 49, No. 5, pp. 249–254 (1994)

表 1: Glycan データに対する編集距離計算の実行結果

ノード数 インスタンス数 IP Ted DpIP Ted

Avg. t.o. Avg. t.o.

[50,54] 100 3093 0 424 0 [55,59] 100 6559 3 511 0 [60,64] 88 14955 21 519 0 [65,69] 36 24417 26 775 0 [70,74] 100 14120 11 776 0 [75,79] 29 18805 18 983 0 [80,84] 9 16224 8 1286 0 [85,89] 5 * 5 1559 0 [90,94] 4 * 4 1689 0 表 2: Glycan データに対する断片距離とボトムアップ断片距離計算の実行結果

ノード数 インスタンス数 IP Sg DpIP Sg IP BotSg DpIP BotSg

Avg. t.o. Avg. t.o. Avg. t.o. Avg. t.o.

[50,54] 100 6692 3 135 0 1642 0 134 0 [55,59] 100 9032 26 136 0 2607 0 136 0 [60,64] 88 13448 58 138 0 5077 0 138 0 [65,69] 36 20843 36 141 0 6874 0 140 0 [70,74] 100 * 100 146 0 9880 2 145 0 [75,79] 29 21112 27 149 0 14480 8 147 0 [80,84] 9 * 9 153 0 14892 6 152 0 [85,89] 5 * 5 157 0 * 5 157 0 [90,94] 4 * 4 160 0 * 4 160 0

[5] Akutsu, T., Tamura, T., Fukagawa, D., Takasu, A.: Efficient exponential-time algorithms for edit distance between unordered trees, Journal of Discrete Algorithms, Vol. 25, pp. 79–93 (2014) [6] Horeseh, Y., Mehr, R., Unger, R.: Designing an

A* Algorithm for Calculating Edit Distance be-tween Rooted-Unordered Trees, Journal of Com-putational Biology, Vol. 13, No. 6, pp. 1165–1176 (2006)

[7] Higuchi, S., Kan, T., Yamamoto, Y., Hirata, K.: An A* Algorithm for Computing Edit Distance between Rooted Labeled Unordered Trees, New Frontiers in Artificial Intelligence, Vol. 7258, No. 1, pp. 186–196 (2012)

[8] Fukagawa, D., Tamura, T., Takasu, A., Tomita, E., Akutsu, T.: A clique-based method for the edit distance between unordered trees and its

ap-plication to analysis of glycan structures, BMC Bioinformatics, Vol. 12, No. 1 (2011)

[9] Mori, T., Tamura, T., Fukagawa, D., Takasu, A., Tomiya, E., Akutsu, T.: An Improved Clique-Based Method for Computing Edit Distance be-tween Rooted Unordered Trees, IPSJ SIG Tech-nical Report, Vol. BIO-26, No. 3 (2011)

[10] Kondo, S., Otaki, K., Ikeda, M., Yamamoto, A.: Fast Computation of The Tree Edit Distance Be-tween Unordered Trees Using IP Solvers, Discov-ery Science, Vol. 8777, pp. 156–167 (2014) [11] Kuhn, H.: The Hungarian Method for the

assign-ment problem, Naval Research Logistics Quar-tely, Vol. 2, pp. 88–97 (1955)

[12] Kanehisa, M., Goto, S.: KEGG: kyoto encyclo-pedia of genes and genomes, Nucleic acids re-search, Vol. 28, No. 1, pp. 27–30 (2000)