A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry
peer-reviewed · Journal of Computational Biology · 2001
peer-reviewed · Journal of Computational Biology · 2001. Ting Chen et al. Tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged…
| Date | 2001-06-01 |
| Type | peer-reviewed |
| Venue | Journal of Computational Biology |
| Publisher | SAGE Publications |
| Contribution | algorithm |
| DOI | 10.1089/10665270152530872 |
| Citations (OpenAlex) | 252 |
| Venue 2-year citedness | 1.45 |
Abstract
Tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged molecules of prefix and suffix peptide 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/2) space using dynamic programming. For an ideal noise-free spectrum with only b- and y-ions, we improve the algorithm to O(/V/ + /E/) time and O(/V/) space. Our approach can be further used to discover a modified amino acid in O(/V//E/) time. The algorithms have been implemented and tested on experimental data.
Methods and tools
- DP-based de novo peptide sequencing: Dynamic-programming formulation over an NC-spectrum graph for de novo peptide sequencing.
Cites (2)
Cited by (36)
- PepGo: a deep learning and tree search-based model for de novo peptide sequencing (2025) crossref
- Mitigating the missing-fragmentation problem in de novo peptide sequencing with a two-stage graph-based deep learning model (2023) both
- Algorithms for de-novo sequencing of peptides by tandem mass spectrometry: A review (2023) crossref
- DPST: De Novo Peptide Sequencing with Amino-Acid-Aware Transformers (2022) semanticscholar
- Spectrum graph-based de-novo sequencing algorithm MaxNovo achieves high peptide identification rates in collisional dissociation MS/MS spectra (2021) both
- Computationally instrument-resolution-independent de novo peptide sequencing for high-resolution devices (2021) crossref
- A potential golden age to come—current tools, recent use cases, and future avenues for de novo sequencing in proteomics (2018) crossref
- De novo peptide sequencing by deep learning (2017) crossref
- Evaluating de novo sequencing in proteomics: already an accurate alternative to database-driven peptide identification? (2017) crossref
- Open-pNovo: De Novo Peptide Sequencing with Thousands of Protein Modifications (2017) crossref
- Peptide de novo sequencing of mixture tandem mass spectra (2016) both
- UniNovo: a universal tool for de novo peptide sequencing (2013) both
- pNovo+: De Novo Peptide Sequencing Using Complementary HCD and ETD Tandem Mass Spectra (2013) crossref
- Constrained De Novo Sequencing of Conotoxins (2012) both
- Antilope—A Lagrangian Relaxation Approach to the de novo Peptide Sequencing Problem (2012) both
- De Novo Sequencing and Homology Searching (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
- Spectral Dictionaries: Integrating de novo Peptide Sequencing with Database Search of Tandem Mass Spectra (2009) both
- MSNovo: A Dynamic Programming Algorithm for de Novo Peptide Sequencing via Tandem Mass Spectrometry (2007) crossref
- A mixed-integer optimization framework for de novo peptide identification (2007) crossref
- Performance Evaluation of Existing De Novo Sequencing Algorithms (2006) crossref
- De novo peptide sequencing using exhaustive enumeration of peptide composition (2006) 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
- An effective algorithm for peptide de novo sequencing from MS/MS spectra (2005) both
- Shotgun Protein Sequencing by Tandem Mass Spectra Assembly (2004) crossref
- Algorithms for de novo peptide sequencing using tandem mass spectrometry (2004) crossref
- “De novo” peptide sequencing by MALDI-quadrupole-ion trap mass spectrometry: A preliminary study (2003) crossref
- PEAKS: powerful software for peptide de novo sequencing by tandem mass spectrometry (2003) crossref
- A Suboptimal Algorithm for De Novo Peptide Sequencing via Tandem Mass Spectrometry (2003) crossref
- New computational approaches for de novo peptide sequencing from MS/MS experiments (2002) crossref
- De novo sequencing of peptides using MALDI/TOF-TOF (2002) both