FAST DE NOVO PEPTIDE SEQUENCING AND SPECTRAL ALIGNMENT VIA TREE DECOMPOSITION

peer-reviewed · Biocomputing 2006 · 2005

peer-reviewed · Biocomputing 2006 · 2005. Chunmei Liu et al. De novo sequencing and spectral alignment are computationally important for the prediction of new protein…
Date 2005-12-01
Type peer-reviewed
Venue Biocomputing 2006
Publisher WORLD SCIENTIFIC
Contribution algorithm
DOI 10.1142/9789812701626_0024
Citations (OpenAlex) 19

Abstract

De novo sequencing and spectral alignment are computationally important for the prediction of new protein peptides via tandem mass spectrometry (MS/MS). Both approaches are established upon the problem of finding the longest antisymmetric path on formulated graphs. The problem is of high computational complexity and the prediction accuracy is compromised when given spectra involve noisy data, missing mass peaks, or post translational modifications (PTMs) and mutations. This paper introduces a graphical mechanism to describe relationships among mass peaks that, through graph tree decomposition, yields linear and quadratic time algorithms for optimal de novo sequencing and spectral alignment respectively. Our test results show that, in addition to high efficiency, the new algorithms can achieve desired prediction accuracy on spectra containing noisy peaks and PTMs while allowing the presence of both b-ions and y-ions.

Authors

  1. Chunmei Liu · Howard University, University of Georgia
  2. Yinglei Song · Jiangsu University of Science and Technology
  3. Bo Yan · University of Georgia
  4. Ying Xu · Oak Ridge National Laboratory, University of Georgia
  5. LIMING CAI · University of Georgia

Methods and tools

  • Tree-decomposition de novo sequencing: 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.

Seen in the charts

Back to the full map

Back to top