南山の先生

学部別インデックス

理工学部・システム数理学科

小市 俊悟

職名 准教授
専攻分野 「離散数学」「情報化学」
主要著書・論文 Algorithm for Advanced Canonical Coding of Planar Chemical Structures that Considers Stereochemical and Symmetric Information. Journal of Chemical Information and Modeling, 47 (2007), pp. 1734 - 1746.(共著)
将来的研究分野 離散最適化とその実践的応用。
担当の授業科目 数学演習A・B

分子とグラフ

実際の問題を数理的に解決するということの例をひとつ紹介したいと思います。

昨今では、分子構造を解析する技術の発展により、毎日のように新しい分子が発見されています。しかし、発見した分子が本当に新しいものなのかはどのように調べるのでしょうか。そんなとき、新たな分子をそれまでに発見された分子のデータベースと照合できれば助かります。そのためには、まず、二つの分子が同じものであるか否かを判定できなければなりません。

二つの分子が同じであるとは、原子の位置を色々と変えたとき、二つの分子がピタリと重なることです。しかし、大きな分子に対して、照合の度にそのようなことをしていたら、いくら速いコンピュータでもいつまで経っても終わりません。そこで、分子を分子式のような文字列で表現して、その文字列が一致するか否かで分子が同じであるか否かが判定できないかと考えます。しかし、そのような文字列を作ることは意外にも難しいのです。

例えば分子の文字列表現として、分子式を考えてみましょう。分子式を書くとき、小さな分子、例えばメタンなどを分子式で書くときは迷わず書けるけど、大きな分子になると、どの分子を先頭にして書き始めたらいいのだろうか悩んだ経験はないでしょうか。同じ分子を表すはずなのに私とあなたの書く分子式が異なる。大きい分子になるほど、分子式の書き方は千差万別となります。同じ分子であれば、いつも決まった文字列になるようにするのは実は易しくないのです。

さて、このように二つの分子が同じであるかの判定は難しい問題ですが、それを解決するヒントが、離散数学の一分野であるグラフ理論にありました。グラフとは、いくつかの点とそれらを結ぶ辺からなるものですが、図のように分子は原子を点、結合を辺だと思えば、まさにグラフとなります。このグラフという概念を用いると、分子が同じであるかという問題は、グラフが同じであるかという問題になります。しかも、この問題はグラフ同型性判定問題という名でグラフ理論の分野において長年研究されてきました。そして、それを解決する方法がいくつか提案されていたのです。それらの解法を組み合わせると、大きな分子でもいつも決まった文字列で表現できるようになりました。

291_01.jpg

図. 分子(左)とグラフ(右)

この例では、分子に関する問題が、グラフと呼ばれる一段抽象化された数学的概念を用いることで、問題の本質がグラフの同型性判定にあることがわかり、また、そのように理解したことで、解決の糸口をグラフ同型性判定問題の解決法に求めることができました。このように実際の問題に対して、数学的な抽象化(モデリング)と数学を用いた解決を図ることが数理的な問題解決です。今後、多くの実際の問題に対して数理的手法が適用されることが期待されています。