.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)解的过程是很费时的。 基于此，本文提出了一种基于概率图模型的方 法来解决蛋白质推断问题。 本文的主要着眼点放在 两个问题上，一个是概率图模型在蛋白质推断问题 上的应用，另一个是串联质谱数据对于蛋白质存在 概率的影响。 前者将蛋白质推断问题抽象成一个概 率图模型的求解问题，鉴定到的肽段以及候选蛋白 质都抽象为节点，候选蛋白质及其对应肽段之间的 关系抽象为有向边，这样就可以抽象成一个有向的 二部图；后者主要是考虑肽鉴定过程中谱与肽段之 间指派的正确性的影响，也可称作肽段识别概率，是 指鉴定肽在样本中存在的后验概率，作为本文概率 图模型的输入。 １ 基于概率图模型的蛋白质推断算法 １．１ 算法介绍 概率图模型是由图论和概率论结合而成的描述 多元统计关系的有效模型［１４］ ，它为多个变量之间复 杂的依赖关系的表示提供了统一的框架，具有紧凑 有效、简洁直观的特点。 其在计算机视觉、生物信息 学、自然语言处理等领域都有广泛的应用。 图 ３ 引入质谱信息的三层图结构 Ｆｉｇ．３ Ｔｈｅ ｔｈｒｅｅ⁃ｌａｙｅｒ ｇｒａｐｈ ｗｈｅｎ ｉｎｔｒｏｄｕｃｉｎｇ ｔｈｅ ＭＳ／ ＭＳ ｄａｔａ 本文提出了基于概率图模型的蛋白质推断算法 （ＰＧＭＰｉ），该方法主要将概率图模型应用到蛋白质 推断问题上，同时引入肽鉴定过程中谱与肽段之间 指派的正确性的影响。 由于蛋白质推断输入数据是 一个二部图，一侧为候选蛋白质的集合，另一侧为肽 段集合。 本文将肽段以及候选蛋白质都抽象为节 点，候选蛋白质及其对应肽段之间的关系抽象为有 向边，这样就可以抽象成一个有向的二部图；同时考 虑串联质谱数据对于蛋白质概率的影响，也将质谱 数据抽象为节点，肽段和其对应谱图之间存在一个 有向边，这样就得到一个三层的有向图结构，从而将 蛋白质鉴定问题抽象为概率图求解问题，如图 ３ 所 示。 本文算法基于有向图模型，也称为贝叶斯网 络［１５］ 。 需明确的是，模型的目标是从候选蛋白质集 合中找到真正存在于样本中的蛋白质子集。 根据这 一目标，本文首先给出了一个图中所有节点联合概 率分布，即谱图、肽段及其对应候选蛋白质同时存在 于样本中的概率。 由于有向图采用乘积法则，对于 ｘ→ｙ，联合概率分布为 ｐ（ｘ，ｙ）＝ ｐ（ｘ）ｐ（ｙ ｜ ｘ）。 其次 对该联合概率分布提出一些基本假设，如蛋白质之 间相互独立、每个鉴定肽打分之间相互独立等，并根 据这些假设条件做简单的数学变换确定参数变量， 之后根据联合概率分布给出蛋白质的后验概率公 式，由于求解具有最大联合概率分布的候选蛋白质 问题规模较大，暴力求解的代价十分昂贵，故本文采 用了吉布斯抽样来获得具有最大后验的最优蛋白质 配置。 相关符号及其定义在表 １ 中给了详细的说明。 表 １ 蛋白质推断的符号说明 Ｔａｂｌｅ １ Ｔｈｅ ｎｏｔａｔｉｏｎ ｕｓｅｄ ｉｎ ｔｈｅ ｐｒｏｔｅｉｎ ｉｎｆｅｒｅｎｃｅ ｍｏｄｅｌ 符号 说明 Ｘ 候选蛋白质集合 ｘ１ ，ｘ２ ，…，ｘｍ 指示变量，如果 ｘｉ ＝ １， 蛋白质 ｉ 存在，否则为 不存在 Ｙ 鉴定得到的肽段集合 ｙ１ ，ｙ２ ，…，ｙｎ 指示变量，如果 ｙｊ ＝１，肽段 ｊ 存在，否则不存在 Ｓ 质谱仪产生的谱图信息对应的打分 ｓ１ ，ｓ２ ，…，ｓｎ 每个肽段 ｊ 对应一个打分 ｓｊ Ｎｊ 可以生成肽段 ｊ 的候选蛋白质的集合 Ｍｉ 候选蛋白质 ｉ 可以产生的肽段的集合 Ｇｉ 蛋白质 ｉ 所存在组的蛋白质集合 ｇｊ 肽段 ｊ 所存在组的肽段的集合 蛋白质、肽段以及质谱的联合概率公式为 Ｐ（Ｘ，Ｙ，Ｓ） ＝ Ｐ（ｘ１，…，ｘｍ）·Ｐ（ｙ１，…，ｙｎ ｜ ｘ１，…，ｘｍ）· Ｐ（ｓ１ ，…，ｓｎ ｜ ｙ１ ，…，ｙｎ ） （１） １．２ 模型参数化 １） 假设两个候选蛋白质之间相互独立： Ｐ（ｘ１ ，ｘ２ ，…，ｘｍ ） ＝ ∏ ｍ ｉ ＝ １ ｐ（ｘｉ） （２） ·３７８· 智 能 系 统 学 报 第 １１ 卷