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 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 /V/ = 2k + 2, we can solve this problem in O(/V//E/) time and O(/V/2) space using dynamic programming. For an ideal noise-free spectrum with only b- and y-ions, we improve the algorithm to O(/V/ + /E/) time and O(/V/) space. Our approach can be further used to discover a modified amino acid in O(/V//E/) time. The algorithms have been implemented and tested on experimental data.
Chen
T
T
Department of Genetics, Harvard Medical School, Boston, MA 02115, USA.
Kao
M Y
MY
Tepel
M
M
Rush
J
J
Church
G M
GM
D000465:Algorithms; D013058:Mass Spectrometry / Q000379:methods*; D010047:Ovalbumin / Q000032:analysis / Q000737:chemistry; D020539:Sequence Analysis, Protein / Q000379:methods*
D010047:Ovalbumin