A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry

Tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged molecules of prefix and suffix peptide subseq uences and then measures mass/charge ratios of these ions. The de novo pept ide sequencing problem is to reconstruct the peptide sequence from a given tandem mass spectral data of k ions. By implicitly transforming the spectra l data into an NC-spectrum graph G = (V, E) where /V/ = 2k + 2, we can solv e this problem in O (/V/ /E/) time and O (/V/(2)) space using dynamic progr amming. For an ideal noise-free spectrum with only b- and y-ions, we improv e the algorithm to O (/V/ + /E/) time and O (/V/(2)) space. Our approach ca n be further used to discover a modified amino acid in O (/V/ /E/) time. Th e algorithms have been implemented and tested on experimental data.