Research On Approximate Graph Matching And Their Applications In Global Network Alignment

Approximate graph matching is widely used in social analysis,informatics,bioinformatics and other fields,and it is the mainstream of current research.Due to the limitation of noise,the traditional approximation algorithm can not solve the approximate graph matching problem efficiently,especially the approximate subgraph matching problem.Using statistical significance model is a feasible strategy to alleviate or even overcome the noise problem.The problem of global network alignment is one of the most popular research fields in bioinformatics.It is of great significance to detect functional similarity proteins and discover the homology of proteins among different species through network alignment.The goal of global network alignment is to find the best global alignment between two networks.By describing it properly,the problem of global network alignment can be transformed into the problem of approximate graph matching.Based on graph theory and statistical significance model,this paper studies and explores the problem of approximate subgraph matching,and global network alignment.The main work of this paper includes:(1)In this paper,the problem of approximate subgraphs matching is studied.Working on solving the problem that the approximate subgraph matching algorithm ignores the potential distribution relationship between the tag information of query graph and the tag information of large data graph to be searched,a method based on the statistical significance captured by Chi-Square statistics is proposed to represent the structure similarity of approximate subgraph matching,in which the statistical significance is robust in dealing with noise and takes into account the neighborhood of internal structure and the potential distribution relationship of label information.Compared with the traditional algorithm,this algorithm is proved to be effective and efficient.(2)Based on the importance of destructive equivalence,the problem of global network alignment is studied.Due to the existing global network alignment algorithms lacks a well thought of difference between the structure and properties of false hub proteins and essential hub proteins,a method based on the idea of destruction equivalent to importance is proposed to measure the importance of protein structure according to the loss of different nodes to the overall connectivity of the network.Compared with other latest and most popular algorithms,it shows higher comparison accuracy and functional consistency.(3)Based on statistical significance,the global network alignment problem is studied.In view of the fact that there is a lot of noise in PPI network data,combined with statistical significance model,a global network alignment algorithm based on ChiSquare statistics is proposed.Experiments on several real datasets show that the algorithm proposed in this paper is superior to some of the most advanced algorithms in the accuracy and efficiency of comparison results.