Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

The tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged prefix and suffix 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|) space using dynamic programming. Our approach can be further used to discover a modified amino acid in O(|V||E|) time and to analyze data with other types of noise in O(|V||E|) time. Our algorithms have been implemented and tested on actual experimental data.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherSIAM
Pages389-398
Number of pages10
StatePublished - Jan 1 2000
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000

Other

Other11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA
Period1/9/001/11/00

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

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

Cite this