SIGMA: a set-cover-based inexact graph matching algorithm.
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.
Mongiovì
Misael
M
Dipartimento di Matematica ed Informatica, Università di Catania, V.le A. Doria, 6, Catania, 95125, Italy. mongiovi@dmi.unict.it
Di Natale
Raffaele
R
Giugno
Rosalba
R
Pulvirenti
Alfredo
A
Ferro
Alfredo
A
Sharan
Roded
R
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
D019380:Anti-HIV Agents; D005656:Fungal Proteins; D046912:Multiprotein Complexes