Graph / DP

45 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 45 methods is Fast peptide sequencing algorithm (Bartels) (1990); 44 more have followed.

Methods 45
Papers describing them 73
Authors 191
Active 1990-06-01 to 2022-08-25
Deep learning 1 of 45
Kinds algorithm (44), adjacent
Acquisition DDA (42)

Methods (45)

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.
  • AUDENS (2002): Open-source automated de novo sequencing tool with preprocessing and dynamic programming over MS/MS spectra.
  • PepSUMS (2002): Computational framework integrating mass tags and dissociation chemistry for de novo peptide sequencing from MS/MS experiments.
  • Suboptimal de novo peptide sequencing (2003): Suboptimal-path algorithm for reporting multiple candidate de novo peptide sequences.
  • Core interpretations (Bafna-Edwards) (2003): A dynamic programming de novo algorithm that assigns ion types (a, b, y and neutral losses) to peaks and introduces core interpretations to give confidence values to parts of a sequence.
  • PEAKS (2003): Commercial DP-based de novo
  • Hierarchical subsequence de novo scoring (PNNL) (2003): PNNL de novo approach that finds sequences and subsequences hierarchically in a reduced spectrum graph, using multiple ion series and natural isotope peaks, and ranks candidates by the probability of random matches.
  • DC-Novo (2004): Divide-and-conquer + spectrum simulation
  • PepNovo (2005): Probabilistic network + DP
  • Two-way parallel searching de novo (2005): A de novo algorithm that searches b and y ion series in parallel from both ends to cut the number of candidate sequences, then screens them by intensity evidence.
  • Multi-charge spectrum de novo sequencing (2005): Generalises spectrum models to charges up to 5 and shows higher-charge fragment ions improve complete de novo peptide prediction.
  • Tree-decomposition de novo sequencing (2005): Models relationships among peaks as a graph and uses tree decomposition to find the longest antisymmetric path, giving linear-time de novo sequencing and quadratic-time spectral alignment that tolerate noise and PTMs.
  • O(n log n) de novo sequencing (Brunetti) (2005): An algorithm that reconstructs a peptide sequence from a tandem spectrum with n peaks in O(n log n) time.
  • Multi-charge strong tags de novo (2007): De novo peptide sequencing that first finds high-confidence strong tags across charge states and then connects them into full sequences.
  • MSNovo (2007): Mass-array dynamic programming
  • Variable-scoring DP de novo sequencing (2008): Dynamic programming over the spectrum graph where vertex scores depend on incident edges, solving forbidden-pairs paths in polynomial time.
  • Ion transformation spectrum graph (2008): Transforms all candidate ion types to b-ions before building the spectrum graph, shrinking it and improving de novo accuracy.
  • Preprocessing and antisymmetry for de novo sequencing (2008): Studies spectrum preprocessing and a relaxed antisymmetry constraint in spectrum-graph de novo sequencing, improving accuracy and speed.
  • Vonode (2010): High-throughput de novo sequencing approach for high-resolution shotgun proteomics spectra.
  • pNovo (2010): First HCD-focused de novo
  • Knapsack DP de novo sequencing (2011): Formulates de novo sequencing as an integer knapsack dynamic program so that ions other than b and y contribute to the score.
  • 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.
  • Bayesian network + DP hybrid de novo (Wang, Zomaya) (2012): Combines a Bayesian network with dynamic programming to explore sub-optimal spectrum-graph paths for de novo peptide sequencing.
  • PEAKS DB (2012): De-novo-assisted DB search
  • Vertex contraction de novo sequencing (2012): Solves the nested forbidden-pairs longest path problem behind spectrum-graph de novo sequencing in cubic time by vertex contraction.
  • QuasiNovo (2013): De novo peptide sequencing algorithm using a neural-network ion classifier, dynamic programming candidate generation, and amino acid usage/edge-frequency scoring.
  • pNovo+ (2013): Complementary HCD + ETD spectra
  • DeNovoPTM (2013): A de novo sequencing algorithm that allows many PTM types while bounding the number of modifications per peptide to keep accuracy.
  • UniNovo (2013): Universal de novo sequencing tool trained across fragmentation methods and instruments.
  • NovoHCD (2013): De novo sequencing of HCD spectra with a multi-edge spectrum graph that integrates amino acid combinations, peptide tags and immonium ions.
  • Parameterized path-width de novo sequencing (2014): Exploits bounded path width of an extended spectrum graph to compute antisymmetric partial paths for fast de novo sequencing.
  • De novo sequencing of mixture spectra (Liu thesis) (2014): 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.
  • NovoExD (2014): De novo peptide sequencing for ECD/ETD spectra, using a spectrum graph with multiple edge types for the c- and z-ion variants those spectra carry.
  • UVnovo (2015): UV photodissociation de novo
  • 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.
  • 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.
  • CycloNovo (2019): Cyclopeptide sequencing
  • 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.
  • 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).

