An efficient algorithm for detecting frequent subgraphs in biological networks.
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/
Koyutürk
Mehmet
M
Department of Computer Sciences, Purdue University, West Lafayette, IN 47907, USA. koyuturk@cs.purdue.edu
Grama
Ananth
A
Szpankowski
Wojciech
W
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
D020543:Proteome