分层模块化结构识别基因Coexpression网络的应用程序

文摘

网络模块(社区)结构一直是近年来的一个研究热点。许多方法被提出了模块探测和识别。层次结构的模块显示存在于许多生物网络和社会网络等网络。partitional模块识别方法相比,更少的研究推理的层次模块化结构。在本文中,我们提出一个方法,构建基于随机块模型分层模块化的结构。统计测试应用于测试不同模块之间的层次关系。我们给人工网络和真实数据的例子来说明我们的方法的性能。应用该方法的酵母基因coexpression网络显示,它有一个分层的模块化结构的模块不同级别对应不同的基因功能。

1。介绍

网络广泛应用于复杂系统模型,包括生物系统中,社会组织,万维网,等等。(顶点)在一个网络中,节点代表系统中的成员,而边缘代表了成员之间的交互。如果两个节点在网络互动,将会有一条边连接。这样一个代表,复杂的系统可以分析计算方法。

模块(社区)结构是一种常见的许多不同类型的网络。模块是一个网络的稠密子组,同一模块中的节点更容易比其他模块的节点相互连接。一般来说,成员在同一模块共享一些共同的属性或扮演类似的角色。coexpression网络,例如,在一个基因的基因在同一模块可能属于同一功能类别,如脂质代谢和急性期反应(1]。以来所发表的论文(2),模块探测和识别成为研究热点在几个不同的领域,如计算机科学,物理,统计数据。大量的相关作品已经出版的物理学家做出了最贡献(3- - - - - -12]。最近的一些评论论文提供细节和模块识别方法的比较6,9,13]。文献[13)对比几种现有方法的性能对计算时间和输出。Reference0020 [6)是一个彻底的,最近的讨论。文献[9不同角度的对比的方法,揭示了一些重要的相似之处的几个方法。最近的一些比较流行的方法是所示(14]。的方法相比,该方法通过在模块和最小化最大化平均程度不同模块之间的平均连接在识别精度优于其他方法。其计算速度也是竞争(14]。除了这些计算方法,理论分析模块识别提出了最近。Bickel陈给第一个统计分析模块的属性(15]。基于随机块模型,他们给了模块化的充分条件的一致估计量模块,提出了一种新的模块化一致。然而,这种模块化是最大化的计算非常耗时。

虽然很多相关作品发表,如何选择一个合适的模块保持一个开放的问题。应用不同的方法输出不同的解决方案时,在同一个网络上。在现实中,所有不同的选择可能是合理的,因为这个数字的不同的选择可能对应于不同层次的模块。在[解释16),一些模块化网络层次结构。例如,在友谊网络,大规模,模块可能对应于不同国家的人。在较小的尺度上,人们在同一模块可能来自同一个大学毕业,在同一社区长大,甚至出生在同一个家庭。这样分层模块化的结构出现在不同类型的网络。例如,默和他的同事们给出了一个示例分层模块化结构在人类的大脑17]。图1显示了一个示例的分层模块化的网络。有两个层次的模块。我们可以确定三个模块对应不同形状的节点在最低水平或两个模块和节点由数据集圈结合在更高的水平。

partitional方式相比,该模块识别(所有模块在同一水平),有更少的工作层次模块化结构分析计算方法(18- - - - - -20.]。尽管这些论文存在一些方法构造层次模块化结构,他们不给清楚这些模块是如何组织和模块之间的关系是什么。在本文中,我们主要考虑在未加权的网络分层模块化结构的问题。基于模块的识别方法(14),我们给该方法如何构造所有可能的模块的层次结构部分2。数值实验模拟网络和真实数据网络都呈现给我们的方法的性能部分3。该方法的应用酵母基因coexpression网络显示它确实有一个层次结构,对应于不同程度的基因功能。最后给出结论的言论。通过构建层次结构,我们的目标是探索的功能模块在不同的水平和解释为什么模块的数量可能有所不同不同的识别方法。

2。方法

