Title: An algorithm for network motif discovery in biological networks
Authors: Guimin Qin; Lin Gao
Addresses: School of Computer Science and Technology, Xidian University Xi'an, Shaanxi 710071, China. ' School of Computer Science and Technology, Xidian University Xi'an, Shaanxi 710071, China
Abstract: Network motif discovery is a key problem in analysis of biological networks. In this paper, we present an efficient algorithm for detecting consensus motifs. First, we extend subgraph searching algorithm Enumerate Subgraphs (ESU) to efficiently search non-treelike subgraphs of which the probability of occurrence in random networks is small. Then, we classify isomorphic subgraphs into different groups. Finally, we use hierarchical clustering method to cluster subgraphs, and derive a consensus motif from the clusters. Our algorithm is applied to the Protein-Protein Interaction (PPI) networks and the transcriptional regulatory networks of E. coli and S. cerevisiae. The experiment results show that the algorithm can efficiently discover motifs, which are consistent with current biology knowledge. And, it can also detect several consensus motifs with a given size, which may help biologists go further into cellular process.
Keywords: network motifs; biological networks; PPI networks; transcriptional regulatory networks; motif discovery; consensus motifs; hierarchical clustering; bioinformatics; protein-protein interaction; E. coli; S. cerevisiae.
DOI: 10.1504/IJDMB.2012.045533
International Journal of Data Mining and Bioinformatics, 2012 Vol.6 No.1, pp.1 - 16
Received: 08 Jul 2009
Accepted: 11 Nov 2009
Published online: 17 Dec 2014 *