Bioinformatics 20(Suppl. 1) © Oxford University Press 2004; all rights reserved.
An efficient algorithm for detecting frequent subgraphs in biological networks
Department of Computer Sciences, Purdue University, West Lafayette, IN 47907, USA
Received on January 15, 2004; accepted on March 1, 2004
Motivation: 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.
Availability: Implementation of the proposed algorithms in the C programming language is available as open source at http://www.cs.purdue.edu/homes/koyuturk/pathway/
Contact: koyuturk{at}cs.purdue.edu
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  R. Y. Pinter, O. Rokhlenko, E. Yeger-Lotem, and M. Ziv-Ukelson Alignment of metabolic pathways Bioinformatics, August 15, 2005; 21(16): 3401 - 3408. [Abstract] [Full Text] [PDF]
|
|