We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On computational complexity of graph inference from counting.
- Authors
Fazekas, Szilárd Zsolt; Ito, Hiro; Okuno, Yasushi; Seki, Shinnosuke; Taneishi, Kei
- 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.
- Subjects
COMPUTATIONAL complexity; ELECTRONIC data processing; MACHINE theory; STRUCTURAL optimization; ALGORITHMS
- Publication
Natural Computing, 2013, Vol 12, Issue 4, p589
- ISSN
1567-7818
- Publication type
Article
- DOI
10.1007/s11047-012-9349-2