Zhao Yang, Tamura Takeyuki, Hayashida Morihiro, Akutsu Tatsuya
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, 611-0011, Japan.
Genome Inform. 2010;24:218-29.
For several decades, many methods have been developed for predicting organic synthesis paths. However these methods have non-polynomial computational time. In this paper, we propose a bottom-up dynamic programming algorithm to predict synthesis paths of target tree-structured compounds. In this approach, we transform the synthesis problem of tree-structured compounds to the generation problem of unordered trees by regarding tree-structured compounds and chemical reactions as unordered trees and rules, respectively. In order to represent rules corresponding to chemical reactions, we employ a subclass of NLC (Node Label Controlled) grammars. We also give some computational results on this algorithm.
几十年来，已经开发了许多用于预测有机合成路径的方法。然而，这些方法具有非多项式的计算时间。在本文中，我们提出了一种自底向上的动态规划算法来预测目标树状结构化合物的合成路径。在这种方法中，我们通过将树状结构化合物和化学反应分别视为无序树和规则，将树状结构化合物的合成问题转化为无序树的生成问题。为了表示与化学反应相对应的规则，我们采用了NLC（节点标签控制）语法的一个子类。我们还给出了该算法的一些计算结果。
