A Suboptimal Algorithm for De Novo Peptide Sequencing via Tandem Mass Spectrometry

peer-reviewed · Journal of Computational Biology · 2003

peer-reviewed · Journal of Computational Biology · 2003. Bingwen Lu et al. Tandem mass spectrometry has emerged to be one of the most powerful high-throughput techniques for protein…
Date 2003-02-01
Type peer-reviewed
Venue Journal of Computational Biology
Publisher SAGE Publications
Contribution algorithm
DOI 10.1089/106652703763255633
Citations (OpenAlex) 83
Venue 2-year citedness 1.54

Abstract

Tandem mass spectrometry has emerged to be one of the most powerful high-throughput techniques for protein identification. Tandem mass spectrometry selects and fragments peptides of interest into N-terminal ions and C-terminal ions, and it measures the mass/charge ratios of these ions. The de novo peptide sequencing problem is to derive the peptide sequences from given tandem mass spectral data of k ion peaks without searching against protein databases. By transforming the spectral data into a matrix spectrum graph G = (V, E), where |V| = O(k(2)) and |E| = O(k(3)), we give the first polynomial time suboptimal algorithm that finds all the suboptimal solutions (peptides) in O(p|E|) time, where p is the number of solutions. The algorithm has been implemented and tested on experimental data. The program is available at http://hto-c.usc.edu:8000/msms/menu/denovo.htm.

Authors

  1. Bingwen Lu · Pfizer (United States), Pfizer Inc., Princeton University, The Scripps Research Institute, University of Southern California
  2. Ting Chen · Harvard University, University of Southern California

Methods and tools

Cites (4)

Cited by (31)

Seen in the charts

Back to the full map

Back to top