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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article