{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T16:23:56Z","timestamp":1779294236271,"version":"3.51.4"},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p><jats:p>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.<\/jats:p><jats:p>Availability: SAGA can be accessed freely via the web at . Binaries are also freely available at this website.<\/jats:p><jats:p>Contact: \u00a0jignesh@eecs.umich.edu<\/jats:p><jats:p>Supplementary material: Supplementary material is available at .<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl571","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T01:17:37Z","timestamp":1163726257000},"page":"232-239","source":"Crossref","is-referenced-by-count":189,"title":["SAGA: a subgraph matching tool for biological graphs"],"prefix":"10.1093","volume":"23","author":[{"given":"Yuanyuan","family":"Tian","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, University of Michigan 1 \u00a0 1 \u00a0 \u00a0 Ann Arbor, MI 48109, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard C.","family":"McEachin","sequence":"additional","affiliation":[{"name":"National Center for Integrative Biomedical Informatics, University of Michigan 2 \u00a0 2 \u00a0 \u00a0 Ann Arbor, MI 48109, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Santos","sequence":"additional","affiliation":[{"name":"Department of Human Genetics and Bioinformatics Program, University of Michigan 3 \u00a0 3 \u00a0 \u00a0 Ann Arbor, MI 48109, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David J.","family":"States","sequence":"additional","affiliation":[{"name":"Department of Human Genetics and Bioinformatics Program, University of Michigan 3 \u00a0 3 \u00a0 \u00a0 Ann Arbor, MI 48109, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jignesh M.","family":"Patel","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, University of Michigan 1 \u00a0 1 \u00a0 \u00a0 Ann Arbor, MI 48109, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2006,11,16]]},"reference":[{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","article-title":"Algorithm 457: finding all cliques of an undirected graph","volume":"16","author":"Bron","year":"1973","journal-title":"CACM"},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"1237","DOI":"10.1192\/bjp.113.504.1237","article-title":"The biochemistry of affective disorders","volume":"113","author":"Coppen","year":"1967","journal-title":"Br. J. Psychiatr."},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"241","DOI":"10.2165\/00822942-200403040-00006","article-title":"PathAligner: metabolic pathway retrieval and alignment","volume":"3","author":"Chen","year":"2004","journal-title":"Appl. Bioinformatics"},{"key":"2023041107035402300_","first-page":"38","article-title":"Closure-tree: an index structure for graph queries","author":"He","year":"2006"},{"key":"2023041107035402300_","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"Hochbaum","year":"1997"},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"D428","DOI":"10.1093\/nar\/gki072","article-title":"Reactome: a knowledgebase of biological pathways","volume":"33","author":"Joshi-Tope","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1016\/S0962-8924(02)02388-7","article-title":"Similarities between the hedgehog and wnt signaling pathways","volume":"12","author":"Kalderon","year":"2002","journal-title":"Trends Cell Biol."},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"D354","DOI":"10.1093\/nar\/gkj102","article-title":"From genomics to chemical genomics: new developments in KEGG","volume":"34","author":"Kanehisa","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"W83","DOI":"10.1093\/nar\/gkh411","article-title":"Pathblast: a tool for alignment of protein interaction networks","volume":"32","author":"Kelley","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023041107035402300_","first-page":"48","article-title":"Pairwise local alignment of protein interaction networks guided by models of evolution","author":"Koyuturk","year":"2005"},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1053\/jhep.2003.50136","article-title":"p18(INK4c) collaborates with other CDK-inhibitory proteins in the regenerating liver","volume":"37","author":"Luedde","year":"2003","journal-title":"Hepatology"},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"5297","DOI":"10.1242\/dev.00821","article-title":"Wnts and hedgehogs: lipid-modified proteins and similarities in signaling mechanisms at the cell surface","volume":"130","author":"Nusse","year":"2003","journal-title":"Development"},{"key":"2023041107035402300_","volume-title":"Introduction to Modern Information Retrieval","author":"Salton","year":"1983"},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"1974","DOI":"10.1073\/pnas.0409522102","article-title":"Conserved patterns of protein interaction in multiple species","volume":"102","author":"Sharan","year":"2005","journal-title":"Proc. Natl Acad Sci. USA"},{"key":"2023041107035402300_","first-page":"39","article-title":"Algorithmics and applications of tree and graph searching","author":"Shasha","year":"2002"},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1126\/science.278.5338.631","article-title":"A genomic perspective on protein families","volume":"278","author":"Tatusov","year":"1997","journal-title":"Science"},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"6283","DOI":"10.1093\/nar\/gkg838","article-title":"Functional modules by relating protein interaction networks and gene expression","volume":"31","author":"Tornow","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023041107035402300_","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S1074-7613(02)00364-3","article-title":"CDK inhibitor p18INK4c is required for the generation of functional plasma cells","volume":"17","author":"Tourigny","year":"2002","journal-title":"Immunity"},{"key":"2023041107035402300_","first-page":"335","article-title":"Graph indexing: a frequent structure-based approach","author":"Yan","year":"2004"},{"key":"2023041107035402300_","first-page":"766","article-title":"Substructure similarity search in graph databases","author":"Yan","year":"2005"},{"key":"2023041107035402300_","first-page":"88","article-title":"Searching substructures with superimposed distance","author":"Yan","year":"2006"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/232\/49820321\/bioinformatics_23_2_232.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/232\/49820321\/bioinformatics_23_2_232.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,8]],"date-time":"2024-02-08T09:31:29Z","timestamp":1707384689000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/2\/232\/205026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11,16]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl571","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,1,15]]},"published":{"date-parts":[[2006,11,16]]}}}