RESEARCH PAPER
Optimization algorithm for de novo analysis of tandem mass spectrometry data

Protein identification is usually achieved by tandem mass spectrometry (MS/MS). Because of the difficulty in

measuring complete proteins using MS/MS, typically a protein is enzymatically digested into peptides and the

MS/MS spectrum of each peptide is measured. The database searching methods are predominant in the task of

peptide identification. Their aim is to find the best match between model spectra generated from the peptides

stored in the database and the experimental mass spectrum obtained for an unidentified peptide. In this approach

one assumes that the peptide under investigation belongs to the scanned database. Otherwise, so called de novo

methods have to be applied to determine the peptide sequence. Unfortunately, de novo sequencing algorithms

are fragile in the presence of missing peaks, background noise or post-translational protein modifications. In this

paper, we propose a post-processing method for optimizing the results obtained from de novo sequencing

algorithms. Our approach in the reconstruction of amino acid sequences employs only spectral features and is

robust with respect to missing data. We demonstrate the significant improvement achieved using our method

applied to sequences reconstructed using a popular de novo sequencing method. The tool is freely available at

http://pepygen. sourceforge.net.