{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T04:08:53Z","timestamp":1759205333717},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p> Network querying is a growing domain with vast applications ranging from screening compounds against a database of known molecules to matching sub-networks across species. Graph indexing is a powerful method for searching a large database of graphs. Most graph indexing methods to date tackle the exact matching (isomorphism) problem, limiting their applicability to specific instances in which such matches exist. Here we provide a novel graph indexing method to cope with the more general, inexact matching problem. Our method, SIGMA, builds on approximating a variant of the set-cover problem that concerns overlapping multi-sets. We extensively test our method and compare it to a baseline method and to the state-of-the-art Grafil. We show that SIGMA outperforms both, providing higher pruning power in all the tested scenarios. <\/jats:p>","DOI":"10.1142\/s021972001000477x","type":"journal-article","created":{"date-parts":[[2010,4,16]],"date-time":"2010-04-16T08:05:38Z","timestamp":1271405138000},"page":"199-218","source":"Crossref","is-referenced-by-count":57,"title":["SIGMA: A SET-COVER-BASED INEXACT GRAPH MATCHING ALGORITHM"],"prefix":"10.1142","volume":"08","author":[{"given":"MISAEL","family":"MONGIOV\u00cc","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica ed Informatica, Universit\u00e0 di Catania, V.le A. Doria, 6, Catania, 95125, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RAFFAELE","family":"DI NATALE","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica ed Informatica, Universit\u00e0 di Catania, V.le A. Doria, 6, Catania, 95125, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ROSALBA","family":"GIUGNO","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica ed Informatica, Universit\u00e0 di Catania, V.le A. Doria, 6, Catania, 95125, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALFREDO","family":"PULVIRENTI","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica ed Informatica, Universit\u00e0 di Catania, V.le A. Doria, 6, Catania, 95125, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALFREDO","family":"FERRO","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica ed Informatica, Universit\u00e0 di Catania, V.le A. Doria, 6, Catania, 95125, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RODED","family":"SHARAN","sequence":"additional","affiliation":[{"name":"Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf6","volume":"9","author":"Ferro A.","journal-title":"BMC Bioinformatics"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114248"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"rf11","first-page":"309","volume":"62","author":"Bijl D.","journal-title":"The Netherlands Journal of Medicine"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl571"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkp474"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2007.0172"},{"key":"rf17","first-page":"85","author":"Karp R. M.","journal-title":"Complexity of Computer Computations"},{"key":"rf18","first-page":"256","author":"Johnson D. S.","journal-title":"J. Comput. System. Sci."},{"key":"rf22","volume":"36","author":"Ruepp A.","journal-title":"Nucleic. Acids. Res."},{"key":"rf24","volume":"34","author":"Stark C.","journal-title":"Nucleic. Acids. Res."}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021972001000477X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:42:31Z","timestamp":1565145751000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021972001000477X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":11,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1142\/S021972001000477X"],"URL":"https:\/\/doi.org\/10.1142\/s021972001000477x","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4]]}}}