Common subgraph isomorphism detection by backtracking search

Graph theory offers a convenient and highly attractive approach to various tasks of pattern recognition. Provided there is a graph representation of the object in question (e.g. a chemical structure or protein fold), the recognition procedure is reduced to the problem of common subgraph isomorphism...

Full description

Saved in:
Bibliographic Details
Published in:Software, practice & experience practice & experience, 2004-05, Vol.34 (6), p.591-607
Main Authors: Krissinel, Evgeny B., Henrick, Kim
Format: Article
Language:English
Subjects:
backtracking algorithm
common subgraphs
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:Graph theory offers a convenient and highly attractive approach to various tasks of pattern recognition. Provided there is a graph representation of the object in question (e.g. a chemical structure or protein fold), the recognition procedure is reduced to the problem of common subgraph isomorphism (CSI). Complexity of this problem shows combinatorial dependence on the size of input graphs, which in many practical cases makes the approach computationally intractable. Among the optimal algorithms for CSI, the leading place in practice belongs to algorithms based on maximal clique detection in the association graph. Backtracking algorithms for CSI, first developed two decades ago, are rarely used. We propose an improved backtracking algorithm for CSI, which differs from its predecessors by better search strategy and is therefore more efficient. We found that the new algorithm outperforms the traditional maximal clique approach by orders of magnitude in computational time. Copyright © 2004 John Wiley & Sons, Ltd.
ISSN:0038-0644
1097-024X
DOI:10.1002/spe.588