The Research Of Algorithm For Identifying Essential Proteins Based On Network Topology Characteristics

With the rapid development of bioinformatics, the study of biology has gradually extended to the level of proteomics. The functional modules will lost its function if remove the essential proteins, and the cells also cannot make the normal life activities, resulting in the organism cannot survive. Identifying and protecting essential proteins is the basis of drug development, and it has important theoretical significance and application value to understand the materials the cells life activities required. Based on the test data by using calculation methods to identify the esssential proteins can greatly save the time and resources, so identify the essential proteins in protein-protein interaction networks is an important research direction in the field of bioinformatics.At present, the widely used identify essential proteins algorithms are:degree centrality, closeness centrality, betweenness centrality, bridge centrality, local average connection centrality, network centrality and so on, but these measure algorithms identify essential proteins only from the global or local information of the protein-protein interaction network. In this paper, by analyzing the relationship of function modules and essential proteins, proposing a new indicator named local coefficient that can reflect the local topology characteristics of each vertex in protein-protein interaction network, and designing a new centrality measure algorithm named LBC that integrated the local coefficient and betweenness centrality. Because this algorithm not only contains the whole information of protein-protein interaction network, but also incorporates the local information of protein vertex, it can identify essential proteins more comprehensive. The experimental results show that in the scale-free networks, the essential protein recognition rate by LBC is higher than the above six centrality measure algorithms about more than 10%, and the stability and universality of LBC is superior to the above six centrality measure algorithm.The computing time complexity of betweenness centrality is higher, so in this paper, we will improve the computing time complexity from two aspects. On the one hand, we will improve from the algorithm itself, using the VC dimension to control sample size only calculate part of the shortest pathes when performing the betweenness centrality, greatly improving the computational efficiency under the lower precision condition. On the other hand, improving the algorithm using GPU, designing and implementing betweenness centrality based on CUDA architecture, through the GPU hardware acceleration. The experimental results show that LBC based on CUDA make the computation time shortened 20-100 times in guarantee under the invariable accuracy condition.