Graph / DP
26 methods · 1990–2022
Graph / DP: The classical formulation: peaks become nodes in a spectrum graph whose edges are residue masses, and the peptide is the best-scoring path through it, found by dynamic programming. Nearly every classical sequencer is a version of this.
The classical formulation: peaks become nodes in a spectrum graph whose edges are residue masses, and the peptide is the best-scoring path through it, found by dynamic programming. Nearly every classical sequencer is a version of this.
The earliest of its 26 methods is Fast peptide sequencing algorithm (Bartels) (1990); 25 more have followed.
| Methods | 26 |
| Papers describing them | 32 |
| Authors | 130 |
| Active | 1990-06-01 to 2022-08-25 |
| Kinds | algorithm (25), adjacent |
| Acquisition | DDA (25) |
Methods (26)
Oldest first, by the paper that describes each one.
- Fast peptide sequencing algorithm (Bartels) (1990): 1990 graph-theory algorithm that sequences polypeptides from FAB tandem mass spectra by scoring mass differences, without needing the amino acid composition, and proposes amino acid pairs or triples to bridge missing peaks. Sub-quadratic in the number of residues.
- Sherenga (1999): Graph-theoretic de novo (foundational)
- DP-based de novo peptide sequencing (2001): Dynamic-programming formulation over an NC-spectrum graph for de novo peptide sequencing.
- Suboptimal de novo peptide sequencing (2003): Suboptimal-path algorithm for reporting multiple candidate de novo peptide sequences.
- PEAKS (2003): Commercial DP-based de novo
- DC-Novo (2004): Divide-and-conquer + spectrum simulation
- PepNovo (2005): Probabilistic network + DP
- AUDENS (2005): Open-source automated de novo sequencing tool with preprocessing and dynamic programming over MS/MS spectra.
- MSNovo (2007): Mass-array dynamic programming
- Vonode (2010): High-throughput de novo sequencing approach for high-resolution shotgun proteomics spectra.
- pNovo (2010): First HCD-focused de novo
- Antilope (2011): Lagrangian-relaxation formulation of de novo peptide sequencing. Frames the problem as a constrained optimization over the spectrum graph and solves it with iterative subgradient ascent.
- PEAKS DB (2012): De-novo-assisted DB search
- pNovo+ (2013): Complementary HCD + ETD spectra
- UniNovo (2013): Universal de novo sequencing tool trained across fragmentation methods and instruments.
- De novo sequencing of mixture spectra (Liu thesis) (2015): PhD work on identifying peptides from MIXTURE tandem mass spectra, where two or more peptides co-fragment: formulates the de novo problem for a mixture spectrum and solves it by dynamic programming.
- T-Bruijn graph top-down de novo sequencing (2015): De novo sequencing from TOP-DOWN spectra, where the whole protein is fragmented rather than tryptic peptides: derives sequence tags and assembles them through a T-Bruijn graph, evaluated on carbonic anhydrase 2 and an alemtuzumab Fab.
- UVnovo (2016): UV photodissociation de novo
- Open-pNovo (2017): pNovo with thousands of PTMs
- MRUniNovo (2017): Hadoop-distributed implementation of UniNovo for efficient de novo peptide sequencing.
- Symmetric difference scoring model (2017): Scores a candidate sequence by the symmetric difference between the masses it explains and the masses actually measured, penalising an explained mass that was not observed as well as an observed mass left unexplained. Earlier scoring models only maximised the number of explained masses.
- Retention-time-aware de novo sequencing (2018): Extends the symmetric difference scoring model with the chromatographic retention time, asking for a sequence consistent with both the fragment spectrum and the observed elution time. Develops an algorithm for each of three retention-time prediction models.
- SWPepNovo (2019): Parallelises a PepNovo-style scoring search across the Sunway many-core architecture, using a two-level task partition and a load-balancing scheme to keep the compute elements busy. Targets the case where the spectrum dataset, not the algorithm, is the bottleneck. From the same Hunan group as MRUniNovo.
- CycloNovo (2020): Cyclopeptide sequencing
- MaxNovo (2021): MaxQuant spectrum-graph de novo
- Protein Acrobat (2022): De novo peptide sequencing tool from the Cindrić group, coupling MALDI-TOF/TOF fragmentation of chemically activated peptides with de novo sequence elucidation and NCBInr alignment for organism identification (bacteria, viruses, meat-species markers).
How they score
1 of the 26 has been run on denovo_benchmarks, which ranks 17 tools over 84 datasets. The family’s best median rank is 13.
- PEAKS: median peptide-level average precision 0.545, median rank 13 of 17
Read these next to the rest of the field, not on their own: what the numbers mean.
Papers describing them (32)
- Fast algorithm for peptide sequencing by mass spectroscopy (1990, Biological Mass Spectrometry, peer-reviewed)
- De novo peptide sequencing via tandem mass spectrometry (1999, Journal of Computational Biology, peer-reviewed)
- A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry (2001, Journal of Computational Biology, peer-reviewed)
- A Suboptimal Algorithm for De Novo Peptide Sequencing via Tandem Mass Spectrometry (2003, Journal of Computational Biology, peer-reviewed)
- PEAKS: powerful software for peptide de novo sequencing by tandem mass spectrometry (2003, Rapid Communications in Mass Spectrometry, peer-reviewed)
- De Novo Peptide Sequencing Based on a Divide-and-Conquer Algorithm and Peptide Tandem Spectrum Simulation (2004, Analytical Chemistry, peer-reviewed)
- PepNovo: de novo peptide sequencing via probabilistic network modeling (2005, Analytical Chemistry, peer-reviewed)
- An effective algorithm for peptide de novo sequencing from MS/MS spectra (2005, Journal of Computer and System Sciences, peer-reviewed)
- AUDENS: A Tool for Automated Peptide de Novo Sequencing (2005, Journal of Proteome Research, peer-reviewed)
- Complexity and scoring function of MS/MS peptide de novo sequencing (2006, Computational Systems Bioinformatics, peer-reviewed)
- De Novo Peptide Sequencing and Identification with Precision Mass Spectrometry (2007, Journal of Proteome Research, peer-reviewed)
- MSNovo: A Dynamic Programming Algorithm for de Novo Peptide Sequencing via Tandem Mass Spectrometry (2007, Analytical Chemistry, peer-reviewed)
- A Ranking-Based Scoring Function for Peptide-Spectrum Matches (2009, Journal of Proteome Research, peer-reviewed)
- A high-throughput de novo sequencing approach for shotgun proteomics using high-resolution tandem mass spectrometry (2010, BMC Bioinformatics, peer-reviewed)
- pNovo: De novo Peptide Sequencing and Identification Using HCD Spectra (2010, Journal of Proteome Research, peer-reviewed)
- Antilope – A Lagrangian Relaxation Approach to the de novo Peptide Sequencing Problem (2011, arXiv, preprint)
- Antilope—A Lagrangian Relaxation Approach to the de novo Peptide Sequencing Problem (2012, IEEE/ACM Transactions on Computational Biology and Bioinformatics, peer-reviewed)
- PEAKS DB: De Novo Sequencing Assisted Database Search for Sensitive and Accurate Peptide Identification (2012, Molecular & Cellular Proteomics, peer-reviewed)
- pNovo+: De Novo Peptide Sequencing Using Complementary HCD and ETD Tandem Mass Spectra (2013, Journal of Proteome Research, peer-reviewed)
- UniNovo: a universal tool for de novo peptide sequencing (2013, Bioinformatics, peer-reviewed)
- Algorithms for Peptide Identification from Mixture Tandem Mass Spectra (2015, thesis)
- De Novo Sequencing of Peptides from Top-Down Tandem Mass Spectra (2015, Journal of Proteome Research, peer-reviewed)
- UVnovo: A de Novo Sequencing Algorithm Using Single Series of Fragment Ions via Chromophore Tagging and 351 nm Ultraviolet Photodissociation Mass Spectrometry (2016, Analytical Chemistry, peer-reviewed)
- Open-pNovo: De Novo Peptide Sequencing with Thousands of Protein Modifications (2017, Journal of Proteome Research, peer-reviewed)
- MRUniNovo: an efficient tool for de novo peptide sequencing utilizing the Hadoop distributed computing framework (2017, Bioinformatics, peer-reviewed)
- Comprehensive de Novo Peptide Sequencing from MS/MS Pairs Generated through Complementary Collision Induced Dissociation and 351 nm Ultraviolet Photodissociation (2017, Analytical Chemistry, peer-reviewed)
- A better scoring model for de novo peptide sequencing: the symmetric difference between explained and measured masses (2017, Algorithms for Molecular Biology, peer-reviewed)
- Improved de novo peptide sequencing using LC retention time information (2018, Algorithms for Molecular Biology, peer-reviewed)
- SWPepNovo: An Efficient De Novo Peptide Sequencing Tool for Large-scale MS/MS Spectra Analysis (2019, International Journal of Biological Sciences, peer-reviewed)
- De Novo Peptide Sequencing Reveals Many Cyclopeptides in the Human Gut and Other Environments (2020, Cell Systems, peer-reviewed)
- Spectrum graph-based de-novo sequencing algorithm MaxNovo achieves high peptide identification rates in collisional dissociation MS/MS spectra (2021, bioRxiv, preprint)
- Direct Identification of Urinary Tract Pathogens by MALDI-TOF/TOF Analysis and De Novo Peptide Sequencing (2022, Molecules, peer-reviewed)