在细节上如何构建层次结构,我们首先给它的定义。我们考虑一个网络与节点,表示节点的集合表示的边缘。邻接矩阵表示为每个条目是0或1。网络的层次结构定义基于随机块模型,这是一个直接的扩展Erdos-Renyi随机图模型(21]。网络是通过从一组开始节点和增加它们之间的边缘概率的方式。任意两个节点之间存在一条边是伯努利事件的概率可能vertex-pair依赖。在一开始,我们假设网络模块。网络生成两个步骤。首先,任何节点分配给一个模块用一个概率,在那里满足。那么任何两个节点和,连接的概率根据,,是对称的。如果有网络的模块化结构,。采用这种模型,可以递归地定义网络的层次结构。对于任何三个模块,,,如果我们说,这三个模块和之间的层次结构可以合并到一个新的模块并行。

构造层次结构,我们使用自底向上的策略。我们首先找到所有可能的模块,然后构建层次结构的最低水平。我们使用的方法(14找到所有可能的模块。假设首先给出。我们让表示子网的节点数量,表示在子网边缘总数的两倍,表示子网之间的连接总数和,在那里。模块识别问题是制定 在哪里网络是一个分区。

以矩阵形式,如果我们让 问题是制定 在这里是一个向量的所有元素是1。

目标函数的目的是同时最大化平均程度在每个模块和最小化平均不同模块之间的连接。我们希望实现一个好的平衡模块的大小和做出正确的推理模块。问题(3)与一个近似方法解决类似于谱聚类。我们首先计算矩阵的特征向量。通过集群这些作为一个矩阵的特征向量对象与尺寸,我们的作业节点进模块。

现在,我们讨论如何确定所有可能的最低水平的模块。对于任何一个节点,可以写成 在哪里 它定义了连接节点的子网。确定可能的模块的数量,我们比较平均连接在一个子网之间的平均连接,其他子网。如果平均连接在一个子网是更大的,我们把它作为一个模块,也就是说, 另外,它也可以写成 如果我们两边。这个条件很弱,因此,我们希望找到的所有模块的最低水平。我们的集群增加两个,直到条件(6)不持有并得到所有可能的模块。上述算法的效率(中可以看到14]。

基于上述结果,我们构建的层次结构(bottom-to-up)烧结的方法。我们直接使用连接概率,计算通过最大似然估计,从聚类结果来衡量不同模块之间的距离。这个连接概率矩阵表示。第一次发现不同模块之间的连接概率最大,我们假定它是与相应的两个模块被记录下来。第二大的连接概率这两个模块还发现,我们认为他们是谁和与相应的模块和。确定是否有这些模块的层次结构,我们用Fisher精确检验是否连接概率和是一样的。也就是说,我们需要测试和。在这里我们将值阈值是0.05。这两个关系的三种不同的情况下可能发生。(1)这两个两个零假设被拒绝。在这种情况下,有层次结构和模块在低水平比吗和。我们把两个模块和并把它们作为一个模块。(2)只有一个和被接受。相应的模块有相同的连接概率结合在一起。我们寻找下一个最大的连接概率这三个模块和测试的关系了。如果两个模块进行测试相同的连接概率,它们组合成一组,同样的步骤实现。(3)这两个两个零假设被接受。这些模块是作为在同一水平,结合在一起。我们搜索下一个最大的连接概率这四个模块和统计检验,直到层次结构发生或所有模块组合在一起。上述步骤完成后,不同模块之间的连接概率是重新计算并记录。上面的搜索和测试步骤是重复的。这些步骤实现递归直到所有模块组合成一个大的模块/网络。统计检验,我们也可以使用以及测试连接概率之间的关系如果不同模块之间的连接的分布可以近似正态分布。用这种方法,我们可以有效地将相同的模块连接到相同的概率水平。

3所示。数值实验

在本节中,我们评估我们的方法的性能通过几个例子的应用程序。我们第一次开始两个人工网络有相对清晰的模块结构。然后我们的方法适用于两个真实网络对其性能进行评估。第一个真正的网络是著名的空手道俱乐部网络和第二个是酵母基因coexpression网络。

3.1。人工网络

3.1.1。派系组成的一个网络

我们考虑一个包含200个节点的网络,它是由4个派系。派系的大小是90,30岁,40岁,40岁。不同派系之间的连接是随机生成的概率如下:

邻接矩阵如图的模式2(一个)。从左上角到右下角,我们表示的四个模块,,,对应位置的连接概率矩阵。我们可以看到的层次结构网络的邻接矩阵。我们应用该方法到这个网络。条件(6)是满足,除非。估计连接概率矩阵

我们运用统计检验到相应的模块,最后我们得到层次结构如图2 (b)。层次上的值树的概率的估计连接相应的模块。在最低水平,有四个模块。如果树削减在0.205和0.029之间,有三个模块如果截止大于0.029时,只有两个模块。这些结果是一致的网络一代的策略。

3.1.2。一个随机生成的网络

在这个例子中,我们还考虑与200年网络节点和4个模块。每个模块的大小10,45岁,45岁和100年。我们设置每个节点的度在其模块6,15日,15日和30日。然后不同的节点之间的连接是随机生成的。我们把所有的边缘为每个节点生成。每个模块内最后的平均程度大于指定的号码。不同模块之间的连接概率是0.002。邻接矩阵如图的模式3。从左上角到右下角,四个模块,,,,分别。与我们的方法,网络上正确地划分为四个模块和估计的连接概率的最低水平 通过使用统计测试,确定这四个模块并行模块,这是一样的,在我们的网络一代的策略。

3.2。空手道俱乐部网络

我们考虑扎贾里的空手道俱乐部网络成员(22在这个例子中。这个网络中有34个节点对应一个空手道俱乐部的成员。这个数据集被应用作为基准测试许多模块识别算法由于真正的模块在这个网络。俱乐部的人观察一段三年。外的边缘代表连接的个人活动的俱乐部。在某种程度上,俱乐部的管理员和老师分手了因为他们之间的冲突。俱乐部分为两组支持管理员和老师。图4显示了网络。最初,有两个模块,有16个节点(图中正方形和五边形)和18节点(图中圆圈和三角形),分别。

我们应用该方法到这个网络。标准(6)是满足,除非。结果如图4,不同形状的节点表示不同的模块。估计连接概率矩阵

从这个矩阵,它很容易看到和更有可能互相连接。通过统计检验,我们可以得到概率之间的连接,,是相同的。虽然没有连接和,它有一个更大的连接概率比,来。因此这四个模块在同一水平。在[19],作者认为建立这个网络的分层模块化的结构。起初,他们还发现四个模块的最低水平。然后他们发现这个网络有两个模块和节点(31)3、9、10、14日属于他们两人。在本文中,我们没有考虑重叠节点。然而,我们可以看到,因为这些属于两个重叠节点和,他们两个部分紧密联系,我们的检测方法和,和具有相同的连接。

3.3。酵母基因Coexpression网络中的分层模块化结构

在本节中,我们应用我们建议的方法来分析基因coexpression酵母的网络。我们使用的数据集是由Brem和Kruglyak从两个不同的同基因的菌株之间的交叉和RM (23]。如[23),共有5740个orf数据预处理后得到。在我们的分析中,我们只使用1800作为输入的差异表达基因大多数构建coexpression网络和导出模块。当构造网络的邻接矩阵,我们使用硬阈值,即:如果两个基因之间的皮尔逊相关系数的绝对值大于给定值,我们分配之间的优势;否则,没有优势。我们之间的线性回归系数计算的频率程度()和改变程度(),并选择阈值导致大约规模网络的自由属性中描述(24]。最后,阈值设置为0.705,大约是0.75。在这种环境下,这种基因coexpression网络分为690无关的部分最大的尺寸788的一部分。在这里,我们只分析层次模块化结构最大的网络连接。

从,我们应用方法14这个网络,和条件(6)持有,直到。解决方案更准确,我们做一个全球最大化通过改变边界节点的索引模块从近似的解决方案。由于近似解已经好,这一步是非常快。网络的结构如图5(一个),不同的颜色和形状表示不同的模块如表所示1。然后我们构建分层模块化的结构如图5 (b)。最低水平,有十个模块,在最高级别,有四个模块。

因为coexpressed基因往往是coregulated和可能有类似的功能,基因在同一模块预计将丰富对一些函数类别。为了了解网络的生物学基础模块,我们认为每个识别模块进行浓缩的注释基因本体论(去)25]。在我们的分析中,从Bioconductor浓缩的分析是由去统计。对于每个模块,统计最重要的类别进行了分析。表1为十个模块显示了富集的结果。“M-size”和“G-size”大小的模块和类别,分别。“重叠”是模块的重叠大小和类别。表2显示模块的浓缩的结果在不同的水平。从表,很容易看到,不同的基因功能分类是最不同层次丰富。例如,模块丰富的类别“翻译”最重要的是,而合并后的模块,丰富了“核糖核蛋白复杂的生物起源”最重要的是,包含42个基因在这个函数。合并后的模块,,,也丰富了这个函数,而本身大大丰富了“细胞呼吸”。在的层面上,模块组成的,,,,,丰富了四个最重要的功能类别,所有的基因都是重叠的。三个(“蜂窝组件生源论”,“细胞组件生源论在细胞水平,”和“核糖体生物起源”)是不同于最丰富的基因功能这六个模块。这些结果表明,分层模块化结构确实存在基因coexpression网络和不同层次不同的基因功能最丰富。

我们使用软件REViGO检查浓缩去类别的层次结构(26]。我们认为丰富去分类表1和2除了类别“平移终止的规定”,因为它的G-size非常小和值较大。图6显示了最丰富的树图类别。我们不标记的子图模块与模块相结合,,,,,。这里的模块,和其他模块是相互平行的,这与我们的研究结果是一致的。和属于一个大的类别,这是“家庭支链氨基酸代谢过程”。这个大范畴不同于最丰富的类别合并后的模块和。这可能来自于事实很小,它不包括很大一部分浓缩类别。和相互平行,也符合我们的分析。这些结果表明,我们建议的方法可以解释一些层次结构的类别。由于网络规模,我们没有处理所有基因的酵母。这可能是一个原因我们的一些计算结果不符合去树映射函数。

4所示。结论

模块识别问题吸引了来自不同领域的关注,它仍然是一个热门研究课题。如何确定模块的数量在模块化网络一直开放问题模块识别方法的研究。这个问题可能来自于模块化网络的层次结构。不同的数字对应于不同级别的层次结构和他们可能是合理的。在本文中,我们提出了一个方法,构建网络的层次模块化结构。通过统计检验,我们可以识别并行模块和层次结构。根据不同层次树的短裤,不同数量的模块可以被识别。这可能会解决这个问题在某种程度上网络模块的数量。给出一些例子来演示我们的方法的效率。应用该方法的基因coexpression网络表明,酵母基因层次模块coexpression网络。 On different levels of such networks, the genes in the module belong to different gene functions most. Thus studying the gene function through constructing the hierarchical modular structure instead of specifying the number of modules should perform better. Application of such algorithms to other kinds of networks may also contribute to other research fields.

确认

这项工作的部分支持由国家自然科学基金委资助10901042,10971075,91130032。本文的主要版本出现在2012年IEEE的特色。

引用

1. r . Guimera和l·a·n·阿马拉尔”功能制图学复杂的代谢网络,自然,卷433,不。7028年,第900 - 895页,2005年。视图:出版商的网站|谷歌学术搜索
2. m . Girvan m·e·j·纽曼,“在社会和生物群落结构的网络,”美国国家科学院院刊》上的美利坚合众国,卷99,不。12日,第7826 - 7821页,2002年。视图:出版商的网站|谷歌学术搜索
3. 竞技场,j . Borge-Holthoefer s戈麦斯,g . Zamora-Lopez“复杂网络的模块化结构,优化地图”新物理学杂志ID 053009条,卷。12日,2010年。视图:出版商的网站|谷歌学术搜索
4. 盾和美国阅读”模块,理解网络概念”BMC系统生物学第二十四条,卷。1日,2007年。视图:出版商的网站|谷歌学术搜索
5. 大肠埃斯特拉达和n .波多野“传染性在复杂网络,”物理评论E,卷77,不。第三条ID 036111, 2008。视图:出版商的网站|谷歌学术搜索
6. 走,“社区检测图”,物理的报告,卷486,不。3 - 5,75 - 174年,2010页。视图:出版商的网站|谷歌学术搜索
7. m·e·j·纽曼,“发现社区结构在网络中使用的特征向量矩阵,”物理评论E,卷74,不。第三条ID 036104, 2006。视图:出版商的网站|谷歌学术搜索
8. m·e·j·纽曼,“模块化和社区结构的网络,”美国国家科学院院刊》上的美利坚合众国,卷103,不。23日,第8582 - 8577页,2006年。视图:出版商的网站|谷歌学术搜索
9. m·a·波特j.p. Onnela, p . j .木栅。社区网络,“美国数学协会的通知卷,56号9日,第1102 - 1082页,2010年。视图:谷歌学术搜索
10. f . Radicchi c可以见到效果,f . Cecconi住诉洛雷托,和d .巴黎”的定义和识别社区网络,美国国家科学院院刊》上的美利坚合众国,卷101,不。9日,第2663 - 2658页,2004年。视图:出版商的网站|谷歌学术搜索
11. 李z s张R.-S。王,X.-S。张,l .陈“量化函数为社区检测,”物理评论E,卷77,不。第三条ID 036109, 2008。视图:出版商的网站|谷歌学术搜索
12. m . Rosvall和c t Bergstrom,”一位信息理论解决复杂网络社区结构,框架”美国国家科学院院刊》上的美利坚合众国,卷104,不。18日,第7331 - 7327页,2007年。视图:出版商的网站|谷歌学术搜索
13. l . Danon a . Diaz-Guilera j .杜赫,竞技场,群落结构识别相比,“统计力学杂志,没有。9篇文章ID 09008年,第228 - 219页,2005年。视图:出版商的网站|谷歌学术搜索
14. 美国张和h .赵“社区识别网络结构不平衡,”物理评论E,卷85,不。6、文章ID 066114, 2012。视图:出版商的网站|谷歌学术搜索
15. p . j . Bickel和A .陈”的网络模型和非参数视图Newman-Girvan和其他模块化,”美国国家科学院院刊》上的美利坚合众国,卷106,不。50岁,21068 - 21073年,2009页。视图:出版商的网站|谷歌学术搜索
16. 答:竞技场,a . Diaz-Guilera和c j . Perez-Vicente“同步显示在复杂网络拓扑尺度,”物理评论快报,卷96,不。11日,ID 114102条,2006年。视图:出版商的网站|谷歌学术搜索
17. d·莫尼耶,r . Lambiotte和e . t .图像“大脑网络的模块化和分层次模块化的组织。”神经科学前沿,4卷,不。200年,2010年。视图:谷歌学术搜索
18. k . h .沈x Cheng Cai, M.-B。胡”,发现重叠社区结构和层次的网络,”自然史一,卷388,不。8,1706 - 1712年,2009页。视图:出版商的网站|谷歌学术搜索
19. a . Lancichinetti s Fortunato, j .安德烈•柯特兹”检测重叠和层次复杂网络社区结构,”新物理学杂志ID 033015条,卷。11日,2009年。视图:出版商的网站|谷歌学术搜索
20. e . Ravasz“检测在生物网络分层模块化,”计算系统生物学54卷,第160 - 145页,2009年。视图:谷歌学术搜索
21. p . Erdős和a . r . Renyi”随机图。我,”出版Mathematicae》第六卷,第297 - 290页,1959年。视图:谷歌学术搜索
22. w·w·扎卡里,”一个信息流模型在小群体冲突和分裂,”《人类学研究33卷,第473 - 452页,1977年。视图:谷歌学术搜索
23. r . b . Brem和l . Kruglyak”景观的遗传复杂性在5700年酵母基因表达特征,“美国国家科学院院刊》上的美利坚合众国,卷102,不。5,1572 - 1577年,2005页。视图:出版商的网站|谷歌学术搜索
24. b .张和美国阅读”一般加权基因co-expression网络分析框架,“统计应用遗传学和分子生物学,4卷,不。1,第十七条,2005。视图:谷歌学术搜索
25. m . ashburn c a球,j·a·布莱克et al .,“基因本体:工具的统一生物学、基因本体财团”自然遗传学,25卷,不。1、25 - 29,2000页。视图:出版商的网站|谷歌学术搜索
26. f . Supek m . Bošnjak:Škunca, t .Šmuc”REVIGO总结和可视化长列表的基因本体术语中,“《公共科学图书馆•综合》》第六卷,没有。7篇文章ID 21800 2011。视图:出版商的网站|谷歌学术搜索

版权

版权©2012 Shuqin张。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。