木構造および化学構造に対する特徴ベクトル： 埋め込み、検索、構造推定 阿久津　達也 京都大学 化学研究所 バイオインフォマティクスセンター

講演内容 木の編集距離の埋め込み 特徴ベクトルからの構造推定 順序木：オイラー文字列を利用した文字列の編集距離への埋め込み 　　　　⇒文字列編集距離の L1 空間への埋め込み 　　　　⇒順序木編集距離の L1 空間への埋め込み 無順序木：特徴ベクトルを用いた L1 空間への埋め込み 特徴ベクトルからの構造推定 特徴ベクトルからの木構造推定 その新規化学構造設計への応用可能性

埋め込み 編集距離空間 L1空間 O 距離： DL1 距離： DT O 構造推定 CH3 O NH2 特徴ベクトル 空間 化合物空間

Part-I 木の編集距離の埋め込み

背景

背景 木構造のパターンマッチング バイオインフォマティクス XMLデータベース 画像理解 RNA構造の比較、糖鎖構造の比較

木構造の比較 部分グラフに基づく最大共通部分木 編集距離に基づく最大共通部分木 本研究での対象 順序木：O(n2)時間 無順序木： O(n2.5/log n)時間 編集距離に基づく最大共通部分木 順序木： O(n3)時間 無順序木：NP困難（MAX SNP困難） 本研究での対象 順序木、および、無順序木　　（頂点にラベルあり） 高さに制限（無順序木の場合） DBLPのXML文書では高さは最大で６、99%は2以下 単位編集コスト 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] 最大共通部分木 一方が高さ１の木で、もう一方が高さ２の木でも 　　　定数近似困難 [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, Fukagawa, Takasu, 2008]

文字列の編集距離の埋め込み 編集距離 計算 最適に近い結果 O(n2)程度の時間がかかる ⇒ 近似 2000年代に多くの優れた研究 L1埋め込みの近似（歪み）下限 　　　　 　 [Khot & Naor, FOCS2005] [Krauthgamer & Rabani, SODA2006] L1埋め込みの近似（歪み）上限 　　 [Ostrovsky & Rabani, STOC2006 & JACM 2007] 編集距離の近似計算 ほぼ線形時間で　　　　　　　　近似 　 [Andoni & Onak, STOC2009]

講演内容（Part-1） 順序木 （Ω(n3)) 無順序木 (MAX SNP-hard) 文字列の編集距離への変換　[Akutsu, IPL, 2006] 　　　⇒O(n2)時間O(h)近似アルゴリズム O(n2)時間、O(n3/4)近似アルゴリズム ただし、木の最大次数は定数以下 　　　　　　　　　　　　 [Akutsu, Fukagawa & Takasu, Algorithmica (to appear)] 無順序木 (MAX SNP-hard) 特徴ベクトルによる編集距離の2h+2近似 　　　　　　　　　　　　　　　 [Fukagawa, Akutsu & Takasu,　SPIRE 2009]

木の編集距離

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

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

木間写像と最大共通部分木の例 編集距離＝３ 最大共通部分木

