Bioinformatics Advance Access originally published online on November 16, 2006
Bioinformatics 2007 23(2):232-239; doi:10.1093/bioinformatics/btl571
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
SAGA: a subgraph matching tool for biological graphs
1 Department of Electrical Engineering and Computer Science, University of Michigan Ann Arbor, MI 48109, USA
2 National Center for Integrative Biomedical Informatics, University of Michigan Ann Arbor, MI 48109, USA
3 Department of Human Genetics and Bioinformatics Program, University of Michigan Ann Arbor, MI 48109, USA
*To whom correspondence should be addressed.
 |
Abstract |
|---|
Motivation: With the rapid increase in the availability of biological graph datasets, there is a growing need for effective and efficient graph querying methods. Due to the noisy and incomplete characteristics of these datasets, exact graph matching methods have limited use and approximate graph matching methods are required. Unfortunately, existing graph matching methods are too restrictive as they only allow exact or near exact graph matching. This paper presents a novel approximate graph matching technique called SAGA. This technique employs a flexible model for computing graph similarity, which allows for node gaps, node mismatches and graph structural differences. SAGA employs an indexing technique that allows it to efficiently evaluate queries even against large graph datasets.
Results: SAGA has been used to query biological pathways and literature datasets, which has revealed interesting similarities between distinct pathways that cannot be found by existing methods. These matches associate seemingly unrelated biological processes, connect studies in different sub-areas of biomedical research and thus pose hypotheses for new discoveries. SAGA is also orders of magnitude faster than existing methods.
Availability: SAGA can be accessed freely via the web at http://www.eecs.umich.edu/saga. Binaries are also freely available at this website.
Contact: jignesh{at}eecs.umich.edu
Supplementary material: Supplementary material is available at http://www.eecs.umich.edu/periscope/publ/saga-suppl.pdf.
Associate Editor: Martin Bishop
Received on August 22, 2006; revised on November 7, 2006; accepted on November 8, 2006
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  J. Gao, A. S. Ade, V. G. Tarcea, T. E. Weymouth, B. R. Mirel, H.V. Jagadish, and D. J. States Integrating and annotating the interactome using the MiMI plugin for cytoscape Bioinformatics, January 1, 2009; 25(1): 137 - 138. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 V. G. Tarcea, T. Weymouth, A. Ade, A. Bookvich, J. Gao, V. Mahavisno, Z. Wright, A. Chapman, M. Jayapandian, A. Ozgur, et al. Michigan molecular interactions r2: from interacting proteins to pathways Nucleic Acids Res., January 1, 2009; 37(suppl_1): D642 - D646. [Abstract] [Full Text] [PDF]
|
|