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

Ting Chen, Matthew Tepel, John Rush, George M. Church, Ming Yang Kao

Research output: Contribution to journalArticlepeer-review

190 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)325-337
Number of pages13
JournalJournal of Computational Biology
Volume8
Issue number3
DOIs
StatePublished - Aug 2001

Keywords

  • Computational biology
  • Dynamic programming
  • Mass spectrometry, computational proteomics
  • Peptide sequencing
  • Protein identification

ASJC Scopus subject areas

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry'. Together they form a unique fingerprint.

Cite this