埋め込み α、βが１に近いほど良い 空間X (e.g., L1空間）における高速 アルゴリズム（eg. 検索）が利用可 編集距離空間 O 距離： DX 距離： DT O α、βが１に近いほど良い 空間X (e.g., L1空間）における高速 　　アルゴリズム（eg. 検索）が利用可

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

オイラー文字列 木を深さ優先探索 探索した順に頂点のラベルを並べる ただし、戻る時のラベルは の様に区別する T1 s(T1)= A B C ただし、戻る時のラベルは の様に区別する A B C E D T1 s(T1)= “ ”

アルゴリズム 定理 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]

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

最悪となる場合の例 文字列の距離＝２ 木の距離≒高さ 幹の頂点にAD, BD, AE, BE などのラベルをつけてマッチを防げば良い

枝へのラベルの割り当て（１） すべての枝に部分木の情報を割り当てると、（オイラー文字列の）エラーが大きくなりすぎる 　　⇒　一部の枝のみに小さな部分木の情報を付加

枝へのラベルの割り当て（２） Special node: 部分木のサイズが 以下で、 親部分木のサイズが より大 　　　　親部分木のサイズが　　　より大 Special edge:子の少なくとも１個が special node Special nodeを根とする部分木の情報をラベルとして与える

無順序木の編集距離の 2h+2 近似アルゴリズム

無順序木の編集距離の近似 最大共通部分木（最大化）⇔編集距離（最小化） しかし、近似に関しては無関係 編集距離： MAX SNP困難以外の結果が無い ⇒無順序木の編集距離の 2h+2近似 方法 木 T を特徴ベクトル Φ（T） に変換 [Fukagawa, Akutsu & Takasu, SPIRE 2009]

特徴ベクトル T1 T2 r c a b r c a b T(v) : v とその子孫から誘導される T の部分木 Φt(T)= #(T,t)= |{ v | T(v)～t }|, Φ(Ti) = < Φt(Ti) | t∊{Ti(v)|i=1,2} > Φ(T1)= ( 1, 2, 0, 1, 1, 0, 1, 0 ) Φ(T2)= ( 1, 1, 1, 1, 0, 1, 0, 1 ) a b c T1 T2

特徴ベクトルの性質 r c a b T1 T2 Φ(T1)= ( 1, 2, 0, 1, 1, 0, 1, 0 ) Φ(T2)= ( 1, 1, 1, 1, 0, 1, 0, 1 ) 補題1 証明：編集操作1により距離が高々2h+2 増加 補題2 証明：略

乱数の利用による埋め込み 定理: Φ(Ti)の計算 code(T(v)): T(v)の一意な表現（整数値） T1,T2, … , Tm を知る必要があり、データベース検索に不向き code(T(v)): T(v)の一意な表現（整数値） そのままだと O(n) サイズ code(T(v)) mod p を利用 ( pは素数) ⇒ O(log n)サイズ 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（Karp-Rabin の randomized fingerprint） 定理:

結論 （Part-I） Open Problem 順序木 （Ω(n3)) 無順序木 (MAX SNP-hard) 高さが h の木に対するO(n2)時間O(h)近似 O(n2)時間、O(n3/4)近似アルゴリズム 無順序木 (MAX SNP-hard) 特徴ベクトルによる 2h+2近似 Open Problem 無順序木の編集距離の h に依存しない近似 O(n3/4)近似における定数次数制約の除去 順序木の編集距離の埋め込み

Part-II 特徴ベクトルからの構造推定

サポートベクターマシン カーネル法の一つ 1990年代に、Cortes と Vapnik が発明 トレーニングデータとして与えられた正例と負例から、それらを分離する超平面を計算 機械学習、統計学、人工知能、パターン認識、バイオインフォマティクスなど様々な分野に応用 配列分類 タンパク質フォールド予測、二次構造構造 遺伝子発現データ解析 タンパク質相互作用予測 化合物の性質推定

サポートベクターマシン 正例と負例（e.g., 活性あり化合物、活性なし化合物）を与えて、それらを最適（マージンを最大）に分離する超平面を学習 カーネルを適切に定義することにより超平面以外での分離が可能