Papers describing them (73)

Authors (191)

A. Heredia-Langner, Albert Y. Zomaya, Alexey Gurevich, Amanda Doherty-Kirby, Andrea Janeš, Andrew P. Horton, Andrey Prjibelski, Andrija Štajduhar, Anna Tan-Wilson, Anthony J. Kusalik, Antun Lovro Brkić, Ari Frank, Bahar Behsaz, Baozhen Shan, Bin Ma, Bing Yang, Bingwen Lu, Bo Yan, Brenton Morse, Byung H. Park, Carrock Sewell, Changjiang Xu, Changyong Yu, Chao Liu, Chengzhi Liang, Chongle Pan, Christian Bartels, Christopher Hendrie, Chuang Li, Chun-Qing Song, Chunmei Liu, D. M. Cai, D. Varrazzo, Daming Zhu, Debojyoti Dutta, Denis Yuen, Dustin D. Holden, Edward M. Marcotte, Elisa Mori, Ema Svetličić, Eric J. Schwabe, Fang-Xiang Wu, Feng Lin, Fernando Vargas, Franz F. Roos, Frido Welker, George M. Church, Gilles Lajoie, Gunnar W. Klau, Guoren Wang, Haibo Bian, Haifeng Chen, Haipeng Wang, Hao Chi, Hao Yang, Hon Wai Leong, Hosein Mohimani, Iain Rogers, J. Gao, James E. Vath, James Paul Cleveland, Jason Gallia, Jean Gao, Jennifer S. Brodbelt, Jianyun Liu, Jillian F. Banfield, Jing Zhang, Joe R. Cannon, John Rush, Jonas Grossmann, Joshua S. Mylne, Jung Hun Oh, Jürgen Cox, K.D. Jarman, KANG NING, Kaizhong Zhang, Karl R. Clauser, Kenli Li, Keqin Li, Ket Fah Chong, Kira Vyatkina, Kirill Tyshuk, Knut Reinert, Kristin H. Jarman, Kun He, Kyowon Jeong, LIMING CAI, Larry Smarr, Le-Heng Wang, Lei Xin, Lennard J. M. Dekker, Lijuan Mo, Lin He, Ljiljana Paša-Tolić, Long Wu, Lucas K. Mathis, Lucija Dončević, Ludovic Gillet, Luka Ozdanovac, Marina Čeprnja, Mario Cindrić, Mark Cieliebak, Mark Fisher, Martijn M. VanDuijn, Matthew A. Goto, Matthew Tepel, Matthias Müller, Meng-Qiu Dong, Michael L. Nielsen, Mikhail Dvorkin, Mikhail M. Savitski, Ming Li, Ming-Yang Kao, Mingjie Xie, NAN YE, Nagiza F. Samatova, Nathan C. VerBerkmoes, Nathan Edwards, Ngoc Hieu Tran, Nikola Tolić, O. Lubeck, Paolo Penna, Patricia A. Carey, Patrick H Madden, Pavel A. Pevzner, Pelagia Kyriakidou, Penghao Wang, Peter Widmayer, Petra Gutenbrunner, Pieter C. Dorrestein, Qiang He, Robert L. Hettich, Roman A. Zubarev, Rui Qiao, Rui-Xiang Sun, S. Liberatori, Sacha Baginsky, Sahar Rabinoviz, Sandro Andreotti, Sangtae Kim, Sara Brunetti, Scott A. Robotham, Sheng Gu, Shengying Pan, Si Wu, Si-Min He, Simon Rösch, Sonya Alexandrova, Susan R. Wilson, Tao Chen, Theo M. Luider, Theresa A. Addona, Thomas Tschager, Ting Chen, Tomas Hruz, Tomislav Tustonić, Torsten Kleffmann, Valentin Venzin, Victoria C. Cotham, Vineet Bafna, Vlado Dancík, W. Hayes McDonald, W.R. Cannon, Weiming Zhang, Weiwu Chen, Wen-Feng Zeng, Wen-Jing Zhou, Wendan Zhai, Wilhelm Gruissem, XI HAN, Xian Chen, Xianghui Xie, Xianliang He, Xiaowen Liu, Xin Chen (Waterloo), YOUNG BUN KIM, Yan Fu, Yan Yan, Yan Yan (publication 972), Yi Liu, Yi Zhao, Ying Xu, Yinglei Song, Yunhu Wan, Yunping Zhu, Yves Frank, Zefeng Zhang, Zhexue Wei, Zhongqi Zhang, Zsuzsanna Lipták, Zuo-Fei Yuan

Seen in the charts

Back to the full map

Back to top