The Research On Network Motifs Detection Algorithm Based On Symmetric Subgraph And Layered Probability

As the study of human genomics has made great achievements,the focus of research on life science has moved from studying genetic information of life to reveal the molecular genetic information how to affect the overall level of functional,a large number of biological network data also be collected.In proteomics,Protein-Protein Interaction(PPI)networks is the overall expression of relationship between proteins,it also is the key to the research on evolution of biological systems.Network motif is the basic unit of interaction networks and have a major impact on the evolution of the protein.Motifs Detection gradually becomes a hot issue of proteomics research.As the calculation of motifs detection is an computational demanding problem,the network motifs detection algorithms are mostly based on improving time efficiency.This paper studies the precise network motifs algorithm in protein interaction networks,and some new methods are designed to improve time efficiency and accuracy of the sampling method.Studies have shown that symmetric structure existing in the network can cause computing redundancy.This paper proposes a new motif detection method MDBS(Motif Detection based on Basic Symmetric Subgraphs),it is the one to decrease redundant computation by the BSS(Basic Symmetric Subgraph).In this method,firstly it generate compressed graph by the property of BSS,and meanwhile in the process of enumerating subgraphs,it calls classification method to detect the same structure subgraphs,this method can decreases computation time in executing subgraphs isomorphism.By the experiments in different PPI networks,MDBS shows tremendous improvement in time efficiency.Sampling method has been used in enumerating subgraphs to decrease calculated amount.However,the sampling error in this method can not be ignored,because it influences the result validity seriously.This paper is dedicated to improve the stability and accuracy of the sampling algorithm,and comes up with a new method,named LaRand_ESU,which based on the the nodes' layered probability.After analyzing the experiments,it find that the sum of edge clustering coefficient(SoECC)and the Sum of Neighbors' Degrees(SoNDS)are the nodes' major factors about nodes' frequency in result set of subgraphs.Combining above two nodes' property,LaRand ESU make nodes which have different property value belong to different layers,and each layer own different probability value.In process of enumerating subgraphs,the process of expanding search is executed by comparing the random probability and the node's layer probability.Finally,the experiments in the PPI network show that this method improves the stability and accuracy of sampling method about enumerating subgraphs.