Application of approximate graph matching techniques for searching databases of two-dimensional chemical structures

This paper proposes the application of approximate graph matching techniques for best-match searching of two-dimensional chemical structure databases based upon topology. Chemical structures are represented as labeled graphs, each atom a node in the graph and each bond an edge. By inserting; deleting and renaming nodes/edges, one structure may be transformed into another. We define similarity as the weighted sum of the costs of these edit operations. An algorithm for approximating the minimum distance between two graphs based on simulated annealing is applied. Best-match searches are performed utilizing this pre-computed distance information and applying the concepts of triangle inequality to prune out structures from the database which could not possibly satisfy the query. We also extend the best-match retrieval by allowing subgraphs of a data graph to be freely removed. The result is a technique which extends existing substructure search techniques by allowing certain distances to exist between the query and a substructure of the data graph