Overview

SAGA stands for Substructure Index-based Approximate Graph Alignment. It is an efficient tool for approximate subgraph matching. SAGA allows users to match a query graph against a large database of graphs. At the core of SAGA is a flexible graph distance model that incorporates node approximate matching as well as approximate structure matching. A powerful indexing method is implemented to speed up the matching process. Some applications of SAGA include querying/comparing pathways and querying parsed biomedical literature databases to find similar documents.

This web page currently provides access to two applications of SAGA:

  1. Application of SAGA for Matching Biological Pathways (querying a pathway against the KEGG pathway database)
  2. Application of SAGA for Matching Parsed Biological Literature (querying a PubMed document against other PubMed documents)

People

Collaborators:

Publications

Journal Paper

SAGA: A Subgraph Matching Tool for Biological Graphs [PDF] [Supplemental Material]
Yuanyuan Tian, Richard C. McEachin, Carlos Santos, David J. States, Jignesh M. Patel
Bioinformatics Journal, 23(2):232-239, 2007.

Poster

SAGA: A Subgraph Matching Tool for Biological Graphs [Poster Abstract] [Poster]
Yuanyuan Tian, Richard C. McEachin, Carlos Santos, David J. States, Jignesh M. Patel
International Conference on Research in Computational Molecular Biology (RECOMB), 2007.

Funding

This research was primarily supported by the National Institutes of Health under grant 1-U54-DA021519-01A1. Additional funding for this work was provided by a research gift donation from Microsoft.

Contacts

Jignesh M. Patel
email: jignesh AT eecs DOT umich DOT edu
4717 CSE
2260 Hayward
University of Michigan
Ann Arbor, MI 48109-2121

Yuanyuan Tian
email: ytian AT eecs DOT umich DOT edu
4945 CSE
2260 Hayward
University of Michigan
Ann Arbor, MI 48109-2121

Visitor since Nov 3, 2006