Morganアルゴリズムとは？
Morganアルゴリズムは、分子内の原子の優先順位をつけるためのアルゴリズムです。SMILES表記を一意に決めるためのcanonical SMILESにも利用されています。
Morganアルゴリズムのルール
以下のルールで分子内の原子の優先順位をつけます。
- 各重原子に結合している重原子数を「結合原子数」として登録します。（重原子は水素以外の原子）
- 異なる結合原子数を持つ重原子の種類を求め n とします。
- 各重原子に結合している重原子の結合原子数の合計を、次の結合原子数として更新します。
- 異なる結合原子数を持つ重原子の種類を求め、nとします。
- nが増えなくなるまで 3～4 のステップを繰り返します。nが同じの場合は後の世代を採用、nが減少した場合はひとつ前のnが大きい世代を採用します。
- 最大の結合原子数の重原子の番号を1とします。
- 番号付けされた重原子に隣接する重原子の中で最も大きいものに、続く番号をつけます。
- 隣接する重原子にすべて番号付けを終えたら、番号の若い順に (7) のステップを繰り返します。すべての重原子に番号を付けたら終了です。
これを読むだけでは理解しにくいと思いますので、下の項目で具体例を使ってわかりやすく説明します。
Morganアルゴリズムの具体例
文章の説明だけではわかりにくいので、安息香酸メチルを使って具体例を示します。
まず、見た目をシンプルにするために、安息香酸メチルを重原子のグラフ表現にしました。
次に、各重原子に結合している重原子数を「結合原子数」として登録します。これを第１世代とします。第１世代の異なる結合原子数を持つ重原子は3種類（1,2,3）なので、n = 3です。
各重原子に結合している重原子の結合原子数の合計を、第２世代の結合原子数として更新します。第2世代の異なる結合原子数を持つ重原子は6種類（2,3,4,5,6,7）なので、n = 6です。
これを繰り返すと、第３世代と第４世代がそれぞれn = 7になります。そのためここで結合原子数の更新は終了で、第４世代を採用します。
採用した第４世代の結合原子数は36が最大でした。この原子を優先順位１番とします。36のまわりには、30、25、25の3原子がありますので、30を優先順位2番目、ふたつの25をそれぞれ3番目と4番目にします。
優先順位1番のまわりの重原子はすべて優先順位をつけ終わったので、次は優先順位2番を見ます。2番のまわりには優先順位をつけていない重原子がありますので、下都合原子数の大きい順に、5番、6番をつけます。
次は優先順位3番のまわりの重原子に番号をつける・・・ということを繰り返して、下の説明図にあるように最後の10番まで優先順位をつけることができます。
まとめ
Morganアルゴリズムは、分子内の原子の優先順位をつけるためのアルゴリズムです。Morganアルゴリズムについて、ルールと具体例を使ってわかりやすく説明しました。