第11卷第3期 智能系统学报 Vol.11 No.3 2016年6月 CAAI Transactions on Intelligent Systems Jun.2016 D0I:10.11992/is.201603051 网s络出版地址：http:/www.cnki.net/kcms/detail/23.1538.TP.20160513.0913.006.html 基于概率图模型的蛋白质推断算法 赵璨，段琼，何增有 (大连理工大学国家示范性软件学院，辽宁大连116620) 摘要：蛋白质组学是研究细胞内表达的所有的蛋白质及其变化规律的一门新兴学科。蛋白质组学的一个重要目 标是能够快速准确的进行蛋白质鉴定。蛋白质鉴定主要包括肽段鉴定和蛋白质推断两个步骤。肽段鉴定是从原始 质谱数据中鉴定出肽段序列，而蛋白质推断是从这些鉴定得到的肽段中还原出原始的蛋白质序列。但由于质谱数 据固有的不确定性和蛋白质组的复杂性，使得解决蛋白质推断问题变得很困难。本文引入串联质谱数据对于蛋白 质存在概率的影响，提出了一种基于概率图模型的方法(PGMP)来解决蛋白质推断问题，将蛋白质推断问题抽象成 一个概率图模型的求解问题，通过寻找蛋白质的最大后验概率来推断真实存在的蛋白质集合。该方法不仅能够进 行有效的蛋白质推断，而且模型参数少，提高了算法的稳定性。实验结果表明该模型在蛋白质推断上具有很好的表 现。 关键词：蛋白质推断：肽段推断：鸟枪法蛋白质组学：概率图模型 中图分类号：TP393文献标志码：A文章编号：1673-4785(2016)01-0376-08 中文引用格式：赵璨，段琼，何增有.基于概率图模型的蛋白质推断算法[J].智能系统学报，2016,11(2)：376-383. 英文引用格式：ZHAO Can,.DUAN Qiong,.HE Zengyou..Protein inference method based on probabilistic graphical model[J].CAAI transactions on intelligent systems,2016,11(2):376-383. Protein inference method based on probabilistic graphical model ZHAO Can,DUAN Qiong,HE Zengyou (School of Software,Dalian University of Technology,Dalian 116620,China) Abstract:Proteomics is an emerging discipline that focuses on the large-scale study of proteins expressed inan or- ganism.An explicit goal of proteomics is the prompt and accurate identification of all proteins in a cell or tissue. Generally,protein identification can be divided into two parts:peptide identification and protein inference.In pep- tide identification,the peptide sequence is identified from raw tandem mass spectrometry,while the goal of protein inference is to identify which of these identified proteins is truly present in the sample.Because of the inherent un- certainty of MS data and the complexity of the proteome,there are several challenges in protein identification.In this article,we propose a novel method based on the probabilistic graphical model (PGMPi)that introduces the in- fluence of tandem mass spectrometry.This method transforms the protein inference problem into a probabilistic graphical model problem to be solved,in which the maximum posteriori probabilities of proteins are identified in or- der to identify the protein set that is actually present in the sample.PGMPi can not only achieve efficient perform- ance in terms of identification,but also introduces only one parameter,which ensures the algorithm's stability.The experimental results demonstrate that our method is superior to existing state-of-the-art protein inference algo- rithms. Keywords:protein inference;peptide inference;shotgun proteomics;probability graph model 蛋白质组学是研究细胞内表达的所有的蛋白质 及其变化规律的一门新兴学科川。蛋白质组主要 是指由一个基因组，或一个细胞组织表达的所有蛋 收稿日期：2016-03-200.网络出版日期：2016-05-13 基金项目：国家自然科学基金项目(61572094). 白质。基因组基本是固定不变的，而蛋白质组却为 通信作者：何增有.E-mail:zyhc@dlut.cdu.cm
第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０５１ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９１３．００６．ｈｔｍｌ 基于概率图模型的蛋白质推断算法 赵璨，段琼，何增有 （大连理工大学 国家示范性软件学院，辽宁 大连 １１６６２０） 摘 要：蛋白质组学是研究细胞内表达的所有的蛋白质及其变化规律的一门新兴学科。 蛋白质组学的一个重要目 标是能够快速准确的进行蛋白质鉴定。 蛋白质鉴定主要包括肽段鉴定和蛋白质推断两个步骤。 肽段鉴定是从原始 质谱数据中鉴定出肽段序列，而蛋白质推断是从这些鉴定得到的肽段中还原出原始的蛋白质序列。 但由于质谱数 据固有的不确定性和蛋白质组的复杂性，使得解决蛋白质推断问题变得很困难。 本文引入串联质谱数据对于蛋白 质存在概率的影响，提出了一种基于概率图模型的方法（ＰＧＭＰｉ）来解决蛋白质推断问题，将蛋白质推断问题抽象成 一个概率图模型的求解问题，通过寻找蛋白质的最大后验概率来推断真实存在的蛋白质集合。 该方法不仅能够进 行有效的蛋白质推断，而且模型参数少，提高了算法的稳定性。 实验结果表明该模型在蛋白质推断上具有很好的表 现。 关键词：蛋白质推断；肽段推断；鸟枪法蛋白质组学；概率图模型 中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０１⁃０３７６⁃０８ 中文引用格式：赵璨，段琼，何增有．基于概率图模型的蛋白质推断算法［Ｊ］． 智能系统学报， ２０１６， １１（２）： ３７６⁃３８３． 英文引用格式：ＺＨＡＯ Ｃａｎ，ＤＵＡＮ Ｑｉｏｎｇ，ＨＥ Ｚｅｎｇｙｏｕ．Ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｇｒａｐｈｉｃａｌ ｍｏｄｅｌ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（２）： ３７６⁃３８３． Ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｇｒａｐｈｉｃａｌ ｍｏｄｅｌ ＺＨＡＯ Ｃａｎ，ＤＵＡＮ Ｑｉｏｎｇ，ＨＥ Ｚｅｎｇｙｏｕ （Ｓｃｈｏｏｌ ｏｆ Ｓｏｆｔｗａｒｅ， Ｄａｌｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｄａｌｉａｎ １１６６２０， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｐｒｏｔｅｏｍｉｃｓ ｉｓ ａｎ ｅｍｅｒｇｉｎｇ ｄｉｓｃｉｐｌｉｎｅ ｔｈａｔ ｆｏｃｕｓｅｓ ｏｎ ｔｈｅ ｌａｒｇｅ－ｓｃａｌｅ ｓｔｕｄｙ ｏｆ ｐｒｏｔｅｉｎｓ ｅｘｐｒｅｓｓｅｄ ｉｎａｎ ｏｒ⁃ ｇａｎｉｓｍ． Ａｎ ｅｘｐｌｉｃｉｔ ｇｏａｌ ｏｆ ｐｒｏｔｅｏｍｉｃｓ ｉｓ ｔｈｅ ｐｒｏｍｐｔ ａｎｄ ａｃｃｕｒａｔｅ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｏｆ ａｌｌ ｐｒｏｔｅｉｎｓ ｉｎ ａ ｃｅｌｌ ｏｒ ｔｉｓｓｕｅ． Ｇｅｎｅｒａｌｌｙ， ｐｒｏｔｅｉｎ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｃａｎ ｂｅ ｄｉｖｉｄｅｄ ｉｎｔｏ ｔｗｏ ｐａｒｔｓ： ｐｅｐｔｉｄｅ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ａｎｄ ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ． Ｉｎ ｐｅｐ⁃ ｔｉｄｅ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ， ｔｈｅ ｐｅｐｔｉｄｅ ｓｅｑｕｅｎｃｅ ｉｓ ｉｄｅｎｔｉｆｉｅｄ ｆｒｏｍ ｒａｗ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ ， ｗｈｉｌｅ ｔｈｅ ｇｏａｌ ｏｆ ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ｉｓ ｔｏ ｉｄｅｎｔｉｆｙ ｗｈｉｃｈ ｏｆ ｔｈｅｓｅ ｉｄｅｎｔｉｆｉｅｄ ｐｒｏｔｅｉｎｓ ｉｓ ｔｒｕｌｙ ｐｒｅｓｅｎｔ ｉｎ ｔｈｅ ｓａｍｐｌｅ． Ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｉｎｈｅｒｅｎｔ ｕｎ⁃ ｃｅｒｔａｉｎｔｙ ｏｆ ＭＳ ｄａｔａ ａｎｄ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｐｒｏｔｅｏｍｅ， ｔｈｅｒｅ ａｒｅ ｓｅｖｅｒａｌ ｃｈａｌｌｅｎｇｅｓ ｉｎ ｐｒｏｔｅｉｎ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ． Ｉｎ ｔｈｉｓ ａｒｔｉｃｌｅ， ｗｅ ｐｒｏｐｏｓｅ ａ ｎｏｖｅｌ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｇｒａｐｈｉｃａｌ ｍｏｄｅｌ （ＰＧＭＰｉ） ｔｈａｔ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｉｎ⁃ ｆｌｕｅｎｃｅ ｏｆ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ． Ｔｈｉｓ ｍｅｔｈｏｄ ｔｒａｎｓｆｏｒｍｓ ｔｈｅ ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ｐｒｏｂｌｅｍ ｉｎｔｏ ａ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｇｒａｐｈｉｃａｌ ｍｏｄｅｌ ｐｒｏｂｌｅｍ ｔｏ ｂｅ ｓｏｌｖｅｄ， ｉｎ ｗｈｉｃｈ ｔｈｅ ｍａｘｉｍｕｍ ｐｏｓｔｅｒｉｏｒｉ ｐｒｏｂａｂｉｌｉｔｉｅｓ ｏｆ ｐｒｏｔｅｉｎｓ ａｒｅ ｉｄｅｎｔｉｆｉｅｄ ｉｎ ｏｒ⁃ ｄｅｒ ｔｏ ｉｄｅｎｔｉｆｙ ｔｈｅ ｐｒｏｔｅｉｎ ｓｅｔ ｔｈａｔ ｉｓ ａｃｔｕａｌｌｙ ｐｒｅｓｅｎｔ ｉｎ ｔｈｅ ｓａｍｐｌｅ． ＰＧＭＰｉ ｃａｎ ｎｏｔ ｏｎｌｙ ａｃｈｉｅｖｅ ｅｆｆｉｃｉｅｎｔ ｐｅｒｆｏｒｍ⁃ ａｎｃｅ ｉｎ ｔｅｒｍｓ ｏｆ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ， ｂｕｔ ａｌｓｏ ｉｎｔｒｏｄｕｃｅｓ ｏｎｌｙ ｏｎｅ ｐａｒａｍｅｔｅｒ， ｗｈｉｃｈ ｅｎｓｕｒｅｓ ｔｈｅ ａｌｇｏｒｉｔｈｍ＇ｓ ｓｔａｂｉｌｉｔｙ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｏｕｒ ｍｅｔｈｏｄ ｉｓ ｓｕｐｅｒｉｏｒ ｔｏ ｅｘｉｓｔｉｎｇ ｓｔａｔｅ－ｏｆ －ｔｈｅ －ａｒｔ ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ａｌｇｏ⁃ ｒｉｔｈｍｓ． Ｋｅｙｗｏｒｄｓ：ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ； ｐｅｐｔｉｄｅ ｉｎｆｅｒｅｎｃｅ； ｓｈｏｔｇｕｎ ｐｒｏｔｅｏｍｉｃｓ； ｐｒｏｂａｂｉｌｉｔｙ ｇｒａｐｈ ｍｏｄｅｌ 收稿日期：２０１６⁃０３⁃２００． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家自然科学基金项目（６１５７２０９４）． 通信作者：何增有． Ｅ⁃ｍａｉｌ：ｚｙｈｅ＠ ｄｌｕｔ．ｅｄｕ．ｃｎ． 蛋白质组学是研究细胞内表达的所有的蛋白质 及其变化规律的一门新兴学科［１］ 。 蛋白质组主要 是指由一个基因组，或一个细胞组织表达的所有蛋 白质。 基因组基本是固定不变的，而蛋白质组却为
第3期 赵璨，等：基于概率图模型的蛋白质推断算法 ·377· 动态的，具有时空性和可调节性，能反映出特定基因 到目前为止，研究人员已经提出许多成熟可用 的表达时间、表达量以及蛋白质翻译后的加工修饰 的蛋白质推断算法[6o。关于这些方法的细节以及 等信息。蛋白质组学的研究试图比较细胞在不同生 蛋白质推断过程中所遇到的问题挑战，读者可以参 理或病理条件下蛋白质表达的异同，从整体上研究 阅最近的综述文章]。总体来说，可以把蛋白质 细胞或组织内蛋白质的组成及其活动规律。蛋白质 推断问题的输入抽象成一个二分图，如图2(a)所 组学的一个重要目标是能够快速准确地进行蛋白质 示，其中一侧是候选蛋白质集合，另一侧是鉴定肽集 鉴定，即确定一个样本中真实存在的蛋白质。只有 合。例如，ProteinPropphet、IDPicker]均使用标 鉴定到生物样品中真实表达的蛋白质，才能准确地 准二分图作为输入，通过建立不同的假设来设计模 对蛋白质进行定量以及推断出蛋白质之间相互作用 型和算法。在二分图模型中，由于输入被限制，所以 关系(protein--protein interaction,PPI),为进一步的 无论算法多么完美，结果还是无法进一步完善。因 疾病标记物发现和新药开发提供有力的支持)。 此为了提高蛋白质鉴定的准确率，研究人员尝试引 因此，蛋白质鉴定是蛋白质组学研究的基础，对整个 入一些额外信息。借用额外信息改变传统的蛋白质 领域的进一步发展和应用有着十分重要的意义。 推断问题的输入，即在原来的标准二分图输入的基 在高通量蛋白质组学研究中，目前使用的主流 础上，加入额外信息，例如原始串联质谱和一级质 技术是质谱分析法(MS)[),即用电场和磁场将运 谱、蛋白质相互作用网络、mRNA表达信息等。图 动的离子按它们的质荷比分离后进行检测。同时， 2(b)所示为引入质谱数据后的三层图模型。 为了从混合物样本中分离出蛋白质和肽段以便深入 肽段 质谱 肽段 研究，液相色谱技术(LC)也被引入蛋白质鉴定，最 蛋白质 蛋白质 终形成了LC-MS技术。在LC-MS的基础上，鸟 枪法蛋白质组学是蛋白质鉴定最常用的策略)。 鸟枪法蛋白质组学的基本流程如下：1)蛋白质样本 通过酶切消化等生物实验获得肽段的混合物溶液： 2)将所得混合物进行离子化并使用质谱仪进行串 联质谱分析，从而得到一系列的串联质谱(MS/MS) (a)标准的二分图 (b)引人额外信息的图结构 数据：3)对串联谱图进行预处理后通过肽段鉴定和 蛋白质推断得到样本中可能存在的肽段和蛋白质。 图2标准的二分图和引入额外信息的图结构 Fig.2 The standard bipartite graph and the graph when 其大体流程如图1所示。 introducing extra information 蛋白质推断问题的一个最大的挑战来自于肽段 的退化，也称共享肽段问题，即一个鉴定肽段被多个 混合样本 1250150017502M0 质谱仪 质谱图 候选蛋白质所共享。蛋白质推断算法的优劣主要取 蛋白质肽段 质谱图 决于它是否能准确地找出哪些或者哪个蛋白质真正 蛋白质分数 地产生共享的肽段。目前为止，研究人员已经开发 A 1.00 B 0.97 出很多蛋白质推断算法，如ProteinProphet、MSBaye- C 0.90 D sPro9和Fido)等。虽然这些算法使用多种不同的 0.78 E 0.43 方式来解决肽段退化问题，但都存在着一些固有的 蛋白质推断 缺陷。ProeinProphet使用一个类期望最大化的迭代 肽鉴定 过程来估计蛋白质存在的概率，该方法没有明确定 义如何优化模型中计算蛋白质概率的公式。相反 图1鸟枪法蛋白质组学的基本流程 地，MSBayesPro、HSM)和Fido都是从清晰准确的 Fig.1 The entire workflow of shotgun proteomics 统计假设中推导出公式的，但是，这些方法获得最优
动态的，具有时空性和可调节性，能反映出特定基因 的表达时间、表达量以及蛋白质翻译后的加工修饰 等信息。 蛋白质组学的研究试图比较细胞在不同生 理或病理条件下蛋白质表达的异同，从整体上研究 细胞或组织内蛋白质的组成及其活动规律。 蛋白质 组学的一个重要目标是能够快速准确地进行蛋白质 鉴定，即确定一个样本中真实存在的蛋白质。 只有 鉴定到生物样品中真实表达的蛋白质，才能准确地 对蛋白质进行定量以及推断出蛋白质之间相互作用 关系（ｐｒｏｔｅｉｎ－ｐｒｏｔｅｉｎ ｉｎｔｅｒａｃｔｉｏｎ， ＰＰＩ），为进一步的 疾病标记物发现和新药开发提供有力的支持［２］ 。 因此，蛋白质鉴定是蛋白质组学研究的基础，对整个 领域的进一步发展和应用有着十分重要的意义。 在高通量蛋白质组学研究中，目前使用的主流 技术是质谱分析法（ＭＳ） ［３］ ，即用电场和磁场将运 动的离子按它们的质荷比分离后进行检测。 同时， 为了从混合物样本中分离出蛋白质和肽段以便深入 研究，液相色谱技术（ＬＣ）也被引入蛋白质鉴定，最 终形成了 ＬＣ⁃ＭＳ 技术［４］ 。 在 ＬＣ⁃ＭＳ 的基础上，鸟 枪法蛋白质组学是蛋白质鉴定最常用的策略［５］ 。 鸟枪法蛋白质组学的基本流程如下：１）蛋白质样本 通过酶切消化等生物实验获得肽段的混合物溶液； ２）将所得混合物进行离子化并使用质谱仪进行串 联质谱分析，从而得到一系列的串联质谱（ＭＳ ／ ＭＳ） 数据；３）对串联谱图进行预处理后通过肽段鉴定和 蛋白质推断得到样本中可能存在的肽段和蛋白质。 其大体流程如图 １ 所示。 图 １ 鸟枪法蛋白质组学的基本流程 Ｆｉｇ．１ Ｔｈｅ ｅｎｔｉｒｅ ｗｏｒｋｆｌｏｗ ｏｆ ｓｈｏｔｇｕｎ ｐｒｏｔｅｏｍｉｃｓ 到目前为止，研究人员已经提出许多成熟可用 的蛋白质推断算法［６⁃１０］ 。 关于这些方法的细节以及 蛋白质推断过程中所遇到的问题挑战，读者可以参 阅最近的综述文章［１１⁃１３］ 。 总体来说，可以把蛋白质 推断问题的输入抽象成一个二分图，如图 ２（ ａ） 所 示，其中一侧是候选蛋白质集合，另一侧是鉴定肽集 合。 例如，ＰｒｏｔｅｉｎＰｒｏｐｐｈｅｔ ［６］ 、 ＩＤＰｉｃｋｅｒ ［１０］ 均使用标 准二分图作为输入，通过建立不同的假设来设计模 型和算法。 在二分图模型中，由于输入被限制，所以 无论算法多么完美，结果还是无法进一步完善。 因 此为了提高蛋白质鉴定的准确率，研究人员尝试引 入一些额外信息。 借用额外信息改变传统的蛋白质 推断问题的输入，即在原来的标准二分图输入的基 础上，加入额外信息，例如原始串联质谱和一级质 谱、蛋白质相互作用网络、ｍＲＮＡ 表达信息等。 图 ２（ｂ）所示为引入质谱数据后的三层图模型。 （ａ）标准的二分图 （ｂ）引入额外信息的图结构 图 ２ 标准的二分图和引入额外信息的图结构 Ｆｉｇ．２ Ｔｈｅ ｓｔａｎｄａｒｄ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ａｎｄ ｔｈｅ ｇｒａｐｈ ｗｈｅｎ ｉｎｔｒｏｄｕｃｉｎｇ ｅｘｔｒａ ｉｎｆｏｒｍａｔｉｏｎ 蛋白质推断问题的一个最大的挑战来自于肽段 的退化，也称共享肽段问题，即一个鉴定肽段被多个 候选蛋白质所共享。 蛋白质推断算法的优劣主要取 决于它是否能准确地找出哪些或者哪个蛋白质真正 地产生共享的肽段。 目前为止，研究人员已经开发 出很多蛋白质推断算法， 如 ＰｒｏｔｅｉｎＰｒｏｐｈｅｔ、ＭＳＢａｙｅ⁃ ｓＰｒｏ ［９］和 Ｆｉｄｏ ［７］等。 虽然这些算法使用多种不同的 方式来解决肽段退化问题，但都存在着一些固有的 缺陷。 ＰｒｏｅｉｎＰｒｏｐｈｅｔ 使用一个类期望最大化的迭代 过程来估计蛋白质存在的概率，该方法没有明确定 义如何优化模型中计算蛋白质概率的公式。 相反 地，ＭＳＢａｙｅｓＰｒｏ、ＨＳＭ ［８］ 和 Ｆｉｄｏ 都是从清晰准确的 统计假设中推导出公式的，但是，这些方法获得最优 第 ３ 期 赵璨，等：基于概率图模型的蛋白质推断算法 ·３７７·
.378. 智能系统学报 第11卷 解的过程是很费时的。 数据抽象为节点，肽段和其对应谱图之间存在一个 基于此，本文提出了一种基于概率图模型的方 有向边，这样就得到一个三层的有向图结构，从而将 法来解决蛋白质推断问题。本文的主要着眼点放在 蛋白质鉴定问题抽象为概率图求解问题，如图3所 两个问题上，一个是概率图模型在蛋白质推断问题 示。 上的应用，另一个是串联质谱数据对于蛋白质存在 本文算法基于有向图模型，也称为贝叶斯网 概率的影响。前者将蛋白质推断问题抽象成一个概 络)。需明确的是，模型的目标是从候选蛋白质集 率图模型的求解问题，鉴定到的肽段以及候选蛋白 合中找到真正存在于样本中的蛋白质子集。根据这 质都抽象为节点，候选蛋白质及其对应肽段之间的 一目标，本文首先给出了一个图中所有节点联合概 关系抽象为有向边，这样就可以抽象成一个有向的 率分布，即谱图、肽段及其对应候选蛋白质同时存在 二部图：后者主要是考虑肽鉴定过程中谱与肽段之 于样本中的概率。由于有向图采用乘积法则，对于 间指派的正确性的影响，也可称作肽段识别概率，是 x→y,联合概率分布为p(x,y)=p(x)p(ylx)。其次 指鉴定肽在样本中存在的后验概率，作为本文概率 对该联合概率分布提出一些基本假设，如蛋白质之 图模型的输入。 间相互独立、每个鉴定肽打分之间相互独立等，并根 据这些假设条件做简单的数学变换确定参数变量， 1 基于概率图模型的蛋白质推断算法 之后根据联合概率分布给出蛋白质的后验概率公 1.1算法介绍 式，由于求解具有最大联合概率分布的候选蛋白质 概率图模型是由图论和概率论结合而成的描述 问题规模较大，暴力求解的代价十分昂贵，故本文采 多元统计关系的有效模型[]，它为多个变量之间复 用了吉布斯抽样来获得具有最大后验的最优蛋白质 杂的依赖关系的表示提供了统一的框架，具有紧凑 配置。 有效、简洁直观的特点。其在计算机视觉、生物信息 相关符号及其定义在表1中给了详细的说明。 学、自然语言处理等领域都有广泛的应用。 表1蛋白质推断的符号说明 Table 1 The notation used in the protein inference model 蛋白质 符号 说明 X 候选蛋白质集合 肽段 指示变量，如果x,=1,蛋白质i存在，否则为 x1,x2,“,xm 不存在 质谱 上 鉴定得到的肽段集合 12,…,少。指示变量，如果y=1,肽段j存在，否则不存在 质谱仪产生的谱图信息对应的打分 图3引入质谱信息的三层图结构 Fig.3 The three-layer graph when introducing the MS/ 81,52,…,8。 每个肽段j对应一个打分5 MS data N 可以生成肽段j的候选蛋白质的集合 M 候选蛋白质i可以产生的肽段的集合 本文提出了基于概率图模型的蛋白质推断算法 8 蛋白质i所存在组的蛋白质集合 (PGMP),该方法主要将概率图模型应用到蛋白质 肽段j所存在组的肽段的集合 推断问题上，同时引入肽鉴定过程中谱与肽段之间 蛋白质、肽段以及质谱的联合概率公式为 指派的正确性的影响。由于蛋白质推断输入数据是 P(X,Y,S)=P(x1,…,xm）·P(y,…ynIx1,…xm） 一个二部图，一侧为候选蛋白质的集合，另一侧为肽 P(s1,…,sn1y1,…,yn) (1) 段集合。本文将肽段以及候选蛋白质都抽象为节 1.2模型参数化 点，候选蛋白质及其对应肽段之间的关系抽象为有 1)假设两个候选蛋白质之间相互独立： 向边，这样就可以抽象成一个有向的二部图：同时考 虑串联质谱数据对于蛋白质概率的影响，也将质谱 P(x1,x2,…,xm)= p(x) (2)
解的过程是很费时的。 基于此，本文提出了一种基于概率图模型的方 法来解决蛋白质推断问题。 本文的主要着眼点放在 两个问题上，一个是概率图模型在蛋白质推断问题 上的应用，另一个是串联质谱数据对于蛋白质存在 概率的影响。 前者将蛋白质推断问题抽象成一个概 率图模型的求解问题，鉴定到的肽段以及候选蛋白 质都抽象为节点，候选蛋白质及其对应肽段之间的 关系抽象为有向边，这样就可以抽象成一个有向的 二部图；后者主要是考虑肽鉴定过程中谱与肽段之 间指派的正确性的影响，也可称作肽段识别概率，是 指鉴定肽在样本中存在的后验概率，作为本文概率 图模型的输入。 １ 基于概率图模型的蛋白质推断算法 １．１ 算法介绍 概率图模型是由图论和概率论结合而成的描述 多元统计关系的有效模型［１４］ ，它为多个变量之间复 杂的依赖关系的表示提供了统一的框架，具有紧凑 有效、简洁直观的特点。 其在计算机视觉、生物信息 学、自然语言处理等领域都有广泛的应用。 图 ３ 引入质谱信息的三层图结构 Ｆｉｇ．３ Ｔｈｅ ｔｈｒｅｅ⁃ｌａｙｅｒ ｇｒａｐｈ ｗｈｅｎ ｉｎｔｒｏｄｕｃｉｎｇ ｔｈｅ ＭＳ／ ＭＳ ｄａｔａ 本文提出了基于概率图模型的蛋白质推断算法 （ＰＧＭＰｉ），该方法主要将概率图模型应用到蛋白质 推断问题上，同时引入肽鉴定过程中谱与肽段之间 指派的正确性的影响。 由于蛋白质推断输入数据是 一个二部图，一侧为候选蛋白质的集合，另一侧为肽 段集合。 本文将肽段以及候选蛋白质都抽象为节 点，候选蛋白质及其对应肽段之间的关系抽象为有 向边，这样就可以抽象成一个有向的二部图；同时考 虑串联质谱数据对于蛋白质概率的影响，也将质谱 数据抽象为节点，肽段和其对应谱图之间存在一个 有向边，这样就得到一个三层的有向图结构，从而将 蛋白质鉴定问题抽象为概率图求解问题，如图 ３ 所 示。 本文算法基于有向图模型，也称为贝叶斯网 络［１５］ 。 需明确的是，模型的目标是从候选蛋白质集 合中找到真正存在于样本中的蛋白质子集。 根据这 一目标，本文首先给出了一个图中所有节点联合概 率分布，即谱图、肽段及其对应候选蛋白质同时存在 于样本中的概率。 由于有向图采用乘积法则，对于 ｘ→ｙ，联合概率分布为 ｐ（ｘ，ｙ）＝ ｐ（ｘ）ｐ（ｙ ｜ ｘ）。 其次 对该联合概率分布提出一些基本假设，如蛋白质之 间相互独立、每个鉴定肽打分之间相互独立等，并根 据这些假设条件做简单的数学变换确定参数变量， 之后根据联合概率分布给出蛋白质的后验概率公 式，由于求解具有最大联合概率分布的候选蛋白质 问题规模较大，暴力求解的代价十分昂贵，故本文采 用了吉布斯抽样来获得具有最大后验的最优蛋白质 配置。 相关符号及其定义在表 １ 中给了详细的说明。 表 １ 蛋白质推断的符号说明 Ｔａｂｌｅ １ Ｔｈｅ ｎｏｔａｔｉｏｎ ｕｓｅｄ ｉｎ ｔｈｅ ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ｍｏｄｅｌ 符号 说明 Ｘ 候选蛋白质集合 ｘ１ ，ｘ２ ，…，ｘｍ 指示变量，如果 ｘｉ ＝ １， 蛋白质 ｉ 存在，否则为 不存在 Ｙ 鉴定得到的肽段集合 ｙ１ ，ｙ２ ，…，ｙｎ 指示变量，如果 ｙｊ ＝１，肽段 ｊ 存在，否则不存在 Ｓ 质谱仪产生的谱图信息对应的打分 ｓ１ ，ｓ２ ，…，ｓｎ 每个肽段 ｊ 对应一个打分 ｓｊ Ｎｊ 可以生成肽段 ｊ 的候选蛋白质的集合 Ｍｉ 候选蛋白质 ｉ 可以产生的肽段的集合 Ｇｉ 蛋白质 ｉ 所存在组的蛋白质集合 ｇｊ 肽段 ｊ 所存在组的肽段的集合 蛋白质、肽段以及质谱的联合概率公式为 Ｐ（Ｘ，Ｙ，Ｓ） ＝ Ｐ（ｘ１，…，ｘｍ）·Ｐ（ｙ１，…，ｙｎ ｜ ｘ１，…，ｘｍ）· Ｐ（ｓ１ ，…，ｓｎ ｜ ｙ１ ，…，ｙｎ ） （１） １．２ 模型参数化 １） 假设两个候选蛋白质之间相互独立： Ｐ（ｘ１ ，ｘ２ ，…，ｘｍ ） ＝ ∏ ｍ ｉ ＝ １ ｐ（ｘｉ） （２） ·３７８· 智 能 系 统 学 报 第 １１ 卷
第3期 赵璨，等：基于概率图模型的蛋白质推断算法 ·379· 2)假设不同的蛋白质对于其对应鉴定肽的贡 集合。 献是独立的； 1.3模型求解 P(y1y2,…,yn1x1,x2,…,xm）= 给定蛋白质的配置图，以及肽段被正确识别的 Π[1-P(y=11x1,x2,…,xn)]7. 概率s,在参数α确定的情况下，根据式(7)可直接 计算出蛋白质的后验概率。但是这种暴力求解方法 P(=11x1,x2,…,xm）y= 的时间复杂度为O(2"),由于图的规模较大，所以 Π[Π(1-a)][-Π(1-a)]y 直接暴力求解的代价是十分昂贵的，故本文采用了 吉布斯抽样[16]来获得具有最大后验的最优蛋白质 (3) 配置。 式(3)中，由于y,只有0和1两种取值，所以可以表 吉布斯抽样是马尔可夫蒙特卡罗(Markov 示为 Chain monte Carlo,MCMC)算法中的特例，用来构造 P(y1,y2,…,yn|x1,x2,…,xm）= 多变量概率分布的随机样本。考虑具有p(z)= Π(1-y)[Π(1-a)]+[1-Π(1-a)]} ieN p(21,2,…,m)分布的样品集，并且给定一些符合马 (4) 尔可夫性质的初始状态。吉布斯抽样的每一步骤都 会根据剩余变量的当前状态值更新其中一个变量的 P(y1x1,…,xm）三 状态值。也就是说，对于z的第i个组件，可以通过 (1-y)[Π(1-a)]+y[1-Π (1-a)] 计算p(z:Iz)得到，其中表示除z:的所有组件。 (5) 迭代这一过程在每一步使用一个转变函数来更新变 式中：V表示可能产生肽段j的候选蛋白质的集合， 量信息，直到收敛为止。 为对应参数。 将该方法用于求解蛋白质推断问题，大大降低 3)欲求得可能存在于样本中的蛋白质子集，需 了求解模型(PGMP)的时间复杂度，算法收敛所得 使得联合概率最大化。模型可以转化为寻找最大后 的蛋白质后验概率即为该蛋白质真实存在于样本中 验蛋白质配置的问题，对于每个蛋白质的后验概率： 的概率。需要说明的是，该方法所求的解为近似最 AΠp)IP,10IP6,1) 优解，但可以通过改变收敛的判断标准来对近似解 P(x;I S)= 调优。 ΣΠp(,)Py1WPo1) jc M 2实验及结果评估 (6) 为了验证本文提出的蛋白质推断算法PGMPi 4)根据以下规定，将蛋白质和肽段进行分组。 的表现，选取2个典型的蛋白质推断算法MSBaye- ①在同一组中任意两个元素之间至少存在一条 sPro,Fido在6个数据集上进行比较实验。 路径； 2.1数据集 ②除去组中的肽段之外，对于组中的蛋白质没 本文选取了6个公开的数据集来验证PGMPi 有其他的肽段被鉴定到； 的表现：l8 mixtures),Sigma491),Yeast!9 ③没有其他的蛋白质可以生成组中的肽段。 DME2o,HumanMD2]和HumanEKC1。它们主要 A.eHP10A1 分为2类：有参考集的数据集和无参考集的数据集。 P(x;IS)= 瑞= jw调= ∑Πp(x)ΠP(yIX)ΠPIs) 前3个数据集都拥有相对应的蛋白质参考数据集， X 1:GI=G jg=G j:g=GI 即预先知道的存在于样本中的蛋白质集合。另3个 (7) 数据集则不拥有这样的参考集。关于这些数据集的 模型的主要目标为寻找一个具有最大后验的蛋 更多细节详情请参见文献[22]。 白质配置，也就是最大化每个蛋白质后验概率 本文采用广泛使用的目标-诱饵的策略来评估 P(X:IS),从而推断出真实存在于样本中的蛋白质 算法的表现。该策略的主要思想为：在包含所有目
２） 假设不同的蛋白质对于其对应鉴定肽的贡 献是独立的； Ｐ（ｙ１ ，ｙ２ ，…，ｙｎ ｜ ｘ１ ，ｘ２ ，…，ｘｍ ） ＝ ∏ ｊ ［１ － Ｐ（ｙｊ ＝ １ ｜ ｘ１ ，ｘ２ ，…，ｘｍ ）］ １－ｙｊ· Ｐ（ ｙ ｊ ＝ １ ｜ ｘ１ ，ｘ２ ，…，ｘｍ ） ｙｊ ＝ ∏ ｊ ［∏ｉ∈Ｎｊ （１ － α） ｘｉ ］ １－ｙｊ ［ １ － ∏ｉ∈Ｎｊ （１ － α） ｘｉ ］ ｙｊ （３） 式（３）中，由于 ｙｊ 只有 ０ 和 １ 两种取值，所以可以表 示为 Ｐ（ｙ１ ，ｙ２ ，…，ｙｎ ｜ ｘ１ ，ｘ２ ，…，ｘｍ ） ＝ ∏ ｊ ｛（１ － ｙｊ）［∏ｉ∈Ｎｊ （１ － α） ｘｉ ］ ＋ ｙｊ［１ － ∏ｉ∈Ｎｊ （１ － α） ｘｉ ］｝ （４） Ｐ（ｙｊ ｜ ｘ１ ，…，ｘｍ ） ＝ （１ － ｙｊ）［∏ｉ∈Ｎｊ （１ － α） ｘｉ］ ＋ ｙｊ［１ － ∏ｉ∈Ｎｊ （１ － α） ｘｉ］ （５） 式中：Ｎｊ 表示可能产生肽段 ｊ 的候选蛋白质的集合， α 为对应参数。 ３） 欲求得可能存在于样本中的蛋白质子集，需 使得联合概率最大化。 模型可以转化为寻找最大后 验蛋白质配置的问题，对于每个蛋白质的后验概率： Ｐ（ｘｉ ｜ Ｓ） ＝ Ｘ∑：ｘｉ ＝ １∏ｘｉ ｐ（ｘｉ）∏ ｊ∈Ｍｉ Ｐ（ｙｊ ｜ Ｘ）∏ ｊ∈Ｍｉ Ｐ（ｙｊ ｜ ｓｊ） ∑Ｘ ∏ｘｉ ｐ（ｘｉ）∏ ｊ∈Ｍｉ Ｐ（ｙｊ ｜ Ｘ）∏ ｊ∈Ｍｉ Ｐ（ｙｊ ｜ ｓｊ） （６） ４）根据以下规定，将蛋白质和肽段进行分组。 ①在同一组中任意两个元素之间至少存在一条 路径； ②除去组中的肽段之外，对于组中的蛋白质没 有其他的肽段被鉴定到； ③没有其他的蛋白质可以生成组中的肽段。 Ｐ（ｘｉ ｜ Ｓ） ＝ Ｘ∑：ｘｉ ＝ １ｌ：∏Ｇｌ ＝Ｇｉ ｐ（ｘｉ） ｊ：∏ｇｊ ＝Ｇｉ Ｐ（ｙｊ ｜ Ｘ） ｊ：∏ｇｊ ＝Ｇｉ Ｐ（ｙｊ ｜ ｓｊ） ∑Ｘ ｌ：∏Ｇｌ ＝Ｇｉ ｐ（ｘｉ） ｊ：∏ｇｊ ＝Ｇｉ Ｐ（ｙｊ ｜ Ｘ） ｊ：∏ｇｊ ＝Ｇｉ Ｐ（ｙｊ ｜ ｓｊ） （７） 模型的主要目标为寻找一个具有最大后验的蛋 白质配 置， 也 就 是 最 大 化 每 个 蛋 白 质 后 验 概 率 Ｐ（Ｘｉ ｜ Ｓ），从而推断出真实存在于样本中的蛋白质 集合。 １．３ 模型求解 给定蛋白质的配置图，以及肽段被正确识别的 概率 ｓｊ，在参数 α 确定的情况下，根据式（７）可直接 计算出蛋白质的后验概率。 但是这种暴力求解方法 的时间复杂度为 Ｏ（２ ｍ ），由于图的规模较大，所以 直接暴力求解的代价是十分昂贵的，故本文采用了 吉布斯抽样［１６］来获得具有最大后验的最优蛋白质 配置。 吉布斯 抽 样 是 马 尔 可 夫 蒙 特 卡 罗 （ Ｍａｒｋｏｖ Ｃｈａｉｎ ｍｏｎｔｅ Ｃａｒｌｏ，ＭＣＭＣ）算法中的特例，用来构造 多变量概率分布的随机样本。 考虑具有 ｐ （ ｚ） ＝ ｐ（ｚ１ ，ｚ２ ，…，ｚｍ ）分布的样品集，并且给定一些符合马 尔可夫性质的初始状态。 吉布斯抽样的每一步骤都 会根据剩余变量的当前状态值更新其中一个变量的 状态值。 也就是说，对于 ｚ 的第 ｉ 个组件 ｚｉ可以通过 计算 ｐ（ ｚｉ ｜ ｚ＼ｉ）得到，其中 ｚ＼ｉ表示除 ｚｉ 的所有组件。 迭代这一过程在每一步使用一个转变函数来更新变 量信息，直到收敛为止。 将该方法用于求解蛋白质推断问题，大大降低 了求解模型（ＰＧＭＰｉ）的时间复杂度，算法收敛所得 的蛋白质后验概率即为该蛋白质真实存在于样本中 的概率。 需要说明的是，该方法所求的解为近似最 优解，但可以通过改变收敛的判断标准来对近似解 调优。 ２ 实验及结果评估 为了验证本文提出的蛋白质推断算法 ＰＧＭＰｉ 的表现，选取 ２ 个典型的蛋白质推断算法 ＭＳＢａｙｅ⁃ ｓＰｒｏ， Ｆｉｄｏ 在 ６ 个数据集上进行比较实验。 ２．１ 数据集 本文选取了 ６ 个公开的数据集来验证 ＰＧＭＰｉ 的 表 现： １８ ｍｉｘｔｕｒｅｓ ［１７］ ， Ｓｉｇｍａ４９ ［１８］ ， Ｙｅａｓｔ ［１９］ ， ＤＭＥ ［２０］ ，ＨｕｍａｎＭＤ ［２１］ 和 ＨｕｍａｎＥＫＣ ［１９］ 。 它们主要 分为 ２ 类：有参考集的数据集和无参考集的数据集。 前 ３ 个数据集都拥有相对应的蛋白质参考数据集， 即预先知道的存在于样本中的蛋白质集合。 另 ３ 个 数据集则不拥有这样的参考集。 关于这些数据集的 更多细节详情请参见文献［２２］。 本文采用广泛使用的目标－诱饵的策略来评估 算法的表现。 该策略的主要思想为：在包含所有目 第 ３ 期 赵璨，等：基于概率图模型的蛋白质推断算法 ·３７９·
·380 智能系统学报 第11卷 标蛋白质序列以及等量的诱饵蛋白质序列的混合蛋 方法中没有一个能在所有数据集上都表现为最好。 白质数据库中搜索串联质谱：当鉴定得到的蛋白质 在6个数据集上，PGMPi是最稳定的并且没有最差 存在于蛋白质参考集或者来自于目标蛋白质数据库 的表现。总体来说，PGMPi在Yeast,.DME,Sigma_49 时，该蛋白质被认为是正确的鉴定结果。 和HumanEKC数据集上几乎都是表现最好的（或者 2.2参数设置 和其他方法的表现非常相近)。同时，PGMPi在18 实验使用的数据库搜索引擎为X!Tandem mixtures数据集上表现次好。具体地说，在所有6 (v2010.10.01.1)2),使用搜索引擎的默认参数并假 个数据集上，PGMPi击败Fido4次，击败MSBaye- 设这些参数已经被最优化。对于18 mixtures,Sig- sPro5次。另一方面，当q_vaue等于0时（没有报 ma49和Yeast数据集，所有的二级质谱只搜索目标 告任何错误的蛋白质)，PGMPi在HumanMD和Hu- 蛋白质数据库。对于DME,HumanMD和Hu- manEKC数据集上能够报告最多的正确蛋白质。其 manEKC,二级质谱需要同时搜索目标和诱饵数据 他2个推断算法也能在某些数据集上有类似的表现 库。当数据库搜索引擎报告了肽段及其鉴定分数 但没有PGMPi多。具体的数据是：不报告任何错误 后，实验继续使用包含在TPPv4.5中的Pep 的蛋白质时，ido在一个数据集上报告最多的正确 tideProphe'24对鉴定结果做后续处理，得到肽段的 的蛋白质，而MSBayesPro在所有数据集都没有这样 鉴定概率。 的表现。 本文将PGMPi和其他2个蛋白质推断算法 图4绘制了3个蛋白质推断方法PGMPi、Fido MSBayesPro和Fido进行比较。这2个算法都明确 和MSBayesPro在不同q_value下正确报告的蛋白质 地使用条件概率处理肽段退化问题而且它们的程序 的个数。整体来说，PGMPi在6个数据集上表现比 包是开源的。实验运行MSBayesPro和Fido算法时 较稳定，尤其是在DME、HumanEKC及Yeast等3个 均使用默认参数。PGMPi是使用R语言进行实验 数据集上都是表现最好的：在HumanMD和Sigma_ 求解的，该方法只有一个参数α，设定其取值范围为 49数据集上当g_value较小时，表现不是最优的，但 a∈[0.2,0.8]，实验设置PGMPi的参数a=5。 随着g_value的增加，PGMPi较MSBayesPro和Fido 2.3实验结果 而言都是最先达到最优的；I8 mixtures中PGMPi是 本文通过生成曲线评估不同的蛋白质推断算法 表现次优的。而Fido虽然在18 mixtures数据集中 的表现。该曲线根据不同的g_value绘制正确发现 明显优于其他2个算法，但是在其他数据集中的表 的蛋白质鉴定物(TP)的个数。一个鉴定得到的蛋 现都不是太理想，尤其是在Yeast数据集中的表现 白质如果出现在相应的蛋白质参考集或者目标蛋白 远远落后于其他2个算法，这也表明Fido在针对个 质数据库中，则认为被正确发现(TP):反之，则认为 别数据集来说可能会比较适合，模型相对来说不稳 该蛋白质是错误发现的(FP)。给定某个概率阈值 定。对于MSBayesPro,该算法在Sigma_49数据集 t,如果蛋白质概率值大于阈值t的蛋白质中有T,个 上，当q_value较小时，相比于PGMPi和Fido有不 正确发现蛋白质和F,个错误发现蛋白质，那么错误 太显著的优势，但随着g_-value的增加就被PGMPi 发现率(FDR)用如下方式计算：FDR,=F,/(T,+F,)。 超过：在DME和HumanEKC两个数据集上MSBaye- 相应的g-value定义为一个蛋白质被报告的最小 sP0都显著弱于其他2个算法，表现相对较差，尤其 FDR:q,=min:s,FDR,:q,=mins,FDR:。然后，通过 是在HumanEKC数据集上，PGMPi和Fido都在q_ 不断地改变概率阈值t生成最终的曲线。多个方法 value=O.03时可以全部鉴定出样品中存在的蛋白 报告的排名最高的蛋白质拥有相同的分数1.0，这些 质，而对于MSBayesPro,当q_value=0.035时还是 蛋白质在输出文件中的排序是随机的。本文跳过这 没能达到最优解，由于其效果较差，为了便于比较将 些具有相同概率的蛋白质，从下一个出现的拥有不 q_-value>0.035的部分去掉了；MSBayesPro只在 同概率的蛋白质开始计算g_value。. Yeast以及Sigma_49这2个数据集上和表现最好的 图4所示为3种不同的蛋白质推断算法的在6 方法相比，没有明显的差异：总的来说，MSBayesPro 个数据集上的推断结果评估曲线。一方面，这3个 在6个数据集中的表现相比于其他蛋白质推断方法
标蛋白质序列以及等量的诱饵蛋白质序列的混合蛋 白质数据库中搜索串联质谱；当鉴定得到的蛋白质 存在于蛋白质参考集或者来自于目标蛋白质数据库 时，该蛋白质被认为是正确的鉴定结果。 ２．２ 参数设置 实验 使 用 的 数 据 库 搜 索 引 擎 为 Ｘ！ Ｔａｎｄｅｍ （ｖ２０１０．１０．０１．１） ［２３］ ，使用搜索引擎的默认参数并假 设这些参数已经被最优化。 对于 １８ ｍｉｘｔｕｒｅｓ，Ｓｉｇ⁃ ｍａ４９ 和 Ｙｅａｓｔ 数据集，所有的二级质谱只搜索目标 蛋 白 质 数 据 库。 对 于 ＤＭＥ， ＨｕｍａｎＭＤ 和 Ｈｕ⁃ ｍａｎＥＫＣ，二级质谱需要同时搜索目标和诱饵数据 库。 当数据库搜索引擎报告了肽段及其鉴定分数 后，实 验 继 续 使 用 包 含 在 ＴＰＰ ｖ４． ５ 中 的 Ｐｅｐ⁃ ｔｉｄｅＰｒｏｐｈｅ ｔ ［２４］对鉴定结果做后续处理，得到肽段的 鉴定概率。 本文将 ＰＧＭＰｉ 和其他 ２ 个蛋白质推断算法 ＭＳＢａｙｅｓＰｒｏ 和 Ｆｉｄｏ 进行比较。 这 ２ 个算法都明确 地使用条件概率处理肽段退化问题而且它们的程序 包是开源的。 实验运行 ＭＳＢａｙｅｓＰｒｏ 和 Ｆｉｄｏ 算法时 均使用默认参数。 ＰＧＭＰｉ 是使用 Ｒ 语言进行实验 求解的，该方法只有一个参数 α，设定其取值范围为 α∈［０．２，０．８］，实验设置 ＰＧＭＰｉ 的参数 α＝ ５。 ２．３ 实验结果 本文通过生成曲线评估不同的蛋白质推断算法 的表现。 该曲线根据不同的 ｑ＿ｖａｌｕｅ 绘制正确发现 的蛋白质鉴定物（ＴＰ）的个数。 一个鉴定得到的蛋 白质如果出现在相应的蛋白质参考集或者目标蛋白 质数据库中，则认为被正确发现（ＴＰ）；反之，则认为 该蛋白质是错误发现的（ ＦＰ）。 给定某个概率阈值 ｔ，如果蛋白质概率值大于阈值 ｔ 的蛋白质中有 Ｔｔ个 正确发现蛋白质和 Ｆｔ个错误发现蛋白质，那么错误 发现率（ＦＤＲ）用如下方式计算：ＦＤＲｔ ＝ Ｆｔ ／ （Ｔｔ ＋Ｆｔ）。 相应的 ｑ＿ｖａｌｕｅ 定义为一个蛋白质被报告的最小 ＦＤＲ： ｑｔ ＝ ｍｉｎｉ≤ｔＦＤＲｉ：ｑｔ ＝ ｍｉｎｉ≤ｔＦＤＲｉ。 然后，通过 不断地改变概率阈值 ｔ 生成最终的曲线。 多个方法 报告的排名最高的蛋白质拥有相同的分数 １．０，这些 蛋白质在输出文件中的排序是随机的。 本文跳过这 些具有相同概率的蛋白质，从下一个出现的拥有不 同概率的蛋白质开始计算 ｑ＿ｖａｌｕｅ。 图 ４ 所示为 ３ 种不同的蛋白质推断算法的在 ６ 个数据集上的推断结果评估曲线。 一方面，这 ３ 个 方法中没有一个能在所有数据集上都表现为最好。 在 ６ 个数据集上，ＰＧＭＰｉ 是最稳定的并且没有最差 的表现。 总体来说，ＰＧＭＰｉ 在 Ｙｅａｓｔ，ＤＭＥ，Ｓｉｇｍａ＿４９ 和 ＨｕｍａｎＥＫＣ 数据集上几乎都是表现最好的（或者 和其他方法的表现非常相近）。 同时，ＰＧＭＰｉ 在 １８ ｍｉｘｔｕｒｅｓ 数据集上表现次好。 具体地说，在所有 ６ 个数据集上，ＰＧＭＰｉ 击败 Ｆｉｄｏ ４ 次，击败 ＭＳＢａｙｅ⁃ ｓＰｒｏ ５ 次。 另一方面，当 ｑ＿ｖａｌｕｅ 等于 ０ 时（没有报 告任何错误的蛋白质），ＰＧＭＰｉ 在 ＨｕｍａｎＭＤ 和 Ｈｕ⁃ ｍａｎＥＫＣ 数据集上能够报告最多的正确蛋白质。 其 他 ２ 个推断算法也能在某些数据集上有类似的表现 但没有 ＰＧＭＰｉ 多。 具体的数据是：不报告任何错误 的蛋白质时，Ｆｉｄｏ 在一个数据集上报告最多的正确 的蛋白质，而 ＭＳＢａｙｅｓＰｒｏ 在所有数据集都没有这样 的表现。 图 ４ 绘制了 ３ 个蛋白质推断方法 ＰＧＭＰｉ、Ｆｉｄｏ 和 ＭＳＢａｙｅｓＰｒｏ 在不同 ｑ＿ｖａｌｕｅ 下正确报告的蛋白质 的个数。 整体来说，ＰＧＭＰｉ 在 ６ 个数据集上表现比 较稳定，尤其是在 ＤＭＥ、ＨｕｍａｎＥＫＣ 及 Ｙｅａｓｔ 等 ３ 个 数据集上都是表现最好的；在 ＨｕｍａｎＭＤ 和 Ｓｉｇｍａ＿ ４９ 数据集上当 ｑ＿ｖａｌｕｅ 较小时，表现不是最优的，但 随着 ｑ＿ｖａｌｕｅ 的增加，ＰＧＭＰｉ 较 ＭＳＢａｙｅｓＰｒｏ 和 Ｆｉｄｏ 而言都是最先达到最优的；１８ ｍｉｘｔｕｒｅｓ 中 ＰＧＭＰｉ 是 表现次优的。 而 Ｆｉｄｏ 虽然在 １８ ｍｉｘｔｕｒｅｓ 数据集中 明显优于其他 ２ 个算法，但是在其他数据集中的表 现都不是太理想，尤其是在 Ｙｅａｓｔ 数据集中的表现 远远落后于其他 ２ 个算法，这也表明 Ｆｉｄｏ 在针对个 别数据集来说可能会比较适合，模型相对来说不稳 定。 对于 ＭＳＢａｙｅｓＰｒｏ，该算法在 Ｓｉｇｍａ＿４９ 数据集 上，当 ｑ＿ｖａｌｕｅ 较小时，相比于 ＰＧＭＰｉ 和 Ｆｉｄｏ 有不 太显著的优势，但随着 ｑ＿ｖａｌｕｅ 的增加就被 ＰＧＭＰｉ 超过；在 ＤＭＥ 和 ＨｕｍａｎＥＫＣ 两个数据集上 ＭＳＢａｙｅ⁃ ｓＰｒｏ 都显著弱于其他 ２ 个算法，表现相对较差，尤其 是在 ＨｕｍａｎＥＫＣ 数据集上，ＰＧＭＰｉ 和 Ｆｉｄｏ 都在 ｑ＿ ｖａｌｕｅ ＝ ０．０３ 时可以全部鉴定出样品中存在的蛋白 质，而对于 ＭＳＢａｙｅｓＰｒｏ， 当 ｑ＿ｖａｌｕｅ ＝ ０．０３５ 时还是 没能达到最优解，由于其效果较差，为了便于比较将 ｑ＿ ｖａｌｕｅ ＞ ０． ０３５ 的部分去掉了； ＭＳＢａｙｅｓＰｒｏ 只在 Ｙｅａｓｔ 以及 Ｓｉｇｍａ＿４９ 这 ２ 个数据集上和表现最好的 方法相比，没有明显的差异；总的来说，ＭＳＢａｙｅｓＰｒｏ 在 ６ 个数据集中的表现相比于其他蛋白质推断方法 ·３８０· 智 能 系 统 学 报 第 １１ 卷
第3期 赵璨，等：基于概率图模型的蛋白质推断算法 ·381- 不太稳定。 8 ×10 7.5 ×10 ×10 Fido 4r MSBayes Fido 6 PGMPi 5.0 MSBayes Fido PGMPi MSBayes 2.5 PGMPi 0 0.04 0.080.120.16 0.0080.0160.0240.032 0.030.060.090.12 q_value q_value q_value (a)DME (b)HumanEKC (c)HumanMD 12 45 20 9 36 15 之 Fido Fido 6 Fido -MSBaves 三10 -MSBayes MSBayes -PGMPi -PGMPi 3 -PGMPi 9 5 ×10 2.5 5.0 7.5 10.0 015 0.300.450.60 0.150300450.60 g_value q_value g value (d)Yeast (e)Sigma49 (f)18 Mixtures 图43种不同蛋白质推断算法的推断结果 Fig.4 Performance comparison among three different protein inference algorithms 2.4参数影响 其结果有着相对明显的影响，随着参数的增加，效果 由于PGMPi只有一个参数，同MSBayesPro及 相对来说有些下降。总体来说，模型参数在5个数 Fido两个模型的对比实验是在a=0.5的情况下进 据集上表现相对稳定，而对于DME参数对于结果有 行的，但其他参数对推断效果是否有明显的影响，即 着些许的影响，这是由于数据集的不同导致出现的 模型对参数是否是敏感的还未可知。所以本文对参 差异，所以参数可能导致结果有些许的波动，但在可 数在各个数据集上的影响做了对比实验，以测试模 接受的范围内。因此该模型对参数是不敏感的、相 型对参数的敏感度。 对稳定的。关于参数a的取值范围，由于参数α表 由于生物信息的多样性以及不确定性，导致同 示的是某个候选蛋白质存在其对应的一个肽段被检 模型对于相同参数在不同数据集的表现不一，同 测到的概率。理论上来说参数α的取值范围应为 时同一模型不同参数对于结果也有着或多或少的影 (0,1],但是实验证明当参数a=0.1时在某些数据 响。图5报告的是PGMPi模型中不同参数在6个 集上就不能正确地推断蛋白质，其最后的结果中存 数据集上对于结果的影响，本文给定模型的参数取 在某些蛋白质的后验概率为无意义的数(NaN)。导 值区间为ae[0.2,0.8],实验选取了0.2、0.3、0.5、 致这种情况的原因，可能有2种情况：一种是由于生 0.7以及0.8等5个不同参数并绘制出在不同数据集 物样本酶解的过程产生的，酶解过程为生物过程，我 上的结果对比图（如图5所示），可以看出该模型不 们无法精确地测量，在这个过程中，蛋白质酶解的程 同参数的设置对于结果的影响不是很明显，也就是 度对于结果的预测也有着很大的影响，比如可能存 说模型对于参数是不敏感的、相对稳定的。具体而 在这样一种情况，就是某个蛋白质包含肽段j,但是 言，在18 mixtures、Yeast以及Sigma49数据集上不 酶解过程中将肽段水解成较小的氨基酸片段，这样 同参数对于推断的结果几乎没有影响：在H山- 就鉴定不到该肽段的存在，特别是在这个蛋白质只 manEKC和HumanMD两个数据集上，可以看出，当 含有这一种肽段的情况下，就无法鉴定蛋白质的存 参数α=0.2时，其结果相对来说较好，但整体来说 在。另一种可能是由于数据集的不同，也就是产生 相对稳定，波动不大：而对于DME数据集，参数对于 数据集中候选蛋白质的生物组织的不同，蛋白质酶
不太稳定。 图 ４ ３ 种不同蛋白质推断算法的推断结果 Ｆｉｇ．４ Ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ａｍｏｎｇ ｔｈｒｅｅ ｄｉｆｆｅｒｅｎｔ ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ａｌｇｏｒｉｔｈｍｓ ２．４ 参数影响 由于 ＰＧＭＰｉ 只有一个参数，同 ＭＳＢａｙｅｓＰｒｏ 及 Ｆｉｄｏ 两个模型的对比实验是在 α ＝ ０．５ 的情况下进 行的，但其他参数对推断效果是否有明显的影响，即 模型对参数是否是敏感的还未可知。 所以本文对参 数在各个数据集上的影响做了对比实验，以测试模 型对参数的敏感度。 由于生物信息的多样性以及不确定性，导致同 一模型对于相同参数在不同数据集的表现不一，同 时同一模型不同参数对于结果也有着或多或少的影 响。 图 ５ 报告的是 ＰＧＭＰｉ 模型中不同参数在 ６ 个 数据集上对于结果的影响，本文给定模型的参数取 值区间为 α∈［０．２，０．８］，实验选取了 ０．２、０．３、０．５、 ０．７以及 ０．８ 等 ５ 个不同参数并绘制出在不同数据集 上的结果对比图（如图 ５ 所示），可以看出该模型不 同参数的设置对于结果的影响不是很明显，也就是 说模型对于参数是不敏感的、相对稳定的。 具体而 言，在 １８ ｍｉｘｔｕｒｅｓ、Ｙｅａｓｔ 以及 Ｓｉｇｍａ４９ 数据集上不 同参数 对 于 推 断 的 结 果 几 乎 没 有 影 响； 在 Ｈｕ⁃ ｍａｎＥＫＣ 和 ＨｕｍａｎＭＤ 两个数据集上，可以看出，当 参数 α ＝ ０．２ 时，其结果相对来说较好，但整体来说 相对稳定，波动不大；而对于 ＤＭＥ 数据集，参数对于 其结果有着相对明显的影响，随着参数的增加，效果 相对来说有些下降。 总体来说，模型参数在 ５ 个数 据集上表现相对稳定，而对于 ＤＭＥ 参数对于结果有 着些许的影响，这是由于数据集的不同导致出现的 差异，所以参数可能导致结果有些许的波动，但在可 接受的范围内。 因此该模型对参数是不敏感的、相 对稳定的。 关于参数 α 的取值范围，由于参数 α 表 示的是某个候选蛋白质存在其对应的一个肽段被检 测到的概率。 理论上来说参数 α 的取值范围应为 （０，１］，但是实验证明当参数 α ＝ ０．１ 时在某些数据 集上就不能正确地推断蛋白质，其最后的结果中存 在某些蛋白质的后验概率为无意义的数（ＮａＮ）。 导 致这种情况的原因，可能有 ２ 种情况：一种是由于生 物样本酶解的过程产生的，酶解过程为生物过程，我 们无法精确地测量，在这个过程中，蛋白质酶解的程 度对于结果的预测也有着很大的影响，比如可能存 在这样一种情况，就是某个蛋白质包含肽段 ｊ，但是 酶解过程中将肽段水解成较小的氨基酸片段，这样 就鉴定不到该肽段的存在，特别是在这个蛋白质只 含有这一种肽段的情况下，就无法鉴定蛋白质的存 在。 另一种可能是由于数据集的不同，也就是产生 数据集中候选蛋白质的生物组织的不同，蛋白质酶 第 ３ 期 赵璨，等：基于概率图模型的蛋白质推断算法 ·３８１·
·382. 智能系统学报 第11卷 解所需的水解酶不一样，导致酶解效果以及酶解程 结果表明，虽然对于参数的变化模型效果表现比较 度不同，对于蛋白质包含的肽段可能没有酶解出来， 稳定，但是仍可以看出当参数α=0.2时，其推断结 也可能酶解成更小的氨基酸片段。从而导致推断结 果会相对更好一些，也就是说候选蛋白质产生其对 果有误差，甚至出现无意义的数。综合各种情况，本 应的肽段的概率小于0.2，从这也侧面说明了生物酶 文选取了一个比较合理的参数取值[0.2,0.8]，实验 解过程的随机性、不彻底性。 ×109 ×10 0.2 75m 03 0 50 0.2 02 --0.8 2 —03 -03 25 -0.5 0.5 0.7 0.7 -…08 --08 0.040.080.120.16 0.0080.0160.0240.032 0.030.060.090.12 paramater paramater paramater (a)DME (b)HumanEKC (c)HumanMD ×10 12 45 20 9 36 15 02 27 0.2 02 —0.3 -0.3 三10 —03 —0.5 05 —0.5 0.7 9 0.7 5 0.7 -0.8 0.8 -0.8 0.0250.0500.07506 0.150.300.450.60 0.150.300.450.60 paramater paramater paramater (d)Yeast (e)Sigma49 (f)18 Mixtures 图5参数对于模型结果的影响 Fig.5 The effect of the parameter on the identification performance 3结束语 参考文献： 蛋白质组学的一个重要目标是能够快速准确地 [1]ALTELAAR A F M,MUNOZ J,HECK A J R.Next-gener- 进行蛋白质鉴定，即确定一个样本中真实存在的蛋 ation proteomics:towards an integrative view of proteome 白质，故蛋白质鉴定问题得到了许多研究人员的关 dynamics[J].Nature reviews genetics,2013,14(1):35- 注。本文将蛋白质推断问题抽象为概率图求解问 48 题，并提出了一种基于概率图模型的方法(PGMP) [2]NOBLE W S,MACCOSS M J.Computational and statistical analysis of protein mass spectrometry data[J].PLoS comput 来解决蛋白质推断问题。该模型首先给出了质谱、 biol.2012,8(1):e1002296-e1002296. 肽段以及候选蛋白质的联合概率分布，根据给定的 [3]AEBERSOLD R,GOODLETT D R.Mass spectrometry in 一些假设条件以及联合概率确定每个蛋白质的后验 proteomics[]].Chemical reviews,2001,101(2):269- 概率分布，从而将求解具有最大联合概率分布的候 296 选蛋白质子集转化为寻找一个具有最大后验的蛋白 [4]PENG J,ELIAS J E,THOREEN CC,et al.Evaluation of 质配置问题，最后采用吉布斯抽样来对模型进行求 multidimensional chromatography coupled with tandem mass 解，从而获得具有最大后验的最优蛋白质配置。实 spectrometry (LC/LC-MS/MS)for large-scale protein anal- 验结果表明，本文提出的PGMPi的推断表现不弱于 ysis:the yeast proteome[.Journal of proteome research, 其他蛋白质推断算法，并且同Fido和MSBayesPro 2003,2(1):43-50. 相比，表现比较稳定。特别是，PGMPi只有一个参 [5]HUNT D F,YATES J R,SHABANOWITZ J,et al.Protein 数，并且实验表明PGMPi在大多数数据集上对参数 sequencing by tandem mass spectrometry[J].Proceedings of 是不敏感的，不受参数设定的影响。 the national academy of sciences,1986,83(17):6233- 6237
解所需的水解酶不一样，导致酶解效果以及酶解程 度不同，对于蛋白质包含的肽段可能没有酶解出来， 也可能酶解成更小的氨基酸片段。 从而导致推断结 果有误差，甚至出现无意义的数。 综合各种情况，本 文选取了一个比较合理的参数取值［０．２，０．８］，实验 结果表明，虽然对于参数的变化模型效果表现比较 稳定，但是仍可以看出当参数 α ＝ ０．２ 时，其推断结 果会相对更好一些，也就是说候选蛋白质产生其对 应的肽段的概率小于 ０．２，从这也侧面说明了生物酶 解过程的随机性、不彻底性。 图 ５ 参数对于模型结果的影响 Ｆｉｇ．５ Ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｔｈｅ ｐａｒａｍｅｔｅｒ ｏｎ ｔｈｅ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ ３ 结束语 蛋白质组学的一个重要目标是能够快速准确地 进行蛋白质鉴定，即确定一个样本中真实存在的蛋 白质，故蛋白质鉴定问题得到了许多研究人员的关 注。 本文将蛋白质推断问题抽象为概率图求解问 题，并提出了一种基于概率图模型的方法（ＰＧＭＰｉ） 来解决蛋白质推断问题。 该模型首先给出了质谱、 肽段以及候选蛋白质的联合概率分布，根据给定的 一些假设条件以及联合概率确定每个蛋白质的后验 概率分布，从而将求解具有最大联合概率分布的候 选蛋白质子集转化为寻找一个具有最大后验的蛋白 质配置问题，最后采用吉布斯抽样来对模型进行求 解，从而获得具有最大后验的最优蛋白质配置。 实 验结果表明，本文提出的 ＰＧＭＰｉ 的推断表现不弱于 其他蛋白质推断算法，并且同 Ｆｉｄｏ 和 ＭＳＢａｙｅｓＰｒｏ 相比，表现比较稳定。 特别是，ＰＧＭＰｉ 只有一个参 数，并且实验表明 ＰＧＭＰｉ 在大多数数据集上对参数 是不敏感的，不受参数设定的影响。 参考文献： ［１］ＡＬＴＥＬＡＡＲ Ａ Ｆ Ｍ， ＭＵＮＯＺ Ｊ， ＨＥＣＫ Ａ Ｊ Ｒ． Ｎｅｘｔ－ｇｅｎｅｒ⁃ ａｔｉｏｎ ｐｒｏｔｅｏｍｉｃｓ： ｔｏｗａｒｄｓ ａｎ ｉｎｔｅｇｒａｔｉｖｅ ｖｉｅｗ ｏｆ ｐｒｏｔｅｏｍｅ ｄｙｎａｍｉｃｓ［Ｊ］． Ｎａｔｕｒｅ ｒｅｖｉｅｗｓ ｇｅｎｅｔｉｃｓ， ２０１３， １４（１）： ３５⁃ ４８． ［２］ＮＯＢＬＥ Ｗ Ｓ， ＭＡＣＣＯＳＳ Ｍ Ｊ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ａｎｄ ｓｔａｔｉｓｔｉｃａｌ ａｎａｌｙｓｉｓ ｏｆ ｐｒｏｔｅｉｎ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ ｄａｔａ［Ｊ］． ＰＬｏＳ ｃｏｍｐｕｔ ｂｉｏｌ， ２０１２， ８（１）： ｅ１００２２９６⁃ｅ１００２２９６． ［３］ ＡＥＢＥＲＳＯＬＤ Ｒ， ＧＯＯＤＬＥＴＴ Ｄ Ｒ． Ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ ｉｎ ｐｒｏｔｅｏｍｉｃｓ［ Ｊ］． Ｃｈｅｍｉｃａｌ ｒｅｖｉｅｗｓ， ２００１， １０１ （ ２）： ２６９⁃ ２９６． ［４］ＰＥＮＧ Ｊ， ＥＬＩＡＳ Ｊ Ｅ， ＴＨＯＲＥＥＮ Ｃ Ｃ， ｅｔ ａｌ． Ｅｖａｌｕａｔｉｏｎ ｏｆ ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ ｃｈｒｏｍａｔｏｇｒａｐｈｙ ｃｏｕｐｌｅｄ ｗｉｔｈ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ （ＬＣ／ ＬＣ⁃ＭＳ ／ ＭＳ） ｆｏｒ ｌａｒｇｅ⁃ｓｃａｌｅ ｐｒｏｔｅｉｎ ａｎａｌ⁃ ｙｓｉｓ： ｔｈｅ ｙｅａｓｔ ｐｒｏｔｅｏｍｅ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｐｒｏｔｅｏｍｅ ｒｅｓｅａｒｃｈ， ２００３， ２（１）： ４３⁃５０． ［５］ＨＵＮＴ Ｄ Ｆ， ＹＡＴＥＳ Ｊ Ｒ， ＳＨＡＢＡＮＯＷＩＴＺ Ｊ， ｅｔ ａｌ． Ｐｒｏｔｅｉｎ ｓｅｑｕｅｎｃｉｎｇ ｂｙ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ［Ｊ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎａｔｉｏｎａｌ ａｃａｄｅｍｙ ｏｆ ｓｃｉｅｎｃｅｓ， １９８６， ８３ （ １７）： ６２３３⁃ ６２３７． ·３８２· 智 能 系 统 学 报 第 １１ 卷
第3期 赵璨，等：基于概率图模型的蛋白质推断算法 .383. [6]NESVIZHSKII A I,KELLER A,KOLKER E,et al.A sta- (Methodological),1995,57(1):289-300. tistical model for identifying proteins by tandem mass spec- [18]TABB D L,FERNANDO C G,CHAMBERS M C.Myr- trometry[J].Analytical chemistry,2003,75(17):4646- iMatch:highly accurate tandem mass spectral peptide i- 4658. dentification by multivariate hypergeometric analysis[J]. [7]SERANG O,MACCOSS M J,NOBLE W S.Efficient mar- Journal of proteome research,2007,6(2):654-661. ginalization to compute protein posterior probabilities from [19]RAMAKRISHNAN S R,VOGEL C,KWON T,et al.Min- shotgun mass spectrometry data[J].Journal of proteome re- ing gene functional networks to improve mass-spectrometry- 8 earch,2010,9(10):5346-5357. based protein identification[J].Bioinformatics,2009,25 [8]SHEN C,WANG Z,SHANKAR G,et al.A hierarchical (22):2955-2961. statistical model to assess the confidence of peptides and [20]BRUNNER E,AHRENS C H,MOHANTY S,et al.A proteins inferred from tandem mass spectrometry[].Bioin- high-quality catalog of the Drosophila melanogaster pro- formatics,2008,24(2):202-208. teome[J].Nature biotechnology,2007,25(5):576-583. [9]LI Y F,ARNOLD R J,LI Y,et al.A Bay esian approach [21]RAMAKRISHNAN S R,VOGEL C,PRINCE J T,et al. to protein inference problem in shotgun proteomics[.Jour- Integrating shotgun proteomics and mRNA expression data nal of computational biology,2009,16(8):1183-1193. to improve protein identification[J].Bioinformatics,2009, [10]MA Z Q,DASARI S,CHAMBERS M C,et al.IDPicker 25(11):1397-1403. 2.0:Improved protein assembly with high discrimination [22]HUANG T,HE Z.A linear programming model for protein peptide identification filtering[].Journal of proteome re- inference problem in shotgun proteomics[J].Bioinformat- search,2009,8(8):3872-3881. ics,2012,28(22):2956-2962. [11]CLAASSEN M.Inference and validation of protein identifi- [23]CRAIG R,BEAVIS R C.TANDEM:matching proteins cations[J].Molecular cellular proteomics,2012,11 with tandem mass spectra[J].Bioinformatics,2004,20 (11):1097-1104. (9):1466-1467. [12]HUANG T,WANG J,YU W,et al.Protein inference:a [24]KELLER A,NESVIZHSKII A I,KOLKER E,et al.Em- review[J].Briefings in bioinformatics,2012,13(5): pirical statistical model to estimate the accuracy of peptide 586-614. identifications made by MS/MS and database searchJ. [13]LI Y F,RADIVOJAC P.Computational approaches to pro- Analytical chemistry,2002,74(20):5383-5392 tein inference in shotgun proteomics[J].BMC bioinformat- 作者简介： ics,2012,13:1-17. 赵璨，女，出生于1991年，硕士研 [14]CHENG QIANG,CHEN FENG,DONG JIAN WU,et al. 究生，主要研究方向是生物信息学、蛋 Variational approximate inference methods for graphical 白质推断以及PPI网络推断。 models[J].Acta Automatica Sinica,2012,38(11):1721- 1734(in Chinese). 程强，陈峰，董建武等，概率图模型中的变分近似推理 方法[J].自动化学报，2012,38(11)：1721-1734 段琼，男，1990年生，硕士研究生 [15]COOPER G F,HERSKOVITS E.A Bayesian method for 主要研究方向为生物信息学、基于自顶 the induction of probabilistic networks from data[].Ma- 向下的蛋白质推断。 chine learning,1992,9(4):309-347. [16]HASTIE T,TIBSHIRANI R,FRIEDMAN J,et al.The el- ements of statistical leaming:data mining,inference and prediction[]].The mathematical intelligencer,2005,27 何增有，男，1976年生，副教授，主 (2):83-85. 要研究方向为数据挖掘、生物信息学， [17]BENJAMINI Y,HOCHBERG Y.Controlling the false dis- 学术论文均发表在该领域的顶级期刊 covery rate:a practical and powerful approach to multiple 或会议上，出版学术专著1部。 testing[J].Journal of the royal statistical society.series B
［６］ＮＥＳＶＩＺＨＳＫＩＩ Ａ Ｉ， ＫＥＬＬＥＲ Ａ， ＫＯＬＫＥＲ Ｅ， ｅｔ ａｌ． Ａ ｓｔａ⁃ ｔｉｓｔｉｃａｌ ｍｏｄｅｌ ｆｏｒ ｉｄｅｎｔｉｆｙｉｎｇ ｐｒｏｔｅｉｎｓ ｂｙ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃ⁃ ｔｒｏｍｅｔｒｙ［Ｊ］． Ａｎａｌｙｔｉｃａｌ ｃｈｅｍｉｓｔｒｙ， ２００３， ７５（ １７）： ４６４６⁃ ４６５８． ［７］ＳＥＲＡＮＧ Ｏ， ＭＡＣＣＯＳＳ Ｍ Ｊ， ＮＯＢＬＥ Ｗ Ｓ． Ｅｆｆｉｃｉｅｎｔ ｍａｒ⁃ ｇｉｎａｌｉｚａｔｉｏｎ ｔｏ ｃｏｍｐｕｔｅ ｐｒｏｔｅｉｎ ｐｏｓｔｅｒｉｏｒ ｐｒｏｂａｂｉｌｉｔｉｅｓ ｆｒｏｍ ｓｈｏｔｇｕｎ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ ｄａｔａ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｐｒｏｔｅｏｍｅ ｒｅ⁃ ｓｅａｒｃｈ， ２０１０， ９（１０）： ５３４６⁃５３５７． ［８］ＳＨＥＮ Ｃ， ＷＡＮＧ Ｚ， ＳＨＡＮＫＡＲ Ｇ， ｅｔ ａｌ． Ａ ｈｉｅｒａｒｃｈｉｃａｌ ｓｔａｔｉｓｔｉｃａｌ ｍｏｄｅｌ ｔｏ ａｓｓｅｓｓ ｔｈｅ ｃｏｎｆｉｄｅｎｃｅ ｏｆ ｐｅｐｔｉｄｅｓ ａｎｄ ｐｒｏｔｅｉｎｓ ｉｎｆｅｒｒｅｄ ｆｒｏｍ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ［ Ｊ］． Ｂｉｏｉｎ⁃ ｆｏｒｍａｔｉｃｓ， ２００８， ２４（２）： ２０２⁃２０８． ［９］ＬＩ Ｙ Ｆ， ＡＲＮＯＬＤ Ｒ Ｊ， ＬＩ Ｙ， ｅｔ ａｌ． Ａ Ｂａｙ ｅｓｉａｎ ａｐｐｒｏａｃｈ ｔｏ ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ｐｒｏｂｌｅｍ ｉｎ ｓｈｏｔｇｕｎ ｐｒｏｔｅｏｍｉｃｓ［Ｊ］． Ｊｏｕｒ⁃ ｎａｌ ｏｆ ｃｏｍｐｕｔａｔｉｏｎａｌ ｂｉｏｌｏｇｙ， ２００９， １６（８）： １１８３⁃１１９３． ［１０］ＭＡ Ｚ Ｑ， ＤＡＳＡＲＩ Ｓ， ＣＨＡＭＢＥＲＳ Ｍ Ｃ， ｅｔ ａｌ． ＩＤＰｉｃｋｅｒ ２．０： Ｉｍｐｒｏｖｅｄ ｐｒｏｔｅｉｎ ａｓｓｅｍｂｌｙ ｗｉｔｈ ｈｉｇｈ ｄｉｓｃｒｉｍｉｎａｔｉｏｎ ｐｅｐｔｉｄｅ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｆｉｌｔｅｒｉｎｇ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｐｒｏｔｅｏｍｅ ｒｅ⁃ ｓｅａｒｃｈ， ２００９， ８（８）： ３８７２⁃３８８１． ［１１］ＣＬＡＡＳＳＥＮ Ｍ． Ｉｎｆｅｒｅｎｃｅ ａｎｄ ｖａｌｉｄａｔｉｏｎ ｏｆ ｐｒｏｔｅｉｎ ｉｄｅｎｔｉｆｉ⁃ ｃａｔｉｏｎｓ［ Ｊ］． Ｍｏｌｅｃｕｌａｒ ＆ ｃｅｌｌｕｌａｒ ｐｒｏｔｅｏｍｉｃｓ， ２０１２， １１ （１１）： １０９７⁃１１０４． ［１２］ＨＵＡＮＧ Ｔ， ＷＡＮＧ Ｊ， ＹＵ Ｗ， ｅｔ ａｌ． Ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ： ａ ｒｅｖｉｅｗ［ Ｊ］． Ｂｒｉｅｆｉｎｇｓ ｉｎ ｂｉｏｉｎｆｏｒｍａｔｉｃｓ， ２０１２， １３ （ ５）： ５８６⁃６１４． ［１３］ＬＩ Ｙ Ｆ， ＲＡＤＩＶＯＪＡＣ Ｐ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ａｐｐｒｏａｃｈｅｓ ｔｏ ｐｒｏ⁃ ｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ｉｎ ｓｈｏｔｇｕｎ ｐｒｏｔｅｏｍｉｃｓ［Ｊ］． ＢＭＣ ｂｉｏｉｎｆｏｒｍａｔ⁃ ｉｃｓ， ２０１２， １３： １⁃１７． ［１４］ＣＨＥＮＧ ＱＩＡＮＧ， ＣＨＥＮ ＦＥＮＧ， ＤＯＮＧ ＪＩＡＮ ＷＵ， ｅｔ ａｌ． Ｖａｒｉａｔｉｏｎａｌ ａｐｐｒｏｘｉｍａｔｅ ｉｎｆｅｒｅｎｃｅ ｍｅｔｈｏｄｓ ｆｏｒ ｇｒａｐｈｉｃａｌ ｍｏｄｅｌｓ［Ｊ］． Ａｃｔａ Ａｕｔｏｍａｔｉｃａ Ｓｉｎｉｃａ， ２０１２，３８（１１）： １７２１⁃ １７３４（ｉｎ Ｃｈｉｎｅｓｅ）． 程强，陈峰，董建武等，概率图模型中的变分近似推理 方法［Ｊ］． 自动化学报， ２０１２， ３８（１１）： １７２１⁃１７３４． ［１５］ＣＯＯＰＥＲ Ｇ Ｆ， ＨＥＲＳＫＯＶＩＴＳ Ｅ． Ａ Ｂａｙｅｓｉａｎ ｍｅｔｈｏｄ ｆｏｒ ｔｈｅ ｉｎｄｕｃｔｉｏｎ ｏｆ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｎｅｔｗｏｒｋｓ ｆｒｏｍ ｄａｔａ［ Ｊ］． Ｍａ⁃ ｃｈｉｎｅ ｌｅａｒｎｉｎｇ， １９９２， ９（４）： ３０９⁃３４７． ［１６］ＨＡＳＴＩＥ Ｔ， ＴＩＢＳＨＩＲＡＮＩ Ｒ， ＦＲＩＥＤＭＡＮ Ｊ， ｅｔ ａｌ． Ｔｈｅ ｅｌ⁃ ｅｍｅｎｔｓ ｏｆ ｓｔａｔｉｓｔｉｃａｌ ｌｅａｒｎｉｎｇ： ｄａｔａ ｍｉｎｉｎｇ， ｉｎｆｅｒｅｎｃｅ ａｎｄ ｐｒｅｄｉｃｔｉｏｎ［ Ｊ］． Ｔｈｅ ｍａｔｈｅｍａｔｉｃａｌ ｉｎｔｅｌｌｉｇｅｎｃｅｒ， ２００５， ２７ （２）： ８３⁃８５． ［１７］ＢＥＮＪＡＭＩＮＩ Ｙ， ＨＯＣＨＢＥＲＧ Ｙ． Ｃｏｎｔｒｏｌｌｉｎｇ ｔｈｅ ｆａｌｓｅ ｄｉｓ⁃ ｃｏｖｅｒｙ ｒａｔｅ： ａ ｐｒａｃｔｉｃａｌ ａｎｄ ｐｏｗｅｒｆｕｌ ａｐｐｒｏａｃｈ ｔｏ ｍｕｌｔｉｐｌｅ ｔｅｓｔｉｎｇ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ｒｏｙａｌ ｓｔａｔｉｓｔｉｃａｌ ｓｏｃｉｅｔｙ． ｓｅｒｉｅｓ Ｂ （Ｍｅｔｈｏｄｏｌｏｇｉｃａｌ）， １９９５， ５７（１）： ２８９⁃３００． ［１８］ＴＡＢＢ Ｄ Ｌ， ＦＥＲＮＡＮＤＯ Ｃ Ｇ， ＣＨＡＭＢＥＲＳ Ｍ Ｃ． Ｍｙｒ⁃ ｉＭａｔｃｈ： ｈｉｇｈｌｙ ａｃｃｕｒａｔｅ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃｔｒａｌ ｐｅｐｔｉｄｅ ｉ⁃ ｄｅｎｔｉｆｉｃａｔｉｏｎ ｂｙ ｍｕｌｔｉｖａｒｉａｔｅ ｈｙｐｅｒｇｅｏｍｅｔｒｉｃ ａｎａｌｙｓｉｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｐｒｏｔｅｏｍｅ ｒｅｓｅａｒｃｈ， ２００７， ６（２）： ６５４⁃６６１． ［１９］ＲＡＭＡＫＲＩＳＨＮＡＮ Ｓ Ｒ， ＶＯＧＥＬ Ｃ， ＫＷＯＮ Ｔ， ｅｔ ａｌ． Ｍｉｎ⁃ ｉｎｇ ｇｅｎｅ ｆｕｎｃｔｉｏｎａｌ ｎｅｔｗｏｒｋｓ ｔｏ ｉｍｐｒｏｖｅ ｍａｓｓ⁃ｓｐｅｃｔｒｏｍｅｔｒｙ⁃ ｂａｓｅｄ ｐｒｏｔｅｉｎ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ［ Ｊ］． Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ， ２００９， ２５ （２２）： ２９５５⁃２９６１． ［２０］ ＢＲＵＮＮＥＲ Ｅ， ＡＨＲＥＮＳ Ｃ Ｈ， ＭＯＨＡＮＴＹ Ｓ， ｅｔ ａｌ． Ａ ｈｉｇｈ⁃ｑｕａｌｉｔｙ ｃａｔａｌｏｇ ｏｆ ｔｈｅ Ｄｒｏｓｏｐｈｉｌａ ｍｅｌａｎｏｇａｓｔｅｒ ｐｒｏ⁃ ｔｅｏｍｅ［Ｊ］． Ｎａｔｕｒｅ ｂｉｏｔｅｃｈｎｏｌｏｇｙ， ２００７， ２５（５）： ５７６⁃５８３． ［２１］ＲＡＭＡＫＲＩＳＨＮＡＮ Ｓ Ｒ， ＶＯＧＥＬ Ｃ， ＰＲＩＮＣＥ Ｊ Ｔ， ｅｔ ａｌ． Ｉｎｔｅｇｒａｔｉｎｇ ｓｈｏｔｇｕｎ ｐｒｏｔｅｏｍｉｃｓ ａｎｄ ｍＲＮＡ ｅｘｐｒｅｓｓｉｏｎ ｄａｔａ ｔｏ ｉｍｐｒｏｖｅ ｐｒｏｔｅｉｎ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ［Ｊ］． Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ， ２００９， ２５（１１）： １３９７⁃１４０３． ［２２］ＨＵＡＮＧ Ｔ， ＨＥ Ｚ． Ａ ｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌ ｆｏｒ ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ｐｒｏｂｌｅｍ ｉｎ ｓｈｏｔｇｕｎ ｐｒｏｔｅｏｍｉｃｓ［ Ｊ］． Ｂｉｏｉｎｆｏｒｍａｔ⁃ ｉｃｓ， ２０１２， ２８（２２）： ２９５６⁃２９６２． ［２３］ ＣＲＡＩＧ Ｒ， ＢＥＡＶＩＳ Ｒ Ｃ． ＴＡＮＤＥＭ： ｍａｔｃｈｉｎｇ ｐｒｏｔｅｉｎｓ ｗｉｔｈ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃｔｒａ［ Ｊ］． Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ， ２００４， ２０ （９）： １４６６⁃１４６７． ［２４］ＫＥＬＬＥＲ Ａ， ＮＥＳＶＩＺＨＳＫＩＩ Ａ Ｉ， ＫＯＬＫＥＲ Ｅ， ｅｔ ａｌ． Ｅｍ⁃ ｐｉｒｉｃａｌ ｓｔａｔｉｓｔｉｃａｌ ｍｏｄｅｌ ｔｏ ｅｓｔｉｍａｔｅ ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｐｅｐｔｉｄｅ ｉｄｅｎｔｉｆｉｃａｔｉｏｎｓ ｍａｄｅ ｂｙ ＭＳ ／ ＭＳ ａｎｄ ｄａｔａｂａｓｅ ｓｅａｒｃｈ ［ Ｊ］． Ａｎａｌｙｔｉｃａｌ ｃｈｅｍｉｓｔｒｙ， ２００２， ７４（２０）： ５３８３⁃５３９２ 作者简介： 赵璨，女，出生于 １９９１ 年，硕士研 究生，主要研究方向是生物信息学、蛋 白质推断以及 ＰＰＩ 网络推断。 段琼，男，１９９０ 年生，硕士研究生， 主要研究方向为生物信息学、基于自顶 向下的蛋白质推断。 何增有，男，１９７６ 年生，副教授，主 要研究方向为数据挖掘、生物信息学， 学术论文均发表在该领域的顶级期刊 或会议上，出版学术专著 １ 部。 第 ３ 期 赵璨，等：基于概率图模型的蛋白质推断算法 ·３８３·