A Study Of Fuzzy Network Motif And Its Refinement Algorithm

With the entering of bioinformatics research into post-genome era, there are a large amount of complex networks with biological information. This prompts many researchers to study the characteristic of these networks’ topological structure as well as the relationships between their local structure and global functions. Therefore comes out the notion of network motif. There emerge a lot of network motif detection algorithms one after another from forward to now. Most of them need to enumerate all the sub-graphs in the network, generate a fixed number of random networks and make justification of graphic isomorphism. They are able to effectively find out network motifs in networks which have small number of vertices and edges. While with the increasing of the motifs’ and networks’ scale, the majority of these algorithms are faced with exponential growth of their computation complexity and they cannot finish the expected tasks. So, it is of utmost urgency to design some algorithms with lower computation complexity through deeply analysis of the network motif detection problem.The novel feature clustering based algorithm for detecting network motifs, named FCMD is basically independent of scale of motifs. The algorithm also has some problems such as the feature vectors of vertice cannot express the Bi-fan type motifs and the criterion of whether two graphs in one same motif clusters are overlapped is too strict. In this paper we present some improvements to deal with these problems.(1) We expand the range of local graph expressed by the feature vectors of vertice. This makes the graph from a relative sealed range to a range with “spur”.(2) We use a new criterion to judge whether two graphs are overlapped instead of the previous one that they must do not have any overlapped vertice. The new criterion permits certain number of overlapped vertice between two graphs and the number is changed with the total number of the two graphs’ vertice. As a result, when both of the two graphs have less number of vertice, the permitted number of overlapped vertice is less. On the contrary, when the total number of of the vertice of the two graphs increases, so does the permitted number of overlapped vertice. In addition, after careful analysis, we think the motifs detected by FCMD are fuzzy in comparison with the other existing algorithms. So we propose two algorithms to make the fuzzy motifs more precision: one is based onthe continuous Hopfield network, another one is based on the EEA motif detection algorithm which is an enumerating algorithm.In this paper we make experiencesbased on many kinds of real networks data. Through rational design of the experiments and detail analysis of the results, we conclude that:(1) the improved FCMD algorithm is equal to the original one in the quantity and quality of the detected motifs. And the previous one can effectively detect the Bi-fan type motifs.(2) Our proposed continuous Hopfield network can effectively find out the max isomorphic subgraph of two graphs. Because the number of both vertice and edges of motifs in same cluster are not the same, the designed Hopfield network cannot obtain desired result of fuzzy motifs refinement.(3) The EEA algorithm can effectively refine the fuzzy motifs and these motifs are exactly the result obtained when we directly use the EEA algorithm to detect motifs in the same network.