Liu Chunmei, Song Yinglei, Yan Bo, Xu Ying, Cai Liming
Department of Computer Science, University of Georgia, Athens, GA 30602, USA.
Pac Symp Biocomput. 2006:255-66.
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.
从头测序和谱图比对对于通过串联质谱法（MS/MS）预测新的蛋白质肽段在计算上具有重要意义。这两种方法都是基于在构建的图上寻找最长反对称路径的问题。该问题具有很高的计算复杂度，并且当给定的谱图包含噪声数据、缺失质量峰、翻译后修饰（PTM）和突变时，预测准确性会受到影响。本文引入了一种图形机制来描述质量峰之间的关系，通过图树分解，分别产生用于最优从头测序和谱图比对的线性和二次时间算法。我们的测试结果表明，除了高效率之外，新算法在包含噪声峰和PTM的谱图上能够实现所需的预测准确性，同时允许b离子和y离子同时存在。
