A Method for Measuring Similarity or Distance of Molecular and Arbitrary Graphs Based on a Collection of Topological Indices

Abstract

The comparison of graphs using various types of quantitative structural similarity or distance measures has an important place in many scientific disciplines. Two of these are cheminformatics and chemical graph theory, in which the structural similarity or distance measures between molecular graphs are analyzed by calculating the Jaccard/Tanimoto index based on molecular fingerprints. A novel method is proposed to measure the structural similarity or distance for molecular and arbitrary graphs. This method calculates the Jaccard/Tanimoto index based on a collection of topological indices embedded in the entries of a vector. We statistically compare the proposed method with the method for calculating the Jaccard/Tanimoto indices based on five different molecular fingerprints on alkane and cycloalkane isomers. Furthermore, to explore how the method works on non-molecular graphs, we statistically analyze it on the set of all connected graphs with seven vertices. The Jaccard/Tanimoto index values produced by the proposed method cover the value domain. In addition, it provides a discrete similarity distribution with the clustering, which makes the differences clear and provides convenience for comparison. Two outstanding features of the proposed method are its applicability to arbitrary graphs and the computational complexity of the algorithm used in the method is polynomial over the number of graphs and the number of vertices and edges of the graphs.