Protein structure comparisons using a combination of a genetic algorithm, dynamic programming and least-squares minimization

Abstract

We introduce a completely automatic and objective procedure for the comparison of protein structures. A genetic algorithm is used to search for a near optimal solution of the rigid-body superposition of two whole protein structures. The specification of an initial set of equivalences is not required. Topological equivalences in the final structural alignment are defined by a conventional dynamic programming routine, which is commonly used to compare protein sequences. A least-squares fitting algorithm is then used to optimize the fit between the final set of equivalences. We have applied our method to the comparison of ribonucleic acid structures, as well as protein structures. The structural alignments are generally consistent with those previously published. In fact, on most occasions our method defines at least the same number of topological equivalences as other procedures, but always with a lower r.m.s. distance between them.