1. On computational complexity of graph inference from counting.
- Author
-
Fazekas, Szilárd Zsolt, Ito, Hiro, Okuno, Yasushi, Seki, Shinnosuke, and Taneishi, Kei
- Subjects
- *
COMPUTATIONAL complexity , *ELECTRONIC data processing , *MACHINE theory , *STRUCTURAL optimization , *ALGORITHMS - Abstract
In de novo drug design, chemical compounds are quantitized as real-valued vectors called chemical descriptors, and an optimization algorithm runs on known drug-like chemical compounds in a database and outputs an optimal chemical descriptor. Since structural information is needed for chemical synthesis, we must infer chemical graphs from the obtained descriptor. This is formalized as a graph inference problem from a real-value vector. By generalizing subword history, which was originally introduced in formal language theory to extract numerical information of words and languages based on counting, we propose a comprehensive framework to investigate the computational complexity of chemical graph inference. We also propose a (pseudo-)polynomial-time algorithm for inferring graphs in a class of practical importance from spectrums. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF