Speeding up tandem mass spectral identification using indexes

Motivation: Tandem mass spectrometry (MS/MS) has been routinely used in proteomics studies. Post-translational modification (PTM) identification is a challenging problem in tandem mass spectral analysis. Results: In this article, we define two scoring functions for identifying peptides/proteins with PTMs from MS/MS spectra: match scores and diagonal scores, as well as two spectral identification problems based on the two scores. We propose several index-based algorithms for the two problems. Both theoretical and experimental analyses show that the index-based algorithms significantly improve on speed when compared with existing algorithms.