[1]何洁月,赵德京.一种高效的生物网络概率模体发现算法[J].东南大学学报(自然科学版),2012,42(1):35-39.[doi:10.3969/j.issn.1001-0505.2012.01.007]
 He Jieyue,Zhao Dejing.An efficient algorithm for discovering probability motifs in biological networks[J].Journal of Southeast University (Natural Science Edition),2012,42(1):35-39.[doi:10.3969/j.issn.1001-0505.2012.01.007]
点击复制

一种高效的生物网络概率模体发现算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
42
期数:
2012年第1期
页码:
35-39
栏目:
计算机科学与工程
出版日期:
2012-01-18

文章信息/Info

Title:
An efficient algorithm for discovering probability motifs in biological networks
作者:
何洁月12赵德京1
(1东南大学计算机科学与工程学院,南京 210096)(2南京大学计算机软件新技术国家重点实验室,南京 210093)
Author(s):
He Jieyue12Zhao Dejing1
(1School of Computer Science and Engineering,Southeast University,Nanjing 210096,China)
(2National Key Laboratory for Novel Software Technology,Nanjing University, Nanjing 210093, China)
关键词:
概率模体子图挖掘生物网络模拟退火算法遗传算法
Keywords:
probability motifs subgraph mining biological networks simulated annealing algorithm genetic algorithm
分类号:
TP391
DOI:
10.3969/j.issn.1001-0505.2012.01.007
摘要:
针对概率模体发现算法中非树形子图的挖掘和在得分函数最大化的过程中得分函数值计算的2个难点.首先提出基于划分的非树形子图的搜索算法,其次将子图同构应用于最小错配的求解以缩小智能优化算法对得分函数求解的解空间,最后将基于模拟退火算法和遗传算法的混合算法应用于得分函数的求解过程.在大肠杆菌基因调控网络中的实验结果表明,与其他算法相比,混合智能算法可以大大减少非树形子图的搜索时间,并以相对较快的收敛速度收敛到一个较优的解,因此所提出的方法有效地提高了概率模体发现的效率.
Abstract:
Mining nontreelike subgraphs and computing the scoring function are two major bottlenecks in probability motif discovery algorithm. To solve the problem a nontreelike subgraph searching algorithm based on partition is proposed in this paper. And the isomorphism of subgraphs is used for computing the minimum pairwise mismatch to narrow down the searching space when using intelligent optimization algorithm to obtain the most similar subgraphs. Finally, a hybrid algorithm based on the genetic algorithm and the simulated annealing algorithm is applied in the scoring function computing. Experimental results on E. COLI data set show that the proposed algorithm of nontreelike subgraph searching takes less time than the other algorithms, and the hybrid intelligent optimization algorithm converges faster and results in a better solution than a pure simulated annealing algorithm. The methods proposed can identify probability network motifs from the real biological networks data with higher efficiency.

参考文献/References:

[1] Milo R,Shen-Orr S S,Itzkovitz S,et al.Network motifs:simple building blocks of complex networks[J].Science,2002,298(5594):824-827.
[2] Schreiber F,Schwobbermeyer H.Frequency concepts and pattern detection for the analysis of motifs in networks[C]//Transactions on Computational Systems Biology Ⅲ.Heidelberg,Germany:Springer Verlag,2005:89-104.
[3] Cheng C Y,Huang C Y,Sun C T.Mining bridge and brick motifs from complex biological networks for functionally and statistically significant discovery[J].IEEE Transactions on Systems,Man,and Cybernetics,2008,38(1):17-24.
[4] Chen J,Hsu W,Lee M L,et al.NeMoFinder:dissecting genome-wide protein-protein interactions with meso-scale network motifs[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD06.Philadelphia,PV,USA,2006:106-115.
[5] Berg J,Lassig M.Local graph alignment and motif search in biological networks[J].Proc Natl Acad Sci,2004,101(41):14689-14694.
[6] 覃桂敏,高琳,周晓锋.非树形网络模体发现算法[J].电子学报,2009,37(11):2420-2426.
  Qin Guimin,Gao Lin,Zhou Xiaofeng.Non-treelike network motif detection algorithm[J].Acta Electronica Sinica,2009,37(11):2420-2426.(in Chinese)
[7] 周晓锋.一种基于统计的生物网络模体发现算法[D].西安:西安电子科技大学计算机学院,2008.
[8] 孔德生.生物网络中大模体识别算法的研究[D].南京:东南大学计算机科学与工程学院,2010.
[9] 戴琼,邹潇湘,谭建龙.关于图同构复杂性的研究[J].计算机科学,2006,33(11):219-221.
  Dai Qiong,Zou Xiaoxiang,Tan Jianlong.Analysis on complexity of graph isomorphism problem[J].Computer Science,2006,33(11):219-221.(in Chinese)
[10] He Huahai,Singh Ambuj K.Closure-tree:a index structure for graph queries[C]//Proceedings of 22nd International Conference on Data Engineering.Atlanta,GA,USA,2006:39-47.
[11] 王映龙,杨珺,周法国,等.加权最大频繁子图挖掘算法的研究[J].计算机工程与应用,2009,45(20):31-34.
  Wang Yinglong,Yang Jun,Zhou Faguo,et a1.Research on algorithm for mining weighted maximal frequent subgraphs[J].Computer Engineering and Applications,2009,45(20):31-34.(in Chinese)
[12] Kirpatrick S,Gelatt C D,Veccchi M P.Optimization by simulated annealing[J].Science,1983,9(4):161-167.
[13] Soke A,Bingu Z.Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems[J].International Scientific Journal Engineering Applications of Artificial Intelligence,2006,19(5):557-567.
[14] Oysu C,Bingul Z.Application of heuristic and hybrid-GASA algorithms to tool-path optimization problem for minimizing airtime during machining[J].Engineering Applications of Artificial Intelligence,2009,22(3):389-396.
[15] Metropolis N,Rosenbluth A W,Rosenbluth M N,et al.Equation of state calculations by fast computing machine[J].The Jouunal of Chemical Physics,1953,21(6):1087-1092.
[16] Uri Alon Lab.E.COLI [EB/OL].(2002) [2011-07].http://www.weizmann.ac.il/mcb/UriAlon/Network_motifs_in_coli/ColiNet-1.1.

备注/Memo

备注/Memo:
作者简介:何洁月(1964—),女,博士,教授,jieyuehe@seu.edu.cn.
基金项目:南京大学计算机软件新技术国家重点实验室开放课题资助项目(KFKT2010B03)、 东南大学计算机网络和信息集成教育部重点实验室开放课题资助项目(K93-9-2010-19).
引文格式: 何洁月,赵德京.一种高效的生物网络概率模体发现算法[J].东南大学学报:自然科学版,2012,42(1):35-39.[doi:10.3969/j.issn.1001-0505.2012.01.007]
更新日期/Last Update: 2012-01-20