第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),从而推断出真实存在于样本中的蛋白质 算法的表现。该策略的主要思想为：在包含所有目２） 假设不同的蛋白质对于其对应鉴定肽的贡 献是独立的； Ｐ（ｙ１ ，ｙ２ ，…，ｙｎ ｜ ｘ１ ，ｘ２ ，…，ｘｍ ） ＝ ∏ ｊ ［１ － Ｐ（ｙｊ ＝ １ ｜ ｘ１ ，ｘ２ ，…，ｘｍ ）］ １－ｙｊ· Ｐ（ ｙ ｊ ＝ １ ｜ ｘ１ ，ｘ２ ，…，ｘｍ ） ｙｊ ＝ ∏ ｊ ［∏ｉ∈Ｎｊ （１ － α） ｘｉ ］ １－ｙｊ ［ １ － ∏ｉ∈Ｎｊ （１ － α） ｘｉ ］ ｙｊ （３） 式（３）中，由于 ｙｊ 只有 ０ 和 １ 两种取值，所以可以表 示为 Ｐ（ｙ１ ，ｙ２ ，…，ｙｎ ｜ ｘ１ ，ｘ２ ，…，ｘｍ ） ＝ ∏ ｊ ｛（１ － ｙｊ）［∏ｉ∈Ｎｊ （１ － α） ｘｉ ］ ＋ ｙｊ［１ － ∏ｉ∈Ｎｊ （１ － α） ｘｉ ］｝ （４） Ｐ（ｙｊ ｜ ｘ１ ，…，ｘｍ ） ＝ （１ － ｙｊ）［∏ｉ∈Ｎｊ （１ － α） ｘｉ］ ＋ ｙｊ［１ － ∏ｉ∈Ｎｊ （１ － α） ｘｉ］ （５） 式中：Ｎｊ 表示可能产生肽段 ｊ 的候选蛋白质的集合， α 为对应参数。 ３） 欲求得可能存在于样本中的蛋白质子集，需 使得联合概率最大化。 模型可以转化为寻找最大后 验蛋白质配置的问题，对于每个蛋白质的后验概率： Ｐ（ｘｉ ｜ Ｓ） ＝ Ｘ∑：ｘｉ ＝ １∏ｘｉ ｐ（ｘｉ）∏ ｊ∈Ｍｉ Ｐ（ｙｊ ｜ Ｘ）∏ ｊ∈Ｍｉ Ｐ（ｙｊ ｜ ｓｊ） ∑Ｘ ∏ｘｉ ｐ（ｘｉ）∏ ｊ∈Ｍｉ Ｐ（ｙｊ ｜ Ｘ）∏ ｊ∈Ｍｉ Ｐ（ｙｊ ｜ ｓｊ） （６） ４）根据以下规定，将蛋白质和肽段进行分组。 ①在同一组中任意两个元素之间至少存在一条 路径； ②除去组中的肽段之外，对于组中的蛋白质没 有其他的肽段被鉴定到； ③没有其他的蛋白质可以生成组中的肽段。 Ｐ（ｘｉ ｜ Ｓ） ＝ Ｘ∑：ｘｉ ＝ １ｌ：∏Ｇｌ ＝Ｇｉ ｐ（ｘｉ） ｊ：∏ｇｊ ＝Ｇｉ Ｐ（ｙｊ ｜ Ｘ） ｊ：∏ｇｊ ＝Ｇｉ Ｐ（ｙｊ ｜ ｓｊ） ∑Ｘ ｌ：∏Ｇｌ ＝Ｇｉ ｐ（ｘｉ） ｊ：∏ｇｊ ＝Ｇｉ Ｐ（ｙｊ ｜ Ｘ） ｊ：∏ｇｊ ＝Ｇｉ Ｐ（ｙｊ ｜ ｓｊ） （７） 模型的主要目标为寻找一个具有最大后验的蛋 白质配 置， 也 就 是 最 大 化 每 个 蛋 白 质 后 验 概 率 Ｐ（Ｘｉ ｜ Ｓ），从而推断出真实存在于样本中的蛋白质 集合。 １．３ 模型求解 给定蛋白质的配置图，以及肽段被正确识别的 概率 ｓｊ，在参数 α 确定的情况下，根据式（７）可直接 计算出蛋白质的后验概率。 但是这种暴力求解方法 的时间复杂度为 Ｏ（２ ｍ ），由于图的规模较大，所以 直接暴力求解的代价是十分昂贵的，故本文采用了 吉布斯抽样［１６］来获得具有最大后验的最优蛋白质 配置。 吉布斯 抽 样 是 马 尔 可 夫 蒙 特 卡 罗 （ Ｍａｒｋｏｖ Ｃｈａｉｎ ｍｏｎｔｅ Ｃａｒｌｏ，ＭＣＭＣ）算法中的特例，用来构造 多变量概率分布的随机样本。 考虑具有 ｐ （ ｚ） ＝ ｐ（ｚ１ ，ｚ２ ，…，ｚｍ ）分布的样品集，并且给定一些符合马 尔可夫性质的初始状态。 吉布斯抽样的每一步骤都 会根据剩余变量的当前状态值更新其中一个变量的 状态值。 也就是说，对于 ｚ 的第 ｉ 个组件 ｚｉ可以通过 计算 ｐ（ ｚｉ ｜ ｚ＼ｉ）得到，其中 ｚ＼ｉ表示除 ｚｉ 的所有组件。 迭代这一过程在每一步使用一个转变函数来更新变 量信息，直到收敛为止。 将该方法用于求解蛋白质推断问题，大大降低 了求解模型（ＰＧＭＰｉ）的时间复杂度，算法收敛所得 的蛋白质后验概率即为该蛋白质真实存在于样本中 的概率。 需要说明的是，该方法所求的解为近似最 优解，但可以通过改变收敛的判断标准来对近似解 调优。 ２ 实验及结果评估 为了验证本文提出的蛋白质推断算法 ＰＧＭＰｉ 的表现，选取 ２ 个典型的蛋白质推断算法 ＭＳＢａｙｅ⁃ ｓＰｒｏ， Ｆｉｄｏ 在 ６ 个数据集上进行比较实验。 ２．１ 数据集 本文选取了 ６ 个公开的数据集来验证 ＰＧＭＰｉ 的 表 现： １８ ｍｉｘｔｕｒｅｓ ［１７］ ， Ｓｉｇｍａ４９ ［１８］ ， Ｙｅａｓｔ ［１９］ ， ＤＭＥ ［２０］ ，ＨｕｍａｎＭＤ ［２１］ 和 ＨｕｍａｎＥＫＣ ［１９］ 。 它们主要 分为 ２ 类：有参考集的数据集和无参考集的数据集。 前 ３ 个数据集都拥有相对应的蛋白质参考数据集， 即预先知道的存在于样本中的蛋白质集合。 另 ３ 个 数据集则不拥有这样的参考集。 关于这些数据集的 更多细节详情请参见文献［２２］。 本文采用广泛使用的目标－诱饵的策略来评估 算法的表现。 该策略的主要思想为：在包含所有目 第 ３ 期 赵璨，等：基于概率图模型的蛋白质推断算法 ·３７９·