Pairwise Network Alignment Research Based On Protein-protein Interaction Network

Technological advances in high-throughput biological experimental methods for interaction detection have lead to an explosion of protein-protein interaction data.These data will be of great significance for the analysis of biological relationships between different species.Protein-protein interaction data is often abstracted as a network,and network alignment algorithms are an important tool for network data analysis.The network alignment between two different species will help understand cell organization,discover evolutionary conservation relationships of species and individual differences,which are helpful for disease analysis,new drug target treatment,and providing important information for the annotations transfer between species.At present,the protein-protein interaction network extracted from the experiment has the problem of data missing or data noise.Secondly,the topological information contained in the objective function of the existing algorithm is also relatively single,which seriously affects the alignment quality of the algorithm.In addition,the network alignment algorithm based on modularization usually calculates the module similarity by enumeration,which increases the time complexity of the algorithm.This paper aims at the above deficiencies,and the main contents are as follows:1.In order to solve the problem of partial data missing and noise in real protein-protein interaction network,a pairwise protein interaction network alignment algorithm based on state shift and neighborhood weighting was proposed.Firstly,the algorithm introduces the working principle of Markov chain and Page Rank;then,we use the probability sharing strategy of isolated nodes and the damping factor to supplement the similarity matrix,and the Markov chain is used to update the state transition vector iteratively until it converges.Finally,the similarity matrix between nodes is obtained according to the state transition vector,and the neighbor weighted greedy algorithm is used to solve the network alignment problem.The experimental results show that this method has the best biological mass and short running time.2.To solve the single problem of topological information in the objective function,a paired protein interaction network alignment algorithm that integrates multiple topological information is proposed.The algorithm first puts forward the concept of correlation value,which combines the structure information of the network itself to measure the similarity between nodes in the same network;Secondly,in order to more fully mine the similarity information between different network nodes,a topology score calculation method based on eigenvector centrality is proposed.This method combines degree information,the eigenvector centrality information of the node itself,and the average eigenvector centrality of neighbor nodes,and according to the similarity score obtained from this information,perform intramodule alignment;Finally,considering the modular nature of the network,the conservative edge metric between modules is introduced,so that the edge conservative information between different network modules can be obtained as much as possible.Experimental results show that this algorithm obtains a higher topological quality,and compared with other existing methods,this method has the best overall performance.3.In order to further improve the quality of alignment,reduce the time complexity of module similarity calculation and optimize the efficiency of alignment,a paired protein-protein interaction network alignment algorithm based on the divide and conquer strategy is proposed.Algorithm adopts the divide-and-conquer strategy as a whole.Firstly,module division is executed and module similarity is calculated according to the existing alignment information.Then,the candidate result set is obtained according to the subalignment of nodes between modules,and the alignment results are finally obtained through hypergraph matching.The similarity of nodes between different networks is judged from the centrality of the nodes themselves and the differences between nodes.The collective behavior of the existing alignment information is used to estimate the similarity between modules,which greatly improves the efficiency of module matching.The score function based on paths and nodes ensures the similarity of nodes in the same module.Compared with the existing algorithms,the algorithm in this paper performs best in both biological and topological indicators,reached the balance of topology and biological function quality.