Molecular structure matching by simulated annealing. I. A comparison between different cooling schedules

Summary This paper outlines an application of the theory of simulated annealing to molecular matching problems. Three cooling schedules are examined: linear, exponential and dynamic cooling. The objective function is the sum of the elements of the difference distance matrix between the two molecules generated by continual reordering of one molecule. Extensive tests of the algorithms have been performed on random coordinate data together with two related protein structures. Combinatorial problems, inherent in the assignment of atom correspondences, are effectively overcome by simulated annealing. The algorithms outlined here can readily optimize molecular matching problems with 150 atoms.