数理解析研究所講究録
第 1744 巻 2011 年 161-168

161

木オートマトンを用いた化学グラフのスクリーニング手法
藤芳 明生
茨城大学工学部情報工学科

fujiyosi@mx.ibaraki.ac.jp

概要
本稿では，木オートマトンによる化学グラフの所
属問題を考える．化学グラフが木オートマトンによって受理されることを，その化学グラフが木オートマト
ンによって受理される全域木を持つことと定義する．
この所属問題が NP 完全であることと，TYee-Width
が高々2 であるような化学グラフに対する線形時間の所属性判定アルゴリズムを提案する．

(a)

(b)

図 1: (a) アセチルサリチル酸，(b) モルヒネ．

1

はじめに

Canonical Labelling [3] が多項式時間でできること

化学グラフ (分子グラフ) とは，化学物質の分子構造 (構造式) を表現したグラフのことである．各

面的であるということが挙げられる．ゼオライトの頂点は原子の種類でラベル付けされており，各辺は結晶のように，無機化合物には平面的ではないものが知られている．次に，ほとんどの化学グラフは平原子間の結合の種類によってラベル付けされている． も存在するが，それらは例外的であると言ってよい．
更に，立体異性体を区別して表現するために，結合の 平面的グラフに対しては，グラフ同型性判定が線形
位置関係を考慮しなければならない場合もある．図 時間 [4] でできることが知られている．更に，医薬品
1 にアセチルサリチル酸とモルヒネの構造式を示す． 及び医薬品候補化合物に限定すれば，それらの化学
要するに，このような構造式をグラフとして見なし グラフの Tree-Width は十分に小さいということがたものが，化学グラフであるといえる．
挙げられる．表 1 に，ChEMBL[5] に登録されていアルゴリズムの視点から化学グラフを考えると，そ る 635,933 個の医薬品及び医薬品候補化合物の TYeeれらは非常に扱いやすいグラフであるといえる [1]. Width を示す．ほとんどの化合物の rhee-Width はまず，化学グラフの最大次数は定数で制限できるこ 3 以下となっていることが確認された．Tree-Widthとが挙げられる．よく知られているように，炭素原 が定数で制限されたグラフに対しては，グラフ同型
子が共有結合できる数は 4 つまでであり，水素原子 性判定が多項式時間 [6] でできることが知られていは 1 つまで，酸素原子は 2 つまでとなっている．配 るだけでなく，Tree-Width と最大次数が共に定数で位結合も考慮するとしても，化学グラフの次数は 6 制限されたグラフに対しては，部分グラフ同型性判以下であると制限してよい．最大次数が定数で制限 定も多項式時間 [7] でできることが知られている．部
されたグラフに対しては，グラフ同型性判定 [2] 及び 分グラフ同型性判定問題は，よく知られているよう162$T=(V_{2}, E_{2})$ を木， をその頂点ラ関数とする．
$\sigma_{2}$

表 1: ChEMBL 中の化合物の Tree-Width.

ベル付け関数とする． が$T$$V_{1}=V_{2},$$\sigma_{1}=\sigma_{2}$$G$の全域木であるとは，

かつ，,$E_{2}\subseteq E_{1}$となることである．グラフに全域木が存在するためには，連結でなくてはならないので，本稿では，連結グラフだけを考える．
$T=(V, E, r)$ を根付き木， : $Varrow\Sigma$ をその頂$\sigma$

点ラベル付け関数とする． に対応する順序木とは，の元と括弧及びコンマを用いて，次のように再帰$T$$\Sigma$.

的に定義される文字列 $w$ である．

に，一般のグラフに対しては NP 完全問題である．

本稿は，化学グラフの所属性判定に木オートマト.

