第33卷摇第2期2014年摇4月北京生物医学工程
BeijingBiomedicalEngineering
Vol郾33摇No郾2April摇2014
基于代谢网络拓扑结构的基元模块发现方法
操勇摇郑浩然
摘摇要摇目的为提取出物种代谢网络具有的基本结构模块即基元模块,提出一种基于拓扑结构的发现代谢网络基元模块方法。方法首先利用网络模块化方法将不同物种的代谢网络划分为模块集合,然后通过合并相似的模块以及分解较大的代表模块等操作,最终获得基元模块集合。同时,利用超几何假设检验的方法以确定模块所具有的代谢功能,并在此基础上验证发现基元模块方法的合理性。结果对KEGG数据库中的1452个物种代谢网络经上述方法处理后,最终得到11446个基元模块,并且这些基元模块能够很好地表示代谢网络。结论提出了一种基于代谢网络拓扑结构的发现基元模块的方法,该方法能够有效提取出组成物种代谢网络的基元模块。
关键词摇代谢网络;拓扑;模块;基元模块DOI:10郾3969/j.issn.1002-3208郾2014郾02郾06.
中图分类号摇R318郾04摇摇文献标志码摇A摇摇文章编号摇1002-3208(2014)02-0139-05
Amethodtodiscoverelementarymodulesofmetabolic
networksbasedontopology
SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei摇230027proposeamethodofdiscoveringelementarymodulesofmetabolicnetworksbasedontopology.MethodsWefirst
揖Abstract铱摇ObjectiveInordertoextracttheelementarymodulesoforganisms爷metabolicnetworks,we
CAOYong,ZHENGHaoran
decomposeorganisms爷metabolicnetworksintoacollectionofmodulesusingmethodofnetworkmodularity郾Thenwegettheultimateelementarymodulesthroughmergingsimilarmodulesandbreakingdownlargerrepresentativemodulesthatcanbetotallyrepresentedbyothersmallermodules郾Meanwhile,weidentifyApplyingourmethodto1452organisms爷metabolicnetworkfromKEGG,wefinallyacquire11446elementarymodules郾Inaddition,theseelementarymodulescanexcellentlyrepresentorganisms爷metabolicnetwork.whichcanefficientlyextracttheelementarymodulesthatcomposeorganisms爷metabolicnetwork.
揖Keywords铱摇metabolicnetwork;topology;module;elementarymodule
metabolicfunctionsinvolvedinmodulebyhypergeometrichypothesistestingandvalidateourmethod.ResultsConclusionsWeproposeamethodtodiscoverelementarymodulesofmetabolicnetworksbasedontopology,
0摇引言
近年来,随着高通量数据采集技术的发展,生物数据库的大小有了爆炸式的增长,这为彻底改变人们对生命和疾病的理解创造了有利条件。然而,如
基金项目:国家重点基础研究发展计划(2011CB910200)资助
作者单位:中国科学技术大学计算机科学与技术学院(合肥230027)通信作者:郑浩然。E鄄mail:hrzheng@ustc郾edu郾cn
何解释这些数据仍然是一个挑战。后基因组时代研究的一个重要内容就是在系统生物学的基础上对多种分子和基因相互作用网络进行分析,理解生物系统是如何从单个构造模块的基础上组织起来的[1]。
代谢网络把细胞内所有生化反应表示为一个网
络,反映了所有参与代谢过程的化合物之间以及所有催化酶之间的相互作用,是对细胞代谢的抽象表达[2]。模块化是代谢网络的一个重要性质,是生物
·140·
北京生物医学工程摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第33卷
网络的一个重要的组织原则[3-4]。虽然每个物种都拥有各自独立的代谢网络,但存在某些物种具有相同的子网络[5]。为了提取出物种代谢网络所具有的基本结构模块即基元模块,提出了一种基于拓扑结构的发现代谢网络基元模块方法。本方法利用网络模块化方法将不同物种的代谢网络划分为模块集合,然后通过合并那些相似的模块以及分解较大的代表模块,最终获得基元模块集合。同时,利用超几2摇基元模块的发现
在发现基元模块之前,先给出两个定义:图相似度和图相似。具体的定义如下所示。
图的相似度定义:
sim(G1,G2)=
V1疑V2max(V1,V2)
式中,G表示图;V表示图内的边集合。
何假设检验的方法来确定模块所具有的代谢功能,并在此基础上验证了发现基元模块方法的合理性。
1摇代谢网络的反应图表示和模块划分
从KEGG数据库[6]得到了1452个物种的代谢数据,并对这些数据进行了解析。为了将代谢网络分解为反应的子集,用无向的反应图来表示代谢网络,即代谢网络中结点对应于反应,边对应连接两个反应的代谢物。如果反应A的产物是反应B的底物或者反应A与反应节点B的产物是反应B存在边。这样A,的底物得到了,1452则反应节点的代谢网络。图1展示的是如何将代谢网络表示为个物种无向反应图,图(a)为若干个反应构成的代谢网络,
图(b)是对应的转换后的无向反应图。
图1摇代谢网络表示成无向反应图的例子Figure1摇Undirectedreactiongraphrepresentationofmetabolicnetworkasshownforasmallreactionsystem
利用AaronClauset和M郾E郾J郾Newman等提出的发现复杂网络社区的方法[7]对这些代谢网络进行模块划分,总共获得了60824个拓扑模块。
0郾9,即图相似定义sim(G:若两个图G11,G2)逸0郾9,则称图、G2G的相似度不小于基元模块的发现主要包括以下两个过程1与图G2相似。
:淤合
并相似模块并选择出代表模块;于分解较大的代表模块。
2郾1摇合并相似模块
在分析所有的模块时,发现存在很多冗余的模块,即存在很多相似的模块。为此,可以将这些相似的模块进行合并。
合并相似模块的过程如图2(图中的数字是模块的标号)所示,可以分为以下三个步骤。图2摇合并相似模块流程
Figure2摇Theprocessofmergingsimilarmodules
似网络(1)。模块相似网络中的结点表示模块比较所有模块之间的相似度,构造模块相
,若模块之间是相似的,则这两个模块之间存在边。
这样做可以使完全子图中的模块彼此之间都相似(2)将模块相似网络划分为若干个完全子图。,
完全子图表示图中的任意两个结点都存在边,即图中的模块彼此都相似hard。由于寻找完全子图是NP鄄络划分为若干个子图问题,利用图分割算法来近似地将模块相似网。利用图分割算法得到的模块
第2期摇摇摇摇摇摇操勇,等:基于代谢网络拓扑结构的基元模块发现方法
·141·
内结点之间的连接紧密,而模块之间的连接稀疏。在一定程度上,子图可以代替完全子图。
(3)按照某种原则,在完全子图中选取一个代
的分类方案,包括11个主要的代谢功能:碳代谢、能量代谢、脂质代谢、核苷酸代谢、氨基酸代谢、聚糖的生物合成和代谢、辅因子与维他命代谢、次生代谢物的生物合成、外来物质的生物降解和代谢、其他氨基酸代谢和萜类与酮类化合物的代谢,再利用超几何假设检验方法,并设置P值为0郾05,最终获得所有3郾2摇超几何分布和P值
模块所具有的代谢功能。
表模块。这里,选取平均相似度最高且规模最大的模块作为代表模块。
利用上述合并相似模块的方法对所有的608242郾2摇分解较大的代表模块
个模块进行处理,最终得到了13932个代表模块。
在分析得到的13932个代表模块时,发现某些规模较小的代表模块是规模较大的代表模块的真子集。为此,考虑是否可以将某些规模较大的代表模块分解为若干个规模较小的代表模块。
这个问题可以建模为集合覆盖问题:已知规模
较大的代表模块E={e1,…,,e2,…,Ben表模块集合B={B1,B2},规模较小的代m},Bi是较大代表模块的真子集。在集合B中选择规模最小的子集,使得子集中的代表模块的尽可能多地覆盖较大的代表模块且子集中代表模块之间的交集尽可能的小。
集合覆盖问题是一个NP鄄hard问题,这里,提出了一种改进的贪心算法来解决该问题。具体的算法流程如下大代表模块的代谢网络(1)。
规模较小的代表模块集合E,已覆盖的网络B,待覆盖的较F,选择出的规模较小的代表模块集合(2)若E为空或B为空C,,则跳到步骤F、C初始为空(5),。则,执行步骤(3)。
否得p=(3)c疑在规模较小的代表模块集合F/c疑E的值最小基元代表模块B中,选择使c;若存在多个p值最小的模块,则选择c疑E最大的那个模块c。(2)。
(4)E=E-c,F=F胰c,C=C胰c,跳转到步骤否则(5),分解不成功若E为空,不分解该代表模块,则分解成功,分解该代表模块。
。(6)对2郾结束1中所得到的。
13932模块进行上述处理,共有2468个代表模块被分解,最终得到11446个基元模块。
3摇确定模块所具有的代谢功能
3郾1摇基本思想
为了确定模块所具有的代谢功能,用KEGG中
如果随机地从有限个物件中抽取n个物件,则偶然获取i个具有指定特征物件的概率服从超几何分布:
??K??N-k?f(i)=
èi÷??èn-i÷???N?èn÷?
摇征的物件数摇式中,N。是总体的大小于是,偶然获得至少;K是总体中具有指定特k个具有指定特征样本能够由超几何累积分布定义为:
?鄱k-1
?K??N-k?P=1-èi÷??èn-i÷?
i=0
??N?èn÷?
摇小于摇假设显著性水平琢,则表明具有指定特征的物件被随机选择的琢,琢常设为0郾05,如果P的值概率很低。因此,P可以用来衡量是否从来自总体中的n个样本比随机选取更具有指定的特征[8]3郾3摇算法流程
。
利用3郾2节所述的超几何分布以及P值,并设置N为KEGG数据库中存在的所有反应数目,n为模块中所包含的反应数,K为某个主要代谢功能所包含的反应数,i为模块包含某个主要代谢功能所具有的反应数,即模块与某个主要代谢功能的反应交集,就可以确定模块是否具有该主要代谢功能的代谢功能。
确定某个模块所具有的代谢功能的具体流程如下所示合M(1)。
={M获得1,M211,…,个主要代谢功能所包含的反应集M11},Mi表示代谢功能i所包含的反应集合(2)获得模块所具有的反应集合。
合R依次与所有代谢功能所包含的反应作交集R,将反应集
,I,得到交集集合I={I12,…,I11}。
基于代谢网络拓扑结构的基元模块发现方法
