Integrating Quantum Computing into De Novo Metabolite Identification
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
International Institute of Informatics and Cybernetics
2023-04-01
|
| Series: | Journal of Systemics, Cybernetics and Informatics |
| Subjects: | |
| Online Access: | http://www.iiisci.org/Journal/PDV/sci/pdfs/ZA381UC23.pdf
|
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849713923462266880 |
|---|---|
| author | Li-An Tsai Estelle Nuckels Yingfeng Wang |
| author_facet | Li-An Tsai Estelle Nuckels Yingfeng Wang |
| author_sort | Li-An Tsai |
| collection | DOAJ |
| description | 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 NPhard, 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. 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. The possible strategy for further improving the performance is also briefly discussed. |
| format | Article |
| id | doaj-art-09942dbecc3040a2a13e9b6dd61a73f3 |
| institution | DOAJ |
| issn | 1690-4524 |
| language | English |
| publishDate | 2023-04-01 |
| publisher | International Institute of Informatics and Cybernetics |
| record_format | Article |
| series | Journal of Systemics, Cybernetics and Informatics |
| spelling | doaj-art-09942dbecc3040a2a13e9b6dd61a73f32025-08-20T03:13:50ZengInternational Institute of Informatics and CyberneticsJournal of Systemics, Cybernetics and Informatics1690-45242023-04-012128386Integrating Quantum Computing into De Novo Metabolite IdentificationLi-An TsaiEstelle NuckelsYingfeng WangTandem 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 NPhard, 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. 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. The possible strategy for further improving the performance is also briefly discussed.http://www.iiisci.org/Journal/PDV/sci/pdfs/ZA381UC23.pdf undergraduate researchalgorithm designtandem mass spectrometrymetabolite identificationquantum computing |
| spellingShingle | Li-An Tsai Estelle Nuckels Yingfeng Wang Integrating Quantum Computing into De Novo Metabolite Identification Journal of Systemics, Cybernetics and Informatics undergraduate research algorithm design tandem mass spectrometry metabolite identification quantum computing |
| title | Integrating Quantum Computing into De Novo Metabolite Identification |
| title_full | Integrating Quantum Computing into De Novo Metabolite Identification |
| title_fullStr | Integrating Quantum Computing into De Novo Metabolite Identification |
| title_full_unstemmed | Integrating Quantum Computing into De Novo Metabolite Identification |
| title_short | Integrating Quantum Computing into De Novo Metabolite Identification |
| title_sort | integrating quantum computing into de novo metabolite identification |
| topic | undergraduate research algorithm design tandem mass spectrometry metabolite identification quantum computing |
| url | http://www.iiisci.org/Journal/PDV/sci/pdfs/ZA381UC23.pdf
|
| work_keys_str_mv | AT liantsai integratingquantumcomputingintodenovometaboliteidentification AT estellenuckels integratingquantumcomputingintodenovometaboliteidentification AT yingfengwang integratingquantumcomputingintodenovometaboliteidentification |