Back to search

NJIT

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

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Master of Science in Computer Science - (M.S.)
Discipline thesis:degree_discipline
Computer and Information Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pysniak, Karen R.
Contributors dc:contributor
  • Jason T. L. Wang
  • James A. McHugh
  • Peter A. Ng

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.njit.edu/theses/1199

Chain of custody

source
Harvested from
NJIT
Base URL
digitalcommons.njit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pysniak, Karen R.. Application of approximate graph matching techniques for searching databases of two-dimensional chemical structures. https://digitalcommons.njit.edu/theses/1199