A Novel Feature Clustering Based Algorithm For Detecing Network Motifs

With the successful completion of large-scale genome sequencing, gene prediction, as well as the work of the notes, bioinformatics research comes into the post-genome era. As one of the newest research field in bioinformatics, systems biology has attracted more and more attentions. At the same time, the research of motif detection has expanded from biological sequence data (DNA sequences and protein sequences) to the level of complex biological network. Network motif detection technology is exactly a powerful tool to uncover the structural design principles of biological networks as well as the law and trend of their development. Now it has become one of the hottest issues in systems biology field. In recent years, people have presented some effective algorithms in the study of network motif detection, which have shown a good performance in solving the network motif detection problems under small data scale. However, along with the expansion of the data scale, many algorithms can not solve the problems in that case. So studying more effective algorithm for detecting network motifs in a larger scale has become an important task in the biological network motif detection field.In this thesis, we firstly review the basic idea of the network motif detection technology. Also, we study and analyze some network motif detection algorithms based on other different methods. After that, we present a novel feature clustering based algorithm for detecting network motifs, called FCMD. The differences between FCMD and former algorithms are that FCMD expresses the topology structure of the motifs by constructing the local feature structure of each vertex in the input graph with a low computational complexity and searches the motifs rapidly by clustering in the corresponding feature space. Finally, we have experimental evaluation on real network data from various domains, such as biochemical network, neural network, and electronic circuit network, which shows that FCMD can accurately detect expected motifs at a runtime that is basically independent of the motif size. FCMD is proved to be better than former algorithms.