Abstract

Screening a library of molecular graphs for an exact or approximate match with one particular molecular graph, the query graph, is reduced to list comparisons. The lists contain lengths of shortest paths ingraph Voronoi regions. This induces the notion of shortest path similarity. All graphs that are shortest path similar to the query graph are efficiently retrievable. The same applies to approximate or similarity matching. For the retrieval of all superstructures of a query, shortest path lists are modified to distance patterns. This alsoallows algorithmic support for query construction.

Keywords: graph voronoi regions, isomorphism, retrieval, screening