A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry

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.

• Publication year

  2000

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2000-02-01

• Fields of study

  Physics, Chemistry, Computer Science, Mathematics, Medicine

• Identifiers
  DOI 10.1089/10665270152530872arXiv cs/0101016PMID 11535179
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• New computational approaches for de novo peptide sequencing from MS/MS experiments

  2002cited by this paper
• Algorithms for Identifying Protein Cross-Links via Tandem Mass Spectrometry

  2001cited by this paper
• De Novo Peptide Sequencing via Tandem Mass Spectrometry

  1999cited by this paper
• Biomolecule Mass Spectrometry

  1999cited by this paper
• Role of accurate mass measurement (+/- 10 ppm) in protein identification strategies employing MS or MS/MS and database searching.

  1999cited by this paper
• Binding of RHOA G17V to p300 enhances its HAT activity: a new mechanism of epigenetic deregulation in TFH lymphoma

  1999cited by this paper
• De Novo peptide sequencing via tandem mass spectrometry: a graph-theoretical approach

  1999cited by this paper
• Sequence database searches via de novo peptide sequencing by tandem mass spectrometry.

  1997cited by this paper
• Proteome Research: New Frontiers in Functional Genomics

  1997cited by this paper
• Introduction to algorithms

  1996cited by this paper
• An approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database

  1994cited by this paper

• PepGo: a deep learning and tree search-based model for de novo peptide sequencing

  2025cites this paper
• Pathfinding in Self-Deleting Graphs

  2025cites this paper
• De Novo Sequencing of Peptides from Tandem Mass Spectra and Applications in Proteogenomics.

  2025cites this paper
• An efficient branch-and-bound algorithm for the one-to-many shortest path problem with additional disjunctive conflict constraints

  2025cites this paper
• Mitigating the missing-fragmentation problem in de novo peptide sequencing with a two-stage graph-based deep learning model

  2023cites this paper
• DpNovo: A DEEP LEARNING MODEL COMBINED WITH DYNAMIC PROGRAMMING FOR DE NOVO PEPTIDE SEQUENCING

  2023cites this paper
• (k-2)-linear Connected Components in Hypergraphs of Rank K

  2023cites this paper
• Algorithms for de-novo sequencing of peptides by tandem mass spectrometry: A review.

  2023cites this paper
• Current state, existing challenges, and promising progress for de novo sequencing and assembly of monoclonal antibodies

  2022cites this paper
• DPST: De Novo Peptide Sequencing with Amino-Acid-Aware Transformers

  2022cites this paper
• The impact of noise and missing fragmentation cleavages on de novo peptide identification algorithms

  2022cites this paper
• Almost disjoint paths and separating by forbidden pairs

  2022cites this paper
• Discrimination of Leucine and Isoleucine in De Novo peptide sequencing using deep neural networks

  2021cites this paper
• Computationally instrument-resolution-independent de novo peptide sequencing for high-resolution devices

  2021cites this paper
• Branch and Bound and Dynamic Programming Approaches for the Path Avoiding Forbidden Pairs Problem

  2021cites this paper
• Spectrum graph-based de-novo sequencing algorithm MaxNovo achieves high peptide identification rates in collisional dissociation MS/MS spectra

  2021cites this paper
• Understanding the Limit of Open Search in the Identification of Peptides With Post-translational Modifications — A Simulation-Based Study

  2020cites this paper
• Peptide Sequencing with Deep Learning

  2020cites this paper
• A classification of liquid chromatography mass spectrometry techniques for evaluation of chemical composition and quality control of traditional medicines.

  2020cites this paper
• GameTag: A New Sequence Tag Generation Algorithm Based on Cooperative Game Theory

  2020cites this paper
• Evolutionary Algorithms for Improving De Novo Peptide Sequencing

  2020cites this paper
• A Simple Approach to the Reconstruction of a Set of Points from the Multiset of Pairwise Distances in n2 Steps for the Sequencing Problem: III. Noise Inputs for the Beltway Case

  2019cites this paper
