title: A dynamic programming algorithm to predict synthesis processes of tree-structured compounds with graph grammar.
abstract: 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.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, 611-0011, Japan. tyoyo@kuicr.kyoto-u.ac.jp.
authors.forename: Yang
authors.initials: Y
authors.lastname: Zhao
authors.forename: Takeyuki
authors.initials: T
authors.lastname: Tamura
authors.forename: Morihiro
authors.initials: M
authors.lastname: Hayashida
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
mesh_terms: D000465:Algorithms; D002625:Chemistry, Organic / Q000379:methods; D019295:Computational Biology / Q000379:methods*; D015195:Drug Design; D008962:Models, Theoretical; D012984:Software; D049490:Systems Biology; D013997:Time Factors