0.4 Molecular distance measures  (Page 2/6)

Finding the optimal rotation to minimize the RMSD between two point sets is a well-studied problem, and several algorithms exist. The Kabsch Algorithm [1] [2] , which is implemented in several molecular modeling packages, solves a matrix equation for the three dimensional rotation matrix corresponding to the optimal rotation. An alternative approach, discussed in detail after the matrix method, uses a compact representation of rotational transformations called quaternions [3] [4] . Quaternions are currently the preferred representation for global rotation in calculating lRMSD, since they require less numbers to be stored and are easy to re-normalize. In contrast, re-normalization of orthonormal matrices is quite expensive and potentially numerically unstable. Both quaternions and their application to global alignment of conformations will be presented after the next section.

Optimal alignment for lrmsd using rotation matrices

This section presents a method for computing the optimal rotation between 2 datasets as an orthonormal rotation matrix. As stated earlier,this approach is slightly more numerically unstable (since guaranteeing the orthonormality of a matrix is harder than the unit length of aquaternion) and requires taking care of the special case when the resulting matrix may not be a proper rotation, as discussed below.

As stated earlier, the optimal alignment requires both a translation and a rotation. The translational part of the alignment is easy to calculate. It can be proven that the optimal alignment is obtained by translating one set so that its centroid coincides with the other set's centroid (see section 2-C of [3] for proof). The centroid of a point set a is simply the average position of all its points:

One of the first references to the solution of this problem in matrix form is from Kabsch [1] [2] . The Kabsch method uses Lagrange multipliers to solve a minimization problem to find the optimal rotation. Here, we present a slightly more intuitive method based on matrix algebra and properties, that achieves the same result. This formulation can be found in [4] and [5] . Imagine we wish to align two conformations composed of N atoms each, whose Cartesian coordinates are given by the vectors $x$ and $y$ . The main idea behind this approach is to find a 3x3 orthonormal matrix $U$ such that the application of $U$ to the atom positions of one of the data vectors, $x$ , aligns it as best as possible with the other data vector, $y$ , in the sense that the quantity to minimize is the distance $\mathrm{d(Ux,y)}$ , where $x$ and $y$ are assumed to be centered , that is, both their centroids coincide at the origin (centering both conformations is the first step). Mathematically, this problem can be stated as the minimization of the following quantity: