Top-k Similar Graph Matching Using TraM in Biological Networks

Many emerging database applications entail sophisticated graph-based query manipulation, predominantly evident in large-scale scientific applications. To access the information embedded in graphs, efficient graph matching tools and algorithms have become of prime importance. Although the prohibitive...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on computational biology and bioinformatics 2012-11, Vol.9 (6), p.1790-1804
Main Authors: Amin, M. S., Finley, R. L., Jamil, H. M.
Format: Article
Language:English
Subjects:
Algorithms
Animals
Approximation
Bioinformatics
biology and genetics
Computation
Computational biology
Computational Biology - methods
Data Mining - methods
Databases, Factual
Diseases
Drosophila
Genetics
graph and tree search strategies
Graph matching
Graphics
Graphs
Graphs and networks
Humans
knowledge and data engineering tools and techniques
Protein Interaction Maps
Proteins
Query processing
Reproducibility of Results
Searching
Studies
Trams
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many emerging database applications entail sophisticated graph-based query manipulation, predominantly evident in large-scale scientific applications. To access the information embedded in graphs, efficient graph matching tools and algorithms have become of prime importance. Although the prohibitively expensive time complexity associated with exact subgraph isomorphism techniques has limited its efficacy in the application domain, approximate yet efficient graph matching techniques have received much attention due to their pragmatic applicability. Since public domain databases are noisy and incomplete in nature, inexact graph matching techniques have proven to be more promising in terms of inferring knowledge from numerous structural data repositories. In this paper, we propose a novel technique called TraM for approximate graph matching that off-loads a significant amount of its processing on to the database making the approach viable for large graphs. Moreover, the vector space embedding of the graphs and efficient filtration of the search space enables computation of approximate graph similarity at a throw-away cost. We annotate nodes of the query graphs by means of their global topological properties and compare them with neighborhood biased segments of the data-graph for proper matches. We have conducted experiments on several real data sets, and have demonstrated the effectiveness and efficiency of the proposed method.
ISSN:1545-5963
1557-9964
DOI:10.1109/TCBB.2012.90