MATCHING 2-DIMENSIONAL CHEMICAL GRAPHS USING GENETIC ALGORITHMS

This paper describes the application of a genetic algorithm (GA) in the field of 2-D chemical structure handling. A GA is an algorithm based on the process of Darwinian Evolution, whereby potential solutions to a problem are manipulated according to the mechanics of natural selection. A graph-matching GA has been developed for substructure searching of 2-D chemical databases. A variant of the GA has been used to generate hyperstructures, where a hyperstructure is a novel method of representation for 2-D chemical structures. Both GAs were extensively tested. The GA for substructure search was shown to be considerably less effective than conventional search methods, while the hyperstructure-generation algorithm was found to be highly successful.