ン [8] を利用することを提案する．議論が複雑になりすぎるため，辺のラベル (結合の種類) は無視することとし，化学グラフを頂点ラベル付グラフと見$V=\{r\}$ かつ $E=\emptyset$$w=\sigma(r)$ はのとき，$n\geq 1,$$r_{n}),$$T_{1}=(V_{1}, E_{1}, r_{1}),$ $\ldots,$ $T_{n}=(V_{n},$ $E_{n}$$V=V_{1}\cup\cdots\cup V_{n}\cup\{r\},$$r\not\in V_{1}\cup\cdots\cup V_{n}$すべての $1\leq i,j\leq n$ の組に対しトンが受理することを，そのグラフにある根付き全域木が存在し，木オートマトンがその根付き全域木を受理することと定義する．まず，木オートマトン
による頂点ラベル付グラフの所属問題が NP 完全であることを示す．次に，Tree-Width が高々2 である
ような化学グラフに対しては線形時間の所属性判定$E=E_{1}\cup\cdots\cup E_{n}\cup\{\{r, r_{1}\}, \ldots, \{r, r_{n}\}\}$

2$w_{1},$

グラフとは，順序対 $G=$ $(V, E)$ のことである．
$V$ は頂点の有限集合，異なる頂点の組を辺
ここで，$E$ は辺の有限集合である．
$u,$ $v\in V$ かつと呼び，は隣接するという．木とは，閉路を持たないグラフのことである．
$r\in V$ とする．根付き木とは，順$T=(V, E)$ を木，

序対 $T’=(V, E, r)$ のことである．
$G=(V, E)$ をグラフとする． を頂点ラベルの有$\Sigma$限集合とし，関数$\sigma$:$Varrow\Sigma$$w_{n}$

が$\ldots,$$T_{n}$

き，

は $T$ に対応する順序木である．
$w_{1},$$\ldots,$$w_{n}$の並び方は任意であるため， に対応す$T$る順序木はその組み合わせの数だけ存在する．
を変数の集合とする．

を，頂点ラベル付け関木オートマトン

本章では，頂点ラベル付グラフを受理する木オー
トマトンを紹介する．ここで紹介する木オートマト

ンの定義は，通常の木オートマトン [8] と全く同じである．本稿では，トップダウン型の木オートマトンだけを定義するが，同等の認識能力を持ったボトム
アップ型の木オートマトンを定義することもできる．

定義 1(非決定性トップダウン) 木オートマトンとは，四つ組は状態の有限集合，$\mathcal{A}=(Q, \Sigma, q_{0}, R)$$G$ は頂数と呼ぶ． が $V$ 上で定義されているとき，$Q$

点ラベル付きであると言う．本稿では，すべてのグ形の規則の有限集合である．

$\sigma$$q_{0}\in Q$のことである．ここで，は初期状態， は次の$R$

ラフは頂点ラベル付きであるとする．
$G=(V_{1}, E_{1})$をグラフ， をその頂点ラベル付け$\sigma_{1}$かつに対応する順序木のと$w=\sigma(r)(w_{1}, \ldots, w_{n})$3$v$$\ldots,$$T_{1},$$V_{i}\cap V_{j}=\emptyset$,,,$\mathcal{X}=\{x_{1}, x_{2}, \ldots\}$

諸定義

$u$ と
$e=\{u, v\}\in E$ であるとき，に対応する順序木である．

なすことにする．頂点ラベル付グラフを木オートマ

アルゴリズムが存在することを示す．

$T$$q(f(x_{1}, \ldots,x_{n}))arrow f(q_{1}(x_{1}), \ldots,q_{n}(x_{n}))$163$n\geq 0,$
ここで，$f\in\Sigma,$$q,$$q_{1},$$\ldots,$$q_{n}\in Q,$$x_{1},$$\ldots$,をに現れる変数の集合とす
合，る． から頂点ラベル付きグラフ $G=(V, E)$ を次$\mathcal{V}=\{v_{1}, \ldots, v_{n}\}$$\mathcal{F}$$q(f())arrow f()$ の$n=0$ のときは，である．
$q(f)arrow f$ と書く．のように構成する．
代わりに，$x_{n}\in \mathcal{X}$$\mathcal{F}$を頂点ラベル付グラフ， をその頂点ラベルの$D$ が $A$
集合， を 上の木オートマトンとする．
$D$ の根付き全域木
によって受理されるとは，及びに対応する順序木 が存在し， が
によって
$D$

$\Sigma$$\Sigma$$\mathcal{A}$

$T$

$T$

$w$

$w$

$\{v_{1}, \ldots, v_{n}\}\cup\{\overline{v}_{1}, \ldots,\overline{v}_{n}\}\cup\{c_{1}, \ldots, c_{m}\}$$\cup\{s_{v_{1}}, \ldots, s_{v_{n}}\}\cup\{t_{v_{1}}, \ldots, t_{v_{n}}, t_{\overline{v}_{1}}, \ldots, t_{\overline{v}_{n}}\}$$\mathcal{A}$

受理されることである．

4

$V=$

$\cup\{u_{v_{1}}, \ldots, u_{v_{n}}, u_{\overline{v}_{1}}, \ldots, u_{\overline{v}_{n}}\}$$\cup\{w_{[v_{i},c_{j}]}, w_{[\overline{v}_{i},c_{j}]}|1\leq i\leq n, 1\leq j\leq m\}$頂点ラベル付グラフの所属問題の NP 完全性,$E=\{\{s_{v_{i}}, v_{i}\}, \{s_{v_{i}},\overline{v}_{i}\}|1\leq i\leq n\}$$\cup\{\{v_{i}, s_{v_{i+1}}\}, \{\overline{v}_{i}, s_{v_{i+1}}\}|1\leq i\leq n-1\}$$\cup\{\{v_{i}, u_{v_{i}}\}, \{\overline{v}_{i}, u_{\overline{v}_{i}}\}|1\leq i\leq n\}$

文献 [9] で，木オートマトンによる無閉路有向グ$\cup\{\{u_{v_{i}}, w_{[v_{i},c_{1}]}\}, \{u_{\overline{v}_{i}}, w_{[\overline{v}_{i}},$ラフ (DAG) の所属問題が NP 完全であることが証明されている．本稿では，文献 [9] の証明手順を頂点$\cup\{\{w_{[v_{i},c_{j}]}, w_{[v_{i},c_{j+1}]}\},$ $\{w[\overline{v}_{i},c_{j}], w_{[\overline{v}_{i},c_{j+1}]}\}|$$1\leq i\leq n,$

ラベル付グラフの所属問題の結果に適応し，次の結
果を得る．

補題 1

$\Sigma$$1\leq j\leq m-1\}$$\cup\{\{w_{[v_{i},c_{m}]}, t_{v_{i}}\}, \{w_{[\overline{v}_{i},c_{m}]}, t_{\overline{v}_{i}}\}|1\leq i\leq n\}$を頂点ラベルの集合とする．

$|\Sigma|\geq 3$

であるならば，木オートマトンによる頂点ラベル付きグ
ラフの所属問題は $NP$ 完全である．

$\cup\{\{w_{[v_{i},c_{j}]}, c_{j}\}|$$1\leq i\leq n,$ $1\leq i\leq m,$$v_{i}$

が$c_{j}$

ることを示す．

$1\leq i\leq n,$$1\leq i\leq m,\overline{v}_{i}$が$c_{j}$

頂点ラベル付け関数は，$\sigma(s_{v_{1}})=a,$が異なる 3 つのラベル $a,$を含むと仮定し，$b,$ $c$に存在する}$\cup\{\{w_{[\overline{v}_{i},c_{j}]}, c_{j}\}|$(証明) 充足可能性問題 (SAT) をこの問題に還元でき$\Sigma$$1]\} |1\leq i\leq n\}$。

次のような木オートマトン $A=(Q, \Sigma, q_{0}, R)$ を用意する．

$c_{m}\}\cup\{t_{v_{1}}, \ldots, t_{v_{n}}, t_{\overline{v}_{1}}, \ldots, t_{\overline{v}_{n}}\}$に存在する}.
,$v\in\{c_{1},$ $\ldots$$\sigma(v)=c$ ,に対し，$\sigma(v)=b$ と定義する．
それ以外の $v\in V$ に対し，

例として，論理式を考える．図 2 に，この論理式に対応$(v_{1}\vee D_{2}Vv_{3})\wedge(v_{1}\vee v_{3}\vee\overline{v}_{4})\wedge$$(\overline{v}_{2}\vee\overline{v}_{3}\vee v_{4})$$Q=\{q_{0}, q_{1}, q_{2}, q_{3}\}$,する頂点ラベル付きグラフを示す． のラベルが付$a$,$R=\{q_{0}(a(x_{1}, x_{2}))arrow a(q_{1}(x_{1}), q_{3}(x_{2}))$$q0(b(x_{1}, x_{2}))arrow b(q_{1}(x_{1}), q_{3}(x_{2}))$,$q_{1}(b(x_{1}, x_{2}))arrow b(q_{0}(x_{1}), q_{2}(x_{2}))$,$q_{1}(b(x_{1}))arrow b(q_{2}(x_{1}))$$b$$G$ が $A$ に受理される必要十分条件は，
明らかに，
論理式
に充足解が存在することである．よって，
木オートマトンによる頂点ラベル付きグラフの全域$\mathcal{F}$,

木の所属問題は NP 困難である．

,$q_{2}(b(x_{1}))arrow b(q_{2}(x_{1})),$$q_{2}(c)arrow c$$q_{3}(b(x_{1}))arrow b(q_{3}(x_{1})),$$q_{3}(c)arrow c\}$一方，明らかに，与えられた頂点ラベル付きグラ.

を与えられた乗法標準形 (CNF) の論理式とす$C=\{c_{1}, \ldots, c_{m}\}$ をる．

$\mathcal{F}$$c$のラベルが付いた頂点は黒丸で表してある．

,$q_{2}(b(x_{1}, x_{2}))arrow b(q_{2}(x_{1}), q_{2}(x_{2}))$$\mathcal{F}$

いた頂点は斜線， のラベルが付いた頂点は白丸，を構成するクローズの集

フ $G$ に対し，非決定的多項式時間で $G$ の全域木 $T$$T$ が $A$ に受理されるかどうか確認するこを構成し，とができる．よって，木オートマトンによる頂点ラ164$Q’=\{q_{0},q_{1}, q_{2}, q_{3},q_{4}\}$

図 2: 論理?

$\grave$,$(v_{1}\vee\overline{v}_{2}\vee v_{3})\wedge(v_{1}\vee v_{3}\vee\overline{v}_{4})\wedge(\overline{v}_{2}\vee\overline{v}_{3}\vee v_{4})$$R’=\{q_{0}(f(x_{1},x_{2}))arrow f(q_{1}(x_{1}),q_{3}(x_{2}))$に対応するグラフ．

,$q_{0}(f(x_{1},x_{2},x_{3},x_{4}))$

ベル付きグラフの全域木の所属問題はクラス NP に$arrow f(q_{1}(x_{1}), q_{3}(x_{2}),q_{4}(x_{3}),q_{4}(x_{4}))$$q_{1}(f(x_{1},x_{2}, x_{3},x_{4}))$

属する．

ゆえに，

$|\Sigma|\geq 3$

であるならば，木オートマトン

による頂点ラベル付きグラフの全域木の所属問題は

NP 完全である．

口

文献 [9] では，任意のラベルの集合に対し，木オー
トマトンによる無閉路有向グラフ (DAG) の所属問
題が NP 完全であることが証明されている．しかし$arrow f(q_{0}(x_{1}),q_{2}(x_{2}),q_{4}(x_{3}),q_{4}(x_{4}))$結果である．そこで，補題 1 の結果を拡張し，次の$arrow f(q_{2}(x_{1}), q_{4}(x_{2}),q_{4}(x_{3}))$定理 1 任意の頂点ラベルの集合に対し，木オートマ
トンによる頂点ラベル付きグラフの所属問題は $NP$
完全である．

$q_{2}(f(x_{1},x_{2}, x_{3}, x_{4}))$$arrow f(q_{2}(x_{1}), q_{2}(x_{2}),q_{4}(x_{3}),q_{4}(x_{4}))$,$q_{2}(f(x_{1},x_{2},x_{3}))$$arrow f(q_{2}(x_{1}),q_{4}(x_{2}),q_{4}(x_{3}))$,$arrow f(q_{3}(x_{1}), q_{4}(x_{2}),q_{4}(x_{3}))$,$q_{2}(f(x_{1},x_{2},x_{3},x_{4},x_{5}))$$arrow f(q_{4}(x_{1}),q_{4}(x_{2}), q_{4}(x_{3}),q_{4}(x_{4}),q_{4}(x_{5}))$(証明) 少なくとも頂点ラベルは 1 種類はあるはずな$G$,$q_{3}(f(x_{1}, x_{2},x_{3}))$

結果を得る．

$f\in\Sigma$,$q_{1}(f(x_{1},x_{2},x_{3}))$

ながら，補題 1 は，ラベルが 3 種類以上ある場合のので，,と仮定する．補題 1 で構成したグラフに対し，次のような操作を行う．

,$q_{3}(f(x_{1}, x_{2},x_{3},x_{4}, x_{5}))$$arrow f(q_{4}(x_{1}), q_{4}(x_{2}), q_{4}(x_{3}), q_{4}(x_{4}),q_{4}(x_{5}))$$q_{4}(f)arrow f\}$

.

,

165
$G’$ が
明らかに，

の

$G$

が

$A$

$\mathcal{A}’$に受理されることは，補題 1に受理されることと同値である．
$\square$を与えられた木オートマトンと$A=(Q, \Sigma, q_{0}, R)$する． を $R$ に現れる変数の集合とする．次の形$\mathcal{X}_{A}$の規則 $r\in R$ に対し，

5

Tree-Width が高々2 のグラフに対する線形時間の所属性判定$r:q(f(x_{1}, \ldots,x_{n}))arrow f(q_{1}(x_{1}), \ldots,q_{n}(x_{n}))$を表し，sym $(r)$ で記号 を表し，
var $(r)$ で変数の集合
訂を表すものとする．
state $(r)$ で状態

$f$

$q$

$\{x_{1},$アルゴリズム$\ldots,$$x$

所属性判定アルゴリズム

本章では，Tree-Width が高々 2 のグラフに対する
入力: 頂点ラベル付グラフ $G=(V, E)$ とその頂点ラ線形時間の所属性判定アルゴリズムを紹介する．
ベル付け関数
任意の Tree-Width が高々2 のグラフは，次に示す
出力:accept または reject
変形規則によって単一頂点のグラフに変形できるこ$\sigma$1、頂点集合 $V$ に任意の全順序を与えるとが知られている [lO](図 3 も見よ).

1. グラフに頂点$\{v_{1}, v_{2}\}$$\{v_{1}, v_{2}\}$が存在し，正確に 1 つの辺と辺に繋がっているとき，頂点$v_{2}$$\{v_{1}, v_{2}\},$ $\{v_{2}, v_{3}\}$と辺$A[e]:=\emptyset$

5:$B[e]:=\emptyset$が存在し，正確に 2 つの辺

6:$C[e]:=\emptyset$に繋がっているとき，頂点7:$D[e]:=\emptyset$を取り除く．
$v_{2}$$\{v_{1}, v_{2}\},$ $\{v_{2}, v_{3}\}$$\{v_{1}, v_{3}\}$

3: for all $e:(v_{1}, v_{2})\in E’$ do4:$v_{2}$

2. グラフに頂点

2: $E’:=\{(v_{1}, v_{2})|\{v_{1}, v_{2}\}\in E$ かつ $v_{1}<v_{2}\}$$v_{2}$を取り除き，新しい辺$S$:$q_{n}(x_{n}))\in R$

を加える．

3. 規則 2 によって，頂点9.
$V_{1},$$V_{2}$の間に多重辺がで10:きてしまったら，多重辺を取り除き，新しい辺$\{v_{1}, v_{3}\}$$\ldots$do

かつ $\sigma(v_{1})=f$ then$A[e]$ $:=A[e]\cup\{(r, \{x_{i}\}, r’, \emptyset)|1\leq i\leq n$ ,sym$(r’)=\sigma(v_{2})h\backslash$つstate $(r’)=$12:$\backslash ’|’\backslash i\bullet^{\backslash \prime}$$\backslash ’\backslash ’rightarrow^{\backslash l}$$=>$$v_{2}$

13:$v_{1}$

end ifif $n\geq 1$ かつ $\sigma(v_{2})=f$ then$B[e]$ $:=B[e]\cup\{(r’, \emptyset, r, \{x_{i}\})|1\leq i\leq n$ ,$r’\in R$ ,sym$(r’)=\sigma(v_{1})k^{\backslash \text{つ}}$state $(r’)=$’$q_{i}\}$

2.

$’ \backslash \frac{\prime\prime\backslash \prime\prime\backslash \prime\prime\prime\prime}{v_{1}v_{2}v_{\grave{3}}}l’$$=$$’.\prime\prime\prime\backslash \prime\prime\primerightarrow’\backslash r\backslash v_{1}v_{j}\prime\prime$

14:

15:
16:

3.

$\backslash .’\backslash ..l\backslash .’\backslash .’rightarrow’\prime\prime$$\prime\prime\backslash ’\backslash ’\backslash ’\backslash \backslash \Leftrightarrow’’\backslash$$=>$$v_{1}$,$q_{i}\}$

11:$v_{1}$

if$n\geq 1$$r’\in R$ ,

を加える．
’

1.

for all $r:q(f(x_{1}, \ldots, x_{n}))arrow f(q_{1}(x_{1}),$$v_{2}$

17:$v_{I}$$v_{2}$

図 3: 変形規則．

本稿で紹介する所属性判定アルゴリズムは，変形規則にグラフが変形される毎に，各頂点及び辺に与えた値を書き換えていくことで動作する．

end ifend forfor all $(r, r’)\in R\cross R$ do
つ sym $(r’)$
if sym $(r)$then$=\sigma(v_{1})h\backslash$18:$C[e]$

19:

end ifend for

20:$:=C[e]\cup\{(r, \emptyset, r’, \emptyset)\}$21: end for
22: for all $v\in V$ do$=\sigma(v_{2})$166
var $(r’)$ かつ

23:$A[v];=\emptyset$$A[v_{2}],$

24:$B[v]:=\emptyset$$\emptyset\}\cup\{(r, \mathcal{X}_{1}\cup \mathcal{X}_{2})|(r, \mathcal{X}_{1})\in A[v_{1}]$25:

for all $r\in R$ do$(r’, \mathcal{X}_{3}, r, \mathcal{X}_{2})\in A[(v_{2}, v_{1})],$

26:

27:
28:

29:
30:

if sym $(r)=\sigma(v)$ then$B[v_{2}],$$A[v]:=A[v]\cup\{(r, \emptyset)\}$$\mathcal{X}_{3}\cup \mathcal{X}_{4}=$var$\mathcal{X}_{3}\cup \mathcal{X}_{4}=$$(r’)h^{\backslash }$end ifif state $(r)=q0$ かつ sym $(r)=\sigma(v)$ then$(r’, \mathcal{X}_{3}, r, \mathcal{X}_{2})\in D[(v_{2}, v_{1})],$$A[v_{2}],$$B[v]:=B[v]\cup\{(r, \emptyset)\}$$\mathcal{X}_{3}\cup \mathcal{X}_{4}=$var $(r’)$ かっ

46:

34: while $|V|>1$ do

47:$V:=V-\{v_{2}\}$48:

if $v_{1}<v_{2}$ かつ $v_{2}<v_{3}$ then$\{v_{1}, v_{2}\},$

if $v_{2}\in V$ が存在し，正確に 1 つの辺に繋がっている then
$V:=V-\{v_{2}\}$37:

if $v_{1}<v_{2}$ then$E’:=E’-\{(v_{1}, v_{2})\}$

39:$A[v_{1}]$$\{v_{1}, v_{2}\}$$:=\{(r, \mathcal{X}_{1}\cup \mathcal{X}_{2})|(r, \mathcal{X}_{1})\in A[v_{1}]$$\mathcal{X}_{3}\cup \mathcal{X}_{4}=$50:$A:=\{(r, \mathcal{X}_{1}, r’, \mathcal{X}_{2})|(r, \mathcal{X}_{1}, r’’, \mathcal{X}_{3})\in$

var $(r’)$ かつ,$(r’, \mathcal{X}_{4})\in$$\mathcal{X}_{3}$

口

かつ

51:

$\in A[(v_{1}, v_{2})],$$\mathcal{X}_{3}\cup \mathcal{X}_{4}=$var $(r’)$ かつ$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{3})$$\in B[(v_{1}, v_{2})],$$\mathcal{X}_{3}\cup \mathcal{X}_{4}=$var$(r’)$$A[v_{2}],$

口

かつ晶口

$\in D[(v_{1}, v_{2})],$$\mathcal{X}_{3}\cup \mathcal{X}_{4}=$$\mathcal{X}_{3},$は互いに素}$(r”, \mathcal{X}_{4},r’, \mathcal{X}_{2})\in B[(v_{2}, v_{3})]$$\mathcal{X}_{4},$,$A[(v_{1}, v_{2})],$

43:

かつ

$\mathcal{X}_{3},$$\mathcal{X}_{3}\cup \mathcal{X}_{4}=$var $(r’)$ かつ$\mathcal{X}_{3},$$\mathcal{X}_{4},$$\mathcal{X}_{5}$$\{(r, \mathcal{X}_{1}, r’, \mathcal{X}_{2})$$\mathcal{X}_{3}\cap \mathcal{X}_{4}=$$D[(v_{1}, v_{2})],$$(r”, \mathcal{X}_{5})$$(r’, \mathcal{X}_{4})\in$は互いに素}$(r, \mathcal{X}_{1}, r’’, \mathcal{X}_{3})$$|$$\mathcal{X}_{3}\cup \mathcal{X}_{4}\cup \mathcal{X}_{5}=$$B[v_{2}]$$\cup$,$\mathcal{X}_{5}$

$\in$

,

var $(r”)$$(r”, \mathcal{X}_{4}, r’, \mathcal{X}_{2})\in A[(v_{2}, v_{3})]$

$\in$

var

$B[v_{1}]:=\{(r, \mathcal{X}_{1}\cup \mathcal{X}_{2})|(r, \mathcal{X}_{1})\in B[v_{1}]$$\mathcal{X}_{4},$,$=$は互いに素}$(r’, X_{4})\in$,$\mathcal{X}_{3}\cup \mathcal{X}_{4}\cup \mathcal{X}_{5}$$(r”, \mathcal{X}_{4}, r’, \mathcal{X}_{2})\in C[(v_{2}, v_{3})]$$(r”)$$\emptyset\}$$(r’, \mathcal{X}_{3},r, \mathcal{X}_{2})\in B[(v_{2}, v_{1})],$$A[v_{2}],$$D:=\{(r, \mathcal{X}_{1}, r’, \mathcal{X}_{2})|(r, \mathcal{X}_{1}, r’’, \mathcal{X}_{3})\in$$(r”, \mathcal{X}_{5})$$:=\{(r, \mathcal{X}_{1}\cup \mathcal{X}_{2})|(r, \mathcal{X}_{1})\in A[v_{1}]$$(r’, \mathcal{X}_{3}, r, \mathcal{X}_{2})\in B[(v_{2}, v_{1})],$

は互いに素}$(r”, \mathcal{X}_{5})\in A[v_{2}],$$\mathcal{X}_{4}=$,var $(r”)$$(r”, \mathcal{X}_{4}, r’, \mathcal{X}_{2})\in B[(v_{2}, v_{3})]$$\in$$B[(v_{1}, v_{2})],$$A[v_{1}]$$\mathcal{X}_{3}\cup \mathcal{X}_{4}\cup \mathcal{X}_{5}=$$\cup\{(r, \mathcal{X}_{1}, r’, \mathcal{X}_{2})$53:$E’:=E’-\{(v_{2}, v_{1})\}$$\mathcal{X}_{5}$var $(r”)$ かつ$\mathcal{X}_{4}=$var $(r”)$$C:=\{(r, \mathcal{X}_{1}, r’, \mathcal{X}_{2})|(r, \mathcal{X}_{1}, r’’, \mathcal{X}_{3})\in$$(r”, \mathcal{X}_{5})$$(r’, \mathcal{X}_{4})\in$

var $(r’)$ かつ碗口

42:

44:

$\mathcal{X}_{5}$$C[(v_{1}, v_{2})],$

,

else

$A[v_{2}],$52:$(r’,\mathcal{X}_{4})\in$$\emptyset\}$41:$\mathcal{X}_{4},$$\mathcal{X}_{3}\cup \mathcal{X}_{4}\cup \mathcal{X}_{5}=$,$:=\{(r, \mathcal{X}_{1}, r’, \mathcal{X}_{2})|(r, \mathcal{X}_{1}, r’’, \mathcal{X}_{3})\in$かつ$\mathcal{X}_{4}=$$\emptyset\}\cup\{(r, \mathcal{X}_{1}\cup \mathcal{X}_{2})|(r, \mathcal{X}_{1})\in A[v_{1}]$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{3})$,$(r’, \mathcal{X}_{4})\in$$\mathcal{X}_{3}$$\emptyset\}\cup\{(r, \mathcal{X}_{1}\cup \mathcal{X}_{2})|(r, \mathcal{X}_{1})\in A[v_{1}]$$B[v_{2}],$$B$$\mathcal{X}_{3},$$B[(v_{1}, v_{2})],$$\mathcal{X}_{4}=$$B[v_{1}];=\{(r, \mathcal{X}_{1}\cup \mathcal{X}_{2})|(r, \mathcal{X}_{1})\in B[v_{1}]$$A[v_{2}],$$(r”, \mathcal{X}_{4}, r’, \mathcal{X}_{2})\in A[(v_{2}, v_{3})]$$(r”, \mathcal{X}_{5})\in A[v_{2}],$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{3})$$\mathcal{X}_{3}\cap \mathcal{X}_{4}=$$E:=E’-\{(v_{1}, v_{2}), (v_{2}, v_{3})\}$$\emptyset\}$40:,$(r’, \mathcal{X}_{4})\in$

49:$(r”, \mathcal{X}_{5})\in A[v_{2}],$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{3})\in A[(v_{1}, v_{2})],$$A[v_{2}],$$\mathcal{X}_{3}\cap \mathcal{X}_{4}=$$\{v_{2}, v_{3}\}$$A[(v_{1}, v_{2})],$

38:,$(r’, \mathcal{X}_{4})\in$

end ifelse if $v_{2}\in V$ が存在し，正確に 2 つの辺に繋がっている thenend for33: end for

32:

36:

$\mathcal{X}_{4}=$$\emptyset\}$

