On computational complexity of graph inference from counting
On computational complexity of graph inference from counting
复制标题
论计数图推理的计算复杂度
DOI：
10.1007/s11047-012-9349-2
复制
发表时间：
2013
影响因子：
2.1
通讯作者：
and Kei Taneishi
中科院分区：
文献类型：
--
作者：
Szilard Zsolt Fazekas;Hiro Ito;Yasushi Okuno;Shinnosuke Seki;and Kei Taneishi
在从头药物设计中，化合物被量化为称为化学描述符的实值向量，并且优化算法在数据库中的已知药物样化合物上运行并输出最佳化学描述符。由于化学合成需要结构信息，我们必须从获得的描述符推断化学图。这被形式化为从实值向量的图推理问题。通过推广子词历史，这最初是在形式语言理论中引入的基于计数提取单词和语言的数值信息，我们提出了一个全面的框架来研究化学图推理的计算复杂性。我们还提出了一个（伪）多项式时间算法推断图在一类实际的重要性，从频谱。
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.