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

18 Citations (Scopus)

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

Fingerprint

Mass Spectrometry
Dynamic programming
Peptides
Sequencing
Mass spectrometry
Dynamic Programming
Graph Spectra
Suffix
Ions
Prefix
Subsequence
Amino Acids
Amino acids
Fragment
Charge
Molecules
Experimental Data

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Chen, T., Kao, M. Y., Tepel, M., Rush, J., & Church, G. M. (2000). Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 389-398). SIAM.
Chen, Ting ; Kao, Ming Yang ; Tepel, Matthew ; Rush, John ; Church, George M. / Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2000. pp. 389-398
@inproceedings{c9f5664f66e24d20996094df441d2747,
title = "Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry",
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.",
author = "Ting Chen and Kao, {Ming Yang} and Matthew Tepel and John Rush and Church, {George M.}",
year = "2000",
month = "1",
day = "1",
language = "English (US)",
pages = "389--398",
booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "SIAM",

}

Chen, T, Kao, MY, Tepel, M, Rush, J & Church, GM 2000, Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, pp. 389-398, 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 1/9/00.

Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. / Chen, Ting; Kao, Ming Yang; Tepel, Matthew; Rush, John; Church, George M.

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2000. p. 389-398.

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

TY - GEN

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

AU - Chen, Ting

AU - Kao, Ming Yang

AU - Tepel, Matthew

AU - Rush, John

AU - Church, George M.

PY - 2000/1/1

Y1 - 2000/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0033881719&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033881719&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0033881719

SP - 389

EP - 398

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

PB - SIAM

ER -

Chen T, Kao MY, Tepel M, Rush J, Church GM. Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 2000. p. 389-398