title: Identification of large disjoint motifs in biological networks.
abstract: BACKGROUND
  Biological networks provide great potential to understand how cells function. Network motifs, frequent topological patterns, are key structures through which biological networks operate. Finding motifs in biological networks remains to be computationally challenging task as the size of the motif and the underlying network grow. Often, different copies of a given motif topology in a network share nodes or edges. Counting such overlapping copies introduces significant problems in motif identification.
  
  
  RESULTS
  In this paper, we develop a scalable algorithm for finding network motifs. Unlike most of the existing studies, our algorithm counts independent copies of each motif topology. We introduce a set of small patterns and prove that we can construct any larger pattern by joining those patterns iteratively. By iteratively joining already identified motifs with those patterns, our algorithm avoids (i) constructing topologies which do not exist in the target network (ii) repeatedly counting the frequency of the motifs generated in subsequent iterations. Our experiments on real and synthetic networks demonstrate that our method is significantly faster and more accurate than the existing methods including SUBDUE and FSG.
  
  
  CONCLUSIONS
  We conclude that our method for finding network motifs is scalable and computationally feasible for large motif sizes and a broad range of networks with different sizes and densities. We proved that any motif with four or more edges can be constructed as a join of the small patterns.
authors.affiliation: CISE Department, University of Florida, 432 Newell Dr, Gainesville, Florida, 32611, USA. relhesha@cise.ufl.edu.
authors.forename: Rasha
authors.initials: R
authors.lastname: Elhesha
authors.affiliation: CISE Department, University of Florida, 432 Newell Dr, Gainesville, Florida, 32611, USA.
authors.forename: Tamer
authors.initials: T
authors.lastname: Kahveci
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs / Q000235:genetics*; D019295:Computational Biology / Q000379:methods*; D053263:Gene Regulatory Networks; D019288:Herpesvirus 8, Human / Q000502:physiology; D006801:Humans; D010363:Pattern Recognition, Automated; D025941:Protein Interaction Mapping; D014764:Viral Proteins / Q000235:genetics / Q000378:metabolism*
chemical_list: D014764:Viral Proteins
keywords: Biological networks; Motif discovery; Overlap graph; Subgraph isomorphism