The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Application of approximate graph matching techniques for searching databases of two-dimensional chemical structures
Author:	Pysniak, Karen R.
View Online:	njit-etd1995-104 (ix, 84 pages ~ 1.9 MB pdf)
Department:	Department of Computer and Information Science
Degree:	Master of Science
Program:	Computer Science
Document Type:	Thesis
Advisory Committee:	Wang, Jason T. L. (Committee chair) McHugh, James A. (Committee member) Ng, Peter A. (Committee member)
Date:	1995-10
Keywords:	Chemical structure--Data processing. Information retrieval. Pattern recognition systems.
Availability:	Unrestricted
Abstract:	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.