Computer Science – Computational Complexity
Scientific paper
2011-09-15
Computer Science
Computational Complexity
10 pages, submitted
Scientific paper
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.
Böcker Sebastian
Nicolas Francois
No associations
LandOfFree
Various complexity results for computational mass spectrometry problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Various complexity results for computational mass spectrometry problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Various complexity results for computational mass spectrometry problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-673522