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

Abstract

1 Dynamic Programming Approach to Peptide Sequencing 2 Tandem mass spectrometry fragments a large number of molecules of the same pep-tide sequence into charged molecules of prex and suÆx peptide subsequences, and then measures mass/charge ratios of these ions. The de novo peptide sequencing problem is to reconstruct the peptide sequence from a given tandem mass spectral data of k ions. By implicitly transforming the spectral data into an NC-spectrum graph G = (V;E) where jV j = 2k+2, we can solve this problem in O(jV jjEj) time and O(jV j 2) space using dynamic programming. For an ideal noise-free spectrum with only b- and y-ions, we improve the algorithm to O(jV j + jEj) time and O(jV j) space. Our approach can be further used to discover a modied amino acid in O(jV jjEj) time. The algorithms have been implemented and tested on experimental data. Dynamic Programming Approach to Peptide Sequencing 3 1