Bioinformatics

In mass spectrometry, a peptide, i.e. a sequence of amino acids, is analyzed by splitting multiple copies into prefix and suffix sequences and measuring the masses of these fragments. An important problem is then to reconstruct the sequence of a peptide given only the mass of the peptide itself and the masses of its fragments. This is known as the de novo peptide sequencing problem. More formally, the goal is to reconstruct a sequence S over an alphabet of characters with assigned masses, when the mass of the complete sequence S and the masses of some prefixes and suffixes are given.
In real experiments it is often not possible to isolate and analyze a single peptide. This is, for example, the case if one would like to analyze a mixture of peptides systematically. A new measurement strategy developed in the lab of Prof. Aebersold at ETH Zurich aims to analyze all peptides within a predefined mass range simultaneously. In this case, one wants to reconstruct the sequences of multiple peptides simultaneously given the masses of the peptides and a set of all measured fragment masses (without knowing which fragment mass belongs to which peptide).
The de novo sequencing problems is not only of high practical interest, but also very challenging in the context of algorithmic development. The complexity of many variants of the problem is unknown and especially the de novo sequencing problem for multiple peptides has not been studied in great detail.