title: SIGMA: a set-cover-based inexact graph matching algorithm.
abstract: 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.
authors.affiliation: Dipartimento di Matematica ed Informatica, Università di Catania, V.le A. Doria, 6, Catania, 95125, Italy. mongiovi@dmi.unict.it
authors.forename: Misael
authors.initials: M
authors.lastname: Mongiovì
authors.forename: Raffaele
authors.initials: R
authors.lastname: Di Natale
authors.forename: Rosalba
authors.initials: R
authors.lastname: Giugno
authors.forename: Alfredo
authors.initials: A
authors.lastname: Pulvirenti
authors.forename: Alfredo
authors.initials: A
authors.lastname: Ferro
authors.forename: Roded
authors.initials: R
authors.lastname: Sharan
mesh_terms: D000465:Algorithms; D019380:Anti-HIV Agents / Q000737:chemistry; D019295:Computational Biology / Q000379:methods*; D003196:Computer Graphics; D016208:Databases, Factual; D030562:Databases, Protein; D005656:Fungal Proteins / Q000737:chemistry; D006801:Humans; D015394:Molecular Structure; D046912:Multiprotein Complexes; D010363:Pattern Recognition, Automated / Q000379:methods; D025941:Protein Interaction Mapping
chemical_list: D019380:Anti-HIV Agents; D005656:Fungal Proteins; D046912:Multiprotein Complexes