电子学报 ›› 2018, Vol. 46 ›› Issue (8): 2035-2048.DOI: 10.3969/j.issn.0372-2112.2018.08.033
李敏, 王晓桐, 罗慧敏, 孟祥茂, 王建新
收稿日期:
2017-03-23
修回日期:
2017-08-10
出版日期:
2018-08-25
作者简介:
基金资助:
LI Min, WANG Xiao-tong, LUO Hui-min, MENG Xiang-mao, WANG Jian-xin
Received:
2017-03-23
Revised:
2017-08-10
Online:
2018-08-25
Published:
2018-08-25
Supported by:
摘要: 网络生物学是近年来受到国际学术界广泛关注的学术前沿领域,在疾病研究和药物预测等领域有重要应用.随机游走(Random Walk)又称随机游动或随机漫步,是一种数学统计模型,在金融、物理和社会网络分析中都有广泛应用.近年来逐渐被应用到网络生物学,并在技术上得到了新的发展.本文以生物网络为基础,介绍了随机游走技术及其基本理论,并详细阐述了随机游走技术在网络生物学中的应用,具体包括蛋白质功能预测、关键蛋白质识别、疾病基因预测、疾病相关非编码RNA预测、药物相关预测等.最后讨论了随机游走技术在网络生物学研究中存在的问题以及未来的研究方向.
中图分类号:
李敏, 王晓桐, 罗慧敏, 等. 随机游走技术在网络生物学中的研究进展[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. |
[1] | 曹阳, 高旻, 余俊良, 范琪琳, 荣文戈, 文俊浩. 基于双图混合随机游走的社会化推荐模型[J]. 电子学报, 2023, 51(2): 286-296. |
[2] | 李青青, 马慧芳, 李举, 李志欣. 属性网络中相似性增强随机游走的多社区搜索[J]. 电子学报, 2021, 49(11): 2096-2100. |
[3] | 马慧芳, 刘芳, 夏琴, 郝占军. 基于加权超图随机游走的文献关键词提取算法[J]. 电子学报, 2018, 46(6): 1410-1414. |
[4] | 袁红星, 安鹏, 吴少群, 郑悠. 具有容错能力的L1最优化半自动2D转3D[J]. 电子学报, 2018, 46(2): 447-455. |
[5] | 方晨, 张恒巍, 王娜, 王晋东. 基于随机游走和多样性图排序的个性化服务推荐方法[J]. 电子学报, 2018, 46(11): 2773-2780. |
[6] | 牛新征, 牛嘉郡, 苏大壮, 佘堃. 基于加权内容-结构网络和随机游走的社团划分算法[J]. 电子学报, 2017, 45(9): 2135-2142. |
[7] | 康世泽, 马宏, 黄瑞阳. 一种基于Opinosis图和马尔科夫随机游走模型的多文本情感摘要框架[J]. 电子学报, 2017, 45(12): 3005-3011. |
[8] | 吴少群, 袁红星, 安鹏, 程培红. 软分割约束边缘保持插值的半自动2D转3D[J]. 电子学报, 2015, 43(11): 2218-2224. |
[9] | 周家锐, 纪震, 朱泽轩, 陈思平. 基于Memetic优化的智能DNA序列数据压缩算法[J]. 电子学报, 2013, 41(3): 513-518. |
[10] | 陈圣国, 孙正兴, 周杰. 基于FCM和随机游走的地层图像分割方法[J]. 电子学报, 2013, 41(3): 526-531. |
[11] | 邹权;李旭斌;林子雨;江弋;林琛. 下一代测序技术数据中的选择性剪切计算识别方法研究[J]. 电子学报, 2012, 40(2): 350-357. |
[12] | 文韬, 葛泉波. 未建模系统基于观测值的实时分块Kalman滤波估计方法研究[J]. 电子学报, 2012, 40(10): 1958-1964. |
[13] | 纪震;周家锐;朱泽轩;Q H Wu. 基于生物信息学特征的DNA序列数据压缩算法[J]. 电子学报, 2011, 39(5): 991-995. |
[14] | 刘峤;王娟;陈伟;秦志光. 基于随机复杂度约束的高维特征自动选择算法[J]. 电子学报, 2011, 39(2): 370-374. |
[15] | 赵建邦;董安国;高 琳. 一种用于生物网络数据的频繁模式挖掘算法[J]. 电子学报, 2010, 38(8): 1803-1807. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||