The Application Of Large Graph Theory In The Network Interaction Of Protein Interaction

The study of Bioinformatics has been growing rapidly over the past few years, it is mainly focused on DNAs and proteins. Between them, proteins are the main undertakers of all kinds of life activities, and protein-protein interactions are the basis of maintaining the structure of cells and realizing functions, so studying protein interaction networks is of great importance. By aligning and analyzing the protein interaction networks from different species, we can confer unknown proteins’ functions, mine conserved functional modules and so on. Currently a number of methods and tools have been studied for the alignment of protein interaction networks, and most of them focus on finding the conserved interaction regions across different networks by either local or global mapping of similar sequences. But how to improve the speed, scalability and accuracy of the network alignment is still the hot and difficult issue in studying the alignment of protein interaction networks.In this paper, considering the characteristic that a protein interaction network can be represented as a graph, we took the S.cerevisiae and D.melanogaster protein-protein interaction networks as the basic data sets, analyzed and studied a method for network alignment based on the partition theory of big graphs. Firstly, targeted at the protein interaction network, we proposed a partitioning algorithm, and processed the edge nodes by applying a full replication strategy. Secondly, we proposed a kind of protein similarity based on sequence and network topology, and found out all the similar proteins on the basis of network partitions. Thirdly, we mined the corresponding conserved patterns based on the similar proteins which have been found out, and proposed a method of mining the maximum conserved patterns according to a scoring system which consists of sequence similarity, interaction conservation and functional coherence. Finally, we carried out the experimental analysis and verification, and the results proved that applying the partition theory of big graphs to the alignment of protein interaction networks has a good effect, and it can significantly improve the speed of network alignment.