随机游走技术在网络生物学中的研究进展

doi:10.3969/j.issn.0372-2112.2018.08.033

摘要/Abstract

摘要： 网络生物学是近年来受到国际学术界广泛关注的学术前沿领域，在疾病研究和药物预测等领域有重要应用.随机游走（Random Walk）又称随机游动或随机漫步，是一种数学统计模型，在金融、物理和社会网络分析中都有广泛应用.近年来逐渐被应用到网络生物学，并在技术上得到了新的发展.本文以生物网络为基础，介绍了随机游走技术及其基本理论，并详细阐述了随机游走技术在网络生物学中的应用，具体包括蛋白质功能预测、关键蛋白质识别、疾病基因预测、疾病相关非编码RNA预测、药物相关预测等.最后讨论了随机游走技术在网络生物学研究中存在的问题以及未来的研究方向.

关键词: 随机游走, 生物网络, 网络生物学, 生物信息学, 系统生物学

Abstract: Network biology,as a hot academic frontier field,has gained increasingly wide attention in international academic circles in recent years,which plays an important role in disease research and drug discovery.Random walk is a mathematical model,which is widely used in financial,physical and social network analysis.Recently,it has gradually been applied in network biology,and the model has been improved constantly.Based on the biological network,this study introduces the technology and basic theory of random walk model firstly.Then,the applications of random walk in network biology are presented in detail,which include predicting protein functions,identifying essential proteins,predicting disease gene,discovering disease related non-coding RNAs,discovering disease related things and so on.Finally,some existing problems and future research directions of random walk in network biology research are discussed in this study.

Key words: random walk, biological network, network biology, bioinformatics, system biology

中图分类号:

TP301.6

李敏, 王晓桐, 罗慧敏, 等. 随机游走技术在网络生物学中的研究进展[J]. 电子学报, 2018, 46(8): 2035-2048.

LI Min, WANG Xiao-tong, LUO Hui-min, et al. Progress on Random Walk and Its Application in Network Biology[J]. Acta Electronica Sinica, 2018, 46(8): 2035-2048.

参考文献

