Li-An Tsai, Estelle Nuckels, Yingfeng Wang

Proceedings of the 14th International Multi-Conference on Complexity, Informatics and Cybernetics: IMCIC 2023, pp. 84-87 (2023); https://doi.org/10.54808/IMCIC2023.01.84

Li-An Tsai
School of Literature, Media, and Communication, Georgia Institute of Technology, Atlanta, Georgia, United States

Estelle Nuckels
Department of Natural Sciences, Middle Georgia State University, Macon, Georgia, United States

Yingfeng Wang
Department of Computer Science and Engineering, University of Tennessee at Chattanooga, Chattanooga, Tennessee, United States

Cite this paper as:
Tsai, L., Nuckels, E., Wang, Y. (2023). Integrating Quantum Computing into De Novo Metabolite Identification. In N. Callaos, S. Hashimoto, N. Lace, B. Sánchez, M. Savoie (Eds.), Proceedings of the 14th International Multi-Conference on Complexity, Informatics and Cybernetics: IMCIC 2023, pp. 84-87. International Institute of Informatics and Cybernetics. https://doi.org/10.54808/IMCIC2023.01.84

Tandem mass spectrometry (MS/MS) is a widely used technology for identifying metabolites. De novo metabolite identification is an identification strategy that does not refer to any spectral or metabolite database. However, this strategy is time-consuming and cannot meet the need for high-throughput metabolite identification. Böcker et al. converted the de novo identification problem into the maximum colorful subtree (MCS) problem. Unfortunately, the MCS problem is NP-hard, which indicates there are no existing efficient exact algorithms. To address this issue, we propose to apply quantum computing to accelerate metabolite identification. Quantum computing performs computations on quantum computers. The recent progress in this area has brought the hope of making some computationally intractable areas trackable, although there are still no general approaches to converting regular computer algorithms into quantum algorithms. Specifically, there is no efficient quantum algorithm for the MCS problem. This study explores the feasibility of integrating quantum computing into de novo metabolite identification. The MCS problem can be considered as the combination of many maximum spanning tree problems that can be converted into minimum spanning tree problems. This work applies a quantum algorithm designed for the minimum spanning problem to speed up de novo metabolite identification.
Applying quantum computing to solve bioinformatics problems is challenging. It requires knowledge of several areas, such as computer science, quantum computing, and biology. However, conducting this type of research will help students build an interdisciplinary mindset. Therefore, we attempt to design an undergraduate research project for applying quantum computing to identify metabolites without referring to any database. This project provides opportunities for undergraduate students to learn computer programing, algorithm design, quantum computing, quantum algorithm design, and de novo metabolite identification. After students are familiar with these areas, they are guided to identify the potential ways of solving the identification problem by converting problems and searching literature. Böcker et al. have converted the original identification problem into the maximum spanning tree problem. While there is no existing quantum algorithm for the maximum spanning tree problem, there is an existing quantum algorithm for the minimum spanning tree problem. Students find a simple way to convert the maximum spanning tree problem into the minimum spanning tree problem. Carrying out this project does not only provide the path for further accelerating de novo metabolite identification by using quantum computing, but also assists in gaining experience in boosting undergraduate interdisciplinary research.