An Improved Method For Network Motif Detection And Motif Function Analysis

With the entering of bioinformatics research into post-genome era,the notion of motifs used for sequence data has been expanded to the level of networks,and therefore the concept of network motifs appears.Network motif is defined as a frequent and unique subgraph pattern in a network that occurs much more frequently in the target network than in random networks.Network motif is an important functional module building the network,causing widespread concern in many areas.For the problem of network motif discovery,researchers have proposed a number of algorithms,which have shown a good performance for detecting small-scale motifs.However,with the increase of the scale of the network and the size of the subgraph to be searched,the computational complexity of subgraph search and isomorphic subgraph search is significantly improved.Thus many algorithms can not meet the time requirement of scientific research.In addition,most of the literature on network motifs is related to the algorithm for network motif detection,and rarely involves the functional analysis of motifs.Functional analysis of motifs can give us deeper understanding on them,and make the motifs play an important role in understanding and analyzing the network.Therefore,it is imperative to explore a more efficient algorithm for network motif detection and the effective function analysis of motifs.By analyzing the shortcomings of the existing algorithms,this paper presents an improved algorithm for network motif discovery.A new method based on local structure feature representing input graph is proposed,which can extract the topological features of input graph more quickly and accurately.Then the improved affinity propagation clustering algorithm is used to cluster the extracted features.The clustering results are further processed to find the network motifs by the proposed motif decision criteria.In this paper,the effectiveness of the proposed algorithm is proved by the simulation experiment.The experiments of eight kinds of real network data from different research fields cost only a few seconds.Comparing to Kavosh,FANMOD,MFinder and other motif detection tools and algorithms,it shows that our algorithm has high running efficiency.The algorithm not only correctly identifies the various types of motifs that have been found,but also find the other motifs.At the end of the paper,GO and DAVID are introduced,which are two commonly used functional analysis tools.Two main methods for functional analysis are also discussed,which are functional annotation analysis and enrichment analysis.Functional analysis is performed on three motifs discovered in the transcriptional regulation network of Escherichia coli.The results show that they are significantly enriched in some specific functions.