生物网络中概率模体发现算法的分析

《生物网络中概率模体发现算法的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、东南大学硕上学位论文为K2∑q。定义2．7稀疏图给定图G=(圯E)，如果K／Ⅳ～1，则图G是稀疏图。‘定义2．8图的内部连接数给定Ⅳ大小图G=∥，E)及其邻接矩阵c，G的内部连接数为L(c)2芝q。定义2．9子图的联合结点序给定p个子图g“陋一1，⋯，p)，每个子图的大小为阼，子图g。的结点排序为A。=“。，V：。，．．．，心。】．，则这p个子图的结点排序A。@一1，⋯，p)可以确定给定的p个子图的一个联合结点排序，称之为子图的联合结点序九一{A1，A2，．．．，A。)。显而易见，p个子图的联合结点序有∽!

2、)P种。定义2．10两个子图的错配给定子图g。和g卢及其邻接矩阵c。和cp，子图g口和g芦之间的错配定义为M(c8，c卢)=．∑f《(1一《)+(1一《)《】，而两个子图的最小错配M郇定义为子图的所有错配中最小的一个。‘定义2．11图的同构给定图G1一似，巨)和G2一(K，毛)，若存在映射函数，：K-'K，对于u，V，∈K，(u，V，)∈巨，当且仅当厂(u)，，(VJ)∈K，(，化)，厂n))∈易，则称G．，G2同构【17】。2．2模体定义及特性模体的概念首先由Milo等人于2002年提出，此时指的是精确模

3、体，即模体对应的邻接矩阵的中的每个元素要么是0要么是1。而概率模体相当于某些精确模体的叠加，即概率模体对应的矩阵中的元素是介于0到1之间的值，这样更能体现生物网络的进化特性和不确定性。由于概率模体是在精确模体概念的基础上提出的，我们首先对精确模体相关概念进行了概述继而引出概率模体并对其阐述。2．2．1精确模体定义及特性传统的模体即精确模体是指在某个网络的多个不同部分出现的某一相互连接的子结构，6第二章概牢模体识别技术概述其表达程度明显高于在随机网络中的表达，由Milo等人首次提出。在识别模体时，需要根据给定

4、生物网络的度序列用随机化方法生成一组随机图。随机网络生成算法有X交换算法【19】，Matching算法f201和Gowiththewinnersf211算法等。以X交换算法为例，如图2-1所示，在给定的网络中任意选择两条边4_口和C—D，如果边4一D和边C_B不存在，则用边4一D和边C—B替换边彳_B边和C_D。如果4一D和C—B已经至少存在一条边，则放弃此次交换。这样，在给定的生物网络中反复执行上述随机化过程多次后，就可以得到与原网络具有相同大小且具有相同度分布的随机网络。即这个随机网络与原网络具有相同的

5、结点数并且每个结点与原始网络具有相同的出度和入度。④爿精确模体的识别包括如下过程，首先生成一组与给定生物网络具有相同度分布的随机网络，然后在给定生物网络和随机网络中挖掘子图，最后根据模体的统计意义进行评价。精确模体是满足下列条件的子图【7]：(1)Z一脒标准。Z—scD陀公式如下：z(铲笔措(2．1)其中厶，(G)是子图G在真实网络中出现次数，，。埘(q)和s髓(k喊．))分别是子图G在一系列随机网络中出现次数的平均值和标准差。一般要求Z一觥值应大于0．1。(2)P一砌妇标准。P一玩妇法公式如下：‘1ⅣP(

6、q)2专善6拍埘tq)(2·2)其中，(q)是子图q在真实网络中出现的次数，^(q)是模体在第，z个随机网络中出现的次数，Ⅳ是随机网络的个数。当条件c成立时，趣为1，否则为0。通常要求P一玩妣值小于o．01，并且其值越小越好。P一翰抛的含义是某子图G如果是模体，则该子图在真实网东南大学硕十学位论文络对应的随机网络中出现的次数大于它在真实网络中出现的次数的概率是很小的。(3)阈值标准。阂值标准就是直接定义一个阀值u，子图G在真实网络中出现的次数厶，(q)不小于U，一般要求U=4。当计算子图出现次数的时候，需要

7、考虑子图的重叠问题。计算子图出现次数时有三种重叠策略，分别用五，E，E表示。互允许任意结点和边的重叠，最只允许结点的重叠，即边不相交性，只不允许结点和边的重叠，即同时满足边不相交性和结点不相交性。向下封闭性是子图挖掘时一个很有用的性质，是指子图的出现次数随着子图增大单调递减，即子图搜索过程中，如果某个子图出现次数低于某个阀值，则所有由该子图扩展而得到的子图都会低于这个阀值。该性质极大的缩小了候选子图的数量，使得可以使用Apriori算法【281对子图进行剪枝。上述的三种重叠策略中，最和E保持向下封闭性，而E

8、则不保持。在生物反应网络中，同一种蛋白质或者基因经常在若干个模块中分别承担不同的作用，所以允许子图任意结点和边的重叠是合理的。因此，在模体识别的时候不考虑子图重叠问题，也就是在挖掘子图的时候不能用Apriori算法对子图进行剪枝，必须挖掘出给定生物网络中所有指定规模的子图。所以数据挖掘领域中频繁子图的挖掘算法不能应用于模体的识别【22．27】。2．2．2概率模体定义及特性在这些传统的模体识别方法中，无论模体如何定