基于网络节点拓扑参数的关键蛋白质识别研究
|
摘要
蛋白质分子功能的重要性与它在蛋白质网络中对应节点的拓扑特性紧密相关。关键蛋白质的识别有助于从系统水平上理解生命活动的内在组织和过程,在疾病诊疗及药物设计等方面有重要的应用前景。与生物学实验方法及其它方法相比,基于拓扑结构的生物信息学方法在关键蛋白质识别上有独特优势。针对已有方法对关键蛋白质识别度不高的现状,认为进一步提高识别度有两条途径:一是发现与关键蛋白质关系更密切的参数,二是充分挖掘现有参数的信息并进行有效地整合。对于第一种途径,根据点覆盖在网络(图)拓扑结构上的重要地位而研究将其引入关键蛋白质的识别中;对于第二种途径,主要探讨复合参数的构造及异步识别方法,通过将多个参数所隐含的关键蛋白质信息进行有效整合而提高识别度。
点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性。将参数计算理论引进随机网络领域,利用随机网络统计和概率分布等特性,从全局和整体上分析并揭示参数化点覆盖问题低度(1度和2度)节点核化过程中问题的核及度分布演变的内在机制和变化规律。同时,根据核与节点度分布以及边的关系,提出随机网络参数化点覆盖问题的d-核化可决策性。
在1度点核化的研究中,首先分析节点之间的映射关系,然后将它们的邻接关系进行量化,得出1度点核化算法对平均度为ω≤2.3的随机网络点覆盖问题的核化强度最高,同时指出它的d-核化(d=1)可决策性。在2度点核化的研究中,提出2度点三角形子网的计数方法;通过研究子网对节点的共享关系,分析2度点核化过程中核及度分布演变的动态过程,得出2度点核化算法对2度点分布概率在0.75左右的随机网络的核化强度最高,同时也指出它的d-核化(d=2)可决策性。初步结果表明,对随机网络点覆盖问题低度点核化过程的分析方法不但具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力,并提供了随机网络上这一NP完全问题的求解方法,也为参数计算在包括蛋白质网络在内的已知度分布的一类不确定问题中的应用提供了可能。
对一给定的网络(图)来说,虽然最小点覆盖集的大小是一个固定值,但就一般情况而言可以求解出多个节点构成不同的最小覆盖集。为此,提出骨干点覆盖集、非骨干覆盖集及非覆盖集等概念,然后对蛋白质网络进行最小点覆盖分析并获得一种新的拓扑参数——点覆盖参数,从另一种角度描述节点的拓扑重要性。为了避开点覆盖参数精确求解方法中可能出现的NP-难问题,根据稀疏网络中存在大量的◇、Δ_2、∧_2子网的特点,将确定算法与非确定算法相结合,提出基于随机核化的快速算法(A-Q算法)。该算法通过引进参数计算的相关算法将复杂度大幅度降低,同时通过随机和统计方法使得到的结果尽可能接近实际解。结果显示,该算法得到的点覆盖参数与关键蛋白质有着密切的联系,在识别仿真上也表现出较好的性能,因此在描述节点的拓扑特性上具有重要意义。
把关键蛋白质识别看作是一类特殊的模式识别。从相关分析出发对关键蛋白质与其主要拓扑参数的相互关系进行研究,发现参数对关键蛋白质识别能力的大小与两者之间的相关性有关;研究复合参数识别度与独立参数识别度、与独立参数相关性之间的关系,发现参数之间相关性的大小在很大程度上预示它们所蕴含的关键蛋白质信息之间互补性的强弱;根据上述发现,探讨利用包括点覆盖在内的各个参数的有限信息进行整合的方法,提出有效的复合参数构造方法及异步识别方法。实验结果证实,通过该技术获得的识别度明显高于其它识别技术。
Recent research discovers that the essentiality of a protein molecule in function is correlated with its topological properties in a protein network. The study of essential protein (EP) is no only meaningful in the understanding of the organization and process of life activities, but also important in diagnosis-treatment and medicament design. Comparing with biological experiments and other methods, bioinformatics methods based on topological structure possess particular advantage in the identification of EP. However, there is still some dissatisfaction in the identification. To improve the performance, two ways are proposed in this paper: one is to find new parameters closer to EP, the other is to integrate the EP information from known parameters. For the former, the minimal vertex cover (MVC) is introduced to get a new topological parameter - vertex cover parameter (VP) for the first time. For the later, the combination of known parameters is explored.
The exact solution to a minimal vertex cover problem (VCP) can be found within the frame of the theory of parameterized computation. However, there are still some limits in theory and practical. In this paper, the theory is introduced into the realm of random graph, so as to use statistic properties and probability methods to deal with a VCP wholly and uncover the inherence and evolvement laws of the kernel and the degree distribution in the kernelization by low (1 and 2) degree vertex (1-DV and 2-DV). On the base of fixed-parameter tractability, the d-decidable by way of kernelization (d-DBK) of the parameterized VCP of random graph is proposed.
In the study of 1-DV kernelization (1-DVK), the mapping of 1-DV into the other nodes in a random graph is analyzed, and their adjacency relationship is quantified. It is found in this paper that the strength of 1-DVK gets its maximum whenω≤2.3 withωbeing the average degree of the graph, and the 1-DBK of the parameterized VCP of the graph is presented. In the study of 2-DV kernelization (2-DVK), the counting method for 2-DV triangle subnetworks is analyzed and the situation that a node is shared by more than one of the subnetworks is studied. After that, the dynamic and evolvement mechanism of the kernel and the degree distribution in the process of 2-DVK are described. Accordingly, two deductions are obtained: one is that the strength of 2-DVK gets its maximum in a random graph when the probability of its 2-DV is about 0.75, and the other is that the parameterized VCP (G, k) of a random graph given byφ(x) is 2-DBK when k smaller than a given value relation toφ(x).
For its important role in the topology of a network, the minimal vertex cover (MVC) is introduced into the study of EP in a protein network and VP is proposed as a new topological parameter. To avoid the NP-hard which probable met in the calculation of the parameter by exact methods, the kernelization by low degree nodes and the combination of exact and no-exact algorithms are studied according to the sparseness of protein networks with lots of◇,△_2 and∧_2 subnetworks. Then, a quick algorithm (A-Q algorithm) based on randomized kernelization is presented. The result that the identifying degree of VP generated from the algorithm is better than those of the existed parameters obviously in the identification of EP, gives an evidence to approve the importance of the parameter in describing node's topological characteristic.
The identification of EP is considered as a special kind of pattern recognition by setting up the quantification of nodes' (proteins') relationship -topological parameters as its ground. The correlation between a protein's essentiality and its main topological parameters, including VP, is analyzed and so is the nature of the essential-node-judgment of the parameters. In order to study the mutual complement of the EP information from different single parameters (SPs), the relation between the identification degree of a combined parameter (IDCP) and those of its SPs is presented theoretically, so is the relation between IDCP and the correlations of its SPs. With the above observation, the integration of the EP information from different SPs is explored and a combination method is proposed to get combined parameters. After that, an asynchronous recognition algorithm is developed, and the experiment results show that the identifying ability of the technique is greater than those of the others obviously in the identification of EP.
点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性。将参数计算理论引进随机网络领域,利用随机网络统计和概率分布等特性,从全局和整体上分析并揭示参数化点覆盖问题低度(1度和2度)节点核化过程中问题的核及度分布演变的内在机制和变化规律。同时,根据核与节点度分布以及边的关系,提出随机网络参数化点覆盖问题的d-核化可决策性。
在1度点核化的研究中,首先分析节点之间的映射关系,然后将它们的邻接关系进行量化,得出1度点核化算法对平均度为ω≤2.3的随机网络点覆盖问题的核化强度最高,同时指出它的d-核化(d=1)可决策性。在2度点核化的研究中,提出2度点三角形子网的计数方法;通过研究子网对节点的共享关系,分析2度点核化过程中核及度分布演变的动态过程,得出2度点核化算法对2度点分布概率在0.75左右的随机网络的核化强度最高,同时也指出它的d-核化(d=2)可决策性。初步结果表明,对随机网络点覆盖问题低度点核化过程的分析方法不但具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力,并提供了随机网络上这一NP完全问题的求解方法,也为参数计算在包括蛋白质网络在内的已知度分布的一类不确定问题中的应用提供了可能。
对一给定的网络(图)来说,虽然最小点覆盖集的大小是一个固定值,但就一般情况而言可以求解出多个节点构成不同的最小覆盖集。为此,提出骨干点覆盖集、非骨干覆盖集及非覆盖集等概念,然后对蛋白质网络进行最小点覆盖分析并获得一种新的拓扑参数——点覆盖参数,从另一种角度描述节点的拓扑重要性。为了避开点覆盖参数精确求解方法中可能出现的NP-难问题,根据稀疏网络中存在大量的◇、Δ_2、∧_2子网的特点,将确定算法与非确定算法相结合,提出基于随机核化的快速算法(A-Q算法)。该算法通过引进参数计算的相关算法将复杂度大幅度降低,同时通过随机和统计方法使得到的结果尽可能接近实际解。结果显示,该算法得到的点覆盖参数与关键蛋白质有着密切的联系,在识别仿真上也表现出较好的性能,因此在描述节点的拓扑特性上具有重要意义。
把关键蛋白质识别看作是一类特殊的模式识别。从相关分析出发对关键蛋白质与其主要拓扑参数的相互关系进行研究,发现参数对关键蛋白质识别能力的大小与两者之间的相关性有关;研究复合参数识别度与独立参数识别度、与独立参数相关性之间的关系,发现参数之间相关性的大小在很大程度上预示它们所蕴含的关键蛋白质信息之间互补性的强弱;根据上述发现,探讨利用包括点覆盖在内的各个参数的有限信息进行整合的方法,提出有效的复合参数构造方法及异步识别方法。实验结果证实,通过该技术获得的识别度明显高于其它识别技术。
Recent research discovers that the essentiality of a protein molecule in function is correlated with its topological properties in a protein network. The study of essential protein (EP) is no only meaningful in the understanding of the organization and process of life activities, but also important in diagnosis-treatment and medicament design. Comparing with biological experiments and other methods, bioinformatics methods based on topological structure possess particular advantage in the identification of EP. However, there is still some dissatisfaction in the identification. To improve the performance, two ways are proposed in this paper: one is to find new parameters closer to EP, the other is to integrate the EP information from known parameters. For the former, the minimal vertex cover (MVC) is introduced to get a new topological parameter - vertex cover parameter (VP) for the first time. For the later, the combination of known parameters is explored.
The exact solution to a minimal vertex cover problem (VCP) can be found within the frame of the theory of parameterized computation. However, there are still some limits in theory and practical. In this paper, the theory is introduced into the realm of random graph, so as to use statistic properties and probability methods to deal with a VCP wholly and uncover the inherence and evolvement laws of the kernel and the degree distribution in the kernelization by low (1 and 2) degree vertex (1-DV and 2-DV). On the base of fixed-parameter tractability, the d-decidable by way of kernelization (d-DBK) of the parameterized VCP of random graph is proposed.
In the study of 1-DV kernelization (1-DVK), the mapping of 1-DV into the other nodes in a random graph is analyzed, and their adjacency relationship is quantified. It is found in this paper that the strength of 1-DVK gets its maximum whenω≤2.3 withωbeing the average degree of the graph, and the 1-DBK of the parameterized VCP of the graph is presented. In the study of 2-DV kernelization (2-DVK), the counting method for 2-DV triangle subnetworks is analyzed and the situation that a node is shared by more than one of the subnetworks is studied. After that, the dynamic and evolvement mechanism of the kernel and the degree distribution in the process of 2-DVK are described. Accordingly, two deductions are obtained: one is that the strength of 2-DVK gets its maximum in a random graph when the probability of its 2-DV is about 0.75, and the other is that the parameterized VCP (G, k) of a random graph given byφ(x) is 2-DBK when k smaller than a given value relation toφ(x).
For its important role in the topology of a network, the minimal vertex cover (MVC) is introduced into the study of EP in a protein network and VP is proposed as a new topological parameter. To avoid the NP-hard which probable met in the calculation of the parameter by exact methods, the kernelization by low degree nodes and the combination of exact and no-exact algorithms are studied according to the sparseness of protein networks with lots of◇,△_2 and∧_2 subnetworks. Then, a quick algorithm (A-Q algorithm) based on randomized kernelization is presented. The result that the identifying degree of VP generated from the algorithm is better than those of the existed parameters obviously in the identification of EP, gives an evidence to approve the importance of the parameter in describing node's topological characteristic.
The identification of EP is considered as a special kind of pattern recognition by setting up the quantification of nodes' (proteins') relationship -topological parameters as its ground. The correlation between a protein's essentiality and its main topological parameters, including VP, is analyzed and so is the nature of the essential-node-judgment of the parameters. In order to study the mutual complement of the EP information from different single parameters (SPs), the relation between the identification degree of a combined parameter (IDCP) and those of its SPs is presented theoretically, so is the relation between IDCP and the correlations of its SPs. With the above observation, the integration of the EP information from different SPs is explored and a combination method is proposed to get combined parameters. After that, an asynchronous recognition algorithm is developed, and the experiment results show that the identifying ability of the technique is greater than those of the others obviously in the identification of EP.
引文
[1]陈润生.与生物信息学相关的两个前沿方向.生物物理学报.2007,23(4):290—295
[2]Barab(a)si A L,Olvtai ZN:Network biology:understanding the cell's functional organization.Nature Reviews Genetics,2004,5:101-113
[3]Yu J,Fotouhi F.Computational approaches for predicting protein-protein interactions:a survey.Journal of Medical Systems,2006,30(1):39-44
[4]Bu DB,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
[5]Rain JC,Selig L,De Reuse H,et al.The protein-protein interaction map of Helicobacter pylori.Nature,2001,409:211-215
[6]Uetz P,Giot L,Cagney G,et al.A comprehensive anaylsis of protein-protein interactions in Saccharomyces cerevisiae.Nature,2000,403:623-627
[7]Li S,Amrstorng C M,Benin N,et al.A map of the interactome network of the metazoan C.elgeans.Sceince,2004,303:540-543
[8]Giot L,Bader J S,Brouwer C,et al.A protein interaction map of Drosophila melanogaster.Sceince,2003,302:1727-1736
[9]Bader G D,Donaldson I,Wolting C,et al.BIND-The biomolecular interaction network database.Nucleic Acids Research,2001,29:242-245
[10]Zanzoni A,Montecchi-Palazzi L,Quondam M,et al.MINT:a Molecular INTeraction database.FEBS Letter,2002,513:135-140
[11]Breitkreutz B J,Stark C,Tyers M.The GRID:the General Repository for Interaction Datasets.Genome Biology,2003,4:R23
[12]Phizicky E,Bastiaens P I,Zhu H,et al.Protein analysis on a proteomic scale.Nature,2003,422,208 - 215
[13]Fields S,Sternglanz R.The two-hybrid system:an assay for protein - protein interactions.Trends in Genetics,1994,10,286 - 292
[14]Pandey A,Mann M.Proteomics to study genes and genomes.Nature,2000,405,837 - 846
[15]von Mering C,Jensen L J,Snel B,et al.STRING:known and predicted protein-protein associations,integrated and transferred across organisms.Nucleic Acids Research,2005,33(Database Issue):D433
[16]Alfarano C,Andrade C E,Anthony K,et al.The Biomolecular Interaction Network Database and related tools 2005 update.Nucleic Acids Research,2005,33(Database Issue):D418
[17]Peter U,Russell L.Finley J.From protein networks to biological systems.FEBS Letters 2005,579:1821-1827
[18]卢宏超.基于蛋白网络聚类的基因功能研究[博士学位论文].北京:中国科学院计算技术研究所,2006
[19]王建新,黄元南,陈建二.一种基于彩色编码技术的基序发现算法.软件学报,2007,18(6):1298-1307
[20]Yanjun Q,Femanda B,Christos F,et al.Protein complex identification by supervised graph local clustering.Bioinformatics,2008,24(ISMB):i250 - i258
[21]Bing Z,Byung H P,Tatiana K,et al.From pull-down data to protein interaction networks and complexes with biological relevance.Bioinformatics,2008,24(7):979-986
[22]Noga A,Phuong D,Iman H,et al.Biomolecular network motif counting and discovery by color coding.Bioinformatics,2008,24(ISMB):i241-i249
[23]Marcus T D,Gunnar W K,Andreas R,et al.Identifying functional modules in protein - protein interaction networks:an integrated exact approach.Bioinformatics,2008,24(ISMB):i223 - i231
[24]Albert R,Jeong H,Barab(?)si A L.Error and attack:tolerance of complex networks.Nature,2000,406:378-382
[25]Jeong H,Mason S P,Barab(?)si A L,Oltvai Z N.Lethality and centrality in protein networks.Nature,2001,411:41-42
[26]Gerdes S Y.Experimental determination and system-level analysis of essential genes in Escherichia coli.MG 1655,Journal of Bacteriology,2003,185:5673-5684
[27]Alon U,Surette M G,Barkai N,Leibler S.Robustness in bacterial chemotaxis.Nature,1999,397:168-171
[28]Csermely P,Agoston V,Pongor S.The efficiency of multi-target drugs:the network approach might help drug design.Trends in Pharmacological Sciences,2005,26:178-182
[29]谭璐,姜璐.系统生物学与生物网络研究.复杂系统与复杂性科学.2005,2(4):1-9
[30]Watts D J,Strogatz S H.Collective dynamics of Small-world' networks.Nature,1998,393:440-442
[31]Strogatz S H.Exploring complex networks.Nature,2001,410:268-276
[32]Barab(?)si A L,Albert R.Emergence of scaling in random networks.Science,1999,286:509-512
[33]Boccaletti S,Latora V,Moreno Y,et al.Complex Networks:Structure and Dynamics.Physics Reports,2006,424(4,5):175-308
[34]史定华.网络-探索复杂性的新途径.系统工程学报,2005,20(2):115-119
[35]Newman M E J.Who is the best connected scientist? A study of scientific coauthorship networks.Complex Networks,Lecture Notes in Physics.Springer Berlin / Heidelberg,2004,650:337-370
[36]Jeong H,Tombor B,Albert R,Oltvai Z N,Barab(?)si A L.The large-scale organization of metabolic networks.Nature,2000,407:651-654
[37]Wagner A,Fell D.The small world inside large metabolic networks.Proceedings of the Royal Society,London Series B,2001,268:1803-1810
[38]Fell D A,Wagner A.The small world of metabolism.Nature Biotechnology,2000,18:1121-1122
[39]Gil A,Michael X,Isaac S K,et al.Protein Network Topology Metric Conservation:From Yeast to Human.http://www.mit.edu/～gil/pub/Alterovitz_topology_metric_conservation_RECOMB_2005_invited.pdf
[40]Antonio D S,Hirotomo F,Paul O M.Topology of small- world networks of protein-protein complex structures.Bioinformatics,2005,21(8):1311-1315
[41]Barab(?)si A L.Scale-Free Networks.Scientific American,2003,288:60-69
[42]Eisenberg E,Levanon E Y.Preferential attachment in the protein network evolution.Physical Review Letters,2003,91:138701
[43]Schilling C H,Palsson B O.Assessment of the metabolic capabilities of Haemophilus influenzae Rd through a genome-scale pathway ayalysis.Journal of Theoretical Biology,2000,203:249-283
[44]Newman M E J.The structure and function of complex networks.SIAM Review,2003,45(2):167-256
[45]谭跃进,吴俊.网络结构熵及其在非标度网络中的应用.系统工程理论与实践,2004,(6):1-3
[46]王林,戴冠中,胡海波.无尺度网络的一个新的拓扑参数.系统工程理论与实践,2006,(6):49—53
[47]Wang X F.Complex networks:Topology,dynamics and synchronization.International Journal of Bifurcation and Chaos,2002,12(5):885-916
[48]Ravasz E,Somera A L,Mongru D A,et al.Hierarchical organization of modularity in metabolic networks.Science,2002,297:1551-1555
[49]Pr(?)ulj N,Corneil D G,Jurisica I.Efficient estimation of graphlet frequency distributions in protein-protein interaction networks.Bioinformatics,2006,22(8):974-980
[50]Freeman L C.Centrality in social networks:I.Conceptual clarification.Social Networks,1979,1:215-239
[51]Ernesto E.Virtual identification of essential proteins within the protein interaction network of yeast.Proteomics,2005,6(1):35-40
[52]Bonacich P.Power and centrality:a family of measures.American Journal of Sociology,1987,92:1170-1182
[53]谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法.系统工程理论与实践,2006,(11):79—105
[54]李鹏翔.任玉晴,席酉民.网络节点(集)重要性的一种度量指标.系统工程,2004,22(4):13-20
[55] Zhao J, Yu H, Luo J H, Cao Z W, Li Y X. Hierarchical modularity of nested bow-ties in metabolic networks. BMC Bioinformatics, 2006, 7: 386
[56] Guimera R, Sales P M, Amaral L A N.Modularity from fluctuations in random graphs and complex networks. Physical Review, 2004, E, 70(8):025101
[57] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004,69:066133
[58] Shen Orr S S, Milo R, mangan S, et al. Network notifs in the transcriptional regulation network of Escherichia coli. Nature Genetics, 2002, 31:64-68
[59] Yeger Lotem E, Sattath S, Nadav K, et al. Network motifs in integrated cellular networks of transcription-regulation and protein-protein interaction. Proceedings of the National Academy of Sciences, 2004, 101(52): 5934-5939
[60] Milo R, Shen O S, Itzkovitz S, et al. Network motifs: simple building blocks of complex networks. Science, 2002,298:824-827
[61] Vazquez A, Dobrin R, Sergi D, et al. The topological relationship between the large-scale attributes and local interaction patterns of complex networks. Proceedings of the National Academy of Sciences, 2004, 101(52): 17940-17945
[62] Burt R S, Minor M J. Applied Network Analysis: A Methodological Introduction. Social Forces, 1985, 63(3): 856-858
[63] Poulin R, Boily M-C, Masse B R. Dynamical systems to define centrality in social networks. Social Networks, 2000, 22:187-220
[64] 许进.一种研究系统的新方法-核与核度法.系统工程与电子技术, 1994,(6): 1-10
[65] Wasserman S, Faust K. Social network analysis: methods and applications. Cambridge: Cambridge University Press, 1994
[66] Jose B P L, Benjamin A, Jose M P A, et al. An Exponential Core in the Heart of the Yeast Protein Interaction Network. Molecular Biology and Evolution, 2005, 2(3): 421-425
[67] Kwang I G, Michael E C, David V, et al. The human disease network. Proceedings of the National Academy of Sciences, 2007, 104 (21): 8685-8690
[68] Maya R S, Thomas J B, Alan V O, et al. Global network analysis of phenotypic effects: Protein networks and toxicity modulation in Saccharomyces cerevisiae. Proceedings of the National Academy of Sciences, 2004, 101(52): 18006-18011
[69] 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
[70] Jeong H, Oltvai Z N, Barab(?)si A L. Prediction of protein essentiality based on genomic data. ComPlexUs, 2003,1: 19-28
[71] Yu H Y, Dov G, Li H X, et al. Genomic analysis of essentiality within protein networks. Trends in Genetics, 2004, 20(6): 227-231
[72] Igor U, Ron S. Pathway redundancy and protein essentiality revealed in the Saccharomyces cerevisiae interaction networks. Molecular Systems Biology, 2005, 3:104
[73] Kelley R, Ideker T. Systematic interpretation of genetic interactions using protein networks. Nature Biotechnology, 2005, 23: 561-566
[74] He X L, Zhang J Z. Why do hubs tend to be essential in protein networks? PloS Genetics, 2006, 2(6): 0826- 0834
[75] Palumbo M C, Colosimo A, Giuliani A, et al. Functional essentiality from topology features in metabolic networks: A case study in yeast. FEBS Letter, 2005, 579: 4642-4646
[76] Samal A, Singh S, Giri V, et al. Low degree metabolites explain essential reactions and enhance modularity in biological networks. BMC Bioinformatics, 2006, 7:118
[77] Lemke N, Heredia F, Barcellos C K, et al. Essentiality and damage in metabolic networks. Bioinformatics, 2004, 20: 115-119
[78] Mombach J C M, Lemke N, Silva N M, et al. Bioinformatics analysis of mycoplasma metabolism: important enzymes, metabolic similarities, and redundancy. Computers in Biology and Medicine 2006, 36(5): 542-552
[79] Mark L S, Daniel E L P, Aviv B. Functional and evolutionary inference in gene networks: does topology matter? Genetica, 2007, 129:83-103
[80] Coulomb S, Bauer M, Bernard D. Gene essentiality and the topology of protein interaction networks. Proceedings of the Royal Society, 2005, B 272:1721-1725
[81] Gustafson AM, Snitkin ES, Parker SC, et al. Towards the identification of essential genes using targeted genome sequencing and comparative analysis. BMC Genomics, 2006, 7: 265
[82] Feng L, Yunfeng Y, Chin-Fu C, et al. Modular organization of protein interaction networks. Bioinformatics 2007 23(2): 207-214
[83] Schuster S, Pfeiffer T, Moldenhauer F, et al. Exploring the pathway structure of metabolism: Decomposition into subnetworks and application to Mycoplasma pneumonise. Bioinformatics,2002, 18:351-361
[84] Guimera R, Amaral L A N. Function cartography of complex metabolic networks. Nature, 2005, 433:895-900
[85] Pablo B, Itay B, Vladislav V, et al. Functional topology classification of biological computing networks. Natural Computing, 2005, 4: 339-361
[86] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal on Matrix Analysis and Applications, 1990, 11:430
[87]Capocci A,Servedio V D P,Caldarelli G,et al.Detecting communities in large networks.Computer Science,2004,3243:181-187
[88]Girvan M,Newman M E J.Community structure in social and biological networks.Proceedings of the National Academy of Sciences,2001,99:7821-7826
[89]Newman M E J,Girvan M.Finding and evaluating community structure in networks.Physical Review E,2004,69:026113
[90]Ravi R,Sinha A.Hedging Uncertainty:Approximation Algorithms for Stochastic Optimization Problems.Mathematical Programming,2006,108(1):97-114
[91]范辉,华臻,李晋江.原达.点覆盖问题的蚂蚁算法求解.计算机工程与应用,2004.23:71—73
[92]董亚非,张家秀,殷志祥,许进.最小节点覆盖问题的改进粘贴模型.电子与信息学报,2005,27(4):556—560
[93]Adleman L.Molecular computation of solutions to combinatorial problems.Science,1994,266(1):1021-1024
[94]Chen Z,Lu M,Qu H,Zhu H.A Probabilistic Parameterized Algorithm for Vertex Cover in Sticker Model.In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04):IPDPS.Santa Fe,New Mexico,USA:IEEE Computer Society,2004,166
[95]Gilmour S,Dras M.Kernelization as Heuristic Structure for the Vertex Cover Problem.In Proceedings of Ant Colony Optimization and Swarm Intelligence,5th International Workshop (ANTS,2006):LNCS.Brussels,Belgium:Springer Verlag,2006
[96]刘湘辉,殷建平,卢锡城,蔡志平,赵建民.基于原始对偶方法求解网络流量监测集算法.软件学报.2006,17(4):838—844
[97]Alber J,Gramm J,Niedermeier R.Faster exact algorithms for hard problems:a parameterized point of view.Discreted Mathematics,2001,229(1):3-27
[98]曲惠琴.DNA计算若干问题研究[博士学位论文].复旦大学.2005
[99]Chen J,Huang X,Kanj I,Xia G.Linear FTP reductions and computational lower bounds.In Proceedings of the 36th ACM Symposium on Theory of Computing(STOC):L(?)szl(?) Babai,ed.ACM2004.Chicago,IL,USA:ACM Press,2004,212-221
[100]Rizzi R,Bafna V,Istrail S,Lancia G.Practical algorithms and fixed-parameter tractability for the single individual SNP haplotying problem.In Proceedings of the 2nd Workshop on Algorithms in Bioinformatics(WABI 2002):Lecture Notes in Computer Science 2454.Rome:Springer Verlag,2002,29-43
[101]Buhler J,Tompa M.Finding motifs using random projection.In Proceeding of the 5th Annual International Conference on Computational Molecular Biology(RECOMB'2001):ACM2001.Montreal,Canada:ACM Press,2001,69-76
[102] Eskin E, Pevzner P A. Finding composite regulatory patterns in DNA sequences. Bioinformatics, 2002, 18(1): 354-363
[103] Fellows M, Gramm J, Niedermeier R. Parameterized Intractability of Motif Search Problems. In Proceeding of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002): Lecture Notes in Computer Science 2285. Antibes - Juan les Pins, France: Springer-Verlag, 2002, 262-273
[104] Fellows M. Parameterized complexity: the main ideas and some research frontiers. In Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC 2001): Lecture Notes in Computer Science 2223. Christchurch, New Zealand: Springer-Berlin, 2001, 291-307
[105] Chen J. Parameterized computation and complexity: a new approach dealing with NP- hardness. Journal of Computer Science and Technology, 2005, 20(1): 18-37
[106] 肖鸣宇,陈建二,韩旭里.低度图的点覆盖和独立问题下届改进.计算机学报 ,2005,28 (2):153-160
[107] Ge X. Parameterized algorithms and computational lower bounds: a structural approach [Ph.D. dissertation]. Texas A & M University, 2005
[108] Downey R G, Fellows M. Parameterized computational feasibility. In Proceedings of the 2nd Cornell Workshop on Feasible Mathematics: Feasible Mathematics Ⅱ. Birkhauser Boston: 1995, 219-244
[109] Niedermeier R. Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms.In Proceedings of the 29th International Symposium Mathematical Foundations of Computer Science, MFCS 2004:LNCS.Prague, Czech Republic: Springer, 2004, 84-103
[110] Abu-Khzam F N, Langston M A, Shanbhag P, et al. Scalable Parallel Algorithms for FPT Problems. Algorithmica, 2006, 45(3): 269-284
[111] Abu-Khram F N, Collins R L. Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments. In Proceedings of the 6th ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX '04): Lecture Notes in Computer Science. New Orleans, Louisiana:Springer-Verlag, 2004, 62-69
[112] Rodriguez EP. Systematic Kernelization in FPT Algorithm Design [Ph D.dissertation]. The University of Newcastle, 2005
[113] Diaz J, Petit J, Thilikos D M. Kernels for the Vertex Cover Problem on the Preferred Attachment Model.In Proceedings of 5th International Experimental Algorithms Workshop, WEA 2006:Lecture Notes in Computer Science 4007. Cala Galdana, Spain: Springer-Berlin, 2006, 231-240
[114] Abu-Khzam F N, Langston M A, Suters W H. Fast, Effective Vertex Cover Kernelization: A Tale of Two Algorithms. Proceedings of ACS/IEEE International Conference on Computer Systems and Applications,Cairo,Egypt,2005
[115]Bollob(?)s B.Random Graphs,2nd Edition.Cambridge,England:Cambridge University Press,2001
[116]Newman M E J,Strogatz S H,Watts D J.Random graphs with arbitrary degree distributions and their applications.Physical Review,2001,E 64,026118
[117]Wilf H S.Generatingfunctionology.Boston:Academic Press,1990
[118]Garey M,Johnson D.Computers and Intractability:A Guide to the Theory of NP- Completeness.New York:W.H.Freeman,1979
[119]沈项军.基于子网络结构属性的网络分割研究.计算机工程与应用,2007,43(23):64-68
[120]林皎,陈文光,栗强,等.基于图划分的全基因组并行拼接算法.计算机研究与发展,2006,43(8):1 323-1329
[121]Bollob(?)s B,Kohayakawa Y,Luczak T.Connectivity Properties of Random Subnetworks of the Cube.Random Struct.Algorithms,1995,6(2/3):221-230
[122]Nemhauser G L,Trotter L E.Vertex packings:Structoral properties and algorithms.Math.Programming,1975,(8):232-248
[123]Chen J,Kanj I,Jia W.Vertex cover:further observations and further improvements.Journal of Algorithms,2001,41:280-301
[124]Miehalewiez Z,Fogel D B.How to Solve It:Modem Heuristies.Springer,Berlin,2000
[125]Deng M,Sun F,Chen T.Assessment of the reliability of protein-protein interactions and protein function prediction.Pacific Symposium on Biocomputing,2003,140-151
[126]孙廷凯,增强型典型相关分析研究与应用[博士学位论文].南京航空航天大学,2006
[2]Barab(a)si A L,Olvtai ZN:Network biology:understanding the cell's functional organization.Nature Reviews Genetics,2004,5:101-113
[3]Yu J,Fotouhi F.Computational approaches for predicting protein-protein interactions:a survey.Journal of Medical Systems,2006,30(1):39-44
[4]Bu DB,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
[5]Rain JC,Selig L,De Reuse H,et al.The protein-protein interaction map of Helicobacter pylori.Nature,2001,409:211-215
[6]Uetz P,Giot L,Cagney G,et al.A comprehensive anaylsis of protein-protein interactions in Saccharomyces cerevisiae.Nature,2000,403:623-627
[7]Li S,Amrstorng C M,Benin N,et al.A map of the interactome network of the metazoan C.elgeans.Sceince,2004,303:540-543
[8]Giot L,Bader J S,Brouwer C,et al.A protein interaction map of Drosophila melanogaster.Sceince,2003,302:1727-1736
[9]Bader G D,Donaldson I,Wolting C,et al.BIND-The biomolecular interaction network database.Nucleic Acids Research,2001,29:242-245
[10]Zanzoni A,Montecchi-Palazzi L,Quondam M,et al.MINT:a Molecular INTeraction database.FEBS Letter,2002,513:135-140
[11]Breitkreutz B J,Stark C,Tyers M.The GRID:the General Repository for Interaction Datasets.Genome Biology,2003,4:R23
[12]Phizicky E,Bastiaens P I,Zhu H,et al.Protein analysis on a proteomic scale.Nature,2003,422,208 - 215
[13]Fields S,Sternglanz R.The two-hybrid system:an assay for protein - protein interactions.Trends in Genetics,1994,10,286 - 292
[14]Pandey A,Mann M.Proteomics to study genes and genomes.Nature,2000,405,837 - 846
[15]von Mering C,Jensen L J,Snel B,et al.STRING:known and predicted protein-protein associations,integrated and transferred across organisms.Nucleic Acids Research,2005,33(Database Issue):D433
[16]Alfarano C,Andrade C E,Anthony K,et al.The Biomolecular Interaction Network Database and related tools 2005 update.Nucleic Acids Research,2005,33(Database Issue):D418
[17]Peter U,Russell L.Finley J.From protein networks to biological systems.FEBS Letters 2005,579:1821-1827
[18]卢宏超.基于蛋白网络聚类的基因功能研究[博士学位论文].北京:中国科学院计算技术研究所,2006
[19]王建新,黄元南,陈建二.一种基于彩色编码技术的基序发现算法.软件学报,2007,18(6):1298-1307
[20]Yanjun Q,Femanda B,Christos F,et al.Protein complex identification by supervised graph local clustering.Bioinformatics,2008,24(ISMB):i250 - i258
[21]Bing Z,Byung H P,Tatiana K,et al.From pull-down data to protein interaction networks and complexes with biological relevance.Bioinformatics,2008,24(7):979-986
[22]Noga A,Phuong D,Iman H,et al.Biomolecular network motif counting and discovery by color coding.Bioinformatics,2008,24(ISMB):i241-i249
[23]Marcus T D,Gunnar W K,Andreas R,et al.Identifying functional modules in protein - protein interaction networks:an integrated exact approach.Bioinformatics,2008,24(ISMB):i223 - i231
[24]Albert R,Jeong H,Barab(?)si A L.Error and attack:tolerance of complex networks.Nature,2000,406:378-382
[25]Jeong H,Mason S P,Barab(?)si A L,Oltvai Z N.Lethality and centrality in protein networks.Nature,2001,411:41-42
[26]Gerdes S Y.Experimental determination and system-level analysis of essential genes in Escherichia coli.MG 1655,Journal of Bacteriology,2003,185:5673-5684
[27]Alon U,Surette M G,Barkai N,Leibler S.Robustness in bacterial chemotaxis.Nature,1999,397:168-171
[28]Csermely P,Agoston V,Pongor S.The efficiency of multi-target drugs:the network approach might help drug design.Trends in Pharmacological Sciences,2005,26:178-182
[29]谭璐,姜璐.系统生物学与生物网络研究.复杂系统与复杂性科学.2005,2(4):1-9
[30]Watts D J,Strogatz S H.Collective dynamics of Small-world' networks.Nature,1998,393:440-442
[31]Strogatz S H.Exploring complex networks.Nature,2001,410:268-276
[32]Barab(?)si A L,Albert R.Emergence of scaling in random networks.Science,1999,286:509-512
[33]Boccaletti S,Latora V,Moreno Y,et al.Complex Networks:Structure and Dynamics.Physics Reports,2006,424(4,5):175-308
[34]史定华.网络-探索复杂性的新途径.系统工程学报,2005,20(2):115-119
[35]Newman M E J.Who is the best connected scientist? A study of scientific coauthorship networks.Complex Networks,Lecture Notes in Physics.Springer Berlin / Heidelberg,2004,650:337-370
[36]Jeong H,Tombor B,Albert R,Oltvai Z N,Barab(?)si A L.The large-scale organization of metabolic networks.Nature,2000,407:651-654
[37]Wagner A,Fell D.The small world inside large metabolic networks.Proceedings of the Royal Society,London Series B,2001,268:1803-1810
[38]Fell D A,Wagner A.The small world of metabolism.Nature Biotechnology,2000,18:1121-1122
[39]Gil A,Michael X,Isaac S K,et al.Protein Network Topology Metric Conservation:From Yeast to Human.http://www.mit.edu/～gil/pub/Alterovitz_topology_metric_conservation_RECOMB_2005_invited.pdf
[40]Antonio D S,Hirotomo F,Paul O M.Topology of small- world networks of protein-protein complex structures.Bioinformatics,2005,21(8):1311-1315
[41]Barab(?)si A L.Scale-Free Networks.Scientific American,2003,288:60-69
[42]Eisenberg E,Levanon E Y.Preferential attachment in the protein network evolution.Physical Review Letters,2003,91:138701
[43]Schilling C H,Palsson B O.Assessment of the metabolic capabilities of Haemophilus influenzae Rd through a genome-scale pathway ayalysis.Journal of Theoretical Biology,2000,203:249-283
[44]Newman M E J.The structure and function of complex networks.SIAM Review,2003,45(2):167-256
[45]谭跃进,吴俊.网络结构熵及其在非标度网络中的应用.系统工程理论与实践,2004,(6):1-3
[46]王林,戴冠中,胡海波.无尺度网络的一个新的拓扑参数.系统工程理论与实践,2006,(6):49—53
[47]Wang X F.Complex networks:Topology,dynamics and synchronization.International Journal of Bifurcation and Chaos,2002,12(5):885-916
[48]Ravasz E,Somera A L,Mongru D A,et al.Hierarchical organization of modularity in metabolic networks.Science,2002,297:1551-1555
[49]Pr(?)ulj N,Corneil D G,Jurisica I.Efficient estimation of graphlet frequency distributions in protein-protein interaction networks.Bioinformatics,2006,22(8):974-980
[50]Freeman L C.Centrality in social networks:I.Conceptual clarification.Social Networks,1979,1:215-239
[51]Ernesto E.Virtual identification of essential proteins within the protein interaction network of yeast.Proteomics,2005,6(1):35-40
[52]Bonacich P.Power and centrality:a family of measures.American Journal of Sociology,1987,92:1170-1182
[53]谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法.系统工程理论与实践,2006,(11):79—105
[54]李鹏翔.任玉晴,席酉民.网络节点(集)重要性的一种度量指标.系统工程,2004,22(4):13-20
[55] Zhao J, Yu H, Luo J H, Cao Z W, Li Y X. Hierarchical modularity of nested bow-ties in metabolic networks. BMC Bioinformatics, 2006, 7: 386
[56] Guimera R, Sales P M, Amaral L A N.Modularity from fluctuations in random graphs and complex networks. Physical Review, 2004, E, 70(8):025101
[57] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004,69:066133
[58] Shen Orr S S, Milo R, mangan S, et al. Network notifs in the transcriptional regulation network of Escherichia coli. Nature Genetics, 2002, 31:64-68
[59] Yeger Lotem E, Sattath S, Nadav K, et al. Network motifs in integrated cellular networks of transcription-regulation and protein-protein interaction. Proceedings of the National Academy of Sciences, 2004, 101(52): 5934-5939
[60] Milo R, Shen O S, Itzkovitz S, et al. Network motifs: simple building blocks of complex networks. Science, 2002,298:824-827
[61] Vazquez A, Dobrin R, Sergi D, et al. The topological relationship between the large-scale attributes and local interaction patterns of complex networks. Proceedings of the National Academy of Sciences, 2004, 101(52): 17940-17945
[62] Burt R S, Minor M J. Applied Network Analysis: A Methodological Introduction. Social Forces, 1985, 63(3): 856-858
[63] Poulin R, Boily M-C, Masse B R. Dynamical systems to define centrality in social networks. Social Networks, 2000, 22:187-220
[64] 许进.一种研究系统的新方法-核与核度法.系统工程与电子技术, 1994,(6): 1-10
[65] Wasserman S, Faust K. Social network analysis: methods and applications. Cambridge: Cambridge University Press, 1994
[66] Jose B P L, Benjamin A, Jose M P A, et al. An Exponential Core in the Heart of the Yeast Protein Interaction Network. Molecular Biology and Evolution, 2005, 2(3): 421-425
[67] Kwang I G, Michael E C, David V, et al. The human disease network. Proceedings of the National Academy of Sciences, 2007, 104 (21): 8685-8690
[68] Maya R S, Thomas J B, Alan V O, et al. Global network analysis of phenotypic effects: Protein networks and toxicity modulation in Saccharomyces cerevisiae. Proceedings of the National Academy of Sciences, 2004, 101(52): 18006-18011
[69] 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
[70] Jeong H, Oltvai Z N, Barab(?)si A L. Prediction of protein essentiality based on genomic data. ComPlexUs, 2003,1: 19-28
[71] Yu H Y, Dov G, Li H X, et al. Genomic analysis of essentiality within protein networks. Trends in Genetics, 2004, 20(6): 227-231
[72] Igor U, Ron S. Pathway redundancy and protein essentiality revealed in the Saccharomyces cerevisiae interaction networks. Molecular Systems Biology, 2005, 3:104
[73] Kelley R, Ideker T. Systematic interpretation of genetic interactions using protein networks. Nature Biotechnology, 2005, 23: 561-566
[74] He X L, Zhang J Z. Why do hubs tend to be essential in protein networks? PloS Genetics, 2006, 2(6): 0826- 0834
[75] Palumbo M C, Colosimo A, Giuliani A, et al. Functional essentiality from topology features in metabolic networks: A case study in yeast. FEBS Letter, 2005, 579: 4642-4646
[76] Samal A, Singh S, Giri V, et al. Low degree metabolites explain essential reactions and enhance modularity in biological networks. BMC Bioinformatics, 2006, 7:118
[77] Lemke N, Heredia F, Barcellos C K, et al. Essentiality and damage in metabolic networks. Bioinformatics, 2004, 20: 115-119
[78] Mombach J C M, Lemke N, Silva N M, et al. Bioinformatics analysis of mycoplasma metabolism: important enzymes, metabolic similarities, and redundancy. Computers in Biology and Medicine 2006, 36(5): 542-552
[79] Mark L S, Daniel E L P, Aviv B. Functional and evolutionary inference in gene networks: does topology matter? Genetica, 2007, 129:83-103
[80] Coulomb S, Bauer M, Bernard D. Gene essentiality and the topology of protein interaction networks. Proceedings of the Royal Society, 2005, B 272:1721-1725
[81] Gustafson AM, Snitkin ES, Parker SC, et al. Towards the identification of essential genes using targeted genome sequencing and comparative analysis. BMC Genomics, 2006, 7: 265
[82] Feng L, Yunfeng Y, Chin-Fu C, et al. Modular organization of protein interaction networks. Bioinformatics 2007 23(2): 207-214
[83] Schuster S, Pfeiffer T, Moldenhauer F, et al. Exploring the pathway structure of metabolism: Decomposition into subnetworks and application to Mycoplasma pneumonise. Bioinformatics,2002, 18:351-361
[84] Guimera R, Amaral L A N. Function cartography of complex metabolic networks. Nature, 2005, 433:895-900
[85] Pablo B, Itay B, Vladislav V, et al. Functional topology classification of biological computing networks. Natural Computing, 2005, 4: 339-361
[86] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal on Matrix Analysis and Applications, 1990, 11:430
[87]Capocci A,Servedio V D P,Caldarelli G,et al.Detecting communities in large networks.Computer Science,2004,3243:181-187
[88]Girvan M,Newman M E J.Community structure in social and biological networks.Proceedings of the National Academy of Sciences,2001,99:7821-7826
[89]Newman M E J,Girvan M.Finding and evaluating community structure in networks.Physical Review E,2004,69:026113
[90]Ravi R,Sinha A.Hedging Uncertainty:Approximation Algorithms for Stochastic Optimization Problems.Mathematical Programming,2006,108(1):97-114
[91]范辉,华臻,李晋江.原达.点覆盖问题的蚂蚁算法求解.计算机工程与应用,2004.23:71—73
[92]董亚非,张家秀,殷志祥,许进.最小节点覆盖问题的改进粘贴模型.电子与信息学报,2005,27(4):556—560
[93]Adleman L.Molecular computation of solutions to combinatorial problems.Science,1994,266(1):1021-1024
[94]Chen Z,Lu M,Qu H,Zhu H.A Probabilistic Parameterized Algorithm for Vertex Cover in Sticker Model.In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04):IPDPS.Santa Fe,New Mexico,USA:IEEE Computer Society,2004,166
[95]Gilmour S,Dras M.Kernelization as Heuristic Structure for the Vertex Cover Problem.In Proceedings of Ant Colony Optimization and Swarm Intelligence,5th International Workshop (ANTS,2006):LNCS.Brussels,Belgium:Springer Verlag,2006
[96]刘湘辉,殷建平,卢锡城,蔡志平,赵建民.基于原始对偶方法求解网络流量监测集算法.软件学报.2006,17(4):838—844
[97]Alber J,Gramm J,Niedermeier R.Faster exact algorithms for hard problems:a parameterized point of view.Discreted Mathematics,2001,229(1):3-27
[98]曲惠琴.DNA计算若干问题研究[博士学位论文].复旦大学.2005
[99]Chen J,Huang X,Kanj I,Xia G.Linear FTP reductions and computational lower bounds.In Proceedings of the 36th ACM Symposium on Theory of Computing(STOC):L(?)szl(?) Babai,ed.ACM2004.Chicago,IL,USA:ACM Press,2004,212-221
[100]Rizzi R,Bafna V,Istrail S,Lancia G.Practical algorithms and fixed-parameter tractability for the single individual SNP haplotying problem.In Proceedings of the 2nd Workshop on Algorithms in Bioinformatics(WABI 2002):Lecture Notes in Computer Science 2454.Rome:Springer Verlag,2002,29-43
[101]Buhler J,Tompa M.Finding motifs using random projection.In Proceeding of the 5th Annual International Conference on Computational Molecular Biology(RECOMB'2001):ACM2001.Montreal,Canada:ACM Press,2001,69-76
[102] Eskin E, Pevzner P A. Finding composite regulatory patterns in DNA sequences. Bioinformatics, 2002, 18(1): 354-363
[103] Fellows M, Gramm J, Niedermeier R. Parameterized Intractability of Motif Search Problems. In Proceeding of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002): Lecture Notes in Computer Science 2285. Antibes - Juan les Pins, France: Springer-Verlag, 2002, 262-273
[104] Fellows M. Parameterized complexity: the main ideas and some research frontiers. In Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC 2001): Lecture Notes in Computer Science 2223. Christchurch, New Zealand: Springer-Berlin, 2001, 291-307
[105] Chen J. Parameterized computation and complexity: a new approach dealing with NP- hardness. Journal of Computer Science and Technology, 2005, 20(1): 18-37
[106] 肖鸣宇,陈建二,韩旭里.低度图的点覆盖和独立问题下届改进.计算机学报 ,2005,28 (2):153-160
[107] Ge X. Parameterized algorithms and computational lower bounds: a structural approach [Ph.D. dissertation]. Texas A & M University, 2005
[108] Downey R G, Fellows M. Parameterized computational feasibility. In Proceedings of the 2nd Cornell Workshop on Feasible Mathematics: Feasible Mathematics Ⅱ. Birkhauser Boston: 1995, 219-244
[109] Niedermeier R. Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms.In Proceedings of the 29th International Symposium Mathematical Foundations of Computer Science, MFCS 2004:LNCS.Prague, Czech Republic: Springer, 2004, 84-103
[110] Abu-Khzam F N, Langston M A, Shanbhag P, et al. Scalable Parallel Algorithms for FPT Problems. Algorithmica, 2006, 45(3): 269-284
[111] Abu-Khram F N, Collins R L. Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments. In Proceedings of the 6th ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX '04): Lecture Notes in Computer Science. New Orleans, Louisiana:Springer-Verlag, 2004, 62-69
[112] Rodriguez EP. Systematic Kernelization in FPT Algorithm Design [Ph D.dissertation]. The University of Newcastle, 2005
[113] Diaz J, Petit J, Thilikos D M. Kernels for the Vertex Cover Problem on the Preferred Attachment Model.In Proceedings of 5th International Experimental Algorithms Workshop, WEA 2006:Lecture Notes in Computer Science 4007. Cala Galdana, Spain: Springer-Berlin, 2006, 231-240
[114] Abu-Khzam F N, Langston M A, Suters W H. Fast, Effective Vertex Cover Kernelization: A Tale of Two Algorithms. Proceedings of ACS/IEEE International Conference on Computer Systems and Applications,Cairo,Egypt,2005
[115]Bollob(?)s B.Random Graphs,2nd Edition.Cambridge,England:Cambridge University Press,2001
[116]Newman M E J,Strogatz S H,Watts D J.Random graphs with arbitrary degree distributions and their applications.Physical Review,2001,E 64,026118
[117]Wilf H S.Generatingfunctionology.Boston:Academic Press,1990
[118]Garey M,Johnson D.Computers and Intractability:A Guide to the Theory of NP- Completeness.New York:W.H.Freeman,1979
[119]沈项军.基于子网络结构属性的网络分割研究.计算机工程与应用,2007,43(23):64-68
[120]林皎,陈文光,栗强,等.基于图划分的全基因组并行拼接算法.计算机研究与发展,2006,43(8):1 323-1329
[121]Bollob(?)s B,Kohayakawa Y,Luczak T.Connectivity Properties of Random Subnetworks of the Cube.Random Struct.Algorithms,1995,6(2/3):221-230
[122]Nemhauser G L,Trotter L E.Vertex packings:Structoral properties and algorithms.Math.Programming,1975,(8):232-248
[123]Chen J,Kanj I,Jia W.Vertex cover:further observations and further improvements.Journal of Algorithms,2001,41:280-301
[124]Miehalewiez Z,Fogel D B.How to Solve It:Modem Heuristies.Springer,Berlin,2000
[125]Deng M,Sun F,Chen T.Assessment of the reliability of protein-protein interactions and protein function prediction.Pacific Symposium on Biocomputing,2003,140-151
[126]孙廷凯,增强型典型相关分析研究与应用[博士学位论文].南京航空航天大学,2006