Canonical label その2

前回のつづき。

原子のラベル付けを何回か繰り返してcanonical labelを生成する
というプロセスについて書きかけたので、続けてみます。

ペンタン分子（C-C-C-C-C）の場合、まず原子の状態を数値化して、
10106003--20206002--20206002--20206002--10106003
となります。前回のとおりです。ここで、値の小さいものから順位をつけると、
1--2--2--2--1
となります。しかし、同じ2番のついている炭素原子でも、
中心の炭素から見れば両脇にエチル基(-CC)が位置しているのに対し、
その隣の炭素から見ればメチル基(-C)とプロピル基(-CCC)が隣接します。
この違いを順位に反映させるために、「Extended Connectivity」と呼ばれる
考え方を以下で導入します。
基本的な方針は、隣接している原子の順位を数値化することです。

最もシンプルなものは、隣接原子の順位を単純に足し合わせるものです。
ペンタンの場合、
(2)--(1+2)--(2+2)--(2+1)--(2)
これに再び順位を付けると、
1--2--3--2--1
となり、中心の炭素を差別化することができました。

ただし、足し算の場合、和が衝突するという欠点があります。
たとえば、隣接原子の順位が(5, 5, 2)である原子と
(3, 3, 6)である原子を比較した場合、
5+5+2 = 12
3+3+6 = 12
となり、隣接要素が違うにもかかわらず同順位になってしまいます。
二乗和としても、
25+25+4 = 54
9+9+36 = 54
となり、やはり衝突することがあります。

そこで「素数」の登場です。
素数を小さい順に並べた数列 (2, 3, 5, 7, 11, 13, 17, ...) を準備し、
先ほどの順位列をこの数列に置き換えます。
そして、和ではなく、積をとってみましょう。すると、
11x11x3 = 363
5x5x13 = 325
となり、区別できます。素数の特性を活かしたエレガントな方法ですね。

このプロセスを繰り返せば、２つ隣、３つ隣の原子の順位も伝播させることができます。
順位の入れ替わりがなくなった段階で、最終的なcanonical labelが決定します。

詳細は、Weiningerらの論文を参考に*1。次回は実装です。

*1: Weininger et al. SMILES. 2. Algorithm for Generation of Unique SMILES Notation. J. Chem. Inf. Comput. Sci. (1989) 29, 97-101