牟长宁，王海鹏，周丕宇，侯鑫行

（山东理工大学计算机科学与技术学院，山东淄博 255000）

（*通信作者电子邮箱hpwang@sdut.edu.cn）

0 引言

基于串联质谱的蛋白质组学是生命科学研究的重要组成部分，近年来在探索细胞机制、疾病进程以及基因型和表型之间关系等研究上取得了巨大进展［1］。基于串联质谱的蛋白质测序主流的方法是蛋白质数据库搜索，常用工具有Mascot［2］、Comet［3］、MaxQuant［4］、pFind［5-6］等。该方法需要参考已有数据库检索候选肽序列，因此在未知生物蛋白、单克隆抗体测序等研究上失去优势。另一种鉴定方法是从头测序，该方法能够直接从串联质谱中推断出氨基酸序列，无需数据库作为参考，在鉴定未知生物肽序列上具有不可替代的作用。过去20 年间从头测序方法进步显著，应用较为广泛的方案是基于图论的思想，将质谱转化为谱峰关系图（spectrum graph），谱峰作为谱图中的顶点，如果谱峰与谱峰之间的距离等于一个或者两个氨基酸残基的分子量，则两个峰之间用一条边相连；通过搜索图中起始点到结束点的最优路径得到产生这个质谱的候选肽序列。代表性工作包括：2003 年Ma 等［7］发表的PEAKS，通过预处理步骤（图谱噪声过滤和图谱峰聚合）创建谱图并用动态规划算法来生成候选肽序列；2005年Frank等［8］发表了针对碰撞诱导裂解（Collision-Induced Dissociation，CID）质谱的PepNovo 算法，提出了一种基于概率网络模型的候选肽序列评分方法；2010 年Chi 等［9］发表的pNovo，使用带剪枝的深度优先搜索有效提升了在高能碰撞裂解（Higher-energy Collision Dissociation，HCD）质谱数据上的从头测序性能；……