45:

35:

口

$\emptyset\}\cup\{(r, \mathcal{X}_{1}\cup \mathcal{X}_{2})|(r, \mathcal{X}_{1})\in A[v_{1}]$end if31:

つ$\mathcal{X}_{3}$かつ$\mathcal{X}_{3},$,も$\mathcal{X}$$\mathcal{X}_{4},$$\mathcal{X}_{5}$$\cup \mathcal{X}_{4}\cup \mathcal{X}_{5}$は互いに素}$(r, \mathcal{X}_{1}, r’’, \mathcal{X}_{3})$

$|$

$\in$

$(r”, \mathcal{X}_{4}, r’, \mathcal{X}_{2})\in A[(v_{2}, v_{3})]$$\in$var $(r”)$ かっ$A[v_{2}],$$\mathcal{X}_{3},$$\cup\{(r, \mathcal{X}_{1}, r’, \mathcal{X}_{2})$$\mathcal{X}_{3}\cup \mathcal{X}_{4}\cup \mathcal{X}_{5}$$\mathcal{X}_{4},$$|$$\mathcal{X}_{5}$

,

$=$

,

$=$

は互いに素}$(r, \mathcal{X}_{1}, r’’, \mathcal{X}_{3})$

$\in$

167
$B[(v_{1}, v_{2})],$

