0.6 Dimensionality reduction methods for molecular motion  (Page 6/13)

which is a typical measure of the error made by approximating the data set using only the first $d$ principal components.

The above derivation can be written as an algorithm fairly easily.

Pca algorithm

• Let the input data consist of n observations $x_i$ , each of dimensionality M. Construct an nxM matrix $X$ of centered observations by subtracting the data mean from each point, so that
• Construct the covariance matrix $C=X{X}^T$
• Compute the top $d$ eigenvalues and corresponding eigenvectors of $C$ , for example by performing an SVD of $C$ .
• The first $d$ Principal Components (PCs) of the data are given by the eigenvectors, which can be placed in a $d$ xM matrix $P$ . The residual variance can be computed from the eigenvalues as explained above.
• To project the original (centered) points into the optimal $d$ -dimensional hyperplane, compute the dot product of each point with the PCs to obtain the projections $y_i$ . This can be written as $Y=P^{T}X$ .

PCA is very well established as a dimensionality reduction technique and efficient algorithms with guaranteed convergence for its computation are readily available. Software packages that perform SVD and PCA are freely available and trivial to use. For example Matlab has built-in commands for both, and moderately experienced C and Fortran programmers can use the popular and extremely-efficient LAPACK linear algebra package. The concepts explained in this section have not assumed any particular number of dimensions. Even though a 3D example was given at the beginning, the concepts can be lifted to deal with spaces of arbitrary dimensionality, where the input data set can have a large dimension M. PCA has the advantage over other available methods that the principal components have a direct physical interpretation, especially when working with molecular motion data.

Pca of conformational data

In structural bioinformatics we want to apply PCA to a set of molecular conformations, which will serve as our high-dimensional points. The input dimensionality of each point is 3N, where N is the number of atoms in the molecule. We will have n such conformations, that have been gathered through some form of sampling (for example through molecular dynamics simulations), and we want to reduce the dimensionality of each "point" (conformation) for analysis purposes. The data used as input for PCA is in the form of several atomic position vectors corresponding to different structural conformations which together constitute a vector set. Each vector in the conformational vector set has dimension 3N and is of the form [ $x_1$ , $y_1$ , $z_1$ , $x_2$ , $y_2$ , $z_2$ ,..., $x_N$ , $y_N$ , $z_N$ ],where [ $x_{\mathrm{i}}$ , $y_{\mathrm{i}}$ , $z_{\mathrm{i}}$ ] corresponds to the Cartesian coordinates of the $i^{\mathrm{th}}$ atom.

However, before running the PCA procedure outlined above, all conformations need to be aligned with a reference structure first, as discussed in the module Molecular Distance Measures . The reason why alignment is important is that most simulation packages model the exchange of heat between the molecule and a thermal bath, in the form of random velocity perturbations on the atoms. These perturbations will in general add non-zero linear and angular momenta to the molecule structure, and not all simulation packages remove them. As a result, molecular conformations that are almost identical in shape but translated/rotated with respect to each other will have significantly different coordinates, and will be considered as different 3N-dimensional points. The reference structure (to which all structures should be aligned to) can be chosen from the set (e.g., the native structure) or provided from outside the set. Results may vary a little, but aligning all conformations to the same reference structure yields comparable results in general.