Exact solution for minimization of root mean square deviation with G-RMSD to determine molecular similarity

Abstract Generalized root mean square deviation (G-RMSD) is an optimization method for three-dimensional molecular similarity determination. It calculates the minimum value of RMSD among all the possible one-to-one matchings between the atoms and positions of the molecules. The first paper on G-RMSD introduced two approaches called alternating optimization (AO) and tangent space relaxation (TSR) methods, which give local optimum solutions. We propose here a new method of G-RMSD using a branch-and-bound method (BnB) on isometric transformations, called IsometryOpt, which is mathematically proven to give an exact G-RMSD index, i.e. this method can reach the global optimum solution. The performance of IsometryOpt was compared to AO and TSR, as well as the MatchFastOpt method. IsometryOpt shows better performance than MatchFastOpt for molecules with the same number of atoms. AO and TSR fail to reach exact values in some cases. We also have developed two improved methods to search for all possible matches of a substructure in one or more molecules. One is called IsometrySearch, which uses BnB on isometric transformations. The other is a variant version of MatchFPT, called MatchFPT-delta. Computer experiments indicate that MatchFPT-delta performs better than MatchFPT and IsometrySearch.