[1] Barabasi A L,Oltvai Z N.Network biology:understanding the cell's functional organization[J].Nature reviews genetics,2004,5(2):101-113.
[2] BERKHIN P.A survey on pagerank computing[J].Internet Mathematics,2005,2(1):73-120.
[3] CODLING E A,Plank M J,Benhamou S.Random walk models in biology[J].Journal of the Royal Society Interface,2008,5(25):813-834.
[4] PEARSON K.The problem of the random walk[J].Nature,1905,72(1865):294.
[5] BACHELIER L.Théorie De La Spéculation[M].Paris:Gauthier-Villars,1900.
[6] Lovász L.Random walks on graphs:A survey[J].Combinatorics,Paul Erdos is Eighty,1993,2(2):353-397.
[7] HODGKINSON L,KARP R M.Algorithms to detect multiprotein modularity conserved during evolution[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics(TCBB),2012,9(4):1046-1058.
[8] LEI C,RUAN J.A random walk based approach for improving protein-protein interaction network and protein complex prediction[A].Bioinformatics and Biomedicine(BIBM)[C].Philadelphia:IEEE,2012.1-6.
[9] PAGE L,BRIN S,MOTWANI R,et al.The PageRank citation ranking:Bringing order to the web[R].California:Stanford InfoLab,1998.
[10] HAVELIWALA T H.Topic-sensitive pagerank[A].Proceedings of the 11th International Conference on World Wide Web[C].Honolulu:ACM,2002.517-526.
[11] LE D H,KWON Y K.Neighbor-favoring weight reinforcement to improve random walk-based disease gene prioritization[J].Computational Biology and Chemistry,2013,44(1):1-8.
[12] K? HLER S,BAUER S,HORN D,et al.Walking the interactome for prioritization of candidate disease genes[J].The American Journal of Human Genetics,2008,82(4):949-958.
[13] KATZ R H,BREWER E A.The Case for Wireless Pverlay Networks[M].New York:Springer US,1996.621-650.
[14] LI Y,PATRA J C.Genome-wide inferring gene-phenotype relationship by walking on the heterogeneous network[J].Bioinformatics,2010,26(9):1219-1224.
[15] 张松瑶,张绍武.基于二元网络异步重启随机游走算法预测肺癌风险致病基因[J].生物物理学报,2015(1):33-44. ZHANG S Y,ZHANG S W.Prediction of the risk of lung cancer risk in lung cancer based on the two element network with asynchronous reset random walk algorithm[J].Acta Biophysica Sinica,2015(1):33-44.(in Chinese)
[16] XIE M,HWANG T,KUANG R.Prioritizing disease genes by bi-random walk[J].Advances in Knowledge Discovery and Data Mining,2012,7302:292-303.
[17] XIE M,HWANG T H,KUANG R.Reconstructing disease phenome-genome association by bi-random walk[J].Bioinformatics,2012,1(02):1-8.
[18] PENG W,WANG J,CHEN L,et al.Predicting protein functions by using unbalanced bi-random walk algorithm on protein-protein interaction network and functional interrelationship network[J].Current Protein and Peptide Science,2014,15(6):529-539.
[19] PENG W,LI M,CHEN L,et al.Predicting protein functions by using unbalanced random walk algorithm on three biological networks[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2017,14(2):360-369.
[20] PENG W,LAN Wei,WANG Jianxin,et al.Predicting microRNA-disease associations by walking on four biological networks[A].Bioinformatics and Biomedicine(BIBM)[C].Shenzhen:BIBM,2016.299-302.
[21] TATUSOV R L,KOONIN E V,LIPMAN D J.A genomic perspective on protein families[J].Science,1997,278(5338):631-637.
[22] MARCOTTE E M,PELLEGRINI M,THOMPSON M J,et al.A combined algorithm for genome-wide prediction of protein function[J].Nature,1999,402(6757):83-86.
[23] ZHANG X F,DAI D Q.A framework for incorporating functional interrelationships into protein function prediction algorithms[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics(TCBB),2012,9(3):740-753.
[24] FRESCHI V.Protein function prediction from interaction networks using a random walk ranking algorithm[A].IEEE 7th International Symposium on BioInformatics and BioEngineering[C].Silicon valley,USA:BIBE,2007.42-48.
[25] YU G,RANGWALA H,DOMENICONI C,et al.Protein function prediction using multilabel ensemble classification[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2013,10(4):1045-1057.
[26] HU P,JIANG H,EMILI A.Predicting protein functions by relaxation labelling protein interaction network[J].BMC Bioinformatics,2010,11(S1):S64.
[27] 马吉权,贾翠翠,张军杰.基于随机游走的蛋白质功能预测算法设计与实现[J].黑龙江大学工程学报,2015(03):73-78. MA Gequan,JIA Cuicui,ZHANG Junjie.Prediction of protein based on random walk algorithm design and implementation[J].Engineering Journal of Heilongjiang University,2015(03):73-78.(in Chinese)
[28] 邓小龙.基于随机游走的蛋白质功能预测方法的研究[D].长春:吉林大学,2012. DENG X L.Study on protein function prediction based on random walk[D].Changchun:Jilin University,2012.(in Chinese)
[29] ZHANG S,CHEN H,LIU K,et al.Inferring protein function by domain context similarities in protein-protein interaction networks[J].BMC Bioinformatics,2009,10(1):395.
[30] JEONG H,MASON S P,BARABáSI A L,et al.Lethality and centrality in protein networks[J].Nature,2001,411(6833):41-42.
[31] PENG W,WANG J,CHENG Y,et al.UDoNC:an algorithm for identifying essential proteins based on protein domains and protein-protein interaction networks[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics(TCBB),2015,12(2):276-288.
[32] DEL RIO G,KOSCHüTZKI D,COELLO G.How to identify essential genes from molecular networks?[J].BMC Systems Biology,2009,3(1):102.
[33] 杨莉萍,路松峰,黄钰.一种基于随机游走模型的关键蛋白质预测方法[J].华中农业大学学报,2016,35(6):86-91. YANG Liping,LU Songfeng,HUANG Yu.A method for predicting essential proteins based on random walk mode[J].Journal of Huazhong Agricultural University,2016,35(6):86-91.(in Chinese)
[34] PENG W,WANG J,WANG W,et al.Iteration method for predicting essential proteins based on orthology and protein-protein interaction networks[J].BMC Systems Biology,2012,6(1):87.
[35] WANG J,LI M,CHEN J,et al.A fast hierarchical clustering algorithm for functional modules discovery in protein interaction networks[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2011,8(3):607-620.
[36] VANUNU O,MAGGER O,RUPPIN E,et al.Associating genes and protein complexes with disease via network propagation[J].PLoS Comput Biol,2010,6(1):e1000641.
[37] LI M,ZHENG R,LI Q,et al.Prioritizing disease genes by using search engine algorithm[J].Current Bioinformatics,2016,11(2):195-202.
[38] CHEN J,ARONOW B J,JEGGA A G.Disease candidate gene identification and prioritization using protein interaction networks[J].BMC Bioinformatics,2009,10(1):73.
[39] CHEN J,BARDES E E,ARONOW B J,et al.Toppgene suite for gene list enrichment analysis and candidate gene prioritization[J].Nucleic Acids Research,2009,37(suppl 2):W305-W311.
[40] GUO X,GAO L,WEI C,et al.A computational method based on the integration of heterogeneous networks for predicting disease-gene associations[J].PloS One,2011,6(9):e24171.
[41] OMER A,SINGH P,YADAV N K,et al.MicroRNAs:role in leukemia and their computational perspective[J].Wiley Interdisciplinary Reviews:RNA,2015,6(1):65-78.
[42] AMBROS V.MicroRNAs:tiny regulators with great potential[J].Cell,2001,107(7):823-826.
[43] CHEN X,LIU M X,YAN G Y.RWRMDA:predicting novel human micro RNA-disease associations[J].Molecular BioSystems,2012,8(10):2792-2798.
[44] CHEN H,ZHANG Z.Prediction of associations between OMIM diseases and MicroRNAs by random walk on OMIM disease similarity network[J].The Scientific World Journal,2013,2013:204658.
[45] XUAN P,HAN K,Guo Y,et al.Prediction of potential disease-associated microRNAs based on random walk[J].Bioinformatics,2015,31(11):1805-1815.
[46] PENG W,LAN W,YU Z,et al.Predicting microrna-disease associations by random walking on multiple networks[A].International Symposium on Bioinformatics Research and Applications.Springer International Publishing[C].Minsk,Belerus:ISBRA,2016.127-135.
[47] GUPTA R A,SHAH N,WANG K C,et al.Long non-coding RNA HOTAIR reprograms chromatin state to promote cancer metastasis[J].Nature,2010,464(7291):1071-1076.
[48] SUN J,SHI H,WANG Z,et al.Inferring novel lncRNA-disease associations based on a random walk model of a lncRNA functional similarity network[J].Molecular BioSystems,2014,10(8):2074-2081.
[49] ZHOU M,WANG X,LI J,et al.Prioritizing candidate disease-related long non-coding RNAs by walking on the heterogeneous lncRNA and disease network[J].Molecular BioSystems,2015,11(3):760-769.
[50] CHEN X,YOU Z,YAN G,et al.IRWRLDA:improved random walk with restart for lncRNA-disease association prediction[J].Oncotarget,2016,7(36):57919-57931.
[51] CHEN X,LIU M X,YAN G Y.Drug-target interaction prediction by random walk on the heterogeneous network[J].Molecular BioSystems,2012,8(7):1970-1978.
[52] EMIG D,IVLIEV A,PUSTOVALOVA O,et al.Drug target prediction and repositioning using an integrated network-based approach[J].PLoS One,2013,8(4):e60618.
[53] CHEN L C,YEH H Y,YEH C Y,et al.Identifying co-targets to fight drug resistance based on a random walk model[J].BMC Systems Biology,2012,6(1):5.
[54] RAHMANI H,WEISS G,MéNDEZ-LUCIO O,et al.ARWAR:A network approach for predicting adverse drug reactions[J].Computers in Biology and Medicine,2016,68:101-108.
[55] LUO H,WANG J,LI M,et al.Drug repositioning based on comprehensive similarity measures and bi-random walk algorithm[J].Bioinformatics,2016,32(17):2664-2671
[56] ENRIGHT A J,VAN DONGEN S,OUZOUNIS C A.An efficient algorithm for large-scale detection of protein families[J].Nucleic Acids Research,2002,30(7):1575-1584.
[57] PENG W,WANG J,ZHAO B,et al.Identification of protein complexes using weighted pagerank-nibble algorithm and core-attachment structure[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics(TCBB),2015,12(1):179-192.
[58] SUTHRAM S,DUDLEY J T,CHIANG A P,et al.Network-based elucidation of human disease similarities reveals common functional modules enriched for pluripotent drug targets[J].PLoS Comput Biol,2010,6(2):e1000662.
[59] LI P,NIE Y,YU J.Fusing literature and full network data improves disease similarity computation[J].BMC Bioinformatics,2016,17(1):326.
[60] ERTEN S,BEBEK G,KOYUTüRK M.Vavien:an algorithm for prioritizing candidate disease genes based on topological similarity of proteins in interaction networks[J].Journal of Computational Biology,2011,18(11):1561-1574.
[61] CHIPMAN K C,SINGH A K.Predicting genetic interactions with random walks on biological networks[J].BMC Bioinformatics,2009,10(1):17
[62] YOON B J,QIAN X,SAHRAEIAN S M E.Comparative analysis of biological networks:Hidden markov model and markov chain-based approach[J].IEEE Signal Processing Magazine,2012,1(29):22-34.
[63] 赵建邦,董安国,高琳.一种用于生物网络数据的频繁模式挖掘算法[J].电子学报,2010,38(8):1803-1807. ZHAO J,DONG A,GAO L.An algorithm for frequent pattern mining in biological networks[J].Acta Electronica Sinica,2010,38(8):1803-1807.(in Chinese)
[64] SAHRAEIAN S M E,YOON B J.RESQUE:Network reduction using semi-Markov random walk scores for efficient querying of biological networks[J].Bioinformatics,2012,28(16):2129-2136.
[65] 鞠薇.基于随机游走和图割算法的PET-CT肺肿瘤分割[D].苏州:苏州大学,2015. JU W.Random walk and graph cut for co-segmentation of lung tomor on PET-CT images[D].Suzhou:Suzhou University,2015.(in Chinese)
[66] 胡洁.基于图论的医学图像分割随机游走算法研究[D].广州:南方医科大学,2013. HU J.Research on random walk algotithm based graph theory on the application of medical image segmentation[D].Guangzhou:Southern Medical University,2013.(in Chinese)
[67] ZHAO Z Q,HAN G S,YU Z G,et al.Laplacian normalization and random walk on heterogeneous networks for disease-gene prioritization[J].Computational Biology and Chemistry,2015,57C:21-28.
[68] WANG J,PENG X,PENG W,et al.Dynamic protein interaction network construction and applications[J].Proteomics,2014,14(4-5):338-352.
[69] LI M,WU X,WANG J,et al.Towards the identification of protein complexes and functional modules by integrating PPI network and gene expression data[J].BMC Bioinformatics,2012,13(1):109.
[70] 李敏,孟祥茂.动态蛋白质网络的构建、分析及应用研究进展[J].计算机研究与发展,2017,54(6):1281-1299. LI M,MENG X.The construction,analysis,and applications of dynamic protein-protein interaction networks[J].Journal of Computer Research and Development,2017,54(6):1281-1299.(in Chinese)
[71] LI M,MENG X,ZHENG R,et al.Identification of protein complexes by using a spatial and temporal active protein interaction network[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2017,DOI:10.1109/TCBB.2017.2749571.
[72] SUN S Y,LIU Z P,ZENG T,et al.Spatio-temporal analysis of type 2 diabetes mellitus based on differential expression networks[J].Scientific Reports,2013,2013,3(2268):1-13.