• Advancement in Sustainable Agriculture: Computational and Bioinformatics Tools

  2019cites this paper
• MODplus: robust and unrestrictive identification of post-translational modifications using mass spectrometry.

  2019cites this paper
• Integrating machine learning and multiscale modeling—perspectives, challenges, and opportunities in the biological, biomedical, and behavioral sciences

  2019cites this paper
• De novo glycan structural identification from mass spectra using tree merging strategy

  2019cites this paper
• Peptide Sequencing in Graphs for Multiplex Mass Spectra

  2018cites this paper
• A Potential Golden Age to Come—Current Tools, Recent Use Cases, and Future Avenues for De Novo Sequencing in Proteomics

  2018cites this paper
• Deep Omics

  2018cites this paper
• Algorithms for Peptide Identification via Tandem Mass Spectrometry

  2018influential citation
• Understanding the limit of open search in the identification of peptides with post-translational modifications — A simulation-based study

  2018cites this paper
• Evaluating de novo sequencing in proteomics: already an accurate alternative to database‐driven peptide identification?

  2018cites this paper
• Improved de novo peptide sequencing using LC retention time information

  2018cites this paper
• BIOTECHNO 2018

  2018cites this paper
• De novo peptide sequencing by deep learning

  2017cites this paper
• Algorithms and design strategies towards automated glycoproteomics analysis.

  2017cites this paper
• 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.

  2017cites this paper
• CycloAnt: sequencing cyclic peptides using hybrid ants

  2017cites this paper
• Open-pNovo: De Novo Peptide Sequencing with Thousands of Protein Modifications.

  2017cites this paper
• Sequenciamento de novo de peptídeos utilizando grafos para espectros de massa multiplex

  2017cites this paper
• University of Southern Denmark Peptide de novo sequencing of mixture tandem mass spectra

  2017cites this paper
• Protein Identification from Tandem Mass Spectra by Database Searching.

  2017cites this paper
• Impact of a priori MS/MS intensity distributions on database search for peptide identification

  2017cites this paper
• Modern Proteomics – Sample Preparation, Analysis and Practical Applications

  2016influential citation
• A Simple Approach to the Reconstruction of a Set of Points from the Multiset of n2 Pairwise Distances in n2 Steps for the Sequencing Problem: I. Theory

  2016cites this paper
• A Simple Approach to the Reconstruction of a Set of Points from the Multiset of n2 Pairwise Distances in n2 Steps for the Sequencing Problem: II. Algorithm

  2016cites this paper
• Computational Methods in Mass Spectrometry-Based Proteomics.

  2016cites this paper
• Tandem Mass Spectrum Sequencing: An Alternative to Database Search Engines in Shotgun Proteomics.

  2016cites this paper
• A better scoring model for de novo peptide sequencing: the symmetric difference between explained and measured masses

  2016influential citation
• Peptide de novo sequencing of mixture tandem mass spectra

  2016cites this paper
• PIPI: PTM-Invariant Peptide Identification Using Coding Method

  2016cites this paper
• Peptide sequencing via graph path decomposition

  2015cites this paper
• Novel Antifungal Peptides Produced by Leuconostoc mesenteroides DU15 Effectively Inhibit Growth of Aspergillus niger.

  2015cites this paper
• Methods of processing mass spectrometry data to identify peptides and proteins

  2015cites this paper
• Recent Developments in Computational Methods for De Novo Peptide Sequencing from Tandem Mass Spectrometry (MS/MS).

  2015cites this paper
• Algorithms for Peptide Identification from Mixture Tandem Mass Spectra

  2015cites this paper
• Evaluation and assignment of significance levels to peptide identifications from the database search programs using resampling approach

  2015cites this paper
• Software Analysis of Uncorrelated MS1 Peaks for Discovery of Post-Translational Modifications

  2015cites this paper
