  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 an NP-complete problem, and thus
optimal solutions using classical computers fail to scale to large metabolic
networks. In this paper, we consider the TIE problem for identifying drug
targets in metabolic networks. We develop the first quantum optimization
solution, called QuTIE (Quantum optimization for Target Identification by
Enzymes), to this NP-complete problem. We do that by developing an equivalent
formulation of the TIE problem in Quadratic Unconstrained Binary Optimization
(QUBO) form, then mapping it to a logical graph, which is then embedded on a
hardware graph on a quantum computer. Our experimental results on 27 metabolic
networks from Escherichia coli, Homo sapiens, and Mus musculus show that QuTIE
yields solutions which 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.