69:$(r”)$

70:$E$ $:=E’-\{(v_{2}, v_{1}), (v_{2}, v_{3})\}$

は互いに素}

71:

then

72:

(同様なので省略)
else if $v_{2}<v_{1}$ 、つ $v_{3}<v_{2}$ then
$E:=E’-\{(v_{2}, v_{1}), (v_{3}, v_{2})\}$$(r”, \mathcal{X}_{5})\in A[v_{2}],$

かつ

54:

if

$\mathcal{X}_{3},$$\mathcal{X}_{4},$$\mathcal{X}_{5}$$(v_{1}, v_{3})\not\in E’$else if $v_{2}<v_{1}B$,$(r”, \mathcal{X}_{4}, r’, \mathcal{X}_{2})\in D[(v_{2}, v_{3})]$$\mathcal{X}_{3}\cup \mathcal{X}_{4}\cup \mathcal{X}_{5}=$var、$\text{つ_{}v_{2}}<v_{3}$

$B$

55:

$E’:=E’\cup\{(v_{1}, v_{3})\}$

73:

56:

$A[(v_{1}, v_{3})]:=A$

57:$B[(v_{1}, v_{3})]:=B$

58:$C[(v_{1}, v_{3})]:=C$59:$D[(v_{1}, v_{3})]:=D$(同様なので省略)
75:
end if76:
end if
77: end while

