Various complexity results for computational mass spectrometry problems

Define Minimum Soapy Union (MinSU) as the following optimization problem: given a $k$-tuple $(X_1, X_2,..., X_k)$ of finite integer sets, find a $k$-tuple $(t_1, t_2,..., t_k)$ of integers that minimizes the cardinality of $(X_1 + t_1) \cup (X_2 + t_2) \cup ... \cup (X_n + t_k)$. We show that MinSU is NP-complete, APX-hard, and polynomial for fixed $k$. MinSU appears naturally in the context of protein shotgun sequencing: Here, the protein is cleaved into short and overlapping peptides, which are then analyzed by tandem mass spectrometry. To improve the quality of such spectra, one then asks for the mass of the unknown prefix (the shift) of the spectrum, such that the resulting shifted spectra show a maximum agreement. For real-world data the problem is even more complicated than our definition of MinSU; but our intractability results clearly indicate that it is unlikely to find a polynomial time algorithm for shotgun protein sequencing.