A Novel Graph-based Approach for Determining Molecular Similarity

Abstract

In this paper, we tackle the problem of measuring similarity among graphs that represent real objects with noisy data. To account for noise, we relax the definition of similarity using the maximum weighted co-$k$-plex relaxation method, which allows dissimilarities among graphs up to a predetermined level. We then formulate the problem as a novel quadratic unconstrained binary optimization problem that can be solved by a quantum annealer. The context of our study is molecular similarity where the presence of noise might be due to regular errors in measuring molecular features. We develop a similarity measure and use it to predict the mutagenicity of a molecule. Our results indicate that the relaxed similarity measure, designed to accommodate the regular errors, yields a higher prediction accuracy than the measure that ignores the noise.

16 pages, 4 figures

References in corpus (3)

• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
• Quantum Annealing Implementation of Job-Shop Scheduling

Cited by in corpus (7)

• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
• Effective electromagnetic actions for Lorentz violating theories exhibiting the axial anomaly
• Partitioning Dense Graphs with Hardware Accelerators
• Combinatorial Optimization by Decomposition on Hybrid CPU--non-CPU Solver Architectures
• Comparing large-scale graphs based on quantum probability theory