|
|
|
Evaluation of subgraph searching algorithms for
detecting network motifs in biological networks |
| Jialu HU 1, Lin GAO 1, Guimin QIN 2, |
| 1.School of Computer
Science and Technology, Xidian University, Xi’an 710071, China; 2.School of Computer
Science and Technology, Xidian University, Xi’an 710071, China；Software School,
Xidian University, Xi’an 710071, China; |
|
|
|
|
Abstract Despite several algorithms for searching subgraphs in motif detection presented in the literature, no effort has been done for characterizing their performance till now. This paper presents a methodology to evaluate the performance of three algorithms: edge sampling algorithm (ESA), enumerate subgraphs (ESU) and randomly enumerate subgraphs (RAND-ESU). A series of experiments are performed to test sampling speed and sampling quality. The results show that RAND-ESU is more efficient and has less computational cost than other algorithms for large-size motif detection, and ESU has its own advantage in small-size motif detection.
|
| Keywords
network motifs
subgraphs searching
subgraphs enumeration
sampling algorithm
|
|
Issue Date: 05 September 2009
|
|
|
Teichmann S A, Babu M M. Gene regulatory network growthby duplication. Nature Genetics, 2004, 36(5): 492―496
doi: 10.1038/ng1340
|
|
Milo R, Shen-Orr S, Itzkovitz S, et al. Network motifs: simple building blocks of complexnetworks. Science, 2002, 298(5594): 824―827
doi: 10.1126/science.298.5594.824
|
|
Yeger-Lotem E, Sattath S, Kashtan N, et al. Network motifs in integrated cellular networksof transcription-regulation and proteinprotein interaction. In: Proceedings of the National Academy of Sciences, 2004, 101(16): 5934―5939
doi: 10.1073/pnas.0306752101
|
|
Shen-Orr S, Milo R, Mangan S, et al. Network motifs in the transcriptional regulationnetwork of Escherichia coli. Nature Genetics, 2002, 31(1): 64―68
doi: 10.1038/ng881
|
|
Schreiber F, Schwbbermeyer H. Towards motif detection innetworks: frequency concepts and flexible search. In: Proceedings of Intl. Wsh. Network Tools and Applications in Biology, 2004, 91―102
|
|
Lee T I, Nical J R, Francois R, et al. Transcriptional regulatory networks in saccharomycescerevisiae. Science, 2002, 298(5594): 799―804
doi: 10.1126/science.1075090
|
|
Mangan S, Alon U. Structure and function ofthe feed-forward loop network motif. In:Proceedings of the National Academy of Sciences, 2003, 100(21): 11980―11985
doi: 10.1073/pnas.2133841100
|
|
Inokuchi A, Washio T, Motoda H. An apriori-based algorithm for mining frequent substructuresfrom graph data. In: Proceedings of EuropeanConference on Principles of Data Mining and Knowledge Discovery, 2000, 13―23
|
|
Yan X, Han J. gSpan: graph–basedsubstructure pattern mining. In: Proceedingsof IEEE International Conference on Data Mining, 2002, 721―723
|
|
Kashtan N, Itzkovitz S, Milo R, et al. Efficient sampling algorithm for estimatingsubgraph concentrations and detecting network motifs. Bioinformatics, 2004, 20(11): 1746―1758
doi: 10.1093/bioinformatics/bth163
|
|
Wernicke S. Efficientdetection of network motifs. IEEE/ACM Transactionson Computational Biology Bioinformatics, 2006, 3(4): 347―359
doi: 10.1109/TCBB.2006.51
|
|
Itzkovitz S, Milo R, Kastan N, et al. Subgraphs in random networks. Physical Review E, 2003, 68, 06127
doi: 10.1103/PhysRevE.68.026127
|
|
Johnson D B. Finding all the elementary circuits of a directed graph. SIAM Journal on Computing, 1975, 4: 77―84
doi: 10.1137/0204007
|
|
Alon N, Yuster R, Zwick U. Finding and counting given length cycles. Algorithmica, 1997, 17: 209―223
doi: 10.1007/BF02523189
|
|
Akkoyunlu E. Theenumeration of maximal cliques of large graphs. SIAM Journal on Computing, 1973, 2: 1―6
doi: 10.1137/0202001
|
|
Nesetril J, Poljak S. On the complexity of thesubgraph problem. Commentationes MathematicaeUniversitatis Carolinae, 1985, 26:415―419
|
|
Dyer M, Frieze A, Jerrum M. Approximately counting Hamilton cycles in dense graphs. In: Proceedings of the 5th Annual ACM/SIAM Symposiumon Discrete Algorithms, 1994, 336―343
|
|
Frieze A, Kannan R. Quick approximation to matricesand applications. Combinatorica, 1999, 19(2): 175―220
doi: 10.1007/s004930050052
|
|
Jerrum M. Counting,Sampling and Integrating: Algorithms and Complexity. Birkhauser Verlag, 2003
|
|
Itzhack R, Mogilevski Y, Louzoun Y. An optimal algorithm for counting network motifs. Physica A, 2007, 381: 482―490
doi: 10.1016/j.physa.2007.02.102
|
|
Wernicke S, Rasche F. FANMOD: a tool for fast networkmotif detection. Bioinformatics, 2006, 22(9): 1152―1153
doi: 10.1093/bioinformatics/btl038
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
