Functional Module Detection Based on Multi-label Propagation Mechanism in Protein-Protein Interaction Networks
HAN Yue, JI Junzhong, YANG Cuicui
Beijing Municipal Key Laboratory of Multimedia and Intelligent Software Technology, College of Compute Science, Beijing University of Technology, Beijing 100124
Abstract：Due to the fast and efficient solution of multi-label propagation algorithm in detecting community for social network, a functional module detection based on multi-label propagation mechanism in protein-protein interaction (PPI) networks (MLP-FMD) is proposed by merging multi-source protein biological knowledge. Firstly, the labels of nodes are initialized by using the functional and structural information of a PPI Network. Then, the co-expression of the protein is calculated by using the gene expression data and thus the label set of the nodes is constructed, and the label is selected to achieve the true and reliable transmission among the nodes. Finally, the nodes with same identifier are divided into the same functional module, and the final result is obtained. Experiments show good time performance and a certain competitive ability of the detection accuracy of the proposed algorithm.
韩跃，冀俊忠，杨翠翠. 基于多标签传播机制的蛋白质相互作用网络功能模块检测*[J]. 模式识别与人工智能, 2016, 29(6): 548-557.
HAN Yue, JI Junzhong, YANG Cuicui. Functional Module Detection Based on Multi-label Propagation Mechanism in Protein-Protein Interaction Networks. , 2016, 29(6): 548-557.
[1] JI J Z, LIU Z J, ZHANG A D, et al. Ant Colony Optimization with Multi-agent Evolution for Detecting Functional Modules in Protein-Protein Interaction Networks // Proc of the 3rd International Conference on Information Computing and Applications. Berlin, Germany: Springer-Verlag, 2012: 445-453. [2] JI J Z, ZHANG A D, LIU C N, et al. Survey: Functional Module Detection from Protein-Protein Interaction Networks. IEEE Trans on Knowledge and Data Engineering, 2014, 26(2): 261-277. [3] RIGAUT G, SHEVCHENKO A, RUTZ B, et al. A Generic Protein Purification Method for Protein Complex Characterization and Proteome Exploration. Nature Biotechnology, 1999, 17(10): 1030-1032. [4] BADER G D, HOGUE C W V. An Automated Method for Finding Molecular Complexes in Large Protein Interaction Networks. BMC Bioinformatics, 2003. DOI: 10.1186/1471-2105-4-2. [5] PALLA G, DERNYI I, FARKAS I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature, 2005, 435(7043): 814-818. [6] ADAMCSEK B, PALLA G, FARKAS I J, et al. CFinder: Locating Cliques and Overlapping Modules in Biological Networks. Bioinformatics, 2006, 22(8): 1021-1023. [7] ALDECOA R, MARN I. Jerarca: Efficient Analysis of Complex Networks Using Hierarchical Clustering. Plos One, 2010, 5(7). DOI: 10.1371/journal.pone.0011585. [8] VAN DONGEN S. A Cluster Algorithm for Graphs. Technical Report, INS-R0010. Amsterdam, The Netherlands: National Research Institute for Mathematics and Computer Science in the Netherlands, 2000. [9] WU M, LI X L, KWOH C K, et al. A Core-Attachment Based Method to Detect Protein Complexes in PPI Networks. BMC Bioinformatics, 2009. DOI: 10.1186/1471-2105-10-169. [10] JI J Z, LIU Z J, ZHANG A D, et al. Improved Ant Colony Optimization for Detecting Functional Modules in Protein-Protein Interaction Networks // Proc of the 3rd International Conference on Information Computing and Applications. Heidelberg, Germany: Springer-Verlag, 2012, II: 404-413. [11] ZHU X J, GHAHRAMANI Z. Learning from Labeled and Unlabeled Data with Label Propagation. Technical Report, CMU-CALD-02-107. Pittsburgh, USA: Carnegie Mellon University, 2002. [12] YANG L P, JI D H, NIE Y. Information Retrieval Using Label Propagation Based Ranking [EB/OL]. [2015-09-20].http://www.mt-archive.info/NTCIR-2007-Yang.pdf. [13] SPERIOSU M, SUDAN N, UPADHYAY S, et al. Twitter Polarity Classification with Label Propagation over Lexical Links and the Follower Graph // Proc of the 1st Workshop on Unsupervised Learning in Natural Language Processing. Stroudsburg, USA: Association for Computational Linguistics, 2011: 53-63. [14] TANG J H, HUA X S, QI G J, et al. Video Annotation Based on Kernel Linear Neighborhood Propagation. IEEE Trans on Multime- dia, 2008, 10(4): 620-628. [15] ISMAIL M M B. Image Annotation and Retrieval Based on Multi-modal Feature Clustering and Similarity Propagation. Ph.D Dissertation. Louisville, USA: University of Louisville, 2011. [16] RAGHAVAN U N, ALBERT R, KUMARA S. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. Physical Review E, 2007. DOI: 10.1103/PhysRevE.76.036106. [17] LEUNG I X Y, HUI P, LIO P, et al. Towards Real-Time Community Detection in Large Networks. Physical Review E, 2009. DOI: 10.1103/PhysRevE.79.066107. [18] GREGORY S. Finding Overlapping Communities in Networks by Label Propagation. New Journal of Physics, 2010. DOI: 10.1088/1367-2630/12/10/103018. [19] DAI Q G, GUO M Z, LIU X Y, et al. CPL: Detecting Protein Complexes by Propagating Labels on Protein-Protein Interaction Network. Journal of Computer Science and Technology, 2014, 29(6): 1083-1093. [20] 李 敏,武学鸿,费耀平.融合 PPI 网络和基因表达的复合物识别算法.系统工程理论与实践, 2014, 34(2): 437-443. (LI M, WU X H, FEI Y P. An Algorithm for Identifying Protein Complexes Based on the Integration of PPI Network and Gene Expression. Systems Engineering-Theory & Practice, 2014, 34(2): 437-443.) [21] WU Z H, LIN Y F, GREGORY S, et al. Balanced Multi-label Propagation for Overlapping Community Detection in Social Networks. Journal of Computer Science and Technology, 2012, 27(3): 468-479. [22] GAVIN A C, ALOY P, GRANDI P, et al. Proteome Survey Reveals Modularity of the Yeast Cell Machinery. Nature, 2006, 440(7084): 631-636. [23] MEWES H W, AMID C, ARNOLD R, et al. MIPS: Analysis and Annotation of Proteins from Whole Genomes. Nucleic Acids Research, 2004, 32(S1): D41-D44. [24] XENARIOS I, SALWINSKI L, DUAN X J, et al. Dip, the Database of Interacting Proteins: A Research Tool for Studying Cellular Networks of Protein Interactions. Nucleic Acids Research, 2002, 30(1): 303-305. [25] TU B P, KUDLICKI A, ROWICKA M, et al. Logic of the Yeast Metabolic Cycle: Temporal Compartmentalization of Cellular Processes. Science, 2005, 310(5751): 1152-1158. [26] FRIEDEL C C, KRUMSIEK J, ZIMMER R. Bootstrapping the Interactome: Unsupervised Identification of Protein Complexes in Yeast. Journal of Computational Biology, 2009, 16(8): 971-987. [27] BROHE S, VAN HELDEN J. Evaluation of Clustering Algorithms for Protein-Protein Interaction Networks. BMC Bioinformatics, 2006, 7: 2791-2797.
2016, Vol. 29 
