Kabsch algorithm

The Kabsch algorithm is a method for calculating the optimal alignment of two sets of points. It is useful in graphics, and also in Bioinformatics for calculating the RMSD (root mean squared deviation) of two proteins.

The algorithm works by calculating a matrix of multiplied components. The destination matrix, A, is a 3x3 matrix with x, y and z components for each side. The source is two sets of paired points, V1 and V2.

A_ij = Σ V1_iV2_j

(Sum over the points and multiply components).

The formula is

(A^t A)^1/2 A^-1

Or the transpose of A multiplied by A, and take the square root. Then multiply by the inverse of A.

The algorithm calaculatres only the rotation matix. You must transform both sets of coordinates to their centroid first.

C source is available at http://www.personal.leeds.ac.uk/~bgy1mm/Bioinformatics/rmsd.html

References Kabsch, Wolfgang, (1976) A solution of the best rotation to relate two sets of vectors Acta Crystallographica 32:922 Lin Ying-Hung, Chang Hsun-Chang, Lin Yaw-Ling (2004) A Study on Tools and Algorithms for 3-D Protein Structures Alignment and Comparison International Computer Symposium, Dec 15-17, Taipei, Taiwan