• Linear Programming and Integer Linear Programming in Bioinformatics

  2015cites this paper
• De novo peptide sequencing methods for tandem mass spectra

  2015cites this paper
• ProLuCID: An improved SEQUEST-like algorithm with enhanced sensitivity and specificity.

  2015cites this paper
• On the Path Avoiding Forbidden Pairs Polytope

  2015cites this paper
• Reconstruction of sequence from its circular partial sums for cyclopeptide sequencing problem

  2015cites this paper
• On finding the longest antisymmetric path in directed acyclic graphs

  2015cites this paper
• Reconstruction of amino acid sequence of cyclic peptides from mass spectra

  2015cites this paper
• A New Parameterized Algorithm for Rapid Peptide Sequencing

  2014cites this paper
• Towards automated identification of metabolites using mass spectral trees

  2014cites this paper
• Proteomics-Based Theranostics

  2014cites this paper
• New Approaches to Comparative and Animal Stress Biology Research in the Post-genomic Era: A Contextual Overview

  2014cites this paper
• Proteomic and functional analysis of chloroplast and thylacoids sub-compartments

  2014cites this paper
• Peptide Peak Detection for Low Resolution MALDI-TOF Mass Spectrometry.

  2014cites this paper
• Proteomics for systems toxicology

  2014cites this paper
• Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs

  2014cites this paper
• Proteomics and the Analysis of Proteomic Data: 2013 Overview of Current Protein‐Profiling Technologies

  2013cites this paper
• Approximation and Online Algorithms

  2013cites this paper
• Mass spectrometry-based proteomics: basic principles and emerging technologies and directions.

  2013cites this paper
• Counting Approximately-Shortest Paths in Directed Acyclic Graphs

  2013cites this paper
• UniNovo: a universal tool for de novo peptide sequencing

  2013cites this paper
• De novo sequencing with Limited Number of Post-Translational Modifications per peptide

  2013cites this paper
• Computational mass spectrometry for small molecules

  2013cites this paper
• pNovo+: de novo peptide sequencing using complementary HCD and ETD tandem mass spectra.

  2013cites this paper
• QuasiNovo: Algorithms for De Novo Peptide Sequencing

  2013cites this paper
• A new hybrid de novo sequencing method for protein identification

  2012cites this paper
• Protein inference based on peptides identified from

  2012cites this paper
• Proteomics and its application in plant biotechnology

  2012cites this paper
• Machine Learning Approaches to Refining Post-translational Modification Predictions and Protein Identifications from Tandem Mass Spectrometry

  2012cites this paper
• Protein inference based on peptides identified from tandem mass spectra

  2012cites this paper
• Tutorial on de novo peptide sequencing using MS/MS Mass spectrometry

  2012cites this paper
• Evaluation of Database Search Programs for Accurate Detection of Neuropeptides in Tandem Mass Spectrometry Experiments

  2012influential citation
• De Novo Peptide Sequencing Based on Vertex Contraction Algorithm

  2012cites this paper
• Constrained de novo sequencing of conotoxins.

  2012cites this paper
• Inhibition of MMP-9 Activity following Hypoxic Ischemia in the Developing Brain Using a Highly Specific Inhibitor

  2012cites this paper
• Protein identification from tandem mass spectra by database searching.

  2011cites this paper
• CHAPTER 6

  2011cites this paper
• Applications of graph theory in protein structure identification

  2011cites this paper
• Exploiting fragment-ion complementarity for peptide de novo sequencing from collision induced dissociation tandem mass spectra

  2011cites this paper
• The simplified partial digest problem: Approximation and a graph-theoretic model

  2011cites this paper
• Complexity of the path avoiding forbidden pairs problem revisited

  2011influential citation
• Characterization of the Human Host Gut Microbiome with an Integrated Genomics / Proteomics Approach

  2011cites this paper
• De Novo Sequencing and Homology Searching‡‡*

  2011cites this paper