--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

10.25
Thu

2012年10月25日

  • 化学構造式のマッチング問題
  • グラフ同型判定とは
  • Morganアルゴリズム/番号付け
  • Morganアルゴリズム/符号列の生成

化学構造式のマッチング問題

グラフ理論を用いて化学構造式のマッチングを行う。

グラフの同型判定とは

同じ結合表または結合行列を与えるものは同一の分子グラフ表現レベルにおいて同型である。ただし、逆は真ならず(頂点原子の番号付けに依る)

分子グラフの同型判定には個々のグラフに固有のユニークな符号列(規範表現)の生成が必要となる。

  • 頂点原子のユニークな番号付け
  • グラフの符号化

Morganアルゴリズム

番号付け
  • 分子グラフのノード分割
  • 番号付け規則に従った番号付け
化学構造式の符号化
Morgan法では割り当てられた番号付けをもとにMorgan Listと呼ばれる符号列に変換する。

頂点分割(ノード分割)のアルゴリズム

  1. 各ノードの次数をEC値として登録する。
  2. 異なるEC値を持つノードの数を求めkとする。
  3. 各ノードの隣接ノードのEC値の和を求め、これをそれぞれのノードのTEC(Trial EC)とする。
  4. 異なるTEC値を持つノードの数を求めk'とする。
  5. if k' <= k then 終了((kが増えなくなったらおしまい))
  6. if k'&nbps;> then k←k',EC←TECとしてTECを再計算

異なるEC値を持つノードをとりまく環境は互いに異なる環境だと言えるが、等しいEC値を持つノードをとりまく環境は互いに等しいとは言えない。

隣接ノードのEC値を加算することで、その頂点から見える景色(とりまく環境)を広げている印象を受けた。

ノードの番号付け

  1. 最大のEC値を持つノードを番号1とする
  2. n←1
  3. ノードnを対象とする
  4. ノードnに隣接する番号付けされていないノードについて、EC値の大きなものからn+1,n+2,…と番号付けをする
  5. ノードnに隣接するノードについてすべて番号付けを行う
  6. n←n+1
  7. 3.へ戻る

EC値はグラフおけるノードの特徴量として適切で、なおかつ番号付けをするための指標としても優れている印象を受けた。

関連記事

comment 0
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。