title: A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry.
abstract: 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.
authors.affiliation: Department of Genetics, Harvard Medical School, Boston, MA 02115, USA.
authors.forename: T
authors.initials: T
authors.lastname: Chen
authors.forename: M Y
authors.initials: MY
authors.lastname: Kao
authors.forename: M
authors.initials: M
authors.lastname: Tepel
authors.forename: J
authors.initials: J
authors.lastname: Rush
authors.forename: G M
authors.initials: GM
authors.lastname: Church
mesh_terms: D000465:Algorithms; D013058:Mass Spectrometry / Q000379:methods*; D010047:Ovalbumin / Q000032:analysis / Q000737:chemistry; D020539:Sequence Analysis, Protein / Q000379:methods*
chemical_list: D010047:Ovalbumin