蛋白质网络中复合物和功能模块挖掘算法研究
|
摘要
在后基因组时代,一个重要的挑战就是系统地分析和全面理解蛋白质之间是如何通过相互作用来完成生命活动的。从拓扑结构上分析蛋白质网络的特性,进而探寻蛋白质复合物和功能模块、注释未知蛋白质功能正成为当前国内外研究的重要焦点。
本文从蛋白质网络拓扑特性分析出发,利用各物种蛋白质网络所具有的一些共性特征设计了有效的蛋白质复合物和功能模块识别算法,主要研究工作包括:
应用复杂网络理论和图论技术对不同物种的蛋白质网络进行拓扑特性分析,包括节点的度分布、度与度的相关性、网络直径、网络的特征路径长度、边介数、边间隔以及网络的可靠性等,发现了不同物种的蛋白质网络的一些共性特征,为设计合理的蛋白质复合物和功能模块挖掘算法提供依据。
针对目前能够获得的蛋白质相互作用数据还不完全,直接从蛋白质网络中挖掘完备的全连通图(极大团)来预测蛋白质复合物具有很大局限性这一事实,提出了一种基于极大团扩展的蛋白质复合物识别算法IPC-MCE。该算法不需要其它任何辅助信息,简单有效。将算法IPC-MCE应用于酵母蛋白质网络,实验结果表明其能够识别比较多的具有生物意义的蛋白质复合物,且对输入参数不敏感。
基于对已知蛋白质复合物内蛋白质之间的最短距离一般不超过2的发现,提出了一种基于距离测定的蛋白质复合物识别算法IPC-DM。实验结果表明,算法IPC-DM较其它识别蛋白质复合物的聚类方法更能有效地标识已知蛋白质复合物,并且具有较高敏感度、特异性和综合评价。特别地,算法IPC-DM对蛋白质相互作用大规模数据中普遍存在的比例较高的假阳性和假阴性具有很好的健壮性,能够在蛋白质相互作用数据还不完善且具有较高噪声的情况下有效地识别蛋白质复合物,可以为生物学家进行蛋白质复合物识别的实验和进一步研究提供有价值的参考信息。
针对基于介数的层次化聚类算法计算复杂度高,很难应用于大规模蛋白质网络的不足,引入了局部变量边聚集系数,提出了一种基于边聚集系数的快速层次聚类算法FAG-EC。为降低算法对噪声的敏感性,本文应用logistic回归模型对蛋白质相互作用的可靠性进行评估进而建立加权蛋白质网络,并定义了加权的边聚集系数和功能模块,提出了应用于加权网络的层次聚类算法HC-Wpin。基于GO数据库中生物过程、分子功能和细胞成分全部三种注释信息的验证评估结果表明,算法FAG-EC和HC-Wpin不仅能够有效识别蛋白质网络中具有生物意义的功能模块,并且可以通过修改参数取值来展示蛋白质网络中功能模块的层次化组织结构。此外,算法FAG-EC和HC-Wpin的运行效率非常高,随着大规模蛋白质相互作用数据的不断增加,可以应用于更大规模的蛋白质网络。
针对蛋白质网络中普遍存在的“中心性-致死性”法则,提出了一个图分裂.规约模型,并在该模型基础上设计了一种新的交叠功能模块识别算法OMFinder。实验结果表明算法OMFinder能够有效地识别彼此交叠的功能模块,不同功能模块之间的重叠率约为2。与其他识别交叠功能模块的算法比较,算法OMFinder具有更好的识别性能,且具有更低的丢弃率。
本文提出的几个聚类算法从不同角度出发,有效地解决了蛋白质网络聚类过程中存在的一些问题。本文提出的聚类算法不仅运行效率很高,而且具有很好的聚类效果,识别的蛋白质复合物或功能模块都从统计意义上被证明是有生物意义的,有效地预测了一定数量的未知蛋白质的功能,将会对生物实验有指导意义。此外,本文提出的聚类算法对其它具有相似结构的复杂网络也具有普遍意义。
In the post-genome era, one of the most important challenges is to systematically analyze and comprehensively understand how the proteins accomplish the life activities by interacting with each other. Analyzing the characters of protein interaction networks based on the topology structure, identifiying protein complexes and functional modules, and predicting the functions of unknown proteins are becoming the most improtant issues in the domestic and overseas researches.
The characters of topology structures in protein interaction networks are studied firstly. Based on the common characters of different specie protein interaction networks, several effective algorithms for detecting protein complexes or functional modules are proposed. The main original works include:
Complex network theory and graph technology are applied to the analysis of the topology structure characters in different specie protein interaction networks, such as the dgree distribution, the degree-degree correlation, the network diameter, characteristic path lenghth, edge betweenness, range, and the reliability. Some common characters are detected from these protein interaction networks of different species, which can provide foundation for develping reasonable algorithms of mining protein complexes and functional modules.
At present, the available protein-protein interactions are not complete. Only mining maximal cliques are too limited to be used for predicting protein complexes since it is unlikely that all proteins in a large complex can interact with each other. To avoid of the limitation, a new algorithm of identifying protein complexes based on maximal clique extension (IPC-MCE) is proposed, which is easy to be implemented and effective. The algorithm IPC-MCE is applied to the protein interaction network of Sacchromyces cerevisiae and identifies many well known protein complexes. Moreover, algorithm IPC-MCE is not sensitive to the input parameter.
Based on our discovery that most of the shortest paths between proteins in complexes are no more than two, we propose a new algorithm IPC-DM for identifying protein complexes on the basis of distance measure. The experiment results show that the algorithm IPC-DM recalls more known complexes than other previously proposed clustering algorithms and has a relatively higher sensitivity, specificity and F-measure. Moreover, the algorithm IPC-DM is robust to the known high rate of false positives and false negatives in data from high-throughout interaction techniques. Thus, the algorithm IPC-DM can be used in protein interaction network even with high false positives and high false nagatives to identify new protein complexes and to provide references for biologists in their research on protein complexes.
The hierarchical clustering algorithms based on betweenness are not suitable to be used in large protein interaction networks because they are time consuming. A new local variable of edge clustering coefficient is introduced and a new fast hierarchical clustering algorithm FAG-EC based on it is proposed. To decrease the effect of noisy data on the clustering results, a new algorithm HC-Wpin is proposed for hierarchically clustering in the weighted protein interaction network. The logistic regression-based scheme is used to assign each edge a weight. The edge clustering coeffcient and the functional module in weighted graph are redefined. All the identified functional modules are validated by the three types of annotations of Gene Ontology (GO): Biological Process, Molecular Function, and Cellular Component. The experiment results show that algorithm FAG-EC and algorithm HC-Wpin can not only detect the significant functional modules in protein interaction network but also accurately identify functional modules in hierarchy by changing the values of parameter. Moreover, algorithm FAG-EC and algorithm HC-Wpin are extremely fast, which can be used in even larger protein interaction networks of other higher-level organisms as the protein-protein interactions accumulating sharply.
According to the "centrality-lethality rule" generally existing in protein interaction networks, a graph split and reduction model is proposed and a new algorithm OMFinder for identifying overlapping functional modules based on the proposed model is developed. The experiment results show that algorithm OMFinder detect many significant overlapping functional modules. The overlapping rate between different functional modules is about 2. Compared to other algorithms for detecting overlapping functional modules, algorithm OMFinder has better performance and lower discard rate.
The clustering algorithms proposed in this paper start off from different sights and solve some problems effectively in the processes of clustering in protein interaction networks. The proposed clustering algorithms not only can be implemented efficiently and have good clustering performances. The identified protein complexes or functional modules are proved to be statistically significant. A number of unknown protein functions are predicted, which can provide some references for biologists in their biochemical experiments. Moreover, the proposed clustering algorithms can be generalized to other complex networks with the similar structures.
本文从蛋白质网络拓扑特性分析出发,利用各物种蛋白质网络所具有的一些共性特征设计了有效的蛋白质复合物和功能模块识别算法,主要研究工作包括:
应用复杂网络理论和图论技术对不同物种的蛋白质网络进行拓扑特性分析,包括节点的度分布、度与度的相关性、网络直径、网络的特征路径长度、边介数、边间隔以及网络的可靠性等,发现了不同物种的蛋白质网络的一些共性特征,为设计合理的蛋白质复合物和功能模块挖掘算法提供依据。
针对目前能够获得的蛋白质相互作用数据还不完全,直接从蛋白质网络中挖掘完备的全连通图(极大团)来预测蛋白质复合物具有很大局限性这一事实,提出了一种基于极大团扩展的蛋白质复合物识别算法IPC-MCE。该算法不需要其它任何辅助信息,简单有效。将算法IPC-MCE应用于酵母蛋白质网络,实验结果表明其能够识别比较多的具有生物意义的蛋白质复合物,且对输入参数不敏感。
基于对已知蛋白质复合物内蛋白质之间的最短距离一般不超过2的发现,提出了一种基于距离测定的蛋白质复合物识别算法IPC-DM。实验结果表明,算法IPC-DM较其它识别蛋白质复合物的聚类方法更能有效地标识已知蛋白质复合物,并且具有较高敏感度、特异性和综合评价。特别地,算法IPC-DM对蛋白质相互作用大规模数据中普遍存在的比例较高的假阳性和假阴性具有很好的健壮性,能够在蛋白质相互作用数据还不完善且具有较高噪声的情况下有效地识别蛋白质复合物,可以为生物学家进行蛋白质复合物识别的实验和进一步研究提供有价值的参考信息。
针对基于介数的层次化聚类算法计算复杂度高,很难应用于大规模蛋白质网络的不足,引入了局部变量边聚集系数,提出了一种基于边聚集系数的快速层次聚类算法FAG-EC。为降低算法对噪声的敏感性,本文应用logistic回归模型对蛋白质相互作用的可靠性进行评估进而建立加权蛋白质网络,并定义了加权的边聚集系数和功能模块,提出了应用于加权网络的层次聚类算法HC-Wpin。基于GO数据库中生物过程、分子功能和细胞成分全部三种注释信息的验证评估结果表明,算法FAG-EC和HC-Wpin不仅能够有效识别蛋白质网络中具有生物意义的功能模块,并且可以通过修改参数取值来展示蛋白质网络中功能模块的层次化组织结构。此外,算法FAG-EC和HC-Wpin的运行效率非常高,随着大规模蛋白质相互作用数据的不断增加,可以应用于更大规模的蛋白质网络。
针对蛋白质网络中普遍存在的“中心性-致死性”法则,提出了一个图分裂.规约模型,并在该模型基础上设计了一种新的交叠功能模块识别算法OMFinder。实验结果表明算法OMFinder能够有效地识别彼此交叠的功能模块,不同功能模块之间的重叠率约为2。与其他识别交叠功能模块的算法比较,算法OMFinder具有更好的识别性能,且具有更低的丢弃率。
本文提出的几个聚类算法从不同角度出发,有效地解决了蛋白质网络聚类过程中存在的一些问题。本文提出的聚类算法不仅运行效率很高,而且具有很好的聚类效果,识别的蛋白质复合物或功能模块都从统计意义上被证明是有生物意义的,有效地预测了一定数量的未知蛋白质的功能,将会对生物实验有指导意义。此外,本文提出的聚类算法对其它具有相似结构的复杂网络也具有普遍意义。
In the post-genome era, one of the most important challenges is to systematically analyze and comprehensively understand how the proteins accomplish the life activities by interacting with each other. Analyzing the characters of protein interaction networks based on the topology structure, identifiying protein complexes and functional modules, and predicting the functions of unknown proteins are becoming the most improtant issues in the domestic and overseas researches.
The characters of topology structures in protein interaction networks are studied firstly. Based on the common characters of different specie protein interaction networks, several effective algorithms for detecting protein complexes or functional modules are proposed. The main original works include:
Complex network theory and graph technology are applied to the analysis of the topology structure characters in different specie protein interaction networks, such as the dgree distribution, the degree-degree correlation, the network diameter, characteristic path lenghth, edge betweenness, range, and the reliability. Some common characters are detected from these protein interaction networks of different species, which can provide foundation for develping reasonable algorithms of mining protein complexes and functional modules.
At present, the available protein-protein interactions are not complete. Only mining maximal cliques are too limited to be used for predicting protein complexes since it is unlikely that all proteins in a large complex can interact with each other. To avoid of the limitation, a new algorithm of identifying protein complexes based on maximal clique extension (IPC-MCE) is proposed, which is easy to be implemented and effective. The algorithm IPC-MCE is applied to the protein interaction network of Sacchromyces cerevisiae and identifies many well known protein complexes. Moreover, algorithm IPC-MCE is not sensitive to the input parameter.
Based on our discovery that most of the shortest paths between proteins in complexes are no more than two, we propose a new algorithm IPC-DM for identifying protein complexes on the basis of distance measure. The experiment results show that the algorithm IPC-DM recalls more known complexes than other previously proposed clustering algorithms and has a relatively higher sensitivity, specificity and F-measure. Moreover, the algorithm IPC-DM is robust to the known high rate of false positives and false negatives in data from high-throughout interaction techniques. Thus, the algorithm IPC-DM can be used in protein interaction network even with high false positives and high false nagatives to identify new protein complexes and to provide references for biologists in their research on protein complexes.
The hierarchical clustering algorithms based on betweenness are not suitable to be used in large protein interaction networks because they are time consuming. A new local variable of edge clustering coefficient is introduced and a new fast hierarchical clustering algorithm FAG-EC based on it is proposed. To decrease the effect of noisy data on the clustering results, a new algorithm HC-Wpin is proposed for hierarchically clustering in the weighted protein interaction network. The logistic regression-based scheme is used to assign each edge a weight. The edge clustering coeffcient and the functional module in weighted graph are redefined. All the identified functional modules are validated by the three types of annotations of Gene Ontology (GO): Biological Process, Molecular Function, and Cellular Component. The experiment results show that algorithm FAG-EC and algorithm HC-Wpin can not only detect the significant functional modules in protein interaction network but also accurately identify functional modules in hierarchy by changing the values of parameter. Moreover, algorithm FAG-EC and algorithm HC-Wpin are extremely fast, which can be used in even larger protein interaction networks of other higher-level organisms as the protein-protein interactions accumulating sharply.
According to the "centrality-lethality rule" generally existing in protein interaction networks, a graph split and reduction model is proposed and a new algorithm OMFinder for identifying overlapping functional modules based on the proposed model is developed. The experiment results show that algorithm OMFinder detect many significant overlapping functional modules. The overlapping rate between different functional modules is about 2. Compared to other algorithms for detecting overlapping functional modules, algorithm OMFinder has better performance and lower discard rate.
The clustering algorithms proposed in this paper start off from different sights and solve some problems effectively in the processes of clustering in protein interaction networks. The proposed clustering algorithms not only can be implemented efficiently and have good clustering performances. The identified protein complexes or functional modules are proved to be statistically significant. A number of unknown protein functions are predicted, which can provide some references for biologists in their biochemical experiments. Moreover, the proposed clustering algorithms can be generalized to other complex networks with the similar structures.
引文
[1] Wilkins M R, Sanchez J C, Gooley A A, et al. Progress with proteome projects:why all proteins expressed by a genome should be identified and how to do it.Biotechnology and Genetic Engineering Reviews, 1996,13:19-50
[2] Graves P R, Haystead T A. Molecular biologist's guide to proteomics.Microbiology and Molecular Biology Reviews, 2002, 66(1):39-63
[3] Asur S, Ucar D, Parthasarathy S. An ensemble framework for clustering protein-protein interaction networks. Bioinformatics, 2007, 23(13): i29-i40
[4] Bauer A, Kuster B. Affinity purification-mass spectrometry. Powerful tools for the characterization of protein complexes. European Journal of Biochemistry,2003,270(4): 570-578
[5] Gavin A C, Superti-Furga G. Protein complexes and proteome organization from yeast to man. Current Opinion in Chemical Biology, 2003, 7(1):21-27
[6] Sun Jingchun, Xu Jinlin, Li Yixue, et al. Analysis and application of large scale protein-protein interactions. Chinese Science Bulletin, 2005, 50(19):2055-2060
[7] Eisenberg D, Marcotte E M, Xenarios I, et al. Protein function in the post-genomic era. Nature, 2000, 405(6788): 823-826
[8] Wang J. Protein recognition by cell surface receptors: Physiological receptors versus virus interactions. Trends in Biochemical Sciences, 2002, 27(3): 122-126
[9] Loregian A, Marsden H S, Palu G. Protein-protein interactions as targets for antiviral chemotherapy. Reviews in Medical Virology, 2002, 12(4): 239-262
[10]Legrain P, Wojcik J, Gauthier J M. Protein-protein interaction maps: A lead towards cellular functions. Trends in Genetics, 2001,17(6):346-352
[11] Fields S, Song O. A novel genetic system to detect protein-protein interactions. Nature, 1989, 340(6230):245-246
[12] Uetz P, Giot L, Cagney G, et al. A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae. 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.Nature Biotechnology,1999,17(10):1030-1032
[14]Gavin A C,Krause R,Grandi P,et al.Functional organization of the yeast proteome by systematic analysis of protein complexes.Nature,2002,415(6868):141-147
[15]Gavin A C,Aloy P,Grandi P,et al.Proteome survey reveals modularity of the yeast cell machinery.Nature,2006,440(7084):631-636
[16]Ho Y,Gruhler A,Heilbut A,et al.Systematic identification of protein complexes in saccharomyces cerevisiae by mass spectrometry.Nature,2002,415(6868):180-183
[17]Zhu H,Bilgin M,Bangham R,et al.Global analysis of protein activities using proteome chips.Science,2001,293(5537):2101-2105
[18]Tong A H,Drees B,Nardelli G,et al.A combined experimental and computational strategy to define protein interaction networks for petide recognition modules.Science,2002,295(5553):321-324
[19]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:303-305
[20]Mewes H W,Amid C,Arnold R,et al.MIPS:analysis and annotation of proteins from whole genomes.Nucleic Acids Research,2004,32:D41-D44
[21]Bader G D,Donaldson I,Woting C,et al.BIND:The biomelecular interaction network database.Nucleic Acids Research,2001,29:242-245
[22]Breitkreutz B J,Stark C,Tyers M.The GRID:the General Respository for Interaction Datasets.Genome Biology,2003,4(3):R23
[23]Snel B,Lehrnann G,Bork P,et al.STRING:A web-server to re-trieve and display the repeatedly occurring neighbourhood of a gene.Nucleic Acids Research,2000,28(18):3442-3444
[24]http://www.proteome.com/databases
[25]http://www.hipd.org
[26]关薇,王建,贺福初.大规模蛋白质相互作用研究方法进展.生命科学,2006,18(5):507-512
[27] Pellegrini M, Marcotte E M, Thompson M J, et al. Assignning protein functions by comparative genome analysis: Protein phylogenetic profiles. Proc. Natl. Acad.Sci. USA, 1999,96:4285-4288
[28] Allison F G, Joseph M P, Frankie L P, et al. The Staphylococcus aureus collagen adhesion-encoding gene (cna) is within a discrete genetic element. Gene, 1997, 196: 239-248
[29] Marcotte E M, Pellegrini M, HO-Leung N, et al. Detecting protein function and protein-protein interactions from genome sequences. Science, 1999, 285(5428):751-753
[30] Enright A J, Iliopoulos I, Kyrpides N C, et al. Protein interaction maps for complete genomes based on gene fusion events. Nature, 1999,402: 86-90
[31] Pazos F, Valencia A. Similarity of phylogenetic trees as indicator of protein-protein interaction. Proteins Engineering Design & Selection, 2001,14(9): 609-614
[32] Olmea O, Rost B, Valencia A. Effective use of sequence correlation and conservation in fold recognition. Journal of Molecular Biology, 1999, 293(5):1221-1239
[33] Pazos F, Helmer-Citterich M, Ausiello G, et al. Correlated mutations contain information about protein-protein interaction. Journal of Molecular Biology, 1997, 271(4):511-523
[34] Bader G D, Hogue C W. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 2003,4:2
[35] King A D, Przulj N, Jurisica I. Protein complex prediction via cost-based clustering. Bioinformatics, 2004, 20(17): 3013-3020
[36] Paccanaro A, Trifonov V, Yu H Y, et al. Inferring protein-protein interactions using interaction network topologies. Proceeding of the 2005 IEEE International Joint Conference on Neural Networks. Oxford: Elsevier, 2005,1: 161-166
[37] Yu H Y, Paccanaro A, Trifonov V, et al. Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 2006, 22(7): 823-829
[38] Broh(?)e S, van Helden J. Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics, 2006, 7:488
[39]孙景春,徐晋麟,李亦学等.大规模蛋白质相互作用数据的分析与应用.科学通报,2005,50(19):2055-2060
[40]Chen Y,Xu D.Computational analyses of high-throughput pro-tein-protein interaction data.Current Protein & Peptide Science,2003,4(3):159-181
[41]von Mering C,Krause R,Sne B,et al.Comparative assessment of large-scale data sets of protein-protein interactions.Nature,2002,417(6887):399-403
[42]Ito T,Chiba T,Ozawa R,et al.A comprehensive two-hybrid analysis to explore the yeast protein interactome.Proc.Natl.Acad.Sci.USA,2001,98(8):4569-4574
[43]Hazbun T R,Fields S.Networking proteins in yeast.Proc.Natl.Acad.Sci.USA,2001,98(8):4277-4278
[44]Jenssen T K,Laegreid A,Komorowski J,et al.A literature net-work of human genes for high-throughput analysis of gene expres-sion.Nature Genetics,2001,28(1):21-28
[45]Watts D J,Strogatz S H.Collective dynamics of "small-world" networks.Nature,1998,393:440-442
[46]Barab(?)si A L,Albert R.Emergence of scaling in random networks.Science,1999,286(5439):509-512
[47]del Sol A,O'Meara P.Small-world network approach to identify key residues in protein-protein interaction.Proteins,2004,58(3):672-682
[48]del Sol A,Fujihashi H,O'Meara P.Topology of small-world networks of protein-protein complex structures.Bioinformatics,2005,21(8):1311-1315
[49]Wuchty S.Scale-free behavior in protein domain networks.Mollecular Biology and Evolution,2001,18(9):1694-1702
[50]Stumpf M P,Wiuf C,May R M.Subnets of scale-free networks are not scale-free:sampling properties of networks.Proc.Natl.Acad.Sci.USA,2005,102(12):4221-4224
[51]Barab(?)si A L,Bonabeau E.Scale-Free Networks.Scientific American,2003,5:50-59
[52]Jeong H,Mason S,Barab(?)si A L,et al.Lethality and centrality in protein networks.Nature,2001,411(6833):41-42
[53]Jeong H,Oltvai Z,Barab(?)si A L.Prediction of protein essentiality based on genomic data.ComPlexUs,2003,1:19-28
[54]Yu H,Greenbaum D,Lu H,et al.Genomic analysis of essentiality within protein networks.Trends in Genetics,2004,20(6):227-231
[55]Butland G,Peregrin-Alvarez J M,Li J,et al.Interaction network containing conserved and essential protein complexes in Escherichia coli.Nature,2005,433(7025):531-537
[56]Berg J,L(a|¨)ssig M,Wagner A.Structure and evolution of protein interaction networks:a statistical model for link dynamics and gene duplications.BMC Evolutionary Biology,2004,4:51
[57]Rzhetsky A,Gomez S M.Birth of scale-free molecular networks and the number of distinct DNA and protein domains per genome.Bioinformatics,2001,17(10):988-996
[58]Eisenberg E,Levanon E Y.Preferential attachment in the protein network evolution.Physical Review Letters,2003,91(13):138701
[59]Rives A W and Galitski T.Modular organization of cellular networks.Proc.Natl.Acad.Sci.USA,2003,100:1128-1133
[60]Wuchty S,Ravasz E,Barab(?)si A L.The architecture of biological networks.In:Deisboeck T S,Kresh J Y,Kepler T B,eds.Complex Systems in Biomedicine.New York:Kluwer Academic Publishing,2003,1-30
[61]Barabasi A,Oltvai Z.Network biology:Understanding the cells's functional organization.Nature Reviews Genetics,2004,5:101-113
[62]赵静,俞鸿,骆建华,等.应用复杂网络理论研究代谢网络的进展.科学通报,2006,51(11):1241-1248
[63]Luo F,Yang Y,Chen C F,et al.Modular organization of protein interaction networks.Bioinformatics,2007,23(2):207-214
[64]Oltvai Z,Barab(?)si A L.Life's complexity pyramid.Science,2002,298:763-764
[65]Milo R,Shen-Orr S S,Itzkovitz S,et al.Network motifs:Simple building blocks of complex networks.Science,2002,298(5594):824-827
[66]Kashtan N,Itzkovitz S,Milo R,et al.Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs.Bioinformatics, 2004,20(11): 1746-1758
[67] Wernicke S. A faster algorithm for detecting network motifs. In: Casadio R, Myers G, eds. Proceedings of the 5th Workshop on Algorithms in Bioinformatics. Berlin: Springer-Verlag, 2005, 3692: 165-177
[68] Jiang R, Tu Z D, Chen T, et al. Network motif identification in stochastic networks. Proc. Natl. Acad. Sci. USA, 2006, 103(25): 9404-9409
[69] Kashtan N, Itzkovitz S, Milo R, et al. Mfinder tool guide. Technical report,Department of Molecular Cell Biology and Computer Science and Applied Mathematics, Weizman Institute of Science, Israel, 2002,1-15
[70] Batagelj V, Mrvar A. Pajek-analysis and visualization of large networks. In: J(?)nger M, Mutzel P, eds. Graph Drawing Software. Berlin: Springer-Verlag,2003,77-103
[71] Schreiber F, Schw(?)bbermeyer H. Mavisto: a tool for the exploration of network motifs. Bioinformatics, 2005, 21(17): 3572-3574
[72] Wernicke S, Rasche F. FANMOD: a tool for fast network motif detection. Bioinformatics, 2006, 22(9): 1152-1153
[73] Chen J, Lu S, Sze S H, et al. Improved algorithms for Path, Matching, and Packing Problems. In: Gabow H N, ed. Proceedings of the 18th ACM-SIAM Symposium on Discrete Algoritms. 2007, 298-307
[74] Hiiffner F, Wernicke S, Zichner T. Algorithm engineering for color-coding with application to signaling pathway detection. In: Sankoff D, Wang L S, Chin F, eds.Proceedings of the 5th Asia Pacific Bioinformatics Conference. Berlin:Springer-Verlag, 2007, 52:114-132
[75] Mason O and Verwoerd M. Graph theory and networks in biology. IET Systems Biology, 2006, 1(2):89-119
[76] Rice J J, Kershenbaum A, Stolovitzky G. Lasting impressions: Motifs in protein-protein maps may provide footprints of evolutionary events. Proc. Natl.Acad. Sci. USA, 2005, 102(9): 3173-3174
[77]Wuchty S, Oltvai Z, Barab(?)si A L. Evolutionary conservation of motif constituents in the yeast protein interaction network. Nature Genetics, 2003,35(2): 176-179
[78] Ott S, Hansen A, Kim S, et al. Superiority of network motifs over optimal networks and an application to the revelation of gene network evolution. Bioinformatics, 2005,21(2):227-238
[79] Lee W P, Jeng B C, Pai T W, et al. Differential evolutionary conservation of motif modes in the yeast protein interaction network. BMC Genomics, 2006,7:89
[80] Spirin, V and Mirny, L A. Protein complexes and functional modules in molecular networks. Proc. Natl. Acad. Sci. USA, 2003,100:12123-12128
[81] Kumar A and Snyder M. Protein complexes take the bait. Nature, 2002, 415:123-124
[82] Krogan N J, Cagney G, Zhong G, et al. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature, 2006, 440(7084):637-643
[83] Schwikowski B, Uetz P, Fields S. A network of protein-protein interactions in yeast. Nature Biotechnology, 2000, 18(12): 1257-1261
[84] Marcotte E M. Computational genetics: finding protein function by nonhomology methods. Current Opinion in Structural Biology, 2000, 10:359-365
[85] Sharan R, Ulitsky I, Shamir R. Network-based prediction of protein funciton. Molecular Systems Biology, 2007, 3:1-13
[86] Kirac M, Ozsoyoglu G, Yang J. Annotating proteins by mining protein interaction networks. Bioinformatcis, 2006,22(14): e260-e270
[87] Hishigaki H, Nakai K, Ono T, et al. Assessment of prediction accuracy of protein function from protein-protein interaction data. Yeast, 2001, 18(6):523-531
[88] Zhou X, Kao M C, Wong W H. Transitive functional annotation by shortest-path analysis of gene expression data. Proc. Natl. Acad. Sci. USA, 2002, 99(20):12783-12788
[89] Deng M, Tu Z, Chen T, et al. Mapping Gene Ontology to proteins based on protein-protein interaction data. Bioinformatics, 2004,20(6): 895-902
[90] Vazquez A, Flammini A, Maritan A, et al. Global protein function prediction from protein-protein interaction networks. Nature Biotechnology, 2003, 21(6): 697-700
[91]Karaoz U,Murali T M,Letovsky S,et al.Whole-genome annota-tion by using evidence integration in functional-linkage networks.Proc.Natl.Acad.Sci.USA,2004,101(9):2888-2893
[92]Dunn R,Dudbridge F,Sanderson C M.The use of edge-betweenness clustering to inverstigate biological function in protein interaction networks.BMC Bioinformatics,2005,6:39
[93]卢宏超,石秋艳,石宝晨,等.基于蛋白质网络功能模块的蛋白质功能预测.生物化学与生物物理进展,2006,33(5):446-451
[94]梁治.蛋白质相互作用网络的比较生物学分析及其应用:[博士学位论文].合肥:中国科学技术大学,2006
[95]Matthews L R,Vaglio P,Reboul J,et al.Identification of potential interaction networks using sequence based searches for conserved protein-protein interactions or "interologs." Genome Research,2001,11:2120-2126
[96]Kelley B,Sharan R,Karp R M,et al.Conserved pathways within bacteria and yeast as revealed by global protein network alignment.Proc.Natl.Acad.Sci.USA,2003,100(20):11394-11399
[97]Kelley B,Yuan B,Lewitter F,et al.PathBLAST:a tool for alignment of protein interaction networks.Nucleic Acids Research,2004,32:W83-W88
[98]Sharan R,Suthram S,Kelley R M,et al.Conserved patterns of protein interaction in multiple species.Proc.Natl.Acad.Sci.USA,2005,102:1974-1979
[99]Sharan R,Ideker T,Kelley B,et al.Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data.Journal of Computational Biology,2005,12:835-846
[100]Hirsh E,Sharan R.Identification of conserved protein complexes based on a model of protein network evolution.Bioinformatics,2007,23(2):170-176
[101]Koyut(u|¨)rk M,Kim Y,Topkara U,et al.Pairwise Alignment of Protein Interaction Networks.Journal of Computational Biology,2006,13(2):182-199
[102]Liang Z,Xu M,Teng M,et al.Comparison of protein interaction networks reveals species conservation and divergence.BMC Bioinformatics,2006,7:457
[103] Liang Z, Xu M, Teng M, et al. NetAlign: a web-based tool for comparison of protein interaction networks. Bioinformatics, 2006,22: 2175-2177
[104] Sharan R, Ideker T. Modeling cellular machinery through biological network comparison. Nature Biotechnology, 2006,24(4):427-433
[105] Gorey M R, Johnson D S. Computers and Intractability: A Guide to Theory of NP-Completeness.1979, Freeman and Company
[106] Shlomi T, Segal D, Ruppin E, et al. Qpath: a method for querying pathways in a protein-protein interaction network. BMC Bioinformatics, 2006, 7:199
[107] Leser U. A query language for biological networks. Bioinformatcis, 2005, 21(2):1133-1139
[108] Zhang S H, Zhang X S, Chen L N. Biomolecular network querying: a promising approach in systems bioloby. BMC System Biology, 2008,2:5
[109] Garrels J I. Yeast genomic databases and the chanllenge of the post-genomic era. Functional & Integrative Genomics, 2002, 2(4-5): 212-237
[110] Clauset A, Moore C, Newman M. Hierarchical structure and the prediction of missing links in networks. Nature, 2008,453:98-101
[111] Ruan J H, Zhang W X. An efficient spectral algorithm for network community discovery and its applications to biological and social networks. In:Perner P, ed. Proceedings of the 7th IEEE International Conference on Data Mining. 2007, 72: 643-648
[112] Ruan J H, Zhang W X. Identifying network communities with high resolution. Physical Review E, 2007,4, 1-14
[113] Palla G, Dernyi I, Farkas I, et al. Uncoverring the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043):814-818
[114] Adamcsek B, Palla G, Farkas I, et al. CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics. 2006, 22(8):1021-1023
[115] Li X L, Tan S H, Foo C S, et al. Interaction Graph mining for protein complexes using local clique merging. Genome Informatics, 2005,16: 260-269
[116] 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. BMC Bioinformatics, 2006, 7:207
[117] Girvan M and Newman M. Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA, 2002, 99:7821-7826
[118] Newman M, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 1-16
[119] Radicchi F, Castellano C, Cecconi F. Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA, 2004,101 (9): 2658-2663
[120] Hartuv E, Shamir R. A clustering algorithm based graph connectivity. Information Processing Letters, 2000, 76:175-181
[121] Przulj N, Wigle D A, Jurisica I. Functional topology in a network of protein interactions. Bioinformatics, 2004, 20(3):340-348
[122] Van Dongen S. Graph clustering by flow simulation. In PhD thesis Centers for mathematics and computer science (CWI), University of Utrecht, 2000.
[123] Enright A J, Dongen S V, Ouzounis C A. An efficient algorithm for large-scale detection of protein families. Nucleic Acids Research, 2002, 30(7):1575-1584
[124] Hwang W, Cho Y R, Zhang A, et al. A novel functional module detection algorithm for protein-protein interaction networks. Algorithms for Molecular Biology, 2006, 12: 1-24
[125] Bu D, Zhao Y, Cai L, et al. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Research,2003,31(9):2443-2450
[126] Tornow S, Mewes H W. Functional modules by relating protein interaction networks and gene expression. Nucleic Acids Research, 2003, 31(21):6283-6289
[127] Cho Y R, Hwang W, Ramanmathan M, et al. Semantic integration to identify overlapping functional modules in protein interaction networks. BMC Bioinformatics, 2007, 8:265
[128] G(?)ldener U, M(?)nsterk(?)tter M, Kastenm(?)ller G, et al. CYGD: the comprehensive yeast genome database. Nucleic Acids Research, 2005, 33:D364-D368
[129]Yook S,Oltvai Z,Barab(?)si A L.Functional and topological characterization of protein interaction networks.Proteomics,2004,4:928-942
[130]Wuchty S,Almaas E.Peeling the yeast protein network.Proteomics,2005,5(2):444-449
[131]Freeman L.A set of measures of centrality based on betweenness.Sociometry,1977,40:35-41
[132]Ruth D,Frank D,Christopher M.The use of edge-betweenness clustering to investigate biological function in protein interaction networks.BMC Bioinformatics,2005,6:39
[133]Chen J C,Yuan B.Detecting functional modules in the yeast protein-protein interaction network.Bioinformatics,2006,22(18):2283-2290
[134]刘涛,陈忠,陈晓荣.复杂网络理论及其应用研究概述.系统工程,2005,23(6):1-7
[135]Ravasz E,Somera A L,Mongru D A,et al.Hierarchical organization of modularity in metabolic networks.Science,2002,297:1551-1556
[136]Caroline C F and Ralf Z.Inferring topology from clustering coefficients in protein-protein interaction networks.BMC Bioinformatics,2006,7:519
[137]谭跃进,吴俊.网络结构熵及其在非标度网络中的应用.系统工程理论与实践,2004,(6):1-3
[138]Jun W U,Tan Y J,Deng H Z,et al.Normalized entropy of rank distribution:a novel measure of heterogeneity of complex networks.Chinese Physics,2007,16(6):1576-1580
[139]Cui G U,Chen Y,Huang D S,et al.An algorithm for finding functional modules and protein complexes in protein-protein interaction networks.Journal of Biomedicine and Biotechnology,2008,3:1-10
[140]Tsukiyama S,Ide M,Ariyoshi H,et al.A new algorithm for generating all the maximal independent sets.SIAM Journal on Computing,1977,6(3):505-517
[141]Zhang S H,Ning X,Zhang X S.Identification of functional modules in a PPI network by clique percolation clustering.Computational Biology and Chemistry,2006,30(6):445-451
[142]Jonsson P,Cavanna T,Zicha D,et al.Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastatis. BMC Bioinformatics, 2006, 7:2
[143] Krogan N J, Peng W T, Cagney G, et al. High-definition macromolecular composition of yeast RNA-processing complexes. Molecular Cell, 2004, 13:225-239
[144] Ruepp A, Zollner A, Maier D, et al. The FunCat: a functional annotation scheme for systematic classication of proteins from whole genomes. Nucleic Acids Research, 2004, 32: 5539-5545
[145] Friedel C, Zimmer R. Inferring topology from clustering coeffcients in protein-protein interaction networks. BMC Bioinformatics, 2006, 7:519
[146] Saito R, Suzuki H, Hayashizaki Y. Interaction generality, a measurement to assess the reliability of a protein-protein interaction. Nucleic Acids Research,2002,30:1163-1168
[147] Mrowka R, Patzak A, Herzel H. Is there a bias in proteome research?Genome Research, 2001, 11 (12): 1971-1973
[148] Deane C M, Salwinski L, Xenarios I, et al. Protein interactions: two methods for assessment of the reliability of high throughput observations. Molecular & Cellular Proteomics, 2002, 1 (5): 349-356
[149] Issel-Tarver L, Christie K R, Dolinski K, et al: Saccharomyces Genome Database. Methods Enzymol, 2002, 350:329-346
[150] Ashburner M, Ball C A, Blake J A, et al. Gene ontology: tool for the unification of biology. The Gene Ontology Consortium. Nature Genetics, 2000, 25: 25-29
[151] Jeong H, Tombor B, Albert R, et al. The large-scale organization of metabolic networks. Nature, 2000,407: 651-654
[152] Wagner A. The yeast protein interaction network evolves rapidly and contains few redundant duplicate genes. Molecular Biology and Evolution, 2001, 18: 1283-1292
[153] He X, Zhang J. Why do Hubs tend to be essential in protein networks? Plos Genetics, 2006, 2(6): 0826-0834
[154] Winzeler E A, Shoemaker D D, Astromoff A, et al. Functional characterization of the S.cerevisiae genome by gene deletion and parallel analysis.Science,1999,285:901-906
[155]Kamath R S,Fraser A G,Dong Y,et al.Systematic functional analysis of the Caenorhabditis elegans genome using RNAi.Nature,2003,421,231-237
[156]Wuchty S.Interaction and domain networks of yeast.Proteomics,2002,2:1715-1723
[157]Hahn M W,Kern A D.Comparative genomics of centrality and essentiality in three eukaryotic protein-interaction networks.Molecular Biology and Evolution,2005,22:803-806
[158]Cho Y R,Hwang W,Zhang A.Identification of overlapping functional modules in protein interaction networks:information flow-based approach.In:Perner P,ed.Proceeding of the Sixth IEEE International Conference on Data Mining.2006,94:147-152
[159]卢宏超.基于蛋白网络聚类的基因功能研究:[博士学位论文].北京:中国科学院研究生院,2006
[160]Sprinzak E,Sattath S,Margalit H.How reliable are experimental protein-protein interaction data.Journal of Molecular Biology,2003,327:919-923
[161]Deng M,Mehta S,Sun F,et al.Inferring domain-domain interactions from protein-protein interactions.Genome Research,2002,12(10):1540-1548
[2] Graves P R, Haystead T A. Molecular biologist's guide to proteomics.Microbiology and Molecular Biology Reviews, 2002, 66(1):39-63
[3] Asur S, Ucar D, Parthasarathy S. An ensemble framework for clustering protein-protein interaction networks. Bioinformatics, 2007, 23(13): i29-i40
[4] Bauer A, Kuster B. Affinity purification-mass spectrometry. Powerful tools for the characterization of protein complexes. European Journal of Biochemistry,2003,270(4): 570-578
[5] Gavin A C, Superti-Furga G. Protein complexes and proteome organization from yeast to man. Current Opinion in Chemical Biology, 2003, 7(1):21-27
[6] Sun Jingchun, Xu Jinlin, Li Yixue, et al. Analysis and application of large scale protein-protein interactions. Chinese Science Bulletin, 2005, 50(19):2055-2060
[7] Eisenberg D, Marcotte E M, Xenarios I, et al. Protein function in the post-genomic era. Nature, 2000, 405(6788): 823-826
[8] Wang J. Protein recognition by cell surface receptors: Physiological receptors versus virus interactions. Trends in Biochemical Sciences, 2002, 27(3): 122-126
[9] Loregian A, Marsden H S, Palu G. Protein-protein interactions as targets for antiviral chemotherapy. Reviews in Medical Virology, 2002, 12(4): 239-262
[10]Legrain P, Wojcik J, Gauthier J M. Protein-protein interaction maps: A lead towards cellular functions. Trends in Genetics, 2001,17(6):346-352
[11] Fields S, Song O. A novel genetic system to detect protein-protein interactions. Nature, 1989, 340(6230):245-246
[12] Uetz P, Giot L, Cagney G, et al. A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae. 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.Nature Biotechnology,1999,17(10):1030-1032
[14]Gavin A C,Krause R,Grandi P,et al.Functional organization of the yeast proteome by systematic analysis of protein complexes.Nature,2002,415(6868):141-147
[15]Gavin A C,Aloy P,Grandi P,et al.Proteome survey reveals modularity of the yeast cell machinery.Nature,2006,440(7084):631-636
[16]Ho Y,Gruhler A,Heilbut A,et al.Systematic identification of protein complexes in saccharomyces cerevisiae by mass spectrometry.Nature,2002,415(6868):180-183
[17]Zhu H,Bilgin M,Bangham R,et al.Global analysis of protein activities using proteome chips.Science,2001,293(5537):2101-2105
[18]Tong A H,Drees B,Nardelli G,et al.A combined experimental and computational strategy to define protein interaction networks for petide recognition modules.Science,2002,295(5553):321-324
[19]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:303-305
[20]Mewes H W,Amid C,Arnold R,et al.MIPS:analysis and annotation of proteins from whole genomes.Nucleic Acids Research,2004,32:D41-D44
[21]Bader G D,Donaldson I,Woting C,et al.BIND:The biomelecular interaction network database.Nucleic Acids Research,2001,29:242-245
[22]Breitkreutz B J,Stark C,Tyers M.The GRID:the General Respository for Interaction Datasets.Genome Biology,2003,4(3):R23
[23]Snel B,Lehrnann G,Bork P,et al.STRING:A web-server to re-trieve and display the repeatedly occurring neighbourhood of a gene.Nucleic Acids Research,2000,28(18):3442-3444
[24]http://www.proteome.com/databases
[25]http://www.hipd.org
[26]关薇,王建,贺福初.大规模蛋白质相互作用研究方法进展.生命科学,2006,18(5):507-512
[27] Pellegrini M, Marcotte E M, Thompson M J, et al. Assignning protein functions by comparative genome analysis: Protein phylogenetic profiles. Proc. Natl. Acad.Sci. USA, 1999,96:4285-4288
[28] Allison F G, Joseph M P, Frankie L P, et al. The Staphylococcus aureus collagen adhesion-encoding gene (cna) is within a discrete genetic element. Gene, 1997, 196: 239-248
[29] Marcotte E M, Pellegrini M, HO-Leung N, et al. Detecting protein function and protein-protein interactions from genome sequences. Science, 1999, 285(5428):751-753
[30] Enright A J, Iliopoulos I, Kyrpides N C, et al. Protein interaction maps for complete genomes based on gene fusion events. Nature, 1999,402: 86-90
[31] Pazos F, Valencia A. Similarity of phylogenetic trees as indicator of protein-protein interaction. Proteins Engineering Design & Selection, 2001,14(9): 609-614
[32] Olmea O, Rost B, Valencia A. Effective use of sequence correlation and conservation in fold recognition. Journal of Molecular Biology, 1999, 293(5):1221-1239
[33] Pazos F, Helmer-Citterich M, Ausiello G, et al. Correlated mutations contain information about protein-protein interaction. Journal of Molecular Biology, 1997, 271(4):511-523
[34] Bader G D, Hogue C W. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 2003,4:2
[35] King A D, Przulj N, Jurisica I. Protein complex prediction via cost-based clustering. Bioinformatics, 2004, 20(17): 3013-3020
[36] Paccanaro A, Trifonov V, Yu H Y, et al. Inferring protein-protein interactions using interaction network topologies. Proceeding of the 2005 IEEE International Joint Conference on Neural Networks. Oxford: Elsevier, 2005,1: 161-166
[37] Yu H Y, Paccanaro A, Trifonov V, et al. Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 2006, 22(7): 823-829
[38] Broh(?)e S, van Helden J. Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics, 2006, 7:488
[39]孙景春,徐晋麟,李亦学等.大规模蛋白质相互作用数据的分析与应用.科学通报,2005,50(19):2055-2060
[40]Chen Y,Xu D.Computational analyses of high-throughput pro-tein-protein interaction data.Current Protein & Peptide Science,2003,4(3):159-181
[41]von Mering C,Krause R,Sne B,et al.Comparative assessment of large-scale data sets of protein-protein interactions.Nature,2002,417(6887):399-403
[42]Ito T,Chiba T,Ozawa R,et al.A comprehensive two-hybrid analysis to explore the yeast protein interactome.Proc.Natl.Acad.Sci.USA,2001,98(8):4569-4574
[43]Hazbun T R,Fields S.Networking proteins in yeast.Proc.Natl.Acad.Sci.USA,2001,98(8):4277-4278
[44]Jenssen T K,Laegreid A,Komorowski J,et al.A literature net-work of human genes for high-throughput analysis of gene expres-sion.Nature Genetics,2001,28(1):21-28
[45]Watts D J,Strogatz S H.Collective dynamics of "small-world" networks.Nature,1998,393:440-442
[46]Barab(?)si A L,Albert R.Emergence of scaling in random networks.Science,1999,286(5439):509-512
[47]del Sol A,O'Meara P.Small-world network approach to identify key residues in protein-protein interaction.Proteins,2004,58(3):672-682
[48]del Sol A,Fujihashi H,O'Meara P.Topology of small-world networks of protein-protein complex structures.Bioinformatics,2005,21(8):1311-1315
[49]Wuchty S.Scale-free behavior in protein domain networks.Mollecular Biology and Evolution,2001,18(9):1694-1702
[50]Stumpf M P,Wiuf C,May R M.Subnets of scale-free networks are not scale-free:sampling properties of networks.Proc.Natl.Acad.Sci.USA,2005,102(12):4221-4224
[51]Barab(?)si A L,Bonabeau E.Scale-Free Networks.Scientific American,2003,5:50-59
[52]Jeong H,Mason S,Barab(?)si A L,et al.Lethality and centrality in protein networks.Nature,2001,411(6833):41-42
[53]Jeong H,Oltvai Z,Barab(?)si A L.Prediction of protein essentiality based on genomic data.ComPlexUs,2003,1:19-28
[54]Yu H,Greenbaum D,Lu H,et al.Genomic analysis of essentiality within protein networks.Trends in Genetics,2004,20(6):227-231
[55]Butland G,Peregrin-Alvarez J M,Li J,et al.Interaction network containing conserved and essential protein complexes in Escherichia coli.Nature,2005,433(7025):531-537
[56]Berg J,L(a|¨)ssig M,Wagner A.Structure and evolution of protein interaction networks:a statistical model for link dynamics and gene duplications.BMC Evolutionary Biology,2004,4:51
[57]Rzhetsky A,Gomez S M.Birth of scale-free molecular networks and the number of distinct DNA and protein domains per genome.Bioinformatics,2001,17(10):988-996
[58]Eisenberg E,Levanon E Y.Preferential attachment in the protein network evolution.Physical Review Letters,2003,91(13):138701
[59]Rives A W and Galitski T.Modular organization of cellular networks.Proc.Natl.Acad.Sci.USA,2003,100:1128-1133
[60]Wuchty S,Ravasz E,Barab(?)si A L.The architecture of biological networks.In:Deisboeck T S,Kresh J Y,Kepler T B,eds.Complex Systems in Biomedicine.New York:Kluwer Academic Publishing,2003,1-30
[61]Barabasi A,Oltvai Z.Network biology:Understanding the cells's functional organization.Nature Reviews Genetics,2004,5:101-113
[62]赵静,俞鸿,骆建华,等.应用复杂网络理论研究代谢网络的进展.科学通报,2006,51(11):1241-1248
[63]Luo F,Yang Y,Chen C F,et al.Modular organization of protein interaction networks.Bioinformatics,2007,23(2):207-214
[64]Oltvai Z,Barab(?)si A L.Life's complexity pyramid.Science,2002,298:763-764
[65]Milo R,Shen-Orr S S,Itzkovitz S,et al.Network motifs:Simple building blocks of complex networks.Science,2002,298(5594):824-827
[66]Kashtan N,Itzkovitz S,Milo R,et al.Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs.Bioinformatics, 2004,20(11): 1746-1758
[67] Wernicke S. A faster algorithm for detecting network motifs. In: Casadio R, Myers G, eds. Proceedings of the 5th Workshop on Algorithms in Bioinformatics. Berlin: Springer-Verlag, 2005, 3692: 165-177
[68] Jiang R, Tu Z D, Chen T, et al. Network motif identification in stochastic networks. Proc. Natl. Acad. Sci. USA, 2006, 103(25): 9404-9409
[69] Kashtan N, Itzkovitz S, Milo R, et al. Mfinder tool guide. Technical report,Department of Molecular Cell Biology and Computer Science and Applied Mathematics, Weizman Institute of Science, Israel, 2002,1-15
[70] Batagelj V, Mrvar A. Pajek-analysis and visualization of large networks. In: J(?)nger M, Mutzel P, eds. Graph Drawing Software. Berlin: Springer-Verlag,2003,77-103
[71] Schreiber F, Schw(?)bbermeyer H. Mavisto: a tool for the exploration of network motifs. Bioinformatics, 2005, 21(17): 3572-3574
[72] Wernicke S, Rasche F. FANMOD: a tool for fast network motif detection. Bioinformatics, 2006, 22(9): 1152-1153
[73] Chen J, Lu S, Sze S H, et al. Improved algorithms for Path, Matching, and Packing Problems. In: Gabow H N, ed. Proceedings of the 18th ACM-SIAM Symposium on Discrete Algoritms. 2007, 298-307
[74] Hiiffner F, Wernicke S, Zichner T. Algorithm engineering for color-coding with application to signaling pathway detection. In: Sankoff D, Wang L S, Chin F, eds.Proceedings of the 5th Asia Pacific Bioinformatics Conference. Berlin:Springer-Verlag, 2007, 52:114-132
[75] Mason O and Verwoerd M. Graph theory and networks in biology. IET Systems Biology, 2006, 1(2):89-119
[76] Rice J J, Kershenbaum A, Stolovitzky G. Lasting impressions: Motifs in protein-protein maps may provide footprints of evolutionary events. Proc. Natl.Acad. Sci. USA, 2005, 102(9): 3173-3174
[77]Wuchty S, Oltvai Z, Barab(?)si A L. Evolutionary conservation of motif constituents in the yeast protein interaction network. Nature Genetics, 2003,35(2): 176-179
[78] Ott S, Hansen A, Kim S, et al. Superiority of network motifs over optimal networks and an application to the revelation of gene network evolution. Bioinformatics, 2005,21(2):227-238
[79] Lee W P, Jeng B C, Pai T W, et al. Differential evolutionary conservation of motif modes in the yeast protein interaction network. BMC Genomics, 2006,7:89
[80] Spirin, V and Mirny, L A. Protein complexes and functional modules in molecular networks. Proc. Natl. Acad. Sci. USA, 2003,100:12123-12128
[81] Kumar A and Snyder M. Protein complexes take the bait. Nature, 2002, 415:123-124
[82] Krogan N J, Cagney G, Zhong G, et al. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature, 2006, 440(7084):637-643
[83] Schwikowski B, Uetz P, Fields S. A network of protein-protein interactions in yeast. Nature Biotechnology, 2000, 18(12): 1257-1261
[84] Marcotte E M. Computational genetics: finding protein function by nonhomology methods. Current Opinion in Structural Biology, 2000, 10:359-365
[85] Sharan R, Ulitsky I, Shamir R. Network-based prediction of protein funciton. Molecular Systems Biology, 2007, 3:1-13
[86] Kirac M, Ozsoyoglu G, Yang J. Annotating proteins by mining protein interaction networks. Bioinformatcis, 2006,22(14): e260-e270
[87] Hishigaki H, Nakai K, Ono T, et al. Assessment of prediction accuracy of protein function from protein-protein interaction data. Yeast, 2001, 18(6):523-531
[88] Zhou X, Kao M C, Wong W H. Transitive functional annotation by shortest-path analysis of gene expression data. Proc. Natl. Acad. Sci. USA, 2002, 99(20):12783-12788
[89] Deng M, Tu Z, Chen T, et al. Mapping Gene Ontology to proteins based on protein-protein interaction data. Bioinformatics, 2004,20(6): 895-902
[90] Vazquez A, Flammini A, Maritan A, et al. Global protein function prediction from protein-protein interaction networks. Nature Biotechnology, 2003, 21(6): 697-700
[91]Karaoz U,Murali T M,Letovsky S,et al.Whole-genome annota-tion by using evidence integration in functional-linkage networks.Proc.Natl.Acad.Sci.USA,2004,101(9):2888-2893
[92]Dunn R,Dudbridge F,Sanderson C M.The use of edge-betweenness clustering to inverstigate biological function in protein interaction networks.BMC Bioinformatics,2005,6:39
[93]卢宏超,石秋艳,石宝晨,等.基于蛋白质网络功能模块的蛋白质功能预测.生物化学与生物物理进展,2006,33(5):446-451
[94]梁治.蛋白质相互作用网络的比较生物学分析及其应用:[博士学位论文].合肥:中国科学技术大学,2006
[95]Matthews L R,Vaglio P,Reboul J,et al.Identification of potential interaction networks using sequence based searches for conserved protein-protein interactions or "interologs." Genome Research,2001,11:2120-2126
[96]Kelley B,Sharan R,Karp R M,et al.Conserved pathways within bacteria and yeast as revealed by global protein network alignment.Proc.Natl.Acad.Sci.USA,2003,100(20):11394-11399
[97]Kelley B,Yuan B,Lewitter F,et al.PathBLAST:a tool for alignment of protein interaction networks.Nucleic Acids Research,2004,32:W83-W88
[98]Sharan R,Suthram S,Kelley R M,et al.Conserved patterns of protein interaction in multiple species.Proc.Natl.Acad.Sci.USA,2005,102:1974-1979
[99]Sharan R,Ideker T,Kelley B,et al.Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data.Journal of Computational Biology,2005,12:835-846
[100]Hirsh E,Sharan R.Identification of conserved protein complexes based on a model of protein network evolution.Bioinformatics,2007,23(2):170-176
[101]Koyut(u|¨)rk M,Kim Y,Topkara U,et al.Pairwise Alignment of Protein Interaction Networks.Journal of Computational Biology,2006,13(2):182-199
[102]Liang Z,Xu M,Teng M,et al.Comparison of protein interaction networks reveals species conservation and divergence.BMC Bioinformatics,2006,7:457
[103] Liang Z, Xu M, Teng M, et al. NetAlign: a web-based tool for comparison of protein interaction networks. Bioinformatics, 2006,22: 2175-2177
[104] Sharan R, Ideker T. Modeling cellular machinery through biological network comparison. Nature Biotechnology, 2006,24(4):427-433
[105] Gorey M R, Johnson D S. Computers and Intractability: A Guide to Theory of NP-Completeness.1979, Freeman and Company
[106] Shlomi T, Segal D, Ruppin E, et al. Qpath: a method for querying pathways in a protein-protein interaction network. BMC Bioinformatics, 2006, 7:199
[107] Leser U. A query language for biological networks. Bioinformatcis, 2005, 21(2):1133-1139
[108] Zhang S H, Zhang X S, Chen L N. Biomolecular network querying: a promising approach in systems bioloby. BMC System Biology, 2008,2:5
[109] Garrels J I. Yeast genomic databases and the chanllenge of the post-genomic era. Functional & Integrative Genomics, 2002, 2(4-5): 212-237
[110] Clauset A, Moore C, Newman M. Hierarchical structure and the prediction of missing links in networks. Nature, 2008,453:98-101
[111] Ruan J H, Zhang W X. An efficient spectral algorithm for network community discovery and its applications to biological and social networks. In:Perner P, ed. Proceedings of the 7th IEEE International Conference on Data Mining. 2007, 72: 643-648
[112] Ruan J H, Zhang W X. Identifying network communities with high resolution. Physical Review E, 2007,4, 1-14
[113] Palla G, Dernyi I, Farkas I, et al. Uncoverring the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043):814-818
[114] Adamcsek B, Palla G, Farkas I, et al. CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics. 2006, 22(8):1021-1023
[115] Li X L, Tan S H, Foo C S, et al. Interaction Graph mining for protein complexes using local clique merging. Genome Informatics, 2005,16: 260-269
[116] 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. BMC Bioinformatics, 2006, 7:207
[117] Girvan M and Newman M. Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA, 2002, 99:7821-7826
[118] Newman M, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 1-16
[119] Radicchi F, Castellano C, Cecconi F. Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA, 2004,101 (9): 2658-2663
[120] Hartuv E, Shamir R. A clustering algorithm based graph connectivity. Information Processing Letters, 2000, 76:175-181
[121] Przulj N, Wigle D A, Jurisica I. Functional topology in a network of protein interactions. Bioinformatics, 2004, 20(3):340-348
[122] Van Dongen S. Graph clustering by flow simulation. In PhD thesis Centers for mathematics and computer science (CWI), University of Utrecht, 2000.
[123] Enright A J, Dongen S V, Ouzounis C A. An efficient algorithm for large-scale detection of protein families. Nucleic Acids Research, 2002, 30(7):1575-1584
[124] Hwang W, Cho Y R, Zhang A, et al. A novel functional module detection algorithm for protein-protein interaction networks. Algorithms for Molecular Biology, 2006, 12: 1-24
[125] Bu D, Zhao Y, Cai L, et al. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Research,2003,31(9):2443-2450
[126] Tornow S, Mewes H W. Functional modules by relating protein interaction networks and gene expression. Nucleic Acids Research, 2003, 31(21):6283-6289
[127] Cho Y R, Hwang W, Ramanmathan M, et al. Semantic integration to identify overlapping functional modules in protein interaction networks. BMC Bioinformatics, 2007, 8:265
[128] G(?)ldener U, M(?)nsterk(?)tter M, Kastenm(?)ller G, et al. CYGD: the comprehensive yeast genome database. Nucleic Acids Research, 2005, 33:D364-D368
[129]Yook S,Oltvai Z,Barab(?)si A L.Functional and topological characterization of protein interaction networks.Proteomics,2004,4:928-942
[130]Wuchty S,Almaas E.Peeling the yeast protein network.Proteomics,2005,5(2):444-449
[131]Freeman L.A set of measures of centrality based on betweenness.Sociometry,1977,40:35-41
[132]Ruth D,Frank D,Christopher M.The use of edge-betweenness clustering to investigate biological function in protein interaction networks.BMC Bioinformatics,2005,6:39
[133]Chen J C,Yuan B.Detecting functional modules in the yeast protein-protein interaction network.Bioinformatics,2006,22(18):2283-2290
[134]刘涛,陈忠,陈晓荣.复杂网络理论及其应用研究概述.系统工程,2005,23(6):1-7
[135]Ravasz E,Somera A L,Mongru D A,et al.Hierarchical organization of modularity in metabolic networks.Science,2002,297:1551-1556
[136]Caroline C F and Ralf Z.Inferring topology from clustering coefficients in protein-protein interaction networks.BMC Bioinformatics,2006,7:519
[137]谭跃进,吴俊.网络结构熵及其在非标度网络中的应用.系统工程理论与实践,2004,(6):1-3
[138]Jun W U,Tan Y J,Deng H Z,et al.Normalized entropy of rank distribution:a novel measure of heterogeneity of complex networks.Chinese Physics,2007,16(6):1576-1580
[139]Cui G U,Chen Y,Huang D S,et al.An algorithm for finding functional modules and protein complexes in protein-protein interaction networks.Journal of Biomedicine and Biotechnology,2008,3:1-10
[140]Tsukiyama S,Ide M,Ariyoshi H,et al.A new algorithm for generating all the maximal independent sets.SIAM Journal on Computing,1977,6(3):505-517
[141]Zhang S H,Ning X,Zhang X S.Identification of functional modules in a PPI network by clique percolation clustering.Computational Biology and Chemistry,2006,30(6):445-451
[142]Jonsson P,Cavanna T,Zicha D,et al.Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastatis. BMC Bioinformatics, 2006, 7:2
[143] Krogan N J, Peng W T, Cagney G, et al. High-definition macromolecular composition of yeast RNA-processing complexes. Molecular Cell, 2004, 13:225-239
[144] Ruepp A, Zollner A, Maier D, et al. The FunCat: a functional annotation scheme for systematic classication of proteins from whole genomes. Nucleic Acids Research, 2004, 32: 5539-5545
[145] Friedel C, Zimmer R. Inferring topology from clustering coeffcients in protein-protein interaction networks. BMC Bioinformatics, 2006, 7:519
[146] Saito R, Suzuki H, Hayashizaki Y. Interaction generality, a measurement to assess the reliability of a protein-protein interaction. Nucleic Acids Research,2002,30:1163-1168
[147] Mrowka R, Patzak A, Herzel H. Is there a bias in proteome research?Genome Research, 2001, 11 (12): 1971-1973
[148] Deane C M, Salwinski L, Xenarios I, et al. Protein interactions: two methods for assessment of the reliability of high throughput observations. Molecular & Cellular Proteomics, 2002, 1 (5): 349-356
[149] Issel-Tarver L, Christie K R, Dolinski K, et al: Saccharomyces Genome Database. Methods Enzymol, 2002, 350:329-346
[150] Ashburner M, Ball C A, Blake J A, et al. Gene ontology: tool for the unification of biology. The Gene Ontology Consortium. Nature Genetics, 2000, 25: 25-29
[151] Jeong H, Tombor B, Albert R, et al. The large-scale organization of metabolic networks. Nature, 2000,407: 651-654
[152] Wagner A. The yeast protein interaction network evolves rapidly and contains few redundant duplicate genes. Molecular Biology and Evolution, 2001, 18: 1283-1292
[153] He X, Zhang J. Why do Hubs tend to be essential in protein networks? Plos Genetics, 2006, 2(6): 0826-0834
[154] Winzeler E A, Shoemaker D D, Astromoff A, et al. Functional characterization of the S.cerevisiae genome by gene deletion and parallel analysis.Science,1999,285:901-906
[155]Kamath R S,Fraser A G,Dong Y,et al.Systematic functional analysis of the Caenorhabditis elegans genome using RNAi.Nature,2003,421,231-237
[156]Wuchty S.Interaction and domain networks of yeast.Proteomics,2002,2:1715-1723
[157]Hahn M W,Kern A D.Comparative genomics of centrality and essentiality in three eukaryotic protein-interaction networks.Molecular Biology and Evolution,2005,22:803-806
[158]Cho Y R,Hwang W,Zhang A.Identification of overlapping functional modules in protein interaction networks:information flow-based approach.In:Perner P,ed.Proceeding of the Sixth IEEE International Conference on Data Mining.2006,94:147-152
[159]卢宏超.基于蛋白网络聚类的基因功能研究:[博士学位论文].北京:中国科学院研究生院,2006
[160]Sprinzak E,Sattath S,Margalit H.How reliable are experimental protein-protein interaction data.Journal of Molecular Biology,2003,327:919-923
[161]Deng M,Mehta S,Sun F,et al.Inferring domain-domain interactions from protein-protein interactions.Genome Research,2002,12(10):1540-1548