Fast rotational matching of rigid bodies by fast Fourier transform acceleration of five degrees of freedom

The 'fast rotational matching' method (an approach to find the three rotational degrees of freedom in matching problems using just one three-dimensional FFT) is extended to the full six-dimensional (rotation and translation) matching scenario between two three-dimensional objects. By recasting this problem into a formulation involving five angles and just one translational parameter, it was possible to accelerate, by means of fast Fourier transforms, five of the six degrees of freedom of the problem. This method was successfully applied to the docking of atomic structures of components into three-dimensional low-resolution density maps. Timing comparisons performed with our method and with 'fast translational matching' (the standard way to accelerate the translational parameters utilizing fast Fourier transforms) demonstrates that the performance gain can reach several orders of magnitude, especially for large map sizes. This gain can be particularly advantageous for spherical-and toroidal-shaped maps, since the scanning range of the translational parameter would be significantly constrained in these cases. The method can also be harnessed to the complementary surface (or 'exterior docking') problem and to pattern recognition in image processing.