カーネル サポートベクターマシン：基本的には超平面で分離 Φ(x) (特徴ベクトル）：「非線形曲面⇒超平面」に写像 カーネル　K(x,y)=Φ(x)・Φ(y) x と y の類似度が高い ⇔ K(x,y)が大

カーネル法に基づく化合物活性予測 化合物を特徴ベクトルに写像 SVM（SVR）を用いて活性の有無（活性値）を予測 Φ 特徴ベクトル 空間 化合物空間 Φ O O CH3 O NH2 O

化合物に対する特徴ベクトル Walk based (パスの出現頻度) Descriptor based (部分構造の出現頻度)

特徴ベクトルからの化学構造の推定 従来のカーネル法 我々のアプローチ （pre-image 問題） データ ⇒ 特徴ベクトル (写像 Φ） 　データ ⇒ 特徴ベクトル　　　 (写像 Φ） 我々のアプローチ　　　（pre-image 問題） 　特徴ベクトル　⇒　データ　　　（逆写像 Φ-1） 化合物空間 特徴空間 Φ CH3 Φ-1 none approximate pre-image Φ-1

創薬への応用可能性（１） 二つの化合物の中間構造を持つ新たな化合物の設計

創薬への応用可能性（２） 以下の化合物は既知 ここから、効能があり、 悪い副作用が無い 化合物を設計したい (A) 効能はあるが、悪い副作用もある (B) 効能も無く、悪い副作用も無い (C) 効能は無いが、悪い副作用はある ここから、効能があり、 　　悪い副作用が無い 　　化合物を設計したい

既存研究 カーネルPCA + 回帰 [Bakir, Wetson & Schoelkopf, 2003] シミュレーテッドアニーニング　　[Bakir, Tsuda & Schoelkopf, 2004] 文字列のpre-image オイラー閉路問題に帰着 [Cortes, Mohri & Weston, 2005] グラフに対しては厳密アルゴリズムや計算論的考察は無し

問題の定式化 v 入力: 長さ K 以下のラベル付きパスの出現頻度からなる特徴ベクトル v 出力: 特徴ベクトルをΦ(G)とする時、 Φ(G)=v を満たす化学構造（グラフ） G(V,E) Φ v

理論的結果 特徴ベクトルからの化学構造推定は、以下の場合、動的計画法により多項式時間で計算可能 ラベルの種類が定数以下 パスの長さが定数以下 最大次数が定数以下の木構造 　　　（木構造はある制約つきの外平面グラフに拡張可能） 一方、パスの長さに制約がない場合には、木構造に対しても NP困難 [Akutsu & Fukagawa, CPM 2005,BIOINFO 2005] 特徴ベクトルからの化学構造推定は、K=1の場合、Graph Detachment を用いることにより、一般のグラフに対しても多項式時間で計算可能 [Nagamochi, COCOON 2006]

動的計画法アルゴリズムの概要 木は葉を１個づつ付加することにより生成可能 D(v)=1  Φ(T)=v を満たす v が存在 a b D(v)=1　  　Φ(T)=v を満たす v が存在 　多項式とはいえ、 　　　計算量が大きく 　　　非実用的

単純な分枝限定法アルゴリズム 頂点を一つずつ追加することにより木構造（もしくは木に似た構造）を生成 いくつかの候補を記憶しておき、最も目的の特徴ベクトルに近いものを展開 深さ優先探索 (DFS, depth-first search procedure)に基づく 現時点での木構造が、対象の特徴ベクトルに至らないことが判明した時点でバックトラックを行う 木構造＋ベンゼン環に対応可能

数え上げに基づく分枝限定法アルゴリズム 中野 & 宇野の木構造数え上げと以下の組み合わせ 主に永持研で開発 二つのバージョン 次数制約によるカット 特徴ベクトルによるカット Detachment カット　[Ishida et al., GIW 2008] 主に永持研で開発 二つのバージョン 水素原子を陽に扱う、扱わない アルカン（CnH2n+2)の数え上げでは、ほぼ最高速 特徴ベクトルからの化学構造推定では、水素を除いて20～30原子程度の化合物まで対応可能 [Fujiwara et al., J. Chemical Information & Modeling, 2008]

化学構造数え上げサーバ

制約を満たす木構造の数え上げサーバ 与えられたパス頻度に関する制約を満たす木構造を数え上げて表示 SMILE形式の構造式も出力 http://sunflower.kuicr.kyoto-u.ac.jp/~ykato/chem/ 与えられたパス頻度に関する制約を満たす木構造を数え上げて表示 SMILE形式の構造式も出力 永持研で開発されたプログラムを実装 限定的ながらもベンゼン環にも対応 アルカンなどの数え上げも可能 Web server開発: Y. Kato

サーバの 実行例 C6H14

サーバの 実行例 C6H14

結論（Part-II）：特徴ベクトルからの構造推定 木に対する多項式時間アルゴリズム パスの長さに制約がない場合のNP困難性 分枝限定法アルゴリズム 木構造の数え上げ 次数制約カット、特徴ベクトルによるカット、detachmentカット WEBサーバの構築 今後の課題 提案手法の新規化合物設計における有効性の証明 更なる改良、拡張 より広いグラフクラスへの拡張 エラーを許した場合のアルゴリズムの開発 他問題への応用 NMR/質量分析データからの構造推定

結論 （Part-I）： 特徴ベクトルによる木の編集距離の埋め込み 順序木 （Ω(n3)) 高さが h の木に対するO(n2)時間O(h)近似 O(n2)時間、O(n3/4)近似アルゴリズム 無順序木 (MAX SNP-hard) 特徴ベクトルによる 2h+2近似 結論（Part-II）：　特徴ベクトルからの構造推定 木に対する多項式時間アルゴリズム パスの長さに制約がない場合のNP困難性 分枝限定法アルゴリズム 木構造の数え上げ 次数制約カット、特徴ベクトルによるカット、detachmentカット WEBサーバの構築 Acknowledgment A. Takasu & D. Fukagawa at NII H. Nagamochi & Members of Nagamochi Lab. at Kyoto U. Y. Kato at BIC, Kyoto U.