Comparison of protein surfaces using a genetic algorithm

A genetic algorithm (GA) is described which is used to compare the solvent-accessible surfaces of two proteins or fragments of proteins, represented by a dot surface calculated using the Connolly algorithm. The GA is used to move one surface relative to the other to locate the most similar surface region between the two. The matching process is enhanced by the use of the surface normals and shape terms provided by the Connolly program and also by a simple hydrogen-bonding descriptor and an additional shape descriptor. The algorithm has been tested in applications ranging from the comparison of small surface patches to the comparison of whole protein surfaces, and it has performed correctly in all cases. Examples of the matches are given and a quantitative analysis of the quality of the matches is performed. A number of possible future enhancements to the program are described which would allow the GA to be used for more complex surface comparisons.