The Rigid-Body Transformation Problem

Before one attempts to classify protein structures, it is important to evaluate structure similarities. Many ways exist in which protein structures can be compared, that will be reviewed below. Most of these approaches proceed in two steps (1) find the transformation that provides the optimal superposition between the two structures, and (2) define the similarity score as the distance between the two structures after superposition. This section describes how to obtain the optimal transformation for step (1). 

We begin with the (relatively) easy problem of comparing two protein structures with the same number of atoms and a known correspondence table between these atoms (for a review, see Ref. 84). This problem is often solved when comparing two possible models for the structure of a protein. Because it is such a common problem, and because there still exists some confusion about 

3Dee http //www.compbio.dundee.ac.uk/3Dee DOMAK 

Authors http //www.bmm.icnet.uk/ domains/test/ Domains identified 

DALI http //www.ebi.ac.Uk/dali/domain/3.lbeta DALI Domain Definition 

---

The two subsets A(P) and B(Q) define a correspondence, and p = IA(P)I = IB(Q)I is called the correspondence length. Once the optimal correspondence is defined, it is easy to find the optimal rotation and translation using the rigid-body transformation algorithm described earlier. The concept of optimal correspondence, however, requires more explanation. It is clear that p = l defines a trivial solution to the protein superposition problem Any point of A can be aligned with any point of B, with a cRMS of 0. In practice, we are interested in finding the largest possible value for p under the condition that A(P) and B Q) remain similar. ... 

The problem of comparing two different models of a protein can be formalized as given two sets of points A = ui, az, , an) and B = (bi,bx,. .. b ) in three dimensional space and assuming that they have the same cardinality, i.e., n = m, and that the element a, corresponds to the element b, find the optimal rigid body transformation Gopt between the two sets that minimizes a given distance metric D over all possible rigid body transformation G, as in Eq. [1] ... 

Equation [3] states that distances are conserved, whereas Eq. [4] says that internal reflection is not allowed. Rotations and translations are two examples of rigid body transformation, and in fact, a general rigid body transformation can be expressed as a combination of a rotation R and a translation T. The transformation problem can then be restated as finding the optimal rotation R and optimal translation Tsuch that A — RB — T is a minimum. 

---