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.