On computational complexity of graph inference from counting

Abstract: In de novo drug design, chemical compounds are quantitized as real-valued vectors called chemical descriptors, and an optimization algorithm runs on those of 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.

Bio: Shinnosuke Seki is a postdoctral researcher at the Department of Information and Computer Science, Aalto University. He received his Ph.D. from the University of Western Ontario, Canada, on combinatorics in information encoding on DNA, in 2010.  His research interest lies in algorithms, combinatorics, and automata theory.