A Suboptimal Algorithm for De Novo Peptide Sequencing via Tandem Mass Spectrometry
peer-reviewed · Journal of Computational Biology · 2003
| Date | 2003-02-01 |
| Type | peer-reviewed |
| Venue | Journal of Computational Biology |
| Publisher | SAGE Publications |
| Contribution | algorithm |
| DOI | 10.1089/106652703763255633 |
| Citations (OpenAlex) | 82 |
| Venue 2-year citedness | 1.45 |
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.
Methods and tools
- Suboptimal de novo peptide sequencing: Suboptimal-path algorithm for reporting multiple candidate de novo peptide sequences.
Cites (3)
Cited by (15)
- De novo sequencing of proteins by mass spectrometry (2020) both
- NIPTL-Novo: Non-isobaric peptide termini labeling assisted peptide de novo sequencing (2017) crossref
- Peptide de novo sequencing of mixture tandem mass spectra (2016) both
- pNovo+: De Novo Peptide Sequencing Using Complementary HCD and ETD Tandem Mass Spectra (2013) crossref
- Mass spectrometry-based protein identification by integrating de novo sequencing with database searching (2013) both
- Antilope—A Lagrangian Relaxation Approach to the de novo Peptide Sequencing Problem (2012) both
- Algorithms for the de novo sequencing of peptides from tandem mass spectra (2011) crossref
- pNovo: De novo Peptide Sequencing and Identification Using HCD Spectra (2010) crossref
- A high-throughput de novo sequencing approach for shotgun proteomics using high-resolution tandem mass spectrometry (2010) both
- De novo peptide sequencing by tandem MS using complementary CID and electron transfer dissociation (2009) crossref
- A mixed-integer optimization framework for de novo peptide identification (2007) crossref
- De Novo Analysis of Peptide Tandem Mass Spectra by Spectral Graph Partitioning (2006) crossref
- DeNovoID: a web-based tool for identifying peptides from sequence and mass tags deduced from de novo peptide sequencing by mass spectroscopy (2005) semanticscholar
- SPIDER: software for protein identification from sequence tags with de novo sequencing error (2005) crossref
- Algorithms for de novo peptide sequencing using tandem mass spectrometry (2004) crossref