SIMILARITY COMPARISON OF CHEMICAL STRUCTURES BY 2D-GRAPH ISOMORPHISM ALGORITHMS

Abstract

It is often desired in many applications to be able to compare objects represented as graphs and to determine their graph to graph similarity. A usual approach is to apply Maximum Common Subgraph (MCS) to the graphs being compared. However in this project, a new and more effective algorithm based on edge induced formulation of MCS is presented. The proposed inexact graph matching method RASCAL (RApid Similarity CALculation) consists of two components and they are screening and rigorous graph matching.

The methodology would be using Visual Basic Programming Language to write an algorithm for RASCAL and the coding involves finding the values of V(G1), V(G2), E(G1), E(G2), V(G1G2) and E(G1G2) from the txt files of the chemical database.

The result of this project was satisfactory with the completion of the GUI and the algorithm until 1st Tier. The algorithm is relatively quite accurate. The molecular structures of those compounds generated under the “Output” section were quite similar to the reference compound. The algorithm was also speedy in generating results which is one of the advantages of RASCAL.

In conclusion, it was a relatively successful project but more improvements can be made like adding more compounds into the database or adding