60:
61:

74:

else

78:

$A[(v_{1}, v_{3})]$$\mathcal{X}_{4})$

$|$

$;=$

$\{(r,$$\mathcal{X}_{1}\cup \mathcal{X}_{2},$$(r, \mathcal{X}_{1}, r’, \mathcal{X}_{3})$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{4})\in C,$

$\in$

$|$

,

$\mathcal{X}_{1}\cap \mathcal{X}_{2}=\emptyset$

かつ

$r’,$

$\mathcal{X}_{3}\cup$$(r, \mathcal{X}_{1}, r’, \mathcal{X}_{3})$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{4})\in A,$$r’,$ $\mathcal{X}_{3}\cup$$A[(v_{1}, v_{3})]$$\mathcal{X}_{3}\cap \mathcal{X}_{4}=\emptyset\}\cup\{(r,$ $\mathcal{X}_{1}\cup \mathcal{X}_{2},$$\mathcal{X}_{4})$

then

$\in$

$C[(v_{1}, v_{3})]$$\mathcal{X}_{1}\cap \mathcal{X}_{2}=\emptyset$,$V$

79: ifの唯一の要素を$(r, \mathcal{X})\in B[v]$

so:

$v$

とする

が存在して，var$(r)=\mathcal{X}$thenreturn accept
sl: else:
return reject
S3: end if
$S2$

かつ

$\mathcal{X}_{3}\cap \mathcal{X}_{4}=\emptyset\}$62:$B[(v_{1}, v_{3})]$$\mathcal{X}_{4})$$|$$;=\{(r,$$\mathcal{X}_{1}\cup \mathcal{X}_{2},$$(r, \mathcal{X}_{1}, r’, \mathcal{X}_{3})$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{4})\in C,$$\in$$B[(v_{1}, v_{3})]$$\mathcal{X}_{1}\cap \mathcal{X}_{2}=\emptyset$$\mathcal{X}_{3}\cap \mathcal{X}_{4}=\emptyset\}\cup\{(r,$ $\mathcal{X}_{1}\cup \mathcal{X}_{2},$$\mathcal{X}_{4})$$|$$(r, \mathcal{X}_{1}, r’, \mathcal{X}_{3})$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{4})\in B,$$r’,$ $\mathcal{X}_{3}\cup$

