(Review Article) Scalable Distance Similarity of Chemical Structures
Thomas Kämpke · Combinatorial Chemistry & High Throughput Screening · 2004
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 in graph 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 also allows algorithmic support for query construction.