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

Marcin Borowski; Karolina Baumgard

doi:10.2478/fcds-2025-0007

.blurhash-client-img { display: none !important; }

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

Foundations of Computing and Decision Sciences

Volume 50 (2025): Issue 2 (June 2025)

By: Marcin Borowski and Karolina Baumgard

Open Access

|Jun 2025

Abstract

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.

References

Achterberg T., Scip: Solving constraint integer programs. Mathematical Programming Computation, 1(1):1–41, July 2009.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Blazewicz J., Hammer P.L., Lukasiak P., Predicting secondary structures of proteins, IEEE Engineering in Medicine and Biology, 24, pp.88-94, 2005.
Search in Google Scholar Back to article
Bocker S., Liptak Z.. A Fast and Simple Algorithm for the Money Changing Problem. Algorithmica, 48(4):413–432, 2007.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Borowski M., 2011, Models and algorithms for peptide sequence identification, Wydawnictwo NAKOM, Poznan Monographs in Computing and Its Applications (Edition 1, Volume 14), 2011.
Search in Google Scholar Back to article
DiMaggio P.A., Floudas C.A., De Novo Peptide Identification via Tandem Mass Spectrometry and Integer Linear Optimization, Analytical Chemistry, 2007
Search in Google Scholar Back to article
Gross J.H.. Mass Spectrometry. Springer Berlin Heidelberg, 2011.
Search in Google Scholar Back to article
Hong Y., Li S., Ye Y., Tang H., FIDDLE: a deep learning method for chemical formulas prediction from tandem mass spectra, bioRxiv, 2024
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Kuehl D., Wang Y., The role of spectral accuracy in mass spectrometry, Spectroscopy Supplements Special Issues 04/01, 2007.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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
Search in Google Scholar Back to article
McNaught A. D., Wilkinson A. IUPAC. Compendium of Chemical Terminology, 2nd ed. (the “Gold Book”). Blackwell Scientific Publications, Oxford, 1997.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Neumann, Steen, Anton Pervukhin and Sebastian Böcker, Mass decomposition with the Rdisop package, Chemistry, Physics, 2006, 2008, 2009.
Search in Google Scholar Back to article
Patiny L., Borel A.. ChemCalc: a building block for tomorrow’s chemical infrastructure. J Chem Inf Model, 53(5):1223–1228, May 2013.
Search in Google Scholar Back to article
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
Search in Google Scholar Back to article
Remes et al., The Role of Spectral Accuracy in Mass Spectrometry, Chromatography Online, 2007.
Search in Google Scholar Back to article
Silberring J., Kraj A., Drabik A. Proteomika i metabolomika. Wydawnictwo Uniwersytetu Warszawskiego, Warszawa, 2010.
Search in Google Scholar Back to article
Silberring J., Kraj A. Proteomika. Wydział Chemii Uniwersytetu Jagiellońskiego, Kraków, 2004.
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/fcds-2025-0007 | Journal eISSN: 2300-3405 | Journal ISSN: 0867-6356

Journal RSS Feed

Language: English

Page range: 191 - 206

Submitted on: May 6, 2025

Accepted on: May 26, 2025

Published on: Jun 10, 2025

Published by: Poznan University of Technology

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

scip,

tabu search,

mass spectrometry,

spectra identification

Related subjects:

Computer sciences,

Artificial intelligence,

Software development

© 2025 Marcin Borowski, Karolina Baumgard, published by Poznan University of Technology
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 50 (2025): Issue 2 (June 2025)