On de novo interpretation of tandem mass spectra for peptide identification

ABSTRACT

The correct interpretation of tandem mass spectra is a difficult problem, even when it is limited to scoring peptides against a database. De novo sequencing is considerably harder, but critical when sequence databases are incomplete or not available. In this paper we build upon earlier work due to Dancik et al., and Chen et al. to provide a dynamic programming algorithm for interpreting de novo spectra. Our method can handle most of the commonly occurring ions, including a; b; y, and their neutral losses. Additionally, we shift the emphasis away from sequencing to assigning ion types to peaks. In particular, we introduce the notion of core interpretations, which allow us to give confidence values to individual peak assignments, even in the absence of a strong interpretation. Finally, we introduce a systematic approach to evaluating de novo algorithms as a function of spectral quality. We show that our algorithm, in particular the core-interpretation, is robust in the presence of measurement error, and low fragmentation probability.

REFERENCES

• 1: V. Bafna and N. Edwards. SCOPE: a probabilistic model for scoring tandem mass spectra against a peptide database. Bioinformatics, 17 Suppl 1:S13--21, June 2001. Appeared in Intl. Conference on Intelligent Systems for Molecular Biology.
• 2: C. Bartels. Fast algorithm for peptide sequencing by mass spectrometry. Biomedical and Environmental Mass Spectrometry, 19:363--368, 1990.
• 3: T. Chen, M. Y. Kao, M. Tepel, J. Rush, and G.M. Church. A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. Journal of Computational Biology, 8(6):571--83, 2001.
• 4: V. Dancik, T. Addona, K. Clauser, J. Vath, and P.A. Pevzner. De novo peptide sequencing via tandem mass spectrometry. Journal of Computational Biology, 6:327--342, 1999.
• 5: J. Fernandez de Cossio, J. Gonzales, and V. Besada. Protein identification using mass spectrometric information. Comput. Appl. Biosci., 11:427--434, 1995.
• 6: J. Eng, A. McCormack, and J. Yates. An approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database. Journal of American Society of Mass Spectrometry, 5:976--989, 1994.
• 7: D. Fenyo, J. Qin, and B.T. Chait. Protein identification using mass spectrometric information. Electrophoresis, 19(6):998--1005, 1998.
• 8: R.J. Johnson and K. Biemann. Computer program (seqpep) to aid in the interpretation of high-energy collision tandem mass spectra of peptides. Biomedical and Environmental Mass Spectrometry, 18:945--957, 1989.
• 9: D.J. Lipman and W.R. Pearson. Rapid and sensitive protein similarity searches. Science, 227:1435--1441, 1985.
• 10: M. Mann and M. Wilm. Error-tolerant identification of peptides in sequence databases by peptide sequence tags. Analytical Chemistry, 66:4390--4399, 1994.
• 11: P. A. Pevzner. Computational Molecular Biology: An Algorithmic Approach. MIT Press, 2000.
• 12: Pavel A. Pevzner , Vlado Dančík , Chris L. Tang, Mutation-tolerant protein identification by mass-spectrometry, Proceedings of the fourth annual international conference on Computational molecular biology, p.231-236, April 2000, Tokyo, Japan [doi>10.1145/332306.332560]
• 13: J.A. Taylor and R.S. Johnson. Sequence database searches via de novo peptide sequencing by mass spectrometry. Rapid Communications in Mass Spectrometry, 11:1067--1075, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

General Terms:
Algorithms, Experimentation, Theory

Keywords:
de novo interpretation, proteomics, tandem mass spectrometry