An Ant Algorithm for the Conformational Analysis of Flexible Molecules

Originally, the ant system was developed for optimization in discrete search spaces such as the traveling salesman problem. The ant algorithm was adapted to apply it to the problem of conformational analysis of flexible molecules. For molecules containing more than ~6 rotatable bonds, the number of low energy conformations becomes very large, and their exhaustive enumeration unpractical. For such molecules, flexible docking and alignment algorithms have been developed. In these algorithms, the score to be optimized is bi-functional: on the one hand, the molecules must be docked or aligned; on the other hand, the conformational strain must be kept low. In order to calculate the conformational strain, the energy of the lowest energy conformation must be known. We developed the 'ant' algorithm to determine this lowest energy.
Reprints of this paper can be requested at info@molmo.be

The ant algorithm is inspired by the behaviour of real ants. Despite being almost blind, ants manage to find the shortest path from their nest to sources of food in an environment strewn with, for a creature the size of an ant, gigantic obstacles. It was found by ethologists that ants communicate by leaving a chemical trail of pheromone on their errants. An initially randomly traveling ant that encounters a pheromone trail, will either follow this trail or continue its random search for food. The stronger the pheromone trail, the higher the probability that the ant will follow it. If the trail encountered is a short route to a food source, more ants will have followed it and the pheromone level will be high. Through this simple positive feed-back mechanism, succesfull trails soon become highly populated.