Fast de novo peptide sequencing and spectral alignment via tree decomposition.
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.
Liu
Chunmei
C
Department of Computer Science, University of Georgia, Athens, GA 30602, USA. chunmei@cs.uga.edu
Song
Yinglei
Y
Yan
Bo
B
Xu
Ying
Y
Cai
Liming
L
D000465:Algorithms; D000595:Amino Acid Sequence; D019295:Computational Biology; D008969:Molecular Sequence Data; D009154:Mutation; D010455:Peptides / Q000737:chemistry* / Q000235:genetics; D011499:Protein Processing, Post-Translational; D016415:Sequence Alignment / Q000706:statistics & numerical data*; D020539:Sequence Analysis, Protein / Q000706:statistics & numerical data*; D053719:Tandem Mass Spectrometry / Q000706:statistics & numerical data
D010455:Peptides