The Research On Probability Network Motifs Detection Algorithm Based On Protein-protein Interactions

As the development of high-throughput experiments on bioscience field, peopleget more and more biological data to protein structure and function. The researchgradually focuses from decoding the human genome project to protein structure forfurther process in terms of the whole biological evolution. Protein-protein interactionnetworks (PPI network) show the relationships of different protein structure andfunction in the biological activities. Network motifs are the basic building blocks ofthe PPI networks. The research on motifs has become a hot topic of the whole PPInetworks.Based on the PPI networks, this paper analyze the topological property andstatistic feature of network motifs, then summarize the existing research results aboutnetwork motifs in the biological networks and analysis the advantages anddisadvantages of the motifs detection algorithms. Aiming at some problems of this,this paper puts forward new algorithms of probability motif detection in PPI networks.Probability motifs are grouping from mutually similar subgraphs in biologicalnetworks. Based on the structural property, in this paper, an algorithm called AS-ESU(Adaptive Sampling Enumeration Subgraph) has been proposed to do subgraph miningand sampling. It is based on the adaptivity of the extension set of the subgraph. Thisalgorithm redistribution the probability values to each branch in the ESU-tree base onthe topological features of the complex biological networks. The new samplingalgorithm brings more stable results and the sampling subgraphs can be morerepresentative of the original networks. Then a new subgraph matching rule isproposed based on multiple features. This algorithm introduces a new subgraphmatching rule, makes the classification of the final probability motifs not onlyconsidered from the topological structure, but also have a biological significance.According to the experimental, the new algorithm can find kinds of probabilitynetwork motifs with different size.To further improve the accuracy of probability motifs detection, in this paper, anew graph encoding algorithm is proposed to change the subgraph adjacency matrix to0-1string. The purpose is to improve the clustering similarity in each class. Thismethod combines the whole network vertex degree (global) and subgraph edges (local)to ensure the exact0-1string of each subgraph. Because of the large numbers of subgraphs and the large amount of calculation, this paper also improve the clusteringprocess and make it more suitable for probability motif detection. During theclustering process, update the candidate probability motifs as the class representativeafter each iteration. It makes the similarity getting larger in each class and gettingsmaller between classes. According to the experimental, this method improve theclustering similarity of probability motifs.