蛋白质相互作用网络分析的图聚类方法研究进展

摘要/Abstract

摘要：

随着可获得的大规模蛋白质相互作用数据的迅速增长，从系统水平上对细胞机制的基本组件和结构的理解成为了一种可能。如今所面临的最大挑战是如何通过分析此类复杂的相互作用数据来反映细胞组织、进程以及功能的规律。基于图理论的聚类方法是分析蛋白质相互作用数据的有效手段。本文将从蛋白质相互作用网络（PPI网络）的图模型、聚类算法、评估方法及应用几个方面描述PPI网络聚类分析的最新研究进展。最后，讨论该方向研究所面临的挑战及进一步的研究方向。

关键词: 系统生物学, 蛋白质相互作用网络, 图聚类方法, 蛋白质复合物, 蛋白质功能

Abstract:

With the increase of largescale proteinprotein interaction data available, it has been possible to understand the basic components and organization of the cell mechanism from the system level. The challenge is how to analyze such complex interacting data to reveal the principles of cellular organization, processes and functions. Many studies have shown that using graphbased clustering methods is an effective approach to analyzing proteinprotein interaction data. In this review, several aspects will be presented to describe the recent advances in clustering methods for protein interaction networks, such as the graph models of the PPI network, clustering methods, evaluation methods and applications. Finally, the challenges and directions for future research will be discussed.

Key words: system biology;protein interaction network;graphbased clustering algorithms;protein complex;protein function

李敏1，武学鸿1，王建新1，潘毅1,2. 蛋白质相互作用网络分析的图聚类方法研究进展[J]. J4, 2012, 34(1): 124-136.

LI Min1,WU Xuehong1,WANG Jianxin1,PAN Yi 1,2. Progress on GraphBased Clustering Methods for the Analysis of ProteinProtein Interaction Networks[J]. J4, 2012, 34(1): 124-136.

参考文献［87］

