We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
SIGMA:: A SET-COVER-BASED INEXACT GRAPH MATCHING ALGORITHM.
- Authors
MONGIOVÌ, MISAEL; DI NATALE, RAFFAELE; GIUGNO, ROSALBA; PULVIRENTI, ALFREDO; FERRO, ALFREDO; SHARAN, RODED
- 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.
- Subjects
SET theory; PRUNING; BRANCHING (Botany); PLANT morphology; ALGORITHMS; ISOMORPHISM (Mathematics)
- Publication
Journal of Bioinformatics & Computational Biology, 2010, Vol 8, Issue 2, p199
- ISSN
0219-7200
- Publication type
Article
- DOI
10.1142/S021972001000477X