Algorithm for Determining the Sum Formula of Metabolites from Mass Spectrometry Spectra

• Autorzy: Borowski Marcin , Baumgard Karolina

Identyfikatory

DOI

10.2478/fcds-2025-0007

• Języki publikacji: EN

Abstrakty

EN

This work addresses the challenge of determining chemical sum formulas from mass spectrometry data through a three-fold approach: establishing a formal problem framework, analyzing its computational complexity, and developing an approximate algorithm that synergizes reference database integration with functional group property analysis to enable accurate compound identification and structural characterization. By bridging theoretical foundations in computational complexity with practical solutions for chemical structure elucidation, the proposed methodology advances analytical capabilities in mass spectrometry data interpretation.

Słowa kluczowe

EN

scip; tabu search; mass spectrometry; spectra identification

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2025
• Tom: Vol. 50, No. 2
• Strony: 191--206
• Opis fizyczny: Bibliogr. 22 poz., rys., tab.

Twórcy

autor

Borowski Marcin

• Institute of Computing Science, Poznan University of Technology, Poznań

autor

Baumgard Karolina

• Institute of Computing Science, Poznan University of Technology, Poznań

Bibliografia

• [1] Achterberg T. Scip: Solving constraint integer programs. Mathematical Programming Computation, 1(1): 1-41, July 2009.
• [2] Achterberg T., Berthold T., Koch T., Wolter K. Constraint integer programming: A new approach to integrate CP and MIP. Lecture Notes in Computer Science, 5015: 6-20, 2008.
• [3] Blazewicz J., Hammer P.L., Lukasiak P. Predicting secondary structures of proteins, IEEE Engineering in Medicine and Biology, 24, pp. 88-94, 2005.
• [4] Bocker S., Liptak Z. A Fast and Simple Algorithm for the Money Changing Problem. Algorithmica, 48(4): 413-432, 2007.
• [5] Bocker S., Liptak Z., Martin M., Pervukhin A., Sudek H. DECOMP-from interpreting Mass Spectrometry peaks to solving the Money Changing Problem. Bioinformatics, 24(4): 591-593, Feb 2008.
• [6] Borowski M. 2011, Models and algorithms for peptide sequence identification, Wydawnictwo NAKOM, Poznan Monographs in Computing and Its Applications (Edition 1, Volume 14), 2011.
• [7] DiMaggio P. A. Floudas C.A., De Novo Peptide Identification via Tandem Mass Spectrometry and Integer Linear Optimization, Analytical Chemistry, 2007
• [8] Gross J. H. Mass Spectrometry. Springer Berlin Heidelberg, 2011.
• [9] Hong Y., Li S., Ye Y., Tang H. FIDDLE: a deep learning method for chemical formulas prediction from tandem mass spectra, bioRxiv, 2024
• [10] Kind T., Fiehn O. Metabolomic database annotations via query of elemental compositions. Mass accuracy is insufficient even at less than 1 ppm. BMC Bioinformatics, 7(1), 2006, 1-10.
• [11] Kuehl D., Wang Y. The role of spectral accuracy in mass spectrometry, Spectroscopy Supplements Special Issues 04/01, 2007.
• [12] Lukasiak P., Blazewicz J., Milostan M. Some operations research methods for analyzing protein sequences and structures, Annals of Operations Research, 175, pp. 9-35, 2010.
• [13] Marczak Ł., Znajdek-Awiżeń P., Bylka W. The use of mass spectrometric techniques to differentiate isobaric and isomeric flavonoid conjugates from axyris amaranthoides. Molecules, 2016, 21(9): 1229.
• [14] Marczak L., Idkowiak J., Tracz J., Stobiecki M., Perek B., Kostka-Jeziorny K., Tykarski A., Wanic-Kossowska M., Borowski M., Osuch M., Formanowicz D. and Luczak M. Mass Spectrometry-Based Lipidomics Reveals Differential Changes in the Accumulated Lipid Classes in Chronic Kidney Disease, Metabolites, 11(5): 275, April 2021, DOI: 10.3390/metabo11050275
• [15] McNaught A. D., Wilkinson A. IUPAC. Compendium of Chemical Terminology, 2nd ed. (the “Gold Book”). Blackwell Scientific Publications, Oxford, 1997.
• [16] Meringer M., Reinker S., Zhang J., Muller A. MS/MS Data Improves Automated Determination Molecular Formulas by Mass Spectrometry. MATCH Communications in Mathematical and Computer Chemistry, 65(2): 259-290, June 2011.
• [17] Neumann, Steen, Anton Pervukhin and Sebastian Böcker, Mass decomposition with the Rdisop package, Chemistry, Physics, 2006, 2008, 2009.
• [18] Patiny L., Borel A.. ChemCalc: a building block for tomorrow’s chemical infrastructure. J Chem Inf Model, 53(5): 1223-1228, May 2013.
• [19] Pluskal t., Uehara T., Yanagida M., Highly Accurate Chemical Formula Prediction Tool Utilizing High-Resolution Mass Spectra, MS/MS Fragmentation, Heuristic Rules, and Isotope Pattern Matching, Analytical Chemistry, 2012
• [20] Remes et al. The Role of Spectral Accuracy in Mass Spectrometry, Chromatography Online, 2007.
• [21] Silberring J., Kraj A. Drabik A. Proteomika i metabolomika. Wydawnictwo Uniwersytetu Warszawskiego, Warszawa, 2010.
• [22] Silberring J., Kraj A. Proteomika. Wydział Chemii Uniwersytetu Jagiellońskiego, Kraków, 2004.