title: An efficient algorithm for detecting frequent subgraphs in biological networks.
abstract: BACKGROUND
  With rapidly increasing amount of network and interaction data in molecular biology, the problem of effectively analyzing this data is an important one. Graph theoretic formalisms, commonly used for these analysis tasks, often lead to computationally hard problems due to their relation with subgraph isomorphism.
  
  
  RESULTS
  This paper presents an innovative new algorithm for detecting frequently occurring patterns and modules in biological networks. Using an innovative graph simplification technique, which is ideally suited to biological networks, our algorithm renders these problems computationally tractable. Indeed, we show experimentally that our algorithm can extract frequently occurring patterns in metabolic pathways extracted from the KEGG database within seconds. The proposed model and algorithm are applicable to a variety of biological networks either directly or with minor modifications.
  
  
  BACKGROUND
  Implementation of the proposed algorithms in the C programming language is available as open source at http://www.cs.purdue.edu/homes/koyuturk/pathway/
authors.affiliation: Department of Computer Sciences, Purdue University, West Lafayette, IN 47907, USA. koyuturk@cs.purdue.edu
authors.forename: Mehmet
authors.initials: M
authors.lastname: Koyutürk
authors.forename: Ananth
authors.initials: A
authors.lastname: Grama
authors.forename: Wojciech
authors.initials: W
authors.lastname: Szpankowski
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D015870:Gene Expression / Q000502:physiology*; D020869:Gene Expression Profiling / Q000379:methods*; D008954:Models, Biological; D025941:Protein Interaction Mapping / Q000379:methods*; D020543:Proteome / Q000378:metabolism*; D015398:Signal Transduction / Q000502:physiology*; D012984:Software
chemical_list: D020543:Proteome