Jiaya Zhou
M.Sc. Candidate
Co-supervisors: Dr. Edward Brown and Dr. Sharene Bungay

A robust algorithm to compare chemical structures

Department of Computer Science
Thursday, September 18, 2014, 1:00 pm, Room EN 2022

---

 

Abstract

The recognition of chemical similarities between molecules plays an important role in chemical science, especially in the state-of-the-art subjects of chemistry, biology and pharmaceutics. Traditional methods of structure recognition are time consuming, usually involving a lot of experimentation and computational effort. The goal of the research is to create an algorithm to compare two chemical structures automatically with basic information. The algorithm only requires atom Cartesian coordinates, atom types and connectivity information of the structures as input. It uses a novel method to pair the atoms in the two structures such that the best superimposition is achieved. A similarity score is computed based on this best superimposition.

The algorithm can also be used to search a large set of molecules for a structure similar to a query molecule. An application is developed to display the two structures to be compared and provide a 3D image of their best superimposition based on the auto-pairing of the atoms. Run-time analysis of the algorithm reveals that the traditional time complexity does not describe the run-time of the algorithm well. Linear regression indicates that the run-time is strongly influenced by the number of triplets (consisting of 3 atoms joined by 2 bonds) matched between the two structures. Testing of the algorithm on an in-house data set of 737 structures as well as a larger NCI-sourced database demonstrates its utility.