Building blocks of biological networks: a review on major network motif discovery algorithms
Building blocks of biological networks: a review on major network motif discovery algorithms
- Author(s): A. Masoudi-Nejad ; F. Schreiber ; Z.R.M. Kashani
- DOI: 10.1049/iet-syb.2011.0011
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): A. Masoudi-Nejad 1 ; F. Schreiber 2, 3 ; Z.R.M. Kashani 1
-
-
View affiliations
-
Affiliations:
1: Laboratory of Systems Biology and Bioinformatics (LBB), Institute of Biochemistry and Biophysics, University of Tehran, Iran
2: Institute of Computer Science, Martin Luther University Halle-Wittenberg, Halle, Germany
3: Institute of Computer Science, Leibniz Institute of Plant Genetics and Crop Plant Research (IPK), Gatersleben, Germany
-
Affiliations:
1: Laboratory of Systems Biology and Bioinformatics (LBB), Institute of Biochemistry and Biophysics, University of Tehran, Iran
- Source:
Volume 6, Issue 5,
October 2012,
p.
164 – 174
DOI: 10.1049/iet-syb.2011.0011 , Print ISSN 1751-8849, Online ISSN 1751-8857
In recent years, there has been a great interest in studying different aspects of complex networks in a range of fields. One important local property of networks is network motifs, recurrent and statistically significant sub-graphs or patterns, which assists researchers in the identification of functional units in the networks. Although network motifs may provide a deep insight into the network's functional abilities, their detection is computationally challenging. Therefore several algorithms have been introduced to resolve this computationally hard problem. These algorithms can be classified under various paradigms such as exact counting methods, sampling methods, pattern growth methods and so on. Here, the authors will give a review on computational aspects of major algorithms and enumerate their related benefits and drawbacks from an algorithmic perspective.
Inspec keywords: sampling methods; statistical analysis; complex networks; network theory (graphs); graph theory; computational complexity; biology; pattern classification
Other keywords:
Subjects: Systems theory applications in biology and medicine; Combinatorial mathematics; Computational complexity; Other topics in statistics
References
-
-
1)
- Grochow, J.A., Kellis, M.: `Network motif discovery using sub-graph enumeration and symmetry-breaking', RECOMB, 2007, p. 92–106.
-
2)
- B.D. McKay . Isomorph-free exhaustive generation. J. Algorithms , 306 - 324
-
3)
- S. Omidi , F. Schreiber , A. Masoudi-Nejad . MODA: an efficient algorithm for network motif discovery in biological networks. Genes Genet. Syst. , 5 , 385 - 395
-
4)
- L.A.N. Amaral , A. Scala , M. Barthélémy . Classes of small-world network. Proc. Natl. Acad. Sci. , 21 , 11149 - 11152
-
5)
- J.R. Ullman . An algorithm for subgraph isomorphism. J. ACM , 1 , 31 - 42
-
6)
- Ribeiro, P., Silva, F.: `-tries: an efficient data structure for discovering network motifs', ACM, 2010.
-
7)
- S. Bornholdt , H.G. Schuster . (2003) Handbook of graphs and networks: from the genome to the Internet.
-
8)
- F. Picard , J.-J. Daudin , S. Schbath , S. Robin . Assessing the exceptionality of network motifs. J. Comput. Biol. , 1 , 1 - 20
-
9)
- F. Schreiber , H. Schwöbbermeyer . Frequency concepts and pattern detection for the analysis of motifs in networks. Trans. Comput. Syst. Biol. III , 89 - 104
-
10)
- R. Milo , S. Shen-Orr , S. Itzkovitz . Network motifs: simple building blocks of complex networks. Science , 824 - 827
-
11)
- Huan, J., Wang, W., Prins, J.: `SPIN: mining maximal frequent sub-graphs from graph databases', Proc. Tenth ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, 2004, p. 581–586.
-
12)
- A.-L. Barabasi , R. Albert . Emergence of scaling in random networks. Science , 509 - 511
-
13)
- N. Kashtan , S. Itzkovitz , R. Milo , U. Alon . Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics , 11 , 1746 - 1758
-
14)
- S. Wernicke . Efficient detection of network motifs. IEEE/ACM Trans. Comput. Biol. Bioinf. , 4 , 347 - 359
-
15)
- E.A. Bender , E.R. Canfield . The asymptotic number of labeled graphs with given degree sequences. J. Comb. Theory A , 296 - 307
-
16)
- N. Alon , P. Dao , I. Hajirasouliha , F. Hormozdiari , S.C. Sahinalp . Biomolecular network motif counting and discovery by color coding. Bioinformatics , i241 - i249
-
17)
- H. Schwöbbermeyer , B.H. Junker , F.H. Schreiber . (2008) Network motifs, Analysis of biological networks.
-
18)
- B.D. McKay . Practical graph isomorphism. Congr. Numer. , 45 - 87
-
19)
- P. Dwight Kuo , W. Banzhaf , A. Leier . Network topology and the evolution of dynamics in an artificial genetic regulatory network model created by whole genome duplication and divergence. Biosystems , 3 , 177 - 200
-
20)
- F. Harary . (1969) Graph theory.
-
21)
- R. Albert , A.-L. Barabasi . Statistical mechanics of complex networks. Rev. Mod. Phys. , 47 - 92
-
22)
- A. Mazurie , S. Bottani , M. Vergassola . An evolutionary and functional assessment of regulatory network motifs. Genome Biol. , 4
-
23)
- R.V. Sole , S. Valverde . Are network motifs the sprandrels of cellular complexity?. Trends Ecol. Evol. , 8 , 419 - 422
-
24)
- M.E.J. Newman , S.H. Strogatz , D.J. Watts . Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E
-
25)
- G. Ciriello , C. Guerra . A review on models and algorithms for motif discovery in protein-protein interaction networks. Brief Funct. Genomic Proteomic , 2
-
26)
- Grochow, J.A.: `Massachusetts institute of technology. dept. of electrical engineering and computer science.: on the structure and evolution of protein interaction networks', 2006, MEng, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science.
-
27)
- R. Milo , S. Itzkovitz , N. Kashtan . Superfamilies of designed and evolved networks. Science , 5663 , 1538 - 1542
-
28)
- A. Vázquez , R. Dobrin , D. Sergi . The topological relationship between the large-scale attributes and local interaction patterns of complex networks. Proc. Natl. Acad. Sci. , 52 , 17940 - 17945
-
29)
- Chen, J., Hsu, W., Li Lee, M.: `NeMoFinder: dissecting genome-wide protein–protein interactions with meso-scale network motifs', Proc. 12th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining 2006;, 2006, Philadelphia, PA, USA, p. 106–115.
-
30)
- Z.R. Kashani , H. Ahrabian , E. Elahi . Kavosh: a new algorithm for finding network motifs. BMC Bioinf.
-
31)
- F. Schreiber , H. Schwobbermeyer . MAVisto: a tool for the exploration of network motifs. Bioinformatics , 17 , 3572 - 3574
-
32)
- U. Alon . (2006) An introduction to systems biology: design principles of biological circuits.
-
33)
- P. Uetz , L. Giot , G. Cagney . A comprehensive analysis of protein–protein interactions in Saccharomyces cerevisiae. Nature , 6770 , 623 - 627
-
1)
Related content
