有機化学×グラフ理論(2)

こんにちは、D2の星です。

前回に引き続き、グラフ理論についてです。今回のテーマは、「最短の合成経路を見つけ出す」です。

前回は、化学変換をグラフに落とし込めるというお話でした。ここからは、「そんなことをして何が嬉しいのか？」を考えていきます。

今の世の中には、これまでに蓄積されてきた無数の化合物、化学反応があります。それらの知見を活用しようにも、その膨大なデータを人間の手だけで捌くのはもはや不可能であり、コンピュータの力を借りることになります。そのためには、実験データをコンピュータが扱いやすい形で保存しないといけません。

仮に数十万の化合物、化学反応が登録されているデータベースがあったとしましょう。ここで重要なのは、「それぞれの化合物がどんな化学反応で繋がっているのか？」ということであり、グラフ理論の出番です。すなわち、各化合物に番号をつけて「頂点」とし、同じく各反応に番号をつけて「(有向)辺」とします。

さて、このデータベースを元に、「ある化合物Aから化合物Bを合成する最小の工程数はいくつか？」を求めたいとします。実際には反応時間や試薬の値段、収率など重要な要素が他にもたくさんありますが、今回は工程数のみを考えてみます。

当然ですが十万もの頂点や辺は書けませんので、以下の小さいグラフで考えることにします。

: 小さい有向グラフを考えます

この程度のサイズなら、コンピュータの演算能力を活かして、深く考えず総当たり的に経路を探索することもできるでしょう。しかしグラフのサイズが何十万という規模になったらいくらコンピュータといえども時間がかかりすぎます。そこで、効率的なアルゴリズムが必要になります。

例えば、グラフ上では「アルコールをアルデヒドに酸化して、また還元して元のアルコールに戻る」ということも可能でしょうが、明らかに無駄ですよね。あるいは工程数だけを考える今回の場合、アルコールからカルボン酸に一工程で変換できるならわざわざアルデヒドを経由する必要はないわけです。そういった無駄を排除するために、次のように最小工程数を決定します。

1. 出発原料は工程数0とします。

: 工程数0 (出発原料)

2. 出発原料から一工程で到達できる化合物を全て工程数1とします。

: 工程数1

3. 工程数1から一工程で到達できる化合物を全て工程数2とします。

: 工程数2

4. 工程数2から一工程で到達できる化合物を全て工程数3とします。ここで重要なのは、到達先に既に数字が書いてある場合は変更しない、ということです。

: 工程数3 (終了)

これで全ての化合物の最小工程数が求まりました。

このアルゴリズムを見て、ごく当たり前のことをしているだけじゃないかと思われた方もいると思います。私たちも特に意識せずこのような手順を踏んでいると思いますが、グラフ理論の世界ではこのアルゴリズムには「幅優先探索」という名前がついています。それだけ重要なアルゴリズムというわけですね。これにより無駄な探索はなくなり、化合物や化学反応が数十万程度ならなんと一秒もかからずに答えが出てしまいます。

しかし前述の通り実際には工程数だけが重要なわけではありません。例えば「とにかく早く合成したいから、総反応時間を最小化したい」という場合はどうでしょうか。工程数の場合は各辺の”長さ”は全て1ですが、反応時間だとそうはなりません。実はその場合、今回紹介した単純な幅優先探索はうまくいきません。

次回はそういったもう少し複雑な状況においてどのようなアルゴリズムが知られているのかを紹介したいと思います。それではまた。