Molecular Similarity. 1. Analytical Description of the Set of Graph Similarity Measures

The elaboration of methods for defining molecular similarity measures is one of the important fields of modern theoretical chemistry. These measures are used for solving a number of problems of theoretical and computer chemistry, in particular the prediction of properties of chemical compounds. For the construction of any molecular similarity measures molecules are represented as some mathematical objects { M }, on which quantitative similarity measures d ( M 1, M 2 ) ( M 1, M 2 ∈ { M }) are introduced. The most widely used way of molecular representation is based on picturing molecules as labeled graphs, labels of which encode types of atoms and bonds. There are many different similarity measures defined for graphs, expressed in terms of vectors of graph invariant, sequences, and sets derived from graphs or in terms of maximal common subgraph, etc. In general, there exists an infinite number of graph similarity measures. In the present paper an analytical description of the set of symmetric similarity measures defined for arbitrary labeled graphs is given. The found general formula for the measure depends on a number of parameters satisfying some conditions. Any particular graph similarity measure may be obtained from this formula at definite values of parameters.