Vol 3 No 2 (2008)
Articles

A Combinatorial Optimization Approach for Determining Composition and Sequence of Polymers

Renato Bruni
Department of Electronic and Information Engineering, University of Perugia, Via G. Duranti, 93 - 06125 Perugia - Italy.
How to Cite
Bruni, R. (1). A Combinatorial Optimization Approach for Determining Composition and Sequence of Polymers. Algorithmic Operations Research, 3(2). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/9705

Abstract

Polymers are compounds formed by the joining of smaller, often repeating, units linked by covalent bonds. The analysis of their structure is a fundamental issue in a number of fields. This work gives an exact mathematical formalization of the problems of determining the composition or the sequence of polymers by processing data obtained from their tandem mass spectrometry analysis and describes effective solution algorithms for such problems. The procedure is exemplified by considering the case of peptides, but may be used for generic polymeric compounds submitted to mass spectrometry. The analysis does not rely on databases, but on computation of solutions compatible with the given spectral data. Note that the proposed approach guarantees finding all the above solutions, while other known methods cannot give this guarantee. Both the computational running times and the biological accuracy of the experimental analyses are encouraging.