Biomaterial Database

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

T Chen, and M Y Kao, and M Tepel, and J Rush, and G M Church

Department of Genetics, Harvard Medical School, Boston, MA 02115, USA.

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.

UI	MeSH Term	Description	Entries
D010047	Ovalbumin	An albumin obtained from the white of eggs. It is a member of the serpin superfamily.	Serpin B14
D000465	Algorithms	A procedure consisting of a sequence of algebraic formulas and/or logical steps to calculate or determine a given task.	Algorithm
D013058	Mass Spectrometry	An analytical method used in determining the identity of a chemical based on its mass using mass analyzers/mass spectrometers.	Mass Spectroscopy,Spectrometry, Mass,Spectroscopy, Mass,Spectrum Analysis, Mass,Analysis, Mass Spectrum,Mass Spectrum Analysis,Analyses, Mass Spectrum,Mass Spectrum Analyses,Spectrum Analyses, Mass
D020539	Sequence Analysis, Protein	A process that includes the determination of AMINO ACID SEQUENCE of a protein (or peptide, oligopeptide or peptide fragment) and the information analysis of the sequence.	Amino Acid Sequence Analysis,Peptide Sequence Analysis,Protein Sequence Analysis,Sequence Determination, Protein,Amino Acid Sequence Analyses,Amino Acid Sequence Determination,Amino Acid Sequence Determinations,Amino Acid Sequencing,Peptide Sequence Determination,Protein Sequencing,Sequence Analyses, Amino Acid,Sequence Analysis, Amino Acid,Sequence Analysis, Peptide,Sequence Determination, Amino Acid,Sequence Determinations, Amino Acid,Acid Sequencing, Amino,Analyses, Peptide Sequence,Analyses, Protein Sequence,Analysis, Peptide Sequence,Analysis, Protein Sequence,Peptide Sequence Analyses,Peptide Sequence Determinations,Protein Sequence Analyses,Protein Sequence Determination,Protein Sequence Determinations,Sequence Analyses, Peptide,Sequence Analyses, Protein,Sequence Determination, Peptide,Sequence Determinations, Peptide,Sequence Determinations, Protein,Sequencing, Amino Acid,Sequencing, Protein