A set-cover-based approach for inexact graph matching

M. Mongiovi*, R. Di Natale, R. Guigno, A. Pulvirenti, A. Ferro, R. Sharan

Dipartimento di Matematica ed Informatica, Universita di Catania, Catania, 95125, Italy. mongiovi@dmi.unict.it

Proc LSS Comput Syst Bioinform Conf. August, 2009. Vol. 8, p. 81-90. Full-Text PDF

*To whom correspondence should be addressed.

Network querying is a growing domain with vast applications ranging from screening compounds against a database of known molecules to matching subnetworks across species. Graph indexing is a powerful method for searching for queries in 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 new variant of the set-cover problem that concerns overlapping multi-sets. We extensively test our method and compare it to a layman approach and to the state-of-the-art Grafil. We show that SIGMA outperforms both, providing higher pruning power in all the tested scenarios.