QuTIE: quantum optimization for target identification by enzymes

Abstract

Summary: Target identification by enzymes (TIE) problem aims to identify the set of enzymes in a given metabolic network, such that their inhibition eliminates a given set of target compounds associated with a disease while incurring minimum damage to the rest of the compounds. This is a NP-hard problem, and thus optimal solutions using classical computers fail to scale to large metabolic networks. In this article, we develop the first quantum optimization solution, called QuTIE (quantum optimization for target identification by enzymes), to this NP-hard problem. We do that by developing an equivalent formulation of the TIE problem in quadratic unconstrained binary optimization form. We then map it to a logical graph, and embed the logical graph on a quantum hardware graph. Our experimental results on 27 metabolic networks from Escherichia coli, Homo sapiens, and Mus musculus show that QuTIE yields solutions that are optimal or almost optimal. Our experiments also demonstrate that QuTIE can successfully identify enzyme targets already verified in wet-lab experiments for 14 major disease classes.

Availability and implementation: Code and sample data are available at: https://github.com/ngominhhoang/Quantum-Target-Identification-by-Enzymes.

Figure 1.

Analysis of QuTIE on small datasets. (a–c) Damage values provided by QuTIE and the exact method for the three species E.coli, H.sapiens, and M.musculus, respectively. Each point corresponds to the average of a combination of one network and one k value across all test cases. The diagonal line is the x = y line. (d) Average damage value of QuTIE across all parameters grouped by the number of target compounds. (e) Average damage value of QuTIE across all parameters grouped by the network function. (f) Comparison between QuTIE and the exact method on small datasets in terms of running time.

Figure 2.

Analysis of the IP method and QuTIE. (a–c) Damage values for the three species E.coli, H.sapiens, and M.musculus, respectively. Each point corresponds to the average of a combination of one network and one k value across all test cases. The diagonal line is the x = y line.

Figure 3.

Comparison between QuTIE and the heuristic double iterative method in large datasets in terms of damage. The less damage is, the better solution is. Data points outside the envelope formed by the green dash line, and the blue dash line indicate cases in which QuTIE significantly outperforms the heuristic method.

Figure 4.

Comparison between QuTIE and the SA method on small datasets in terms of their success in finding valid solutions.

Figure 5.

Analysis of the QuTIE in cases of disease-related target compounds in the biosynthesis of amino acids metabolic network. (a) Summary of the number of target compounds related to different disease classes. (b) The correlation between disease classes, and average resulting damage. (c) The correlation between disease classes, and the average number of inhibited enzymes.