$\in$

$r’$

$h\backslash$,純

つ$\cup$$C[(v_{1}, v_{3})]$$\mathcal{X}_{1}\cap \mathcal{X}_{2}=\emptyset h^{t}$

,

,

つ

$C[(v_{1}, v_{3})]$$\mathcal{X}_{4})$$|$$;=\{(r,$, も 火$C[(v_{1}, v_{3})]$ ,$\mathcal{X}_{1}\cup \mathcal{X}_{2},$$(r, \mathcal{X}_{1}, r’, \mathcal{X}_{3})$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{4})\in C,$

$\in$

$r’$

$\mathcal{X}_{1}\cap \mathcal{X}_{2}=\emptyset$$\mathcal{X}$かつ$D[(v_{1}, v_{3})]$$\mathcal{X}_{4})$$|$$;=\{(r,$, r’, も俺$D[(v_{1}, v_{3})]$ ,$\in$$\mathcal{X}_{1}\cap \mathcal{X}_{2}=\emptyset\hslash\backslash$$\mathcal{X}_{3}\cap \mathcal{X}_{4}=\emptyset\}\cup\{(r,$ $\mathcal{X}_{1}\cup \mathcal{X}_{2},$$|$$(r, \mathcal{X}_{1}, r’, \mathcal{X}_{3})$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{4})\in D,$

$\in$

66:

end ifelSe if$v_{1}<v_{2}h^{\backslash }$$r’,$

つ $v_{3}<v_{2}$

then

67:

$E:=E’-\{(v_{1}, v_{2}), (v_{3}, v_{2})\}$

68:(同様なので省略)つ$\mathcal{X}_{3}\cup$$C[(v_{1}, v_{3})]$$\mathcal{X}_{1}\cap \mathcal{X}_{2}=\emptyset$$\mathcal{X}_{3}\cap \mathcal{X}_{4}=\emptyset\}$65:$\mathcal{X}$$\mathcal{X}_{1}\cup \mathcal{X}_{2}$$(r, \mathcal{X}_{1}, r’, \mathcal{X}_{3})$$(r, \mathcal{X}_{2}, r’, \mathcal{X}_{4})\in C,$$\mathcal{X}_{4})$かつて，創薬の研究は，製薬会社の研究員か製薬会社につながりのある研究者に限られていた．もしくは，膨大な手間と費用とかけて自前の医薬品デー

