近年来,蛋白质组学以其重要的应用前景受到广泛的关注,成为了后基因组时代十分重要的研究课题之一。其中,蛋白质鉴定是蛋白质组学中尤为重要的一步,是后续蛋白功能和相互协作分析的基本保障。目前,串联质谱技术以其高度的准确性和灵敏性成为了大规模、快速、准确的蛋白质鉴定的主要技术手段。然而,高分辨率的串联质谱数据的特点决定了其在计算上的困难,也给计算机算法提出了新的挑战。造成基于串联质谱蛋白质鉴定算法设计困难的主要因素有:(1)离子成分复杂。经过CID碎裂而形成的多肽串联质谱的离子成分非常复杂,包括噪音离子峰、多种已知类型离子峰(如N端的a,b,c和C端的x,y,z等)、同位素离子峰和未知类型离子峰等等。串联质谱离子成分的复杂性增加了算法的计算复杂度和离子峰的错误指认和匹配的概率,从而增加了鉴定结果的假阳性。(2)数据不完备。CID过程中,多肽主链的某些肽键及其周围的化学键发生的断裂较少,从而导致串联质谱数据中该处断裂信息的丢失。这使得计算机算法无法推断该处的序列信息或导致正确多肽序列因在该处打分极低而被剔除,增加了鉴定结果的假阴性。(3)翻译后修饰。多肽序列的突变及翻译后修饰能够造成其串联质谱中包含修饰或突变的离子以一定质量进行偏移,从而进一步增大了解释其串联质谱的难度。本文针对基于串联质谱的蛋白质鉴定问题的上述难点进行了详细的分析和深入的研究。本文的贡献点可概括如下:(1)针对从头测序算法中图模型引进的噪音顶点多,计算复杂度高等问题,本文提出了一系列的算法,以达到减小质谱图的规模及降低计算复杂度的目的。首先,提出了PShifter算法,该算法能够将串联质谱中的其它类型离子转换为b离子。其次,应用SVM分类理论提出了Ion-Classifier算法,该算法用于串联质谱中δ_i类型离子与非δ_i类型离子的分类。最后,基于频繁模式挖掘和决策树方法提出了b/y-Classifier算法,该算法用于串联质谱中b和y离子的分类。实验结果表明,这些算法对解决噪音离子过滤,离子分类等问题取得了较好的结果,提高了从头测序的准确性。(2)针对蛋白质数据库搜索算法中串联质谱和多肽序列匹配打分的问题,提出了一系列算法。首先,基于信息熵理论提出了ITPIA算法,该算法计算理论谱的每一个离子位点的信息熵来衡量该多肽序列在串联质谱中的表达信息,从而衡量匹配程度。其次,提出了基于kNN技术的匹配打分算法。该算法很好地利用了强度信息,在已知的高精度的数据集上建立了强度匹配知识集合,通过现有匹配对当前的匹配对打分。最后,提出了ReCheck算法。该算法针对数据的不完备性提出了连续三元位点的概念,将对一个肽键位置的判断信息扩展为其周围三个位点的信息。实验结果表明,这些算法能够应用到蛋白质数据库搜索算法中,并且在一些数据集上可以取得较好的准确性。(3)提出了基于多肽序列标签的蛋白质数据库搜索鉴定算法,即PepCheck算法。首先,构建了质谱图(Spectrum Graph),将多肽序列标签的推导问题转化为质谱图中最长平行路径和互补路径的求解问题。其次,引进了枚举树作为蛋白质数据库的索引,以便利用多肽序列标签更加快速地进行数据库搜索。最后,基于断裂点的匹配特征提出了多肽序列标签与蛋白质序列的匹配打分算法。实验结果表明,多肽序列标签的生成和数据库搜索均取得了很高的鉴定准确率。(4)提出了基于质谱比对模型的蛋白质翻译后修饰鉴定算法,即Check-PTM算法。首先,根据带有PTM的串联质谱中离子峰的偏移特性给出了更加合理的质谱比对模型,提出了该模型的组合优化求解算法。为了进一步提高算法的效率,提高算法的可用性,提出了质谱比对模型的近似求解算法,降低了模型求解的复杂度。接下来,通过分析偏移量之间的关系和分析发生偏移的离子峰集合,提出了修饰类型发现和位点识别算法。实验结果表明,带有PTM的多肽的质谱比对打分算法和带有PTM多肽的修饰类型发现和位点识别算法均取得了很高的鉴定准确率。