·704 智能系统学报 第11卷 的蛋白链接关系发生了紊乱[】，并进一步提出了拓 表示顶点集、E表示边集。矩阵A表示邻接矩阵，A 扑模块、功能模块和疾病模块是存在相同的共有蛋 的定义为 白成员的。大家普遍认为在拓扑结构上链接比较紧 1 (:,y)∈E 密的蛋白在生物功能上也更加相似。基于这个假 Ag20, (1) 其他 设，为了可以精确地寻找到与疾病相关的蛋白模块， 式中：A,表示节点i和节点j有连边，：和表示节 需要先从PPI网络中检测出具有比较显著生物意义 点i和节点j。 的功能模块。 目前功能模块的检测方法主要是使用复杂网络 1.2模块检测算法 模块目前还没有一个统一的定义，大家对模块 领域中的社团划分方法将PPI网络划分为多个拓扑 模块，然后对这些拓扑模块再进行生物功能的检测。 的共识是：模块内部的边比较紧密而模块之间的边 Bader等提出了一种叫做MCODE的方法，该方法首 要尽量稀硫[6。本文主要使用K均值和非负矩阵 先根据节点的邻居对每一个节点赋一个权重，然后 分解2种算法对PPI网络进行模块检测。 选择权重较大的节点作为种子节点进行社团划 1)K均值) 分)。该方法可以发现重叠的蛋白质功能模块。 K均值是一个比较经典的聚类算法。给定一个 DPClus等使用类似的方法对网络中的每条边赋权 含有N个节点的数据集{x1,x2,…,x},其中每个节 重，然后选择权重最大的边的节点作为初始种子节 点的维度是D维，将该数据集划分为k个类。每一 点进行社团划分I)。Edward等提出了一种基于熵 类的类中心表示为44，为每一个节点定义一个指示 的方法进行功能模块的检测，该方法首先随机选择 向量rt,其物理含义是如果节点n的类标号为k,则 一个节点作为种子节点，然后将该种子节点和其周 值为1：否则为0。 围的邻居作为一个种子类，通过嫡的减少来移除边 K均值算法的主要思想就是所有样本点到各自 界点和增加新节点形成蛋白模块，直到遍历完网络 的类中心的距离最短，其目标函数为 中的所有节点4。 miW=立会rlx-4I (2) 上述功能模块划分算法主要是根据PPI中的链 接关系，也就是只找到了在拓扑结构上链接紧密的 根据式(2)可以得到类中心的迭代公式为 模块。由于目前人类所获取的蛋白相互作用数据只 ∑rwx 获取了实际相互作用的10%~20%[)，所以PPI网 4g三 ∑.re (3) 络是比较稀疏的，使用传统的复杂网络中的社团划 其代表的物理含义是第k个类中所有样本点的 分方法并不能保证精确地找到具有某种生物功能的 均值作为该类的类中心，然后其他节点根据与该类 模块。蛋白质复合体(protein complex)是2个及其 中心的距离来判断是不是属于这个类。通过不停地 以上的蛋白相互作用而形成的复合物，一般分为结 迭代，直到所有的类中心不在改变为止。 构型的蛋白质复合体和功能型蛋白质复合体2大 2)非负矩阵分解 类。目前关于蛋白质复合体的数据已经可以方便地 非负矩阵分解最早是由Lee和Seung8)提出 获取，因此可以考虑将蛋白质复合体的数据融合到 PPI网络中，从而可以提高功能模块的发现精度。 的。若一个矩阵其所有的元素没有负数，这样的矩 本文首先将蛋白质复合体数据融合到PPI网络 阵叫做非负矩阵。对一个n×m的非负矩阵X,其行 中，然后使用K均值(K-Means)和非负矩阵分解 向量代表特征，列向量代表样本。非负矩阵分解的 (non-negative matrix factorization,NMF)2种算法对 任务就是把X分解为两个非负矩阵使得X≈FG, 融合后的数据进行模块划分，针对得到的模块进行 其中F是一个n×k的矩阵，G是mxk的矩阵(k为 基因本体(gene ontolog,GO)和通路(pathway)富集 类的个数)。其目标函数为 分析并进一步计算模块的G0同质性。 minJ=IX-FGT 2 (4) 式中：G为最后的划分矩阵。F和G的迭代规则 社团划分及模块生物学分析 如下： 1.1PPI网络的表示 (XG). Ft=F PPI网可以表示为一个无向无权图，其中V (FGG)的蛋白链接关系发生了紊乱［１］ ，并进一步提出了拓 扑模块、功能模块和疾病模块是存在相同的共有蛋 白成员的。 大家普遍认为在拓扑结构上链接比较紧 密的蛋白在生物功能上也更加相似。 基于这个假 设，为了可以精确地寻找到与疾病相关的蛋白模块， 需要先从 ＰＰＩ 网络中检测出具有比较显著生物意义 的功能模块。 目前功能模块的检测方法主要是使用复杂网络 领域中的社团划分方法将 ＰＰＩ 网络划分为多个拓扑 模块，然后对这些拓扑模块再进行生物功能的检测。 Ｂａｄｅｒ 等提出了一种叫做 ＭＣＯＤＥ 的方法，该方法首 先根据节点的邻居对每一个节点赋一个权重，然后 选择权重较大的节点作为种子节点进行社团划 分［２］ 。 该方法可以发现重叠的蛋白质功能模块。 ＤＰＣｌｕｓ 等使用类似的方法对网络中的每条边赋权 重，然后选择权重最大的边的节点作为初始种子节 点进行社团划分［３］ 。 Ｅｄｗａｒｄ 等提出了一种基于熵 的方法进行功能模块的检测，该方法首先随机选择 一个节点作为种子节点，然后将该种子节点和其周 围的邻居作为一个种子类，通过熵的减少来移除边 界点和增加新节点形成蛋白模块，直到遍历完网络 中的所有节点［４］ 。 上述功能模块划分算法主要是根据 ＰＰＩ 中的链 接关系，也就是只找到了在拓扑结构上链接紧密的 模块。 由于目前人类所获取的蛋白相互作用数据只 获取了实际相互作用的 １０％ ～ ２０％ ［５］ ，所以 ＰＰＩ 网 络是比较稀疏的，使用传统的复杂网络中的社团划 分方法并不能保证精确地找到具有某种生物功能的 模块。 蛋白质复合体（ ｐｒｏｔｅｉｎ ｃｏｍｐｌｅｘ）是 ２ 个及其 以上的蛋白相互作用而形成的复合物，一般分为结 构型的蛋白质复合体和功能型蛋白质复合体 ２ 大 类。 目前关于蛋白质复合体的数据已经可以方便地 获取，因此可以考虑将蛋白质复合体的数据融合到 ＰＰＩ 网络中，从而可以提高功能模块的发现精度。 本文首先将蛋白质复合体数据融合到 ＰＰＩ 网络 中，然后使用 Ｋ 均值（Ｋ⁃Ｍｅａｎｓ） 和非负矩阵分解 （ｎｏｎ⁃ｎｅｇａｔｉｖｅ ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａｔｉｏｎ，ＮＭＦ） ２ 种算法对 融合后的数据进行模块划分，针对得到的模块进行 基因本体（ｇｅｎｅ ｏｎｔｏｌｏｇｙ，ＧＯ）和通路（ｐａｔｈｗａｙ）富集 分析并进一步计算模块的 ＧＯ 同质性。 １ 社团划分及模块生物学分析 １．１ ＰＰＩ 网络的表示 ＰＰＩ 网络可以表示为一个无向无权图，其中 Ｖ 表示顶点集、Ｅ 表示边集。 矩阵 Ａ 表示邻接矩阵，Ａ 的定义为 Ａｉｊ ＝ １， ０， （ｖｉ，ｖｊ） ∈ Ｅ 其他 { （１） 式中：Ａｉｊ表示节点 ｉ 和节点 ｊ 有连边，ｖｉ 和 ｖｊ 表示节 点 ｉ 和节点 ｊ。 １．２ 模块检测算法 模块目前还没有一个统一的定义，大家对模块 的共识是：模块内部的边比较紧密而模块之间的边 要尽量稀疏［６］ 。 本文主要使用 Ｋ 均值和非负矩阵 分解 ２ 种算法对 ＰＰＩ 网络进行模块检测。 １） Ｋ 均值［７］ Ｋ 均值是一个比较经典的聚类算法。 给定一个 含有 Ｎ 个节点的数据集 ｘ１ ，ｘ２ ，…，ｘｎ { } ，其中每个节 点的维度是 Ｄ 维，将该数据集划分为 ｋ 个类。 每一 类的类中心表示为 μｋ，为每一个节点定义一个指示 向量 ｒｎｋ，其物理含义是如果节点 ｎ 的类标号为 ｋ，则 值为 １；否则为 ０。 Ｋ 均值算法的主要思想就是所有样本点到各自 的类中心的距离最短，其目标函数为 ｍｉｎＪ ＝ ∑ Ｎ ｎ ＝ １∑ Ｋ ｋ ＝ １ ｒｎｋ‖ｘｎ － ｕｋ‖ ２ （２） 根据式（２）可以得到类中心的迭代公式为 μｋ ＝ ∑ｎ ｒｎｋｘｎ ∑ｎ ｒｎｋ （３） 其代表的物理含义是第 ｋ 个类中所有样本点的 均值作为该类的类中心，然后其他节点根据与该类 中心的距离来判断是不是属于这个类。 通过不停地 迭代，直到所有的类中心不在改变为止。 ２）非负矩阵分解 非负矩阵分解最早是由 Ｌｅｅ 和 Ｓｅｕｎｇ ［８］ 提出 的。 若一个矩阵其所有的元素没有负数，这样的矩 阵叫做非负矩阵。 对一个 ｎ×ｍ 的非负矩阵 Ｘ，其行 向量代表特征，列向量代表样本。 非负矩阵分解的 任务就是把 Ｘ 分解为两个非负矩阵使得 Ｘ≈ＦＧ Ｔ ， 其中 Ｆ 是一个 ｎ×ｋ 的矩阵，Ｇ 是 ｍ×ｋ 的矩阵（ ｋ 为 类的个数）。 其目标函数为 ｍｉｎＪ ＝ ‖Ｘ － ＦＧ Ｔ‖２ （４） 式中：Ｇ 为最后的划分矩阵。 Ｆ 和 Ｇ 的迭代规则 如下： Ｆｉｋ ＝ Ｆｉｋ （ＸＧ）ｉｋ （ＦＧ ＴＧ）ｉｋ ·７０４· 智 能 系 统 学 报 第 １１ 卷