In this talk, we consider the pre-image problem for chemical compounds, which is to infer a chemical structure that is mapped to a given feature vector, and has a potential application to design of novel chemical compounds. In particular, we consider the pre-image problem for feature vectors consisting of frequencies of labeled paths of bounded length. We present several time complexity results that include: NP-hardness result for a general case, polynomial time algorithm for tree structured compounds. Then, we present practical algorithms for the pre-image problem, all of which are based on enumeration of chemical structures satisfying given constraints. We also introduce the EnuMol system, which is a web-server for enumeration of tree-like chemical compounds from given path frequencies, and has been developed jointly by Akutsu laboratory and Nagamochi laboratory in Kyoto University.
Back to Workshop II: Optimization, Search and Graph-Theoretical Algorithms for Chemical Compound Space