タベースを作成しなければならなかった．しかし，最いついで公開され，創薬の研究への道が開けている．

本稿では，化学グラフを頂点ラベル付グラフと見なし，化学グラフの木オートマトンによる所属問題を考え，この所属問題が NP 完全であることと，Tree-$\mathcal{X}_{3}\cap \mathcal{X}_{4}=\emptyset\}$64:

まとめと今後の課題

近，自由に利用できるデータベース [5,11,12] があ$\mathcal{X}_{3}\cap \mathcal{X}_{4}=\emptyset\}$63:

6Width が高々2 であるような化学グラフに対する線
形時間の所属性判定アルゴリズムを提案じた．
今後の課題は，木文法を拡張し，化学グラフを生成する文法を提案することである．

,

かつ

参考文献
[1] Jean-Loup Faulon. Isomorphism, automorphism partitioning, and canonical labeling canbe solved in polynomial-time for moleculargraphs. Joumal of Chemical Information and168
Computer Sciences, Vol. 38, No. 3, pp. 432444, 1998.

trees. SIAM J. Algebraic Discrete Methods,
Vol. 7, No. 2, pp. 305-314, 1986.

[2] Eugene M. Luks. Isomorphism of graphs of [11] PubChem. http: //pubchem. ncbi. nlm. nih.
$gov/$ .
bounded valence can be tested in polynomial
time. J. Comput. Syst. Sci., Vol. 25, No. 1, pp.
[12] Worldwide Protein Data Bank. http: $//www$ .
42-65, 1982.
wwpdb. $org/$ .
[3] L\’asz16 Babai and Eugene M. Luks. Canonical labeling of graphs. In STOC, pp. 171-183,

