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)	251
Venue 2-year citedness	1.54

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.

Authors

Methods and tools

DP-based de novo peptide sequencing: Dynamic-programming formulation over an NC-spectrum graph for de novo peptide sequencing.

Cites (3)

Cited by (79)

PepGo: a deep learning and tree search-based model for de novo peptide sequencing (2025) crossref
De Novo Sequencing of Peptides from Tandem Mass Spectra and Applications in Proteogenomics (2024) 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
Current state, existing challenges, and promising progress for de novo sequencing and assembly of monoclonal antibodies (2022) both
The impact of noise and missing fragmentation cleavages on de novo peptide identification algorithms (2022) both
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
Improved de novo peptide sequencing using LC retention time information (2018) both
De novo peptide sequencing by deep learning (2017) crossref
CycloAnt (2017) crossref
A better scoring model for de novo peptide sequencing: the symmetric difference between explained and measured masses (2017) both
Evaluating de novo sequencing in proteomics: already an accurate alternative to database-driven peptide identification? (2017) crossref
Ultrahigh‐resolution Fourier transform ion cyclotron resonance mass spectrometry and tandem mass spectrometry for peptide de novo amino acid sequencing for a seven‐protein mixture by paired single‐residue transposed Lys‐N and Lys‐C digestion (2017) crossref
Open-pNovo: De Novo Peptide Sequencing with Thousands of Protein Modifications (2017) crossref
Tandem Mass Spectrum Sequencing: An Alternative to Database Search Engines in Shotgun Proteomics (2016) crossref
De novo Peptide Sequencing (2016) crossref
Peptide de novo sequencing of mixture tandem mass spectra (2016) both
Novel Antifungal Peptides Produced by Leuconostoc mesenteroides DU15 Effectively Inhibit Growth of Aspergillus niger (2015) crossref
A New Parameterized Algorithm for Rapid Peptide Sequencing (2014) both
UniNovo: a universal tool for de novo peptide sequencing (2013) both
DE NOVO SEQUENCING WITH LIMITED NUMBER OF POST-TRANSLATIONAL MODIFICATIONS PER PEPTIDE (2013) crossref
pNovo+: De Novo Peptide Sequencing Using Complementary HCD and ETD Tandem Mass Spectra (2013) crossref
Tutorial on de novo peptide sequencing using MS/MS mass spectrometry (2012) crossref
Constrained De Novo Sequencing of Conotoxins (2012) both
De Novo Peptide Sequencing Based on Vertex Contraction Algorithm (2012) crossref
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
ProbPS: A new model for peak selection based on quantifying the dependence of the existence of derivative peaks on primary ion intensity (2011) both
Constrained De Novo Sequencing of Peptides with Application to Conotoxins (2011) crossref
Metaheuristics based de novo protein sequencing: A new approach (2011) crossref
EigenMS: De Novo Analysis of Peptide Tandem Mass Spectra by Spectral Graph Partitioning (2010) 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
An Automata Approach to Match Gapped Sequence Tags Against Protein Database (2010) crossref
Better score function for peptide identification with ETD MS/MS spectra (2010) both
De Novo Sequencing Methods in Proteomics (2009) crossref
De novo peptide sequencing by tandem MS using complementary CID and electron transfer dissociation (2009) crossref
Automated protein (re)sequencing with MS/MS and a homologous database yields almost full coverage and accuracy (2009) crossref
Spectrum Fusion: Using Multiple Mass Spectra for De Novo Peptide Sequencing (2009) crossref
Spectral Dictionaries: Integrating de novo Peptide Sequencing with Database Search of Tandem Mass Spectra (2009) both
Unrestrictive Identification of Multiple Post-translational Modifications from Tandem Mass Spectrometry Using an Error-tolerant Algorithm Based on an Extended Sequence Tag Approach (2008) both
Multi-spectra peptide sequencing and its applications to multistage mass spectrometry (2008) both
Peptide De Novo Sequencing with MS/MS (2008) crossref
ON PREPROCESSING AND ANTISYMMETRY IN DE NOVO PEPTIDE SEQUENCING: IMPROVING EFFICIENCY AND ACCURACY (2008) crossref
A Dynamic Programming Algorithm for De Novo Peptide Sequencing with Variable Scoring (2008) crossref
De Novo Sequencing of Nonribosomal Peptides (2008) crossref
De novo peptide identification via mixed-integer linear optimization and tandem mass spectrometry (2008) crossref
A workflow to increase the detection rate of proteins from unsequenced organisms in high‐throughput proteomics experiments (2007) crossref
Shotgun Protein Sequencing: Assembly of Peptide Tandem Mass Spectra from Mixtures of Modified Proteins (2007) both
MSNovo: A Dynamic Programming Algorithm for de Novo Peptide Sequencing via Tandem Mass Spectrometry (2007) crossref
Protein identification by spectral networks analysis (2007) crossref
A mixed-integer optimization framework for de novo peptide identification (2007) crossref
Mass spectrometric genomic data mining: Novel insights into bioenergetic pathways in Chlamydomonas reinhardtii (2006) crossref
Performance Evaluation of Existing De Novo Sequencing Algorithms (2006) crossref
De novo peptide sequencing using exhaustive enumeration of peptide composition (2006) crossref
MODi : a powerful and convenient web server for identifying multiple post-translational peptide modifications from tandem mass spectra (2006) semanticscholar
De Novo Analysis of Peptide Tandem Mass Spectra by Spectral Graph Partitioning (2006) crossref
PRIME: A Mass Spectrum Data Mining Tool for De Nova Sequencing and PTMs Identification (2005) crossref
InsPecT: Identification of Posttranslationally Modified Peptides from Tandem Mass Spectra (2005) 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
AN AUTOMATA APPROACH TO MATCH GAPPED SEQUENCE TAGS AGAINST PROTEIN DATABASE (2005) crossref
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
An algorithm for interpretation of low‐energy collision‐induced dissociation product ion spectra for de novo sequencing of peptides (2005) crossref
A graph-theoretic approach for the separation of b and y ions in tandem mass spectra (2005) crossref
Shotgun Protein Sequencing by Tandem Mass Spectra Assembly (2004) crossref
Probability profile method - new approach to data analysis in tandem mass spectrometry (2004) crossref
Probability profiles-novel approach in tandem mass spectrometry De Novo sequencing (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
An Effective Algorithm for the Peptide De Novo Sequencing from MS/MS Spectrum (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

Seen in the charts

Back to the full map