［1］	von Mering C, Krause R, Sne B, et al. Comparative Assessment of LargeScale Data Sets of ProteinProtein Interactions［J］. Nature, 2002,417(6887):399403.
［2］	del Sol A, O’Meara P. SmallWorld Network Approach to Identify Key Residues in ProteinProtein Interaction［J］. Proteins, 2004, 58(3):672682.
［3］	del Sol A, Fujihashi H, O’Meara P. Topology of SmallWorld Networks of ProteinProtein Complex Structures［J］. Bioinformatics, 2005, 21(8):1311131.
［4］	Brohée S, van Helden J. Evaluation of Clustering Algorithms for Protein Protein Interaction Networks［J］. BMC Bioinformatics,2006, 7:488.
［5］	Spirin V, Mirny LA. Protein Complexes and Functional Modules in Molecular Networks［J］. PNAS, 2003,100:1212312128.
［6］	Fields S, Song O. A Novel Genetic System to Detect ProteinProtein Interactions［J］. Nature, 1989, 340(6230):245246.
［7］	Harwell LH, Hopfield JJ, Leibler S, et al. From Molecular to Modular Cell Biology［J］. Nature, 1999, 402:c47c52.
［8］	AltafUIAmin M, Shinbo Y, Mihara K, et al. Development and Implementation of an Algorithm for Detection of Protein Complexes in Large Interaction Networks［J］. BMC Bioinformatics, 2006, 7:207.
［9］	Wang J X, Li M, Chen J, et al. A Fast Hierarchical Clustering Algorithm for Functional Modules Discovery in Protein Interaction Networks［J］. IEEE/ACM Trans on Computational Biology and Bioinformatics， 2011,8(3):607620.
［10］	Jeong H, Mason S, Barabási AL, et al: Lethality and Centrality in Protein Networks［J］. Nature, 2001, 411(6833):4142.
［11］	Giot L, Bader J S, Brocewer C,et al. A Protein Interaction Map of Drosophila Melanogaster［J］. Science, 2003, 302:17271736.
［12］	Uetz P, Giot L, Cagney G, et al. A Comprehensive Analysis of ProteinProtein Interactions in Saccharomyces Cerevisiae［J］. Nature, 2000, 403(6770):623627.
［13］	Rigaut G, Shevchenko A, Rutz B, et al. A Generic Protein Purification Method for Protein Complex Characterization and Proteome Exploration［J］. Nature Biotechnology, 1999, 17(10):10301032.
［14］	Ho Y, Gruhler A, Heilbut A, et al. Systematic Identification of Protein Complexes in Saccharomyces Cerevisiae by Mass Spectrometry［J］. Nature, 2002, 415(6868):180183.
［15］	Zhu H, Bilgin M, Bangham R, et al. Global Analysis of Protein Activities Using Proteome Chips［J］. Science, 2001, 293(5537):21012105.
［16］	Spirin V, Mirny L A. Protein Complexes and Functional Modules in Molecular Networks［J］. PNAS, 2003, 100(21):1212312128.
［17］	Palla G, Dernyi I, Farkas I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society［J］. Nature, 2005, 435(7043):814818.
［18］	Adamcsek B, Palla G, Farkas I, et al. CFinder: Locating Cliques and Overlapping Modules in Biological Networks［J］. Bioinformatics, 2006, 22(8):10211023.
［19］	Li X L, Tan S H, Foo C S, et al. Interaction Graph Mining for Protein Complexes Using Local Clique Merging［J］. GIW, 2005, 16(2):260269.
［20］	Wang J X, Liu B B, Li M, et al. Identifying Protein Complexes from Interaction Networks Based on Clique Percolation and Distance Restraction［J］. BMC Genomics, 2010,11(S2):S10.
［21］	Li M, Wang J X, Chen J, et al. Identifying the Overlapping Complexes in Protein Interaction Networks［J］.Int. J. DataMing and Bioinformatics, 2010, 4(1):91108.
［22］	Bu D, Zhao Y, Cai L, et al. Topological Structure Analysis of the ProteinProtein Interaction Network in Budding Yeast［J］. Nucleic Acids Research, 2003, 31(9):24432450.
［23］	Bader G D, Hogue C W. An Automated Method for Finding Molecular Complexes in Large Protein Interaction Networks［J］. BMC Bioinformatics, 2003, 4:259.
［24］	Li M, Chen J, Wang J, et al. Modifying the DPClus Algorithm for Identifying Protein Complexes Based on New Topological Structures［J］. BMC Bioinformatics, 2008, 9:398.
［25］	Liu G, Wong L, Chua H. Complex Discovery from Weighted PPI Networks［J］. Bioinformatics, 2009, 25(15):18911897.
［26］	Navlakha S, Schatz MC, Kingsford C. Revealing Biological Modules via Graph Summarization［J］. Journal of Computational Biology, 2009, 16(2):253264.
［27］	Yu L, Gao L, Sun P G. A Hybrid Clustering Algorithm for Identifying Modules in ProteinProtein Interaction Networks［J］. Int J Data Min Bioinform, 2010, 4(5):600615.
［28］	Kim J, Tan K. Discover Protein Complexes in ProteinProtein Interaction Networks Using Parametric Local Modularity［J］. BMC Bioinformatics 2010, 11:521.
［29］	Yook S, Oltvai Z, Barabási. A Functional and Topological Characterization of Protein Interaction Networks［J］. Proteomics, 2004, 4(4):928942.
［30］	Farkas I, Jeong H, Viscek T, et al. The Topology of the Transcriptional Regulatory Network in the Yeast［J］. S. Cerevisiae. Physica A, 2003, 318:601612.
［31］	Girvan M, Newman M. Community Structure in Social and Biological Networks［J］. PNAS, 2002, 99(12):78217826.
［32］	Newman M, Girvan M. Finding and Evaluating Community Structure in Networks［J］. Physical Review E, 2004, 69(2):116.
［33］	Radicchi F, Castellano C, Cecconi F. Defining and Identifying Communities in Networks［J］. PNAS, 2004, 101(9):26582663.
［34］	Prulj N, Wigle D A, Jurisica I. Functional Topology in a Network of Protein Interactions［J］. Bioinformatics, 2004, 20(3):340348.
［35］	Luo F, Yang Y, Chen C F, et al. Modular Organization of Protein Interaction Networks［J］. Bioinformatics, 2007, 23(2):207214.
［36］	Clauset A, Moore C, Newman M. Hierarchical Structure and the Prediction of Missing Links in Networks［J］. Nature, 2008, 453:98101.
［37］	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.
［38］	PereiraLeal J, Enright A, Ouzounis C. Detection of Functional Modules from Protein Interaction Networks［J］. PROTEINS: Structure, Function, and Bioinformatics, 2004, 54:4957.
［39］	King A D, Prulj N, Jurisica I. Protein Complex Prediction via CostBased Clustering［J］. Bioinformatics, 2004, 20(17):30133020.
［40］	Hwang W, Cho Y R, Zhang A, et al. A Novel Functional Module Detection Algorithm for ProteinProtein Interaction Networks［J］. Algorithms for Molecular Biology, 2006, 12:124.
［41］	Ruan J H, Zhang W X. An Efficient Spectral Algorithm for Network Community Discovery and Its Applications to Biological and Social Networks［C］∥Proc of the 7th IEEE Int’l Conf on Data Mining, 2007, 72:643648.
［42］	Mete M, Tang F, Xu X, Yuruk N. A Structural Approach for Finding Functional Modules from Large Biological Networks［J］. BMC Bioinformatics,2008,9(Suppl 9):S19.
［43］	Luo F, Li B, Wan X F, et al. Core and Periphery Structures in Protein Interaction Networks［J］. BMC Bioinformatics, 2009, 10(Suppl 4):S8.
［44］	Maraziotis I, Dimitrakopoulou K, Bezerianos A. Growing Functional Modules from a Seed Protein via Integration of Protein Interaction and Gene Expression Data［J］. BMC Bioinformatics, 2007, 8:408.
［45］	Ulitsky I, Shamir R. Identification of Functional Modules Using Network Topology and Highthroughput Data［J］. BMC Systems Biology, 2007, 1:8.
［46］	Feng J, Jiang R, Jiang T. A MaxFlow Based Approach to the Identification of Protein Complexes Using Protein Interaction and Microarray Data［C］∥Proc of CSB, 2008:5162.
［47］	Jansen R, Greenbaum D, Gerstein M. Relating Wholegenome Expression Data with ProteinProtein Interactions［J］. Genome Research, 2002, 12(1):3746.
［48］	Hanisch D, Zien A, Zimmer R, et al. Coclustering of Biological Networks and Gene Expression Data［J］. Bioinformatics, 2002, 18(S1):S145S154.
［49］	Ideker T, Ozier O, Schwikowski B, et al. Discovering Regulatory and Signaling Circuits in Molecular Interaction Networks［J］. Bioinformatics, 2002,18(S1):S233S240.
［50］	Segal E, Wang H, Koller D. Discovering Molecular Pathways from Protein Interaction and Gene Expression Data［J］. Bioinformatics, 2003,19(Suppl 1): i264i271.
［51］	Lu H, Shi B, Wu G, et al. Integrated Analysis of Multiple Data Sources Reveals Modular Structure of Biological Networks［J］. Biochem Biophys Res Commun, 2006, 345(1):302309.
［52］	Lubovac Z, Gamalielsson J, Olsson B. Combining Functional and Topological Properties to Identify Core Modules in Protein Interaction Networks［J］. Proteins, 2006, 64(4):948959.
［53］	Li X, Foo C, Ng S. Discovering Protein Complexes in Dense Reliable Neighborhoods of Protein Interaction Networks［C］∥Proc of CSB’07, 2007:157168.
［54］	Turanalp M E, Can T. Discovering Functional Interaction Patterns in ProteinProtein Interaction Networks［J］. BMC Bioinformatics, 2008, 9:276.
［55］	Jiang T, Keating A E. AVID: An iIntegrative Framework for Discovering Functional Relationships Among Proteins［J］. BMC Bioinformatics, 2005, 6:136.
［56］	Zheng H, Wang H, Glass D H. Integration of Genomic Data for Inferring Protein Complexes from Global ProteinProtein Interaction Networks［J］. IEEE Transactions on Systems, Man and Cybernetics—Part B,2008, 38(1):516.
［57］	Mewes H W, Amid C, Arnold R, et al. MIPS: Analysis and Annotation of Proteins from Whole Genomes［J］. Nucleic Acids Research, 2004, 32(S1):D41D44.
［58］	http://www.geneontology.org.
［59］	Zhang B, Park B, KarpinetsT, et al. From Pulldown Data to Protein Interaction Networks and Complexes with Biological Relevance［J］. Bioinformatics, 2008, 24(7):979986.
［60］	Song J,Singh M. How and When should Interactomederived Clusters be Used to Predict Functional Modules and Protein Function［J］. Bioinformatics, 2009, 25(29):31433150.
［61］	Lord P W, Stevens R D, Brass A, et al. Semantic Similarity Measures as Tools for Exploring the Gene Ontology［C］∥Proc of the Pacific Symposium on Biocomputing,2003:601612.
［62］	Wang J Z, Du Z, Payattakool R, et al. A New Method to Measure the Semantic Similarity of Go Terms［J］. Bioinformatics,2007,23(10):12741281.
［63］	Zhang Y, Zeng E, Li T, et al. Weighted Consensus Clustering for Identifying Functional Modules in ProteinProtein Interaction Networks［C］∥Proc of the 2009 Int’l Conf on Machine Learning and Applications, 2009:539544.
［64］	田野，刘大有，杨博. 复杂网络聚类算法在生物网络中的应用［J］. 计算机科学与探索,2010,4(4):330337.
［65］	Sharan R, Ulitsky I,Shamir R. Networkbased Prediction of Protein Function［J］. Molecular Systems Biology, 2007, 3:88.
［66］	孙景春,徐晋麟,李亦学,等.大规模蛋白质相互作用数据的分析与应用［J］.科学通报,2005,50(19):20552060.
［67］	王建新, 蔡钊, 李敏. 一种基于极大团的蛋白质相互作用预测方法［J］. 高技术通讯, 2009, 19(1):8288.
［68］	Winzeler E A, Shoemaker D D, Astromoff A, et al. Functional Characterization of the S. Cerevisiae Genome by Gene Deletion and Parallel Analysis［J］. Science, 1999, 285(5429):901906.
［69］	Hart G T, Lee I, Marcotte E. A HighAccuracy Consensus Map of Yeast Protein Complexes Reveals Modular Nature of Gene Essentiality［J］. BMC Bioinformatics, 2007, 8(1):236.
［70］	Wang H, Li M, Wang J, et al. A New Method for Identifying Essential Proteins Based on Edge Clustering Coefficient［C］∥Proc of the ISBRA 2011, 2011:8798.
［71］	Ren J, Wang J, Li M, et al. Prediction of Essential Proteins by Integration of PPI Network Topology and Protein Complexes Information［C］∥Proc of the ISBRA 2011, 2011:1224.
［72］	Li D, Liu W L, Liu Z Y, et al. PRINCESS, a Protein Interaction Confidence Evaluation System with Multiple Data Sources［J］. Molecular & Cellular Proteomics, 2008,7(6):10431052.
［73］	Ge H, Liu Z, Church G M, et al. Correlation Between Transcriptome and Interactome Mapping Data from Saccharomyces Cerevisiae［J］. Nat Genet, 2001,29(4):482486.
［74］	Kentner D,Sourjik V. Dynamic Map of Protein Interactions in the Escherichia Coli Chemotaxis Pathway［J］. Molecular Systems Biology, 2009, 238(5):110.
［75］	Han D, Bertin N, Hao T, et al. Evidence for Dynamically Organized Modularity in the Yeast ProteinProtein Interaction Network［J］. Nature, 2004, 430:8893.
［76］	Komurov K,White M. Revealing Static and Dynamic Modular Architecture of the Eukaryotic Protein Interaction Network［J］. Molecular Systems Biology, 2007, 3(110):111.
［77］	Jin R, Mccallen S, Liu C, et al. Identifying Dynamic Network Modules with Temporal and Spatial Constraints［C］∥Proc of the Pacific Symp on Biocomputing, 2009, 14:203214.
［78］	Taylor I W, Linding R, Farley D W, et al. Dynamic Modularity in Protein Interaction Networks Predicts Breast Cancer Outcome［J］. Nature Biotechnology, 2009, 27(2):199204.
［79］	Przytycka T M, Singh M,Slonim D K. Toward the Dynamic Interactome: It’s About Time［J］. Briefings in Bioinformatics, 2010,11(1):1529.
［80］	Przytycka T M, Kim Y. Network Integration Meets Network Dynamics［J］. BMC Biology, 2010, 8:48.
［81］	Lin C, Hsiang J, Wu C, et al. Dynamic Functional Modules in Coexpressed Protein Interaction Networks of Dilated Cardiomyopathy［J］. BMC Systems Biology, 2010, 4:13.
［82］	Wu M, Li X, Kwoh CK, et al. A CoreAttachment Based Method to Detect Protein Complexes in PPI Networks［J］. BMC Bioinformatics, 2009,10(1):169.
［83］	Jiang P, Singh M. SPICi: A Fast Clustering Algorithm for Large Biological Networks［J］. Bioinformatics, 2010,26(8):11051111.
［84］	Xenarios I, Salwínski L, Duan X J, et al. DIP, the Database of Interacting Proteins: A Research Tool for Studying Cellular Networks of Protein Interactions［J］. Nucleic Acids Research, 2002, 30(1):303305.
［85］	关薇,王建,贺福初.大规模蛋白质相互作用研究方法进展［J］.生命科学,2006,18(5):507512.
［86］	Geva G,Sharan R.Identification of Protein Complexes from Coimmunoprecipitation Data［J］. Bioinformatics, 2009,27(1):111117.
［87］	Kuchaiev O, Rasajski M, Highm D J, et al. Geometric Denoising of Proteinprotein Interaction Networks［J］. PLoS Computational Biology, 2009,5(8):e1000454.

[1]	徐周波, 李萍, 刘华东, 李珍. 基于图嵌入与拓扑结构信息的蛋白质复合物识别算法[J]. 计算机工程与科学, 2021, 43(06): 1052-1059.
[2]	毛伊敏，刘银萍. 基于复合物参与度和密度的关键蛋白质预测[J]. 计算机工程与科学, 2019, 41(10): 1738-1748.
[3]	陈义明1，2,李舟军1,刘军万1. 改进LPU用于蛋白质功能预测[J]. J4, 2011, 33(12): 148-152.
[4]	王兵，姚益平，邢飞. 计算系统生物学中并行随机仿真方法研究进展[J]. J4, 2010, 32(9): 134-138.