分子合成経路発見のためのグラフタイリングアルゴリズム(セッション2)

スポンサーリンク

概要

論文の詳細を見る
現在、小さな分子同士の特定の箇所を既知の酵素によって結合させ、次第に大きな分子を合成していくことによって未知の分子を合成することが研究されている。この際目的分子のグラフ構造を与えられた分子のグラフ構造を用いて敷き詰めることが必要となるが、この問題は一般に非常に難しく膨大な計算コストがかかることが知られている。我々は分子の特徴を用いたアルゴリズムを構成し、敷き詰められる対象の分子の原子数をN、敷き詰める部品となる全ての分子に含まれる原子数をMとしたときにO(NM^3)の前処理を行うことによって可能な敷き詰め方を一つあたり定数時間で高速に列挙できることを示す。またそれを実装してこのアルゴリズムの有用性を検証する。さらにその後、同じ前処理がO(NM)で実行可能であることを示す。
2006-05-18

著者

関連論文

もっと見る

スポンサーリンク