Degree-Based Sampling Method with Partition-Based Subgraph Finder for Larger Motif Detection

Abstract:

Network motifs are subnetworks that appear in the network far more frequently than in randomized networks. They have gathered much attention for uncovering structural design principles of complex networks. One of the previous approaches for motif detection is sampling method, in- troduced to perform the computational challenging task. However, it suffers from sampling bias and probability assignment. In addition, subgraph search, being very time-consuming, is a critical process in motif detection as we need to enumerate subgraphs of given sizes in the original input graph and an ensemble of random generated graphs. Therefore, we present a Degree-based Sampling Method with Partition-based Subgraph Finder for larger motif detection. Inspired by the intrinsic feature of real biological networks, Degree-based Sampling is a new solution for probability assignment based on degree. And, Partition-based Subgraph Finder takes its inspiration from the idea of partition, which improves computational efficiency and lowers space consumption. Experimental study on UETZ and E.COLI data set shows that the proposed method achieves more accuracy and efficiency than previous methods and scales better with increasing subgraph size.

• Periodical: Applied Mechanics and Materials (Volumes 135-136)
• Pages: 509-515
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.135-136.509
• Online since: October 2011
• Authors: Jia Ji Zhou, De Sheng Kong, Jie Yue He
• Keywords: Network Motif, Sampling Probability Assignment, Subgraph Enumeration

References

[1] B.D. McKay. Practical Graph Isomorphism. Congressus Numerantium, 30: 45-87, (1981).

[2] B.D. McKay. User¡¯s Guide (Version 1. 5). Technical Report TR-CS-90-02, Dept. of Computer Science, Australian Nat¡¯l Univ, (1990).

[3] G. Ciriello and C. Guerra. A review on models and algorithms for motif discovery in proteinprotein interaction network. Briefings in Functional Genomics and Proteomics, 7(2): 147-156, (2008).

DOI: 10.1093/bfgp/eln015

[4] Kreher D and Stinson D. Combinatorial algorithms: Generation, Enumeration and Search. CRC Press LTC, Florida, (1998).

[5] P. Erdos and A. Rnyi. On Random Graphs i. Publ. Math. Debrecen 6, pages 290-297, (1959).

[6] Bj˝orn H. Junker. Analysis of Biological Networks. WileyBlackwell, Oxford, (2008).

[7] N. Kashtan, S. Itzkovitz, R. Milo, and U. Alon. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics, 20(11): 1746-1758, (2004).

DOI: 10.1093/bioinformatics/bth163

[8] L. Giot, G. Cagney, and etal. A comprehensive analysis of protein-protein interactions in saccharomyce cerevisiae. Nature, 403(6770): 623-627, (2000).

[9] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, Chklovskii, D., and U. Alon. Network Motifs: Simple Building Blocks of Complex Networks. Science, 298: 824-827, (2002).

DOI: 10.1126/science.298.5594.824

[10] S.S. Shen-Orr, R. Milo, S. Mangan, and U. Alon. Network motif in the transcriptional regulation network of escherichia coli. Nature Genetics, 31(1): 64-68, (2002).

DOI: 10.1038/ng881

[11] S. Wernicke. Efficient detection of network motifs. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4): 347-359, (2006).

DOI: 10.1109/tcbb.2006.51

[12] S. Wernicke. FANMOD: a tool for fast network motif detection. Bioinformatics, 22: 1152-1153, (2006).

DOI: 10.1093/bioinformatics/btl038

[13] Zahra. K, Hayedeh. A, Kavosh, and etal. A new algorithm for finding network motifs. BMC Bioinformatics, 10(318), (2009).