1983.
[4] John E. Hopcroft and J. K. Wong. Linear timealgorithm for isomorphism of planar graphs(preliminary report). In STOC, pp. 172-184,

1974.
[5] ChEMBL.

https: $//www$ . ebi. ac. $uk/$

chembl/.

[6] Hans L. Bodlaender. Polynomial algorithms
for graph isomorphism and chromatic index onpartial k-trees. J. A lgori thms, Vol. 11, No. 4,
pp. 631-643, 1990.
[7] Jir\’i Matousek and Robin Thomas. On thecomplexity of finding iso- and other morphisms
for partial k-trees. Discrete Mathematics, Vol.
108, No. 1-3, pp. 343-364, 1992.

Comon, M. Dauchet, R. Gilleron,F. Jacquemard, D. Lugiez, C. L\"oding,
S. Tison, and M. Tommasi. Tree automata
techniques and applications. Available on:
http: $//www$ . grappa. univ-lille3. $fr/tata$ ,2007. release October, 12th 2007.

[8] H.

[9] Akio Fujiyoshi. Recognition of directed acyclic
graphs by spanning tree automata. Theor.
Comput. Sci., Vol. 411, No. 38-39, pp. 34933506, 2010.
[10] Stefan Arnborg and Andrzej Proskurowski.
Characterization and recognition of partial 3-