Tables for
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2006). Vol. B, ch. 3.3, pp. 360-384   | 1 | 2 |

Chapter 3.3. Molecular modelling and graphics

R. Diamonda*

aMRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England
Correspondence e-mail:

This chapter is in three parts. The first of these (Section 3.3.1[link]) addresses many aspects of computer graphics relevant to both vector and raster machines and includes a discussion of coordinate transformations, including some of the many forms of orthogonal transformations that may arise, superpositions, projective geometry using homogeneous coordinates, perspective and stereo, and the reverse transformations involved in identifying positions in data space from positions on the screen. It also considers transformations affecting drawing which result from changes to molecular features, such as rotations about single bonds, and the organization of such transformations in stacks. This section concludes with a discussion of various drawing techniques as they relate to both vector and raster devices. The second part (Section 3.3.2[link]) is concerned with molecular modelling and reviews methods of specifying connectivity within molecules. It also compares modelling methods for which the atomic coordinates are treated as independent variables with those for which other conformational variables are treated as independent and, for the latter, a solution to the problems arising from chain continuity in polymers or from the closure of flexible rings is given. The third part (Section 3.3.3[link]) gives outline descriptions of some 22 software systems developed in crystallography, most of them intended mainly for macromolecular work. This collection is now of mainly historical interest, but was updated for the second edition.

3.3.1. Graphics

| top | pdf | Coordinate systems, notation and standards

| top | pdf | Cartesian and crystallographic coordinates

| top | pdf |

It is usual, for purposes of molecular modelling and of computer graphics, to adopt a Cartesian coordinate system using mutually perpendicular axes in a right-handed system using the ångström unit or the nanometre as the unit of distance along such axes, and largely to ignore the existence of crystallographic coordinates expressed as fractions of unit-cell edges. Transformations between the two are thus associated, usually, with the input and output stages of any software concerned with modelling and graphics, and it will be assumed after this section that all coordinates are Cartesian using the chosen unit of distance as the unit of coordinates. For a discussion of coordinate transformations and rotations without making this assumption see Chapter 1.1[link] in which formulations using co- and contravariant forms are presented.

The relationship between these systems may be written [{\bf X} = {\bi M}{\bf x} \quad {\bf x} = {\bi M}^{-1} {\bf X}] in which X and x are position vectors in direct space, written as column vectors, with x expressed in crystallographic fractional coordinates (dimensionless) and X in Cartesian coordinates (dimension of length).

There are two forms of M in common use. The first of these sets the first component of X parallel to [{\bf a}^{*}] and the third parallel to c and is [\displaylines{{\bi M} = \pmatrix{a\varphi / \sin \alpha &0 &0\cr a(\cos \gamma - \cos \alpha \cos \beta) / \sin \alpha &b \sin \alpha &0\cr a \cos \beta &b \cos \alpha &c\cr}\cr {\bi M}^{-1} = \pmatrix{\sin \alpha / a\varphi &0 &0\cr (\cos \alpha \cos \beta - \cos \gamma) / b\varphi \sin \alpha &1 / b \sin \alpha &0\cr (\cos \alpha \cos \gamma - \cos \beta) / c\varphi \sin \alpha &- 1 / c \tan \alpha &1 / c\cr}}] in which [\eqalign{\varphi &= \sqrt{1 - \cos^{2} \alpha - \cos^{2} \beta - \cos^{2} \gamma + 2 \cos \alpha \cos \beta \cos \gamma}\cr &= \sin \alpha \sin \beta \sin \gamma^{*}.}]

ϕ is equal to the volume of the unit cell divided by abc, and is unchanged by cyclic permutation of α, β and γ and of [\alpha^{*}], [\beta^{*}] and [\gamma^{*}]. The Cartesian and crystallographic axes have the same chirality if the positive square root is taken.

The second form sets the first component of X parallel to a and the third component of X parallel to [{\bf c}^{*}] and is [\displaylines{{\bi M} = \pmatrix{a &b \cos \gamma &c \cos \beta\cr 0 &b \sin \gamma &c(\cos \alpha - \cos \beta \cos \gamma) / \sin \gamma\cr 0 &0 &c\varphi / \sin \gamma\cr}\cr {\bi M}^{-1} = \pmatrix{1/a &-1/a \tan \gamma &(\cos \alpha \cos \gamma - \cos \beta) / a\varphi \sin \gamma\cr 0 &1/b \sin \gamma &(\cos \beta \cos \gamma - \cos \alpha) / b\varphi \sin \gamma\cr 0 &0 &\sin \gamma / c\varphi\cr}.}]

A third form, suitable only for rhombohedral cells, is [\eqalign{{\bi M} &= {a\over 3} \pmatrix{p + 2q &p - q &p - q\cr p - q &p + 2q &p - q\cr p - q &p - q &p + 2q\cr}\cr {\bi M}^{-1} &= {1\over 3a} \pmatrix{\displaystyle{1\over p} + {2\over q} &\displaystyle{1\over p} - {1\over q} &\displaystyle{1\over p} - {1\over q}\cr \displaystyle{1\over p} - {1\over q} &\displaystyle{1\over p} + {2\over q} &\displaystyle{1\over p} - {1\over q}\cr \displaystyle{1\over p} - {1\over q} &\displaystyle{1\over p} - {1\over q} &\displaystyle{1\over p} + {2\over q}\cr}}] in which [p = \pm \sqrt{1 + 2 \cos \alpha} \quad q = \pm \sqrt{1 - \cos \alpha},] which preserves the equivalence of axes. Here the chiralities of the Cartesian and crystallographic axes are the same if p is chosen positive, and different otherwise, and the two sets of axes coincide in projection along the triad if q is chosen positive and are π out of phase otherwise. Homogeneous coordinates

| top | pdf |

Homogeneous coordinates have found wide application in computer graphics. For some equipment their use is essential, and they are of value analytically even if the available hardware does not require their use.

Homogeneous coordinates employ four quantities, X, Y, Z and W, to define the position of a point, rather than three. The fourth coordinate has a scaling function so that it is the quantity [X/W] (as delivered to the display hardware) which controls the left–right positioning of the point within the picture. A point with [|X / W|\lt 1] is in the picture, normally, and those with [|X / W|\gt 1] are outside it, but see Section[link]

There are many reasons why homogeneous coordinates may be adopted, among them the following:

  • (i) X, Y, Z and W may be held as integers, thus enabling fast arithmetic whilst offering much of the flexibility of floating-point working. A single W value may be common to a whole array of X, Y, Z values.

  • (ii) Perspective transformations can be implemented without the need for any division. Only high-speed matrix multiplication using integer arithmetic is necessary, provided only that the drawing hardware can provide displacements proportional to the ratio of two signals, X and W or Y and W. Rotation, translation, scaling and the application of perspective are all affected by operations of the same form, namely multiplication of a four-vector by a [4 \times 4] matrix. The hardware may thus be kept relatively simple since only one type of operation needs to be provided for.

  • (iii) Since kX, kY, kZ, kW represents the same point as X, Y, Z, W, the hardware may be arranged to maximize resolution without risk of integer overflow.

For analytical purposes it is convenient to regard homogeneous transformations in terms of partitioned matrices [\pmatrix{{\bi M} &{\bf V}\cr {\bf U} &{N}\cr} \pmatrix{{\bf X}\cr {W}\cr},] where M is a [3 \times 3] matrix, V and X are three-element column vectors, U is a three-element row vector and N and W are scalars.

Matrices and vectors which are equivalent under the considerations of (iii[link]) above will be related by the sign ≃ in what follows.

Hardware systems which use true floating-point representations have less need of homogeneous coordinates and for these N and W may normally be set to unity. Notation

| top | pdf |

In this chapter the conventions of matrix algebra will be adhered to except where it is convenient to show operations on elements of vectors, matrices and tensors, where a subscript notation will be used with a modified summation convention in which summation is over lower-case subscripts only. Thus the equation [x_{I} = A_{Ij}X_{j}] is to be read `For any I, [x_{I}] is [A_{Ij}X_{j}] summed over j'.

Subscripts using the letter i or later in the alphabet will relate to the usual three dimensions and imply a three-term summation. Subscripts a to h are not necessarily so limited, and, in particular, the subscript a is used to imply summation over atoms of which there may be an arbitrary number.

We shall use the superscript T to denote a transpose, and also use the Kronecker delta, [\delta_{IJ}], which is 1 if [I = J] and zero otherwise, and the tensor [\varepsilon_{IJK}] which is 1 if I, J and K are a cyclic permutation of 1, 2, 3, −1 if an anticyclic permutation, and zero otherwise. [\varepsilon_{IJK} = (I - J) (J - K) (K - I) / 2 \quad 1 \leq I, J, K \leq 3.]

A useful identity is then [\varepsilon_{iJK} \varepsilon_{iLM} = \delta_{JL} \delta_{KM} - \delta_{JM} \delta_{KL}.] Single modulus signs surrounding the symbol for a square matrix denote its determinant, and around a vector denote its length.

The symbol ≃ is defined in the previous section. Standards

| top | pdf |

The sections of this chapter concerned with graphics are primarily concerned with the mathematical aspects of graphics programming as they confront the applications programmer. The implementations outlined in the final section have all, so far as the author is aware, been developed ab initio by their inventors to deal with these aspects using their own and unrelated techniques and protocols. It is clear, however, that standards are now emerging, and it is to be hoped that future developments in applications software will handle the graphics aspects through one or other of these standards.

First among these standards is the Graphical Kernel System, GKS, defined in American National Standards Institute, American National Standard for Information Processing Systems – Computer Graphics – Graphical Kernel System (GKS) Functional Description (1985[link]) and described and illustrated by Hopgood et al. (1986[link]) and Enderle et al. (1984[link]). GKS became a full International Standards Organization (ISO) standard in 1985, and its purpose is to standardize the interface between application software and the graphics system, thus enhancing portability of software. Specifications for Fortran, Pascal and Ada formulations are at an advanced stage of development. Its value to crystallographers is limited by the fact that it is only two-dimensional. A three-dimensional extension known as GKS-3D, defined in International Standards Organisation, International Standard Information Processing Systems – Computer Graphics – Graphical Kernel System for Three Dimensions (GKS-3D), Functional Description (1988[link]) became an ISO standard in 1988. Perhaps of greatest interest to crystallographers, however, is the Programmers' Hierarchical Interactive Graphics System (PHIGS) (Brown, 1985[link]; Abi-Ezzi & Bunshaft, 1986[link]) since this allows hierarchical segmentation of picture content to exist in both the applications software and the graphics device in a related manner, which GKS does not. Some graphics devices now available support this type of working and its exploitation indicates the choice of PHIGS. Furthermore, Fortran implementations of GKS and GKS-3D require points to be stored in arrays dimensioned as X(N), Y(N), Z(N) which may be equivalenced (in the Fortran sense) to XYZ(N, 3) but not to XYZ(3, N), which may not be convenient. PHIGS also became an International Standard in 1988: American National Standards Institute, American National Standard for Information Processing Systems – Computer Graphics – Programmer's Hierarchical Graphics System (PHIGS) Functional Description, Archive File Format, Clear-Text Encoding of Archive File (1988[link]). PHIGS has also been extended to support the capability of raster-graphics machines to represent reflections, shadows, see-through effects etc. in a version known as PHIGS+ (van Dam, 1988[link]).

Increasingly, manufacturers of graphics equipment are orienting their products towards one or other of these standards. While these standards are not the subject of this chapter it is recommended that they be studied before investing in equipment.

In addition to these standards, related standards are evolving under the auspices of the ISO for defining images in a file-storage, or metafile, form, and for the interface between the device-independent and device-dependent parts of a graphics package. Arnold & Bono (1988[link]) describe the ANSI and ISO Computer Graphics Metafile standard which provides for the definition of (two-dimensional) images. The definition of three-dimensional scenes requires the use of (PHIGS) archive files. Orthogonal (or rotation) matrices

| top | pdf |

It is a basic requirement for any graphics or molecular-modelling system to be able to control and manipulate the orientation of the structures involved and this is achieved using orthogonal matrices which are the subject of these sections. General form

| top | pdf |

If a vector v is expressed in terms of its components resolved onto an axial set of vectors X, Y, Z which are of unit length and mutually perpendicular and right handed in the sense that [({\bf X} \times {\bf Y}) \cdot {\bf Z} = + 1], and if these components are [v_{I}], and if a second set of axes X′, Y′, Z′ is similarly established, with the same origin and chirality, and if v has components [v'_{I}] on these axes then [v'_{I} = a_{Ij} v_{j},] in which [a_{IJ}] is the cosine of the angle between the ith primed axis and the jth unprimed axis. Evidently the elements [a_{IJ}] comprise a matrix R, such that any row represents one of the primed axial vectors, such as X′, expressed as components on the unprimed axes, and each column represents one of the unprimed axial vectors expressed as components on the primed axes. It follows that [{\bi R}^{T} = {\bi R}^{-1}] since elements of the product [{\bi R}^{T} {\bi R}] are scalar products among perpendicular unit vectors.

A real matrix whose transpose equals its inverse is said to be orthogonal.

Since X, Y and Z can simultaneously be superimposed on X′, Y′ and Z′ without deformation or change of scale the relationship is one of rotation, and orthogonal matrices are often referred to as rotation matrices. The operation of replacing the vector v by Rv corresponds to rotating the axes from the unprimed to the primed set with v itself unchanged. Equally, the same operation corresponds to retaining fixed axes and rotating the vector in the opposite sense. The second interpretation is the one more frequently helpful since conceptually it corresponds more closely to rotational operations on objects, and it is primarily in this sense that the following is written.

If three vectors u, v and w form the edges of a parallelepiped, then its volume V is [V = {\bf u} \cdot ({\bf v} \times {\bf w}) = \varepsilon_{ijk} u_{i} v_{j} w_{k}] and if these vectors are transformed by the matrix R as above, then the transformed volume V′ is [V' = \varepsilon_{lmn} u'_{l} v'_{m} w'_{n} = \varepsilon_{lmn} a_{li} a_{mj} a_{nk} u_{i} v_{j} w_{k}.] But the determinant of R is given by [|{\bi R}| \varepsilon_{IJK} = \varepsilon_{lmn} a_{lI} a_{mJ} a_{nK}] so that [V' = |{\bi R}|V] and the determinant of R must therefore be +1 for a transformation which is a pure rotation. Nevertheless orthogonal matrices with determinant −1 exist though these do not describe a pure rotation. They may always be described as the product of a pure rotation and inversion through the origin and are referred to here as improper rotations. In what follows all references to orthogonal matrices refer to those with positive determinant only, unless stated otherwise.

An important general form of an orthogonal matrix in three dimensions was derived as equation ([link] ) and is [{\bi R} = \pmatrix{l^{2} + (m^{2} + n^{2}) \cos \theta &lm(1 - \cos \theta) - n \sin \theta &nl(1 - \cos \theta) + m \sin \theta\cr lm(1 - \cos \theta) + n \sin \theta &m^{2} + (n^{2} + l^{2}) \cos \theta &mn(1 - \cos \theta) - l \sin \theta\cr nl(1 - \cos \theta) - m \sin \theta &mn(1 - \cos \theta) + l \sin \theta &n^{2} + (l^{2} + m^{2}) \cos \theta\cr}] or [{R}_{IJ} = (1 - \cos \theta) l_{I}l_{J} + \delta_{IJ} \cos \theta - \varepsilon_{IJk}l_{k} \sin \theta,] in which l, m and n are the direction cosines of the axis of rotation (which are the same when referred to either set of axes under either interpretation) and θ is the angle of rotation. In this form, and with R operating on column vectors on the right, the sign of θ is such that, when viewed along the rotation axis from the origin towards the point lmn, the object is rotated clockwise for positive θ with a fixed right-handed axial system. If, under the same viewing conditions, the axes are to be rotated clockwise through θ with the object fixed then the components of vectors in the object, on the new axes, are given by R with the same lmn and with θ negated. This is the transpose of R, and if R is constructed from a product, as below, then each factor matrix in the product must be transposed and their order reversed to achieve this. Note that if, for a given rotation, the viewing direction from the origin is reversed, l, m, n and θ are all reversed and the matrix is unchanged.

Any rotation about a reference axis such that two of the direction cosines are zero is termed a primitive rotation, and it is frequently a requirement to generate or to interpret a general rotation as a product of primitive rotations.

A second important general form is based on Eulerian angles and is the product of three such primitives. It is [\eqalign{ {\bi R} &= \pmatrix{\cos \varphi_{3} &- \sin \varphi_{3} &0\cr \sin \varphi_{3} &\cos \varphi_{3} &0\cr 0 &0 &1\cr} \pmatrix{\cos \varphi_{2} &0 &\sin \varphi_{2}\cr 0 &1 &0\cr - \sin \varphi_{2} &0 &\cos \varphi_{2}\cr} \pmatrix{\cos \varphi_{1} &- \sin \varphi_{1} &0\cr \sin \varphi_{1} &\cos \varphi_{1} &0\cr 0 &0 &1\cr}\cr &= \pmatrix{(\cos \varphi_{3} \cos \varphi_{2} \cos \varphi_{1} &- (\cos \varphi_{3} \cos \varphi_{2} \sin \varphi_{1} &\cos \varphi_{3} \sin \varphi_{2}\cr - \sin \varphi_{3} \sin \varphi_{1}) &+ \sin \varphi_{3} \cos \varphi_{1})\cr \noalign{\vskip5pt} (\sin \varphi_{3} \cos \varphi_{2} \cos \varphi_{1} &(- \sin \varphi_{3} \cos \varphi_{2} \sin \varphi_{1} &\sin \varphi_{3} \sin \varphi_{2}\cr + \cos \varphi_{3} \sin \varphi_{1}) &+ \cos \varphi_{3} \cos \varphi_{1})\cr \noalign{\vskip5pt} - \sin \varphi_{2} \cos \varphi_{1} &\sin \varphi_{2} \sin \varphi_{1} &\cos \varphi_{2}\cr}}] which is commonly employed in four-circle diffractometers for which [\varphi = - \varphi_{1}], [\chi = \varphi_{2}] and [\omega = - \varphi_{3}]. In terms of the fixed-axes–moving-object conceptualization this corresponds to a rotation [\varphi_{1}] about Z followed by [\varphi_{2}] about Y followed by [\varphi_{3}] about Z. In the familiar diffractometer example, when [\chi = 0] the ϕ and ω axes are both vertical and equivalent. If ϕ is altered first, then the χ axis is still in the direction of a fixed Y axis, but if ω is altered first it is not. Since all angles are to be rotations about fixed axes to describe a rotating object it follows that it is ϕ rather than ω which corresponds to [\varphi_{1}]. In general, when rotating parts are mounted on rotating parts the rotation closest to the moved object must be applied first, forming the right-most factor in any multiple transformation, with the rotation closest to the fixed part as the left-most factor, assuming data supplied as column vectors on the right.

Given an orthogonal matrix, in either numerical or analytical form, it may be required to discover θ and the axis of rotation, or to factorize it as a product of primitives. From the first form we see that the vector [v_{I} = \varepsilon_{Ijk}a_{jk},] consisting of the antisymmetric part of R, has elements [-2 \sin \theta] times the direction cosines l, m, n, which establishes the direction immediately, and normalization using [l^{2} + m^{2} + n^{2} = 1] determines [\sin \theta]. Furthermore, the trace is [1 + 2 \cos \theta] so that the quadrant of θ is also fixed. This method fails, however, if the matrix is symmetrical, which occurs if [\theta = \pi]. In this case only the direction of the axis is required, which is given by [l: m: n = (a_{23})^{-1}: (a_{31})^{-1}: (a_{12})^{-1}] for non-zero elements, or [l = \sqrt{{\textstyle{1\over 2}} (a_{11} + 1)}] etc., with the signs chosen to satisfy [a_{12} = 2lm] etc.

The Eulerian form may be factorized by noting that [\tan \varphi_{1} = - a_{32}/a_{31}, \tan \varphi_{3} = a_{23}/a_{13}, \cos \varphi_{2} = a_{33}]. There is then freedom to choose the sign of [\sin \varphi_{2}], but the choice then fixes the quadrants of [\varphi_{1}] and [\varphi_{3}] through the elements in the last row and column, and the primitives may then be constructed. These expressions for [\varphi_{1}] and [\varphi_{3}] fail if [\sin \varphi_{2} = 0], in which case the rotation reduces to a primitive rotation about Z with angle [(\varphi_{1} + \varphi_{3}), \varphi_{2} = 0], or [(\varphi_{3} - \varphi_{1}), \varphi_{2} = \pi].

Eulerian angles are unlikely to be the best choice of primitive angles unless they are directly related to the parameters of a system, as with the diffractometer. It is often more important that the changes to primitive angles should be quasi-linearly related to θ for any small rotations, which is not the case with Eulerian angles when the required rotation axis is close to the X axis. In such a case linearized techniques for solving for the primitive angles will fail. Furthermore, if the required rotation is about Z only [(\varphi_{1} + \varphi_{3})] is determinate.

Quasi-linear relationships between θ and the primitive rotations arise if the primitives are one each about X, Y and Z. Any order of the three factors may be chosen, but the choice must then be adhered to since these factors do not commute. For sufficiently small rotations the primitive rotations are then [l\theta], [m\theta] and [n\theta], whilst for larger θ linearized iterative techniques for finding the primitive rotations are likely to be convergent and well conditioned.

The three-dimensional space of the angles [\varphi_{1}, \varphi_{2}] and [\varphi_{3}] in either case is non-linearly related to θ. In the Eulerian case the worst non-linearities occur at the origin of ϕ-space. Equally severe non-linearities occur in the quasi-linear case also but are 90° away from the origin and less likely to be troublesome.

Neither of the foregoing general forms of orthogonal matrix has ideally convenient properties. The first is inconvenient because it uses four non-equivalent variables l, m, n and θ, with a linking equation involving l, m and n, so that they cannot be treated as independent variables for analytical purposes. The second form (the product of primitives) is not ideal because the three angles, though independent, are not equivalent, the non-equivalence arising from the non-commutation of the primitive factors. In the remainder of this section we give two further forms of orthogonal matrix which each use three variables which are independent and strictly equivalent, and a third form using four whose squares sum to unity.

The first of these is based on the diagonal and uses the three independent variables p, q, r, from which we construct the auxiliary variables [\eqalign{P &= \pm \sqrt{1 + p - q - r},\ Q = \pm \sqrt{1 - p + q - r},\cr R &= \pm \sqrt{1 - p - q + r},\ S = \pm \sqrt{1 + p + q + r},}] then [\displaylines{{\bi R} = \pmatrix{p &{\textstyle{1\over 2}}[PQ - RS] &{\textstyle{1\over 2}}[PR + QS]\cr {\textstyle{1\over 2}}[PQ + RS] &q &{\textstyle{1\over 2}}[QR - PS]\cr {\textstyle{1\over 2}}[PR - QS] &{\textstyle{1\over 2}}[QR + PS] &r\cr}}] is orthogonal with positive determinant for any of the sixteen sign combinations. The signs of P, Q, R and S are, respectively, the signs of the direction cosines of the rotation axis and of [\sin \theta]. Using also [T = \sqrt{4 - S^{2}}], which may be deemed positive without loss of generality, [\displaylines{l = P/T, m = Q/T, n = R/T, \sin \theta = ST/2,\cr \cos \theta = 1 - T^{2}/2 = S^{2}/2 - 1.}]

Although p, q and r are independent, the point [pqr] is bound, by the requirement that P, Q, R and S be real, to lie within a tetrahedron whose vertices are the points [111], [[1\bar{1}\bar{1}]], [[\bar{1}1\bar{1}]] and [[\bar{1}\bar{1}1]], corresponding to the identity and to 180° rotations about each of the axes. The facts that the identity occurs at a vertex of the feasible region and that [(1 - \cos \theta)], rather than [\sin \theta], is linear on p, q and r in this vicinity make this form suitable only for substantial rotations.

The second form consists in defining a rotation vector r with components u, v, w such that [u = lt], [v = mt], [w = nt] with [t = \tan (\theta/2)] and [{\bf r} \cdot {\bf r} = t^{2}]. Then the matrix [\displaylines{{\bi R} = \pmatrix{\displaystyle{1 + u^{2} - v^{2} - w^{2}\over 1 + t^{2}} &\displaystyle{2(uv - w)\over 1 + t^{2}} &\displaystyle{2(uw + v)\over 1 + t^{2}}\cr \noalign{\vskip3pt} \displaystyle{2(uv + w)\over 1 + t^{2}} &\displaystyle{1 - u^{2} + v^{2} - w^{2}\over 1 + t^{2}} &\displaystyle{2(vw - u)\over 1 + t^{2}}\cr \noalign{\vskip3pt} \displaystyle{2(uw - v)\over 1 + t^{2}} &\displaystyle{2(vw + u)\over 1 + t^{2}} &\displaystyle{1 - u^{2} - v^{2} + w^{2}\over 1 + t^{2}}\cr}\cr \noalign{\vskip5pt} R_{IJ} = (1 + t^{2})^{-1} [\delta_{IJ} (1 - u_{k}u_{k}) + 2(u_{I}u_{J} - \varepsilon_{IJl}u_{l})]}] is orthogonal and the variables u, v, w are independent, equivalent and unbounded, and, unlike the previous form, small rotations are quasi-linear on these variables. As examples, [{\bf r} = [100]] gives 90° about X, [{\bf r} = [111]] gives 120° about [111].

R then transforms a vector d according to [{\bi R}{\bf d} = {\bf d} + {2\over 1 + t^{2}} \{({\bf r} \times {\bf d}) + [{\bf r} \times ({\bf r} \times {\bf d})]\}.]

Multiplying two such matrices together allows us to establish the manner in which the rotation vectors [{\bf r}_{1}] and [{\bf r}_{2}] combine. [{\bf r} = {{\bf r}_{2} + {\bf r}_{1} + {\bf r}_{2} \times {\bf r}_{1}\over 1 - {\bf r}_{2} \cdot {\bf r}_{1}}] for a rotation [{\bf r}_{1}] followed by [{\bf r}_{2}], so that rotations expressed in terms of rotation angles and axes may be compounded into a single such rotation without the need to form and decompose a product matrix.

Note that if [{\bf r}_{1}] and [{\bf r}_{2}] are parallel this reduces to the formula for the tangent of the sum of two angles, and that if [{\bf r}_{1} \cdot {\bf r}_{2} = 1] the combined rotation is always 180°. Note, too, that reversing the order of application of the rotations reverses only the vector product.

If three rotations [{\bf r}_{1}, {\bf r}_{2}] and [{\bf r}_{3}] are applied successively, [{\bf r}_{1}] first, then their combined rotation is [\eqalign{{\bf r}=\;&[{\bf r}_{3} (1 - {\bf r}_{1} \cdot {\bf r}_{2}) + {\bf r}_{2} (1 + {\bf r}_{3} \cdot {\bf r}_{1}) + {\bf r}_{1} (1 - {\bf r}_{3} \cdot {\bf r}_{2})\cr &+ {{\bf r}_{3} \times {\bf r}_{2} + {\bf r}_{3} \times {\bf r}_{1} + {\bf r}_{2} \times {\bf r}_{1}}]\cr&\times[{1 - {\bf r}_{1} \cdot {\bf r}_{2} - {\bf r}_{2} \cdot {\bf r}_{3} - {\bf r}_{3} \cdot {\bf r}_{1} - {\bf r}_{3} \cdot ({\bf r}_{2} \times {\bf r}_{1})}]^{-1}.}]

Note the irregular pattern of signs in the numerator.

Similar ideas, using a vector of magnitude [\sin (\theta/2)], are developed in Aharonov et al. (1977[link]).

The third form of orthogonal matrix uses four variables, λ, μ, ν and σ, which comprise a four-dimensional vector [\boldrho], such that [\lambda = ls], [\mu = ms], [\nu = ns] with [s = \sin (\theta/2)] and [\sigma = \cos (\theta/2)]. In terms of these variables [{\bi R} = \pmatrix{(\lambda^{2} - \mu^{2} - \nu^{2} + \sigma^{2}) &2(\lambda \mu - \nu \sigma) &2(\lambda \nu + \mu \sigma)\cr 2(\mu \lambda + \nu \sigma) &(-\lambda^{2} + \mu^{2} - \nu^{2} + \sigma^{2}) &2(\mu \nu - \lambda \sigma)\cr 2(\lambda \nu - \mu \sigma) &2(\mu \nu + \lambda \sigma) &(-\lambda^{2} - \mu^{2} + \nu^{2} + \sigma^{2})\cr}.] Two further matrices S and T may be defined (Diamond, 1988[link]), [{\bi S} = \pmatrix{-\sigma &{\phantom-}\nu &-\mu &\lambda\cr -\nu &-\sigma &{\phantom-}\lambda &\mu\cr {\phantom-}\mu &-\lambda &-\sigma &\nu\cr {\phantom-}\lambda &{\phantom-}\mu &{\phantom-}\nu &\sigma\cr} \hbox{ and } {\bi T} = \pmatrix{{\phantom-}\sigma &-\nu &{\phantom-}\mu &\lambda\cr {\phantom-}\nu &{\phantom-}\sigma &-\lambda &\mu\cr -\mu &{\phantom-}\lambda &{\phantom-}\sigma &\nu\cr -\lambda &-\mu &-\nu &\sigma\cr},] which are themselves orthogonal (though S has determinant −1) and which have the property that [{\bi S}^{2} = \pmatrix{{\bi R} &{\bf 0}\cr {\bf 0}^{T} &1\cr}] so that, for example, if homogeneous coordinates are being employed (Section[link]) [\pmatrix{x'\cr y'\cr z'\cr w\cr} = \pmatrix{-\sigma &{\phantom-}\nu &-\mu &\lambda\cr -\nu &-\sigma &{\phantom-}\lambda &\mu\cr {\phantom-}\mu &-\lambda &-\sigma &\nu\cr {\phantom-}\lambda &{\phantom-}\mu &{\phantom-}\nu &\sigma\cr} \pmatrix{-\sigma &{\phantom-}\nu &-\mu &\lambda\cr -\nu &-\sigma &{\phantom-}\lambda &\mu\cr {\phantom-}\mu &-\lambda &-\sigma &\nu\cr {\phantom-}\lambda &{\phantom-}\mu &{\phantom-}\nu &\sigma\cr} \pmatrix{x\cr y\cr z\cr w\cr}] is a rotation of (x, y, z, w) through the angle θ about the axis (l, m, n). With suitably pipelined hardware this forms an efficient means of applying rotations since the `overhead' of establishing S is so trivial.

T has the property that the rotation vector [\boldrho] arising from a concatenation of n rotations is [{\boldrho} = {\bi T}_{n} {\bi T}_{n - 1} \ldots {\bi T}_{1} {\boldrho}_{0},] in which [{\boldrho}_{0}^{T}] is the vector (0, 0, 0, 1) which defines a null rotation. This equation may be used as a basis for factorizing a given rotation into a concatenation of rotations about designated axes (Diamond, 1990a[link]).

Finally, an exact rotation of the vector d may be obtained without using matrices at all by writing [{\bf d} = {\textstyle\sum\limits_{0}^{\infty}} {\bf d}_{n}] in which [{\bf d}_{n} = {1\over n} ({\boldtheta} \times {\bf d}_{n - 1})] and [{\bf d}_{0}] is the initial position which is to be rotated. Here [\boldtheta] is a vector with direction cosines l, m and n, and magnitude equal to the required rotation angle in radians (Diamond, 1966[link]). This method is particularly efficient when [|{\boldtheta}| \ll 1] or when the number of vectors to be transformed is small since the overhead of establishing R is eliminated and the process is simple to program. It is the three-dimensional analogue of the power series for sin θ and cos θ and has the same convergence properties. Measurement of rotations and strains from coordinates

| top | pdf |

Given the coordinates of a molecular fragment it is often a requirement to relate the fragment to its image in some standard orientation by a transformation which may be required to be a pure rotation, or may be required to be a combination of rotation and strain. Of the methods reviewed in this section all except (iv[link]) are concerned with pure rotation, ignoring any strain that may be present, and give the best rigid-body superposition. In all these methods, unless inhomogeneous strain is being considered, the best possible superposition is obtained if the centroids of the two images are first brought into coincidence by translation and treated as the origin.

Methods (i[link] [link] [link] [link]) to (v[link]) seek transformations which perform the superposition and impose on these, in various ways, the requirements of orthogonality for the rotational part. All these methods therefore need some defence against indeterminacy that arises in the general transformation if one or both of the fragments is planar, and, if improper rotations are to be excluded, need a defence against these also if the fragment and its image are of opposite chirality. Methods (vi[link]) and (vii[link]) pay no attention to the general transformation and work with variables which are intrinsically rotational in character, and always produce an orthogonal transformation with positive determinant, with no degeneracy arising from planar fragments which need no special attention. Even collinear atoms cause no problem, the superposition being performed correctly but with an arbitrary rotation about the length of the line being present in the result. These methods are therefore to be preferred over the earlier ones unless the purpose of the operation is to detect differences of chirality, although this, too, can be detected with a simple test.

In this review we adopt the same notation for all the methods which, unavoidably, means that symbols are used in ways which differ from the original publications. We use the symbol x for the vector set which is to be rotated and X for the vector set whose orientation is not to be altered, and write the residuals as [e_{IA} = D_{Ij} x_{jA} - X_{IA}] and, by choice of origin, [W_{a} x_{Ia} = W_{a} X_{Ia} = 0_{I}] for weights W. The quadratic residual to be minimized is [E = W_{a} e_{ia} e_{ia}] and we define the matrix [M_{IJ} = W_{a} x_{Ia} X_{Ja}] and use l for the direction cosines of the rotation axis.

  • (i) McLachlan's first method (McLachlan, 1972[link], 1982[link]) is iterative and conceptually the simplest. It sets [D_{IJ} = A_{Ik} R_{kJ}] in which A and R are both orthogonal with R being a current estimate of D and A being an adjustment which, at the beginning of each cycle, has a zero angle associated with it. One iterative cycle estimates a non-trivial A, after which the product AR replaces R. [A_{IJ} = (1 - \cos \theta) l_{I} l_{J} + \delta_{IJ} \cos \theta - \varepsilon_{IJk} l_{k} \sin \theta] and [\left({\partial A_{IJ}\over \partial \theta}\right)_{\theta = 0} = - \varepsilon_{IJk} l_{k},] therefore [\eqalign{\left({\partial E\over \partial \theta}\right)_{\theta = 0} &= 2 W_{a} \left({\partial A_{ij}\over \partial \theta}\right)_{\theta = 0} R_{jk} x_{ka} (A_{il}R_{lm}x_{ma} - X_{ia})\cr &= 2\varepsilon_{ijl} R_{jk} M_{ki} l_{l}.}] For this to vanish for all possible rotation axes l the vector [g_{L} = \varepsilon_{ijL} R_{jk} M_{ki}] must vanish, i.e. at the end of the iteration R must be such that the matrix [N_{JI} = R_{Jk} M_{kI}] is symmetrical. The vector g represents the couple exerted on the rotating body by forces [2 W_{A} (R_{Ij} x_{jA} - X_{IA})] acting at the atoms. Choosing [l_{L} = g_{L}/|{\bf g}|] gives the greatest [|\partial {E}/\partial \theta|_{\theta = 0}] and [(\partial E/\partial \theta)] vanishes when [\tan \theta = {\varepsilon_{ijk} N_{ji} l_{k}\over N_{pq} (l_{p} l_{q} - \delta_{pq})}] in which N is constructed from the current R matrix. A is then constructed from l and this θ and AR replaces R. The process is iterative because a couple about some new axis can appear when rotation about g eliminates the couple about g.

    Note that for each rotation axis l there are two values of θ, differing by π, which reduce [|{\bf g}|] to zero, corresponding to maximum and minimum values of E. The minimum is that which makes [{\partial^{2} E\over \partial \theta^{2}} = 2(\hbox{tr } N - l_{i} N_{ij} l_{j})] positive. Adding π to θ alters R and N and negates this quantity.

    Note, too, that the process is essentially characterized as that which makes the product RM symmetrical with R orthogonal. We return to this point in (iii[link]).

  • (ii) Kabsch's method (Kabsch, 1976[link], 1978[link]) minimizes E with respect to the nine elements of D, subject to the six constraints [D_{kI} D_{kJ} - \delta_{IJ} = 0_{IJ},] by using an auxiliary function [F = L_{ij} (D_{ki} D_{kj} - \delta_{ij})] in which L is symmetric containing six Lagrange multipliers. The Lagrangian function [G = E + F] then has minima with respect to the elements of D at locations which are dependent, inter alia, on the elements of L. By suitably choosing L a minimum of G may be brought into coincidence with the constrained minimum of E. A minimum of G occurs where [{\partial G\over \partial D_{IJ}} = 2D_{Ik} (S_{Jk} + L_{Jk}) - 2 M_{JI} = 0_{IJ}] and the [9 \times 9] matrix [{\partial^{2} G\over \partial D_{MK} \partial D_{IJ}} = 2\delta_{MI} (S_{JK} + L_{JK})] is positive definite, block diagonal, and has [S_{JK} = W_{a} x_{Ja} x_{Ka}] which is symmetrical. Thus L must be chosen so as to make the symmetric matrix [({\bi S} + {\bi L})] such that [{\bi D} ({\bi S} + {\bi L})^{T} = {\bi M}^{T}] with D orthogonal, or [{\bi RN} = {\bi M}^{T}] with R replacing D since we are now confined to the orthogonal case, and N is symmetric and positive definite.

  • (iii) Comparison of the Kabsch and McLachlan methods. Using the initials of these authors as subscripts, we have seen that the Kabsch solution involves solving [{\bi R}_{\rm WK} {\bi N}_{\rm WK} = {\bi M}^{T}] for an orthogonal matrix [{\bi R}_{\rm WK}] given that [{\bi N}_{\rm WK}] is symmetrical and positive definite. Thus [{\bi MM}^{T} = {\bi N}_{\rm WK}^{T} {\bi R}_{\rm WK}^{T} {\bi R}_{\rm WK} {\bi N}_{\rm WK} = {\bi N}_{\rm WK}^{2}] and [{\bi R}_{\rm WK} = {\bi M}^{T} ({\bi MM}^{T})^{-1/2}.]

    By comparison, the McLachlan treatment leads to an orthogonal R matrix satisfying [{\bi R}_{\rm ADM} = {\bi N}_{\rm ADM} {\bi M}^{-1}] in which [{\bi N}_{\rm ADM}] is also symmetric and positive definite, which similarly leads to [{\bi R}_{\rm ADM} = ({\bi M}^{T} {\bi M})^{1/2} {\bi M}^{-1}.]

    These seemingly different expressions for [{\bi R}_{\rm WK}] and [{\bi R}_{\rm ADM}] are, in fact, equal, as the following shows [{\bi R}_{\rm WK} = {\bi R}_{\rm ADM} {\bi R}_{\rm ADM}^{-1} {\bi R}_{\rm WK} = {\bi R}_{\rm ADM} {\bi MN}_{\rm ADM}^{-1} {\bi M}^{T} {\bi N}_{\rm WK}^{-1},] therefore [\eqalign{ {\bi R}_{\rm WK}^{T} {\bi R}_{\rm WK} &= {\bi I}\cr &= {\bi N}_{\rm WK}^{-1} {\bi MN}_{\rm ADM}^{-1} {\bi M}^{T} {\bi R}_{\rm ADM}^{T} {\bi R}_{\rm ADM} {\bi MN}_{\rm ADM}^{-1} {\bi M}^{T} {\bi N}_{\rm WK}^{-1}.}] Multiplying on both sides by [{\bi N}_{\rm WK}] gives [{\bi N}_{\rm WK}^{2} = ({\bi MN}_{\rm ADM}^{-1} {\bi M}^{T})^{2},] and since both N matrices are positive definite [{\bi N}_{\rm WK} = {\bi MN}_{\rm ADM}^{-1} {\bi M}^{T}] and conversely [{\bi N}_{\rm ADM} = {\bi M}^{T} {\bi N}_{\rm WK}^{-1} {\bi M},] therefore [{\bi R}_{\rm WK} = {\bi M}^{T} {\bi M}^{T-1} {\bi N}_{\rm ADM} {\bi M}^{-1} = {\bi R}_{\rm ADM}.]

  • (iv) Diamond's first method. This method (Diamond, 1976a[link]) differs from the previous ones in that the transformation D is allowed to be a general transformation which is then factorized into the product of an orthogonal matrix R and a symmetrical matrix T. The transformation of x to fit X is thus interpreted as the combination of homogeneous strain and pure rotation in which x is subjected to strain and the result is rotated. [\eqalign{{\bi D} &= {\bi RT}\cr {\bi T}^{2} &= {\bi D}^{T} {\bi D}\cr {\bi T} &= ({\bi D}^{T} {\bi D})^{1/2}\cr {\bi R} &= {\bi D} ({\bi D}^{T} {\bi D})^{-1/2}.}] Furthermore, the solution for D is [{\bi D} = {\bi M}^{T} {\bi S}^{-1}] (in the notation of Kabsch), so that [{\bi R} = {\bi M}^{T} {\bi S}^{-1} ({\bi S}^{-1} {\bi MM}^{T} {\bi S}^{-1})^{-1/2}] which may be compared with the results of the previous paragraph.

    Although this R matrix by itself (i.e. applied without T) does not produce the best rotational superposition (i.e. smallest E), it is the one which exactly superposes the only three vectors in x whose mutual dispositions are conserved, on their equivalents in X, so that the rotation so found is arguably the best defined one.

    Alternatives based on [{\bi D} = {\bi TR}], [{\bi D}^{-1} = {\bi RT}], [{\bi D}^{-1} = {\bi TR}] are all easily developed, and these ideas are developed by Diamond (1976a[link]) to include non-homogeneous strains also.

  • (v) McLachlan's second method. This method (McLachlan, 1979[link]) is based on the properties of the [6\times 6] matrix [\pmatrix{{\bi0} &{\bi M}\cr {\bi M}^{T} &{\bi 0}\cr}] and is immune to singularity of M. If p and q are three-dimensional vectors such that [({\bf p}^{T}, {\bf q}^{T})] is an eigenvector of this matrix then [\pmatrix{{\bi 0} &{\bi M}\cr {\bi M}^{T} &{\bi 0}\cr} \pmatrix{{\bf p}\cr {\bf q}\cr} = \pmatrix{{\bi M}{\bf q}\cr {\bi M}^{T}{\bf p}\cr} = \pmatrix{{\bf p}\lambda\cr {\bf q}\lambda\cr}.]

    If q is negated the second equality is maintained provided λ is also negated. Therefore an orthogonal [6\times 6] matrix [\pmatrix{{\bi H} &{\bi H}\cr {\bi K} &{\bi -K}\cr}] (consisting of [3\times 3] partitions) exists for which [\pmatrix{{\bi H}^{T} &{\bi K}^{T}\cr {\bi H}^{T} &{\bi -K}^{T}\cr} \pmatrix{{\bi 0} &{\bi M}\cr {\bi M}^{T} &{\bi 0}\cr} \pmatrix{{\bi H} &{\bi H}\cr {\bi K} &{\bi -K}\cr} = \pmatrix{{\boldLambda} &{\bi 0}\cr {\bi 0} &{-\boldLambda}\cr}] in which [\boldLambda] is diagonal and contains non-negative eigenvalues. The reverse transformation shows that [{\bi M} = 2 {\bi H\boldLambda K}^{T}] and multiplying the eigenvectors together gives [{\bi H}^{T} {\bi H} = {\bi K}^{T} {\bi K} = {\textstyle{1\over 2}} {\bi I} = {\bi HH}^{T} = {\bi KK}^{T}.] Therefore [2{\bi KH}^{T} {\bi M} = 4{\bi KH}^{T} {\bi H}\boldLambda {\bi K}^{T} = 2{\bi K}\boldLambda {\bi K}^{T},] but [2{\bi KH}^{T}] is orthogonal and [2{\bi K}\boldLambda {\bi K}^{T}] is symmetrical, therefore [by paragraphs (i[link]) and (iii[link]) above] [2{\bi KH}^{T}] is the required rotation. Similarly, forming [\displaylines{{\bi M}^{T} = 2{\bi K}\boldLambda {\bi H}^{T}\cr \noalign{\vskip5pt} 2{\bi M}^{T} {\bi H}\boldLambda^{-1} {\bi H}^{T} = 4{\bi K}\boldLambda {\bi H}^{T} {\bi H}\boldLambda^{-1} {\bi H}^{T} = 2{\bi KH}^{T}}] corresponds to the Kabsch formulation [paragraphs (ii[link]) and (iii[link])] since [2{\bi H}\boldLambda^{-1} {\bi H}^{T}] is symmetrical and the same rotation, [2{\bi KH}^{T}], appears.

    Note that the determinant of the orthogonal matrix so found is twice the product of the determinants of H and of K, and since the positive eigenvalues are collected into [\boldLambda] it follows that the sign of the determinant of M is the same as the sign of the determinant of the resulting orthogonal matrix. If this is negative it means that the best superposition is obtained if one vector set is inverted and that x and X are of opposite chirality.

    Expanding the expression for E, the weighted sum of squares of errors, for an orthogonal transformation shows that this is least when the trace of the product RM is greatest. In this treatment [\hbox{tr} ({\bi RM}) = \hbox{tr} (2{\bi KH}^{T}\cdot 2{\bi H}\boldLambda {\bi K}^{T}) = \hbox{tr} (2{\bi K}\boldLambda {\bi K}^{T}) = \hbox{tr} (\boldLambda).] Hence, if the eigenvalues in [\boldLambda] and −[\boldLambda] are arranged in decreasing order of modulus, and if the determinant of M is negative, then exchanging the third and sixth columns of [\pmatrix{{\bi H} &{\bi H}\cr {\bi K} &{\bi -K}\cr}] produces a product [2{\bi KH}^{T}] with positive determinant (i.e. a proper rotation) at minimum cost in residual. Similarly, if M is singular and one or more eigenvalues in [\boldLambda] vanishes it is necessary only to complete an orthonormal set of eigenvectors such that the determinants of H and K have the same sign.

  • (vi) MacKay's method. MacKay (1984[link]) was the first to consider the rotational superposition problem in terms of the vector r of Section[link] Using quaternion algebra he showed that if a vector x is rotated to [{\bf X} = {\bi R}{\bf x}] then [({\bf X} - {\bf x}) = {\bf r}\times ({\bf X} + {\bf x}),] where [|{\bf r}| = \tan (\theta/2)] and the direction of r is the axis of rotation, as may also be shown from elementary considerations. MacKay then solves this for the vector r by least squares given the vector pairs X and x. The individual errors are [e_{IA} = \varepsilon_{Ijk} r_{j} (X_{kA} + x_{kA}) - (X_{IA} - x_{IA})] and [E = W_{a} e_{ia} e_{ia}.] Setting [\partial E/\partial r_{P} = 0_{P}] gives [\displaylines{W_{a} \varepsilon_{iPk} \varepsilon_{ilm} r_{l} (X_{ka} + x_{ka}) (X_{ma} + x_{ma})\cr = W_{a} \varepsilon_{iPk} (X_{ka} + x_{ka}) (X_{ia} - x_{ia})}] which reduces to [2{\bf V} = - ({\bi Q} + {\bi Q}_{0}){\bf r}] in which [\eqalign{{\bi Q} &= {\bi M} + {\bi M}^{T} - 2{\bi I} \hbox{tr } {\bi M}\cr {\bi Q}_{0} &= {\bi S} + {\bi S}' - {\bi I} (\hbox{tr } {\bi S} + \hbox{tr}\; {\bi S}')\cr V_{I} &= \varepsilon_{Ijk} M_{jk}\cr S_{IJ} &= W_{a} x_{Ia} x_{Ja}\cr S'_{IJ} &= W_{a} X_{Ia} X_{Ja}.}] Thus a direct solution for r is obtained, [{\bf r} = -2({\bi Q}_{0} + {\bi Q})^{-1}{\bf V},] the elements of which are u, v and w, and may be used to construct the orthogonal matrix as in Section[link] [{\bi Q} + {\bi Q}_{0}] may be obtained directly from [{\bi X} + {\bi x}].

    If the requisite rotation is 180°, [({\bi Q}_{0} + {\bi Q})] is singular and cannot be inverted. In this case any row or column of the adjoint of [({\bi Q}_{0} + {\bi Q})] is a vector in the direction of the axis. Normalizing this vector to unity, giving l, gives the requisite orthogonal matrix as [{\bi R} = 2{\bi ll}^{T} - {\bi I}.]

    Note that MacKay's residual E is quadratic in r. E therefore has one minimum and no maximum, and the minimum is reached on the first cycle of least squares. By contrast, the objective function E that is minimized in methods (i[link]), (ii[link]), (v[link]) and (vii[link]) has one minimum, one maximum and two saddle points in the space of the vector r, as shown in (vii[link]).

    It may be shown (Diamond, 1989[link]) that if MacKay's solution vector r is denoted by [{\bf r}_{M}] and that given by the other methods [except (iv[link])] by [{\bf r}_{O}] then [{\bf r}_{M} = {\bf r}_{O} - {\bi A}^{-1} {\bi B}{\bf r}_{O}] in which A and B are real symmetric, positive semi-definite. A is positive definite unless all the individual vector sums [({\bf X} + {\bf x})] are parallel, as can happen when the best rotation is 180°. Thus the MacKay method only gives the same result as the other methods if:

    • (a) the initial orientation is optimal, for then [{\bf r}_{O} = {\bf 0}], or

    • (b) perfect fitting is possible, for then [{\bi B} = {\bf 0}], or

    • (c) all the residual vectors (after fitting by [{\bf r}_{O}]) are parallel to [{\bf r}_{O}], for then B is singular such that [{\bi B}{\bf r}_{O} = {\bf 0}]. In general, [|{\bf r}_{M}|\leq |{\bf r}_{O}|]. [{\bf r}_{O}] may be found by iterating [{\bf r}_{M}], but x must be replaced by Rx on each iteration.

  • (vii) Diamond's second method. This is closely related to MacKay's method, but uses a four-dimensional vector [\boldrho] with components λ, μ, ν and σ in which λ, μ and ν are the direction cosines of the rotation axis multiplied by [\sin (\theta/2)] and σ is [\cos (\theta/2)]. In terms of such a vector Diamond (1988[link]) showed that [E = E_{0} - 2\boldrho^{T} {\bi P}\boldrho] in which E is the weighted sum of squares of coordinate differences, as before, [E_{0}] is its value before any rotation is applied and P is the matrix [{\bi P} = \pmatrix{{\bi Q} &{\bf V}\cr {\bf V}^{T} &0\cr}.] The rotation matrix R corresponding to the vector [\boldrho] is then the last of the forms for R given in Section[link]

    The minimum E is therefore [E_{0}] minus twice the largest eigenvalue of P since [\boldrho^{T} \boldrho = 1], and a stationary value of E occurs when [\boldrho] is any of the four eigenvectors of P. E thus has a maximum, a minimum and two saddle points, in general, and its value may be determined before any coordinates are transformed. Diamond also showed that the orientations giving these stationary values are related by the operations of 222 symmetry. Equivalent results have also been obtained by Kearsley (1989[link]).

    As an alternative to solving a [4\times 4] eigenproblem, Diamond also showed that the vector r, as in MacKay's solution, may be obtained by iterating [\eqalign{\alpha_{0} &= E_{0}/2\cr {\bf r}_{n} &= (\alpha_{n} {\bi I - Q})^{-1} {\bf V}\cr \alpha_{n+1} &= {{\bf V} \cdot {\bf r}_{n} + \alpha_{n} r_{n}^{2}\over 1 + r_{n}^{2}}}] which has the property that if X and x are exactly superposable then [\alpha_{0}] is the exact solution and no iteration is necessary. If X and x are similar but not exactly superposable then a small number of iterations may be required to reach a stable r vector, though the matrix [{\bi Q}_{0}] is not required. As in MacKay's solution, [(\alpha {\bi I} - {\bi Q})] is singular at the end of the iteration if the required rotation is 180°, but the MacKay and Diamond methods both have the advantage that improper rotations are never generated by these means, and methods based on P and [\boldrho] rather than Q and r are trouble-free for 180° rotations. The iterative loop in this method does not require Rx to be redetermined on each cycle.

    Finally, it may be shown that if [p_{1}, p_{2}, p_{3}, p_{4}] are the eigenvalues of P arranged in descending order and [p_{1} - p_{2} - p_{3} + p_{4}] is negative, then a closer superposition may be obtained by reversing the chirality of one of the vector sets, and the R matrix constructed from [{\boldrho_{4}}] optimally superimposes Rx onto − X, the enantiomer of X (Diamond, 1990b[link]). Orthogonalization of impure rotations

| top | pdf |

There are several ways of deriving a strictly orthogonal matrix from a given approximately orthogonal matrix, among them the following.

  • (i) The Gram–Schmidt process. This is probably the simplest and the easiest to compute. If the given matrix consists of three column vectors [{\bf v}_{1}, {\bf v}_{2}] and [{\bf v}_{3}] (later referred to as primers) which are to be replaced by three column vectors [{\bf u}_{1}, {\bf u}_{2}] and [{\bf u}_{3}] then the process is [\eqalign{{\bf u}_{1} &= {\bf v}_{1}/|{\bf v}_{1}|\cr {\bf u}_{2} &= {\bf v}_{2} - ({\bf u}_{1} \cdot {\bf v}_{2}) {\bf u}_{1}\cr {\bf u}_{2} &= {\bf u}_{2}/|{\bf u}_{2}|\cr {\bf u}_{3} &= {\bf v}_{3} - ({\bf u}_{1} \cdot {\bf v}_{3}) {\bf u}_{1} - ({\bf u}_{2} \cdot {\bf v}_{3}) {\bf u}_{2}\cr {\bf u}_{3} &= {\bf u}_{3}/|{\bf u}_{3}|.}]

    As successive vectors are established, each vector v has subtracted from it its components in the directions of established vectors, and the remainder is normalized. The method will fail at the normalization step if the vectors v are not linearly independent. Otherwise, the process may be extended to any number of dimensions.

    The weakness of the method is that, though [{\bf u}_{1}] differs from [{\bf v}_{1}] only in scale, [{\bf u}_{N}] may differ grossly from [{\bf v}_{N}] as the various columns are not treated equivalently.

  • (ii) A preferable method which treats all vectors equivalently is to iteratively replace the matrix M by [{\textstyle{1\over 2}} ({\bi M} + {\bi M}^{T-1})].

    Defining the residual matrix E as [{\bi E} = {\bi MM}^{T} - {\bi I},] then on each iteration E is replaced by [{\bi E}^{2} ({\bi MM}^{T})^{-1}/4] and convergence necessarily ensues.

  • (iii) A third method resolves M into its symmetric and antisymmetric parts [{\bi S} = {\textstyle{1\over 2}} ({\bi M} + {\bi M}^{T}),\quad {\bi A} = {\textstyle{1\over 2}} ({\bi M} - {\bi M}^{T}),\quad {\bi M} = {\bi S} + {\bi A}] and constructs an orthogonal matrix for which only S is altered. A determines l, m, n and θ as shown in Section[link], and from these a new S may be constructed.

  • (iv) A fourth method is to treat the general matrix M as a combination of pure strain and pure rotation. Setting [{\bi M} = {\bi RT}] with R orthogonal and T symmetrical gives [{\bi T} = ({\bi M}^{T} {\bi M})^{1/2}, \quad {\bi R} = {\bi M} ({\bi M}^{T} {\bi M})^{-1/2}.]

    The rotation so found is the one which exactly superposes those three mutually perpendicular directions which remain mutually perpendicular under the transformation M.

    [{\bi T} - {\bi I}] is then the strain tensor of an unrotated body.

    Writing [{\bi M} = {\bi TR}], [{\bi T} = ({\bi MM}^{T})^{1/2}], [{\bi R} = ({\bi MM}^{T})^{-1/2} {\bi M}] may also be useful, in which [{\bi T} - {\bi I}] is the strain tensor of a rotated body. See also Section[link] (iv)[link]. Eigenvalues and eigenvectors of orthogonal matrices

| top | pdf |

If R is the orthogonal matrix given in Section[link] in terms of the direction cosines l, m and n of the axis of rotation, then it is clear that (l, m, n) is an eigenvector of R with eigenvalue unity because [{\bi R} \pmatrix{l\cr m\cr n\cr} = \pmatrix{l\cr m\cr n\cr}.]

Consideration of the determinant [|{\bi R} - \lambda {\bi I}| = 0] shows that the sum of the three eigenvalues is [1 + 2 \cos \theta] and that their product is unity. Hence the three eigenvalues are 1, [e^{i\theta}] and [e^{-i\theta}]. Since R is real, its product with any real vector is also real, yet its product with an eigenvector must, in general, be complex. Thus the eigenvectors must themselves be complex.

The remaining two eigenvectors u may be found using the results of Section[link] (q.v.) according to [{\bi R}{\bf u} = {\bf u} + {2\over 1 + t^{2}} \{({\bf r} \times {\bf u}) + [{\bf r} \times ({\bf r} \times {\bf u})]\} = {\bf u} e^{\pm i\theta} = {\bf u} {1 \pm it\over 1 \mp it},] which is solved by any vector of the form [{\bf u} = {\bf l} \times {\bf v} \mp i{\bf l} \times ({\bf l} \times {\bf v})] for any real vector v, where l is the normalized axis vector, [{\bf l}t = {\bf r}], [|{\bf l}| = 1], [t = \tan (\theta /2)]. Eigenvectors for the two eigenvalues may have unrelated v vectors though the sign choices are coupled. If the vector v is rotated about l through an angle ϕ the corresponding vector u is multiplied by [e^{-i\varphi}] and remains an eigenvector. Using superscript signs to denote the sign of θ in the eigenvalue with which each vector is associated, the matrix [{\bi U} = ({\bf l},\ {\bf u}^{+},\ {\bf u}^{-})] has the properties that [{\bi RU} = {\bi U} \pmatrix{1 &0 &0\cr 0 &e^{i\theta} &0\cr 0 &0 &e^{-i\theta}\cr}] and [{\bi U}^{* T} {\bi U} = \pmatrix{1 &0 &0\cr 0 &2|{\bf l} \times {\bf v}^{+}|^{2} &0\cr 0 &0 &2|{\bf l} \times {\bf v}^{-}|^{2}\cr}] which places restrictions on v if this is to be the identity. Note that the 23 element vanishes even in the absence of any relationship between [{\bf v}^{+}] and [{\bf v}^{-}].

A convenient form for U, symmetrical in the elements of l, is obtained by setting [{\bf v}^{+} = {\bf v}^{-} = [{111}]] and is [{\bi U} = \pmatrix{l &\{(m - n) - i[l(l + m + n) - 1]\}/d &\{(m - n) + i[l(l + m + n) - 1]\}/d\cr m &\{(n - l) - i[m(l + m + n) - 1]\}/d &\{(n - l) + i[m(l + m + n) - 1]\}/d\cr n &\{(l - m) - i[n(l + m + n) - 1]\}/d &\{(l - m) + i[n(l + m + n) - 1]\}/d\cr}] in which the normalizing denominator is given by [d = 2 \sqrt{1 - lm - mn -nl}.] Projection transformations and spaces

| top | pdf |

In the following section we address the question of the relationship between the coordinates of a molecular model and the corresponding coordinates on the screen of the graphics device. A good introduction to this topic is given by Newman & Sproull (1973[link]), and Foley et al. (1990[link]) give a comprehensive account of the field, including recent developments, especially those arising from the development of raster-graphics technologies. Definitions

| top | pdf |

Typically, the coordinates, X, of points in an object to be drawn are held in homogeneous Cartesian form as described in Section[link] Such coordinates are said to be in data space or world coordinates and this coordinate system is generally a constant aspect of the problem.

In order to view these data in convenient ways such coordinates may be subjected to a [4 \times 4] viewing transformation T, affecting orientation, scale etc., the resulting coordinates T X being then in display space . Here, and throughout what follows, we treat position vectors as columns with transformation matrices as factors on the left, though some writers do the reverse.

In general, only some portion of display space which lies inside a certain frustum of a pyramid is required to fall within the picture. The pyramid may be thought of as having the observer's eye at its vertex, with a rectangular base corresponding to the picture area. This volume is called a window . A transformation, U, which takes display-space coordinates as input and generates vectors (X, Y, Z, W) for which [X/W] and [Y/W = \pm 1] for points on the left, right, top and bottom boundaries of the window and for which [Z/W] takes particular values on the front and back planes of the window, is said to be a windowing transformation . In machines for which [Z/W] controls intensity depth cueing, the range of [Z/W] corresponding to the window is likely to be 0 to 1 rather than −1 to 1. Coordinates obtained by multiplying display-space coordinates by U are termed picture-space coordinates. Mathematically, U is a [4 \times 4] matrix like any other, but functionally it is special. Declaring a transformation to be a windowing transformation implies that only resulting points having [|{X}|, |{Y}|\lt {W}] and positive [{Z}\lt {W}] are to be plotted. Machines with clipping hardware to truncate lines which run out of the picture perform clipping on the output from the windowing transformation.

Finally, the picture has to be drawn in some rectangular portion of the screen which is allocated for the purpose. Such an area is termed a viewport and is defined in terms of screen coordinates which are defined absolutely for the hardware in question as ±n for full-screen deflection, where n is declared by the manufacturer. Screen coordinates are obtained from picture coordinates with a viewport transformation , V.1

To summarize, screen coordinates, S, are given by [Scheme scheme1] Translation

| top | pdf |

The transformation [\eqalign{\pmatrix{{N\bi I} &{\bf V}\cr {\bf 0}^{T} &{N}\cr} \pmatrix{{\bf X}\cr {W}\cr} &= \pmatrix{{{\bf X}N} + {{\bf V}W}\cr {NW}\cr} \simeq \pmatrix{{\bf X} + {{\bf V}W/N}\cr {W}\cr}\cr &\simeq \pmatrix{{{\bf X}/W} + {{\bf V}/N}\cr {1}\cr}}] evidently corresponds to the addition of the vector [{{\bf V}W/N}] to the components of X or of [{{\bf V}/N}] to the components of [{{\bf X}/W}]. ( I is the identity.) Displacements may thus be affected by expressing the required displacement vector in homogeneous coordinates with any suitable choice of N (commonly, [N = W]), with V scaled to correspond to this choice, and loading the [4 \times 4] transformation matrix as indicated above. Rotation

| top | pdf |

Rotation about the origin is achieved by [\pmatrix{{N{\bi R}} &{\bf 0}\cr {\bf 0}^{T} &{N}\cr} \pmatrix{{\bf X}\cr {W}\cr} = \pmatrix{{{N}{\bi R}{\bf X}}\cr {NW}\cr} \simeq \pmatrix{{{\bi R}{\bf X}}\cr {W}\cr},] in which R is an orthogonal [3 \times 3] matrix. R necessarily has elements not exceeding one in modulus. For machines using integer arithmetic, therefore, N would be chosen large enough (usually half the largest possible integer) for the product NR to be well represented in the available word length. Characteristically, N affects resolution but not scale. Scale

| top | pdf |

The transformation [\pmatrix{{{SN}\bi I} &{\bf 0}\cr {\bf 0}^{T} &{N}\cr} \pmatrix{{\bf X}\cr {W}\cr} = \pmatrix{{SN{\bf X}}\cr {NW}\cr} \simeq \pmatrix{{S{\bf X}}\cr {W}\cr}] scales the vector (X, W) by the factor S. For integer working and [|S|\lt 1], N should be set to the largest representable integer. For [|S|\gt 1] the product SN should be the largest representable integer, N being reduced accordingly. Windowing and perspective

| top | pdf |

It is necessary at this point to relate the discussion to the axial system inherent in the graphics device employed. One common system adopts X horizontal and to the right when viewing the screen, Y vertically upwards in the plane of the screen, and Z normal to X and Y with +Z into the screen. This is, unfortunately, a left-handed system in that [({\bf X}\times {\bf Y}) \cdot {\bf Z}] is negative. Since it is usual in crystallographic work to use right-handed axial systems it is necessary to incorporate a matrix of the form [\pmatrix{W &0 &0 &0\cr 0 &W &0 &0\cr 0 &0 &-W &0\cr 0 &0 &0 &W\cr}] either as the left-most factor in the matrix T or as the right-most factor in the windowing transformation U (see Section[link]). The latter choice is to be preferred and is adopted here. The former choice leads to complications if transformations in display space will be required. Display-space coordinates are necessarily referred to this axial system.

Let L, R, T, B, N and F be the left, right, top, bottom, near and far boundaries of the windowed volume [(L\lt R, T\gt B, N\lt F)], S be the Z coordinate of the screen, and C, D and E be the coordinates of the observer's eye position, all ten of these parameters being referred to the origin of display space as origin, which may be anywhere in relation to the hardware. L, R, T and B are to be evaluated in the screen plane. All ten parameters may be referred to their own fourth coordinate, V, meaning that the point (X, Y, Z, W) in display space will be on the left boundary of the picture if [X/W = L/V] when [Z/W = S/V]. V may be freely chosen so that all eleven quantities and all elements of U suit the word length of the machine. These relationships are illustrated in Fig.[link]


Figure | top | pdf |

The relationship between display-space coordinates (X, Y, Z, W) and picture-space coordinates (x, y, z, w) derived from them by the window transformation, U. (a) Display space (in X, Z projection) showing a square object P, Q, R, S for display viewed from the position (C, D, E, V). The bold trapezium is the window (volume) and the bold line is the viewport portion of the screen. The points P, Q, R and S must be plotted at p, q, r and s to give the correct impression of the object. (b) Picture space (in x, z projection). The window is mapped to a rectangle and all sight lines are parallel to the z axis, but the object P, Q, R, S is no longer square. The distribution of p, q, r and s is identical in the two cases. Note that [z/w] values are not linear on [Z/W], and that the origin of picture space arises at the midpoint of the near clipping plane, regardless of the location of the origin of display space. The figure is accurately to scale for coincident viewport positions. The words `Left clipping plane', if part of the scene in display space, would currently be obscured, but would come into view if the eye moved to the right, increasing C, as the left clipping plane would pivot about the point [L/V] in the screen plane.

Since [(X, Y, Z, W) \simeq \left({XV\over W}, {YV\over W}, {ZV\over W}, V\right),] [XV/W] is a display-space coordinate on the same scale as the window parameters. This must be plotted on the screen at an X coordinate (on the scale of the window parameters) which is the weighted mean of [XV/W] and C, the weights being [(S - E)] and [(ZV/W - S)], respectively. This provides perspective because the weighted mean is at the point where the straight line from [(X, Y, Z, W)] to the eye intersects the screen. This then has to be mapped into the L-to-R interval, so that picture-space coordinates [(x, y, z, w)] are given by [\pmatrix{\noalign{\vskip10pt}x\cr\noalign{\vskip15pt} y\cr\noalign{\vskip17pt} z\cr \noalign{\vskip8pt} w\cr} = \pmatrix{\displaystyle{2(S - E) V\over (R - L)} &0 &\displaystyle{(2C - R - L) V\over (R - L)} &\displaystyle{(R + L) E - 2 SC\over (R - L)}\cr \noalign{\vskip3pt} 0 &\displaystyle{2(S - E) V\over (T - B)} &\displaystyle{(2D - T - B) V\over (T - B)} &\displaystyle{(T + B) E - 2 SD\over (T - B)}\cr \noalign{\vskip3pt} 0 &0 &\displaystyle{(F - E) V\over (F - N)} &\displaystyle{- N (F - E)\over (F - N)}\cr \noalign{\vskip3pt} 0 &0 &V &-E\cr} \pmatrix{\noalign{\vskip7pt}X\cr \noalign{\vskip14pt} Y\cr \noalign{\vskip17pt} Z\cr \noalign{\vskip9pt} W\cr}] which provides for [|x/w|] and [|y/w|] to be unity on the picture boundaries, which is usually a requirement of the clipping hardware, and for [0\lt z/w\lt 1], zero being for the near-plane boundary. Even though [z/w] is not linear on [Z/W], straight lines and planes in display space transform to straight lines and planes in picture space, the non-linearity affecting only distances. Thus vector-drawing machines are not disadvantaged by the introduction of perspective.

Note that the dimensionality of [X/W] must equal that of [S/V] and that this may be regarded as length or as a pure number, but that in either case [x/w] is dimensionless, consistent with the stipulation that the picture boundaries be defined by the pure number ±1.

The above matrix is U and is suited to left-handed hardware systems. Note that only the last column of U (the translational part) is sensitive to the location of the origin of display space and that if the eye is on the normal to the picture centre then [C = \;{\textstyle{1\over 2}}\; (R + L)], [D = \;{\textstyle{1\over 2}} (T + B)] and simplifications result. If C, D and E can be continuously monitored then dynamic parallax as well as perspective may be obtained (Diamond et al., 1982[link]).

If data space is referred to right-handed axes, the viewing transformation T involves only proper rotations and the hardware uses a left-handed axial system then elements in the third column of U should be negated, as explained in the opening paragraph.

To provide for orthographic projection, multiply every element of U by [-K/E] and then let [E \rightarrow - \infty], choosing some positive K to suit the word length of the machine [see Section[link] (iii[link])]. The result is [{\bi U}' \simeq \pmatrix{\displaystyle{2KV\over (R - L)} &0 &0 &\displaystyle{-K (R + L)\over (R - L)}\cr \noalign{\vskip3pt} 0 &\displaystyle{2KV\over (T - B)} &0 &\displaystyle{-K (T + B)\over (T - B)}\cr \noalign{\vskip3pt} 0 &0 &\displaystyle{KV\over (F - N)} &\displaystyle{-KN\over (F - N)}\cr \noalign{\vskip3pt} 0 &0 &0 &K\cr},] which is the orthographic window.

It may be convenient in some applications to separate the functions of windowing and the application of perspective, and to write [{\bi U} = {\bi U}'{\bi P},] where U and U′ are as above and P is a perspective transformation given by [{\bi P} = ({\bi U}')^{-1} {\bi U} \simeq \pmatrix{S - E &0 &C &-SC/V\cr \noalign{\vskip3pt} 0 &S - E &D &-SD/V\cr \noalign{\vskip3pt} 0 &0 &F - E + N &-NF/V\cr \noalign{\vskip3pt} 0 &0 &V &-E\cr},] which involves F and N but not R, L, T or B. In this form the action of P may be thought of as compressing distant parts of display space prior to an orthographic projection by U′ into picture space.

Other factorizations of U are possible, for example [{\bi U} = {\bi U}'' {\bi P}'] with [\displaylines{{\bi U}'' \simeq \pmatrix{\displaystyle{2KV\over R - L} &0 &0 &\displaystyle{-K (R + L)\over (R - L)}\cr \noalign{\vskip3pt} 0 &\displaystyle{2KV\over T - B} &0 &\displaystyle{-K (T + B)\over (T - B)}\cr \noalign{\vskip3pt} 0 &0 &\displaystyle{KV(N - E)(F - E)\over E^{2} (F - N)} &\displaystyle{KN (F - E)\over E(F - N)}\cr \noalign{\vskip3pt} 0 &0 &0 &K\cr}\cr \noalign{\vskip3pt} {\bi P}' \simeq \pmatrix{S - E &0 &C &-SC/V\cr \noalign{\vskip3pt} 0 &S - E &D &-SD/V\cr \noalign{\vskip3pt} 0 &0 &-E &0\cr \noalign{\vskip3pt} 0 &0 &V &-E\cr},}] which renders P′ independent of all six boundary planes, but U″ is no longer independent of E. It is not possible to factorize U so that the left factor is a function only of the boundary planes and the right factor a function only of eye and screen positions.

Note that as [E \rightarrow -\infty], [{\bi U}'' \rightarrow {\bi U}'], P and [{\bi P}' \rightarrow -{\bi I}E \simeq {\bi I}]. Stereoviews

| top | pdf |

Assuming that left- and right-eye views are to be presented through the same viewport (next section[link]) or that their viewports are to be superimposed by an external optical system, e.g. Ortony mirrors, then stereopairs are obtained by using appropriate eye coordinates in the U matrix of the previous section. However, U may be factorized according to [{\bi U} = {\bi U}''' {\bi S}] in which U‴ is the matrix U obtained by setting [(C, D, E, V)] to correspond to the point midway between the viewer's eyes and [\eqalign{{\bi S} &= \pmatrix{1 &0 &c/(S - E) &-cS/(S - E)V\cr \noalign{\vskip3pt} 0 &1 &0 &0\cr \noalign{\vskip3pt} 0 &0 &1 &0\cr \noalign{\vskip3pt} 0 &0 &0 &1\cr}\cr \noalign{\vskip5pt} &\simeq \pmatrix{V &0 &cV/(S - E) &-cS/(S - E)\cr \noalign{\vskip3pt} 0 &V &0 &0\cr \noalign{\vskip3pt} 0 &0 &V &0\cr \noalign{\vskip3pt} 0 &0 &0 &V\cr}}] in which (c, 0, 0, V) is the position of the right eye relative to the mean eye position, and the left-eye view is obtained by negating c.

Stereo is often approximated by introducing a rotation about the Y axis of [\pm \sin^{-1} [c/(S - E)]] to the views or [\sin^{-1}[2c/(S - E)]] to one of them. The first corresponds to [{\bi S} = \pmatrix{\sqrt{1 - \sigma^{2}} &0 &\sigma &0\cr \noalign{\vskip3pt} 0 &1 &0 &0\cr \noalign{\vskip3pt} -\sigma &0 &\sqrt{1 - \sigma^{2}} &0\cr \noalign{\vskip3pt} 0 &0 &0 &1\cr}] with [\sigma = c/(S - E)]. The main difference is in the resulting Z value, which only affects depth cueing and z clipping. The X translation which arises if [S \neq 0] is also suppressed, but this is not likely to be noticeable. σ is often treated as a constant, such as [\sin 3^{\circ}].

The distinction in principle between the true S and the rotational approximation is that with the true S the eye moves relative to the screen and the displayed object, whereas with the approximation the eye and the screen are moved relative to the displayed object, in going from one view to the other.

Strobing of left and right images may conveniently be accomplished with an electro-optic liquid-crystal shutter as described by Harris et al. (1985[link]). The shutter is switched by the display itself, thus solving the synchronization problem in a manner free of inertia.

A further discussion of stereopairs may be found in Johnson (1970[link]) and in Thomas (1993[link]), the second of which generalizes the treatment to allow for the possible presence of an optical system. Viewports

| top | pdf |

The window transformation of the previous two sections[link] [link] has been constructed to yield picture coordinates (X, Y, Z, W) (formerly called x, y, z, w) such that a point having [X/W] or [Y/W = \pm 1] is on the boundary of the picture, and the clipping hardware operates on this basis. However, the edges of the picture need not be at the edges of the screen and a viewport transformation, V, is therefore needed to position the picture in the requisite part of the screen. [{\bi V} = \pmatrix{(r - l)/2 &0 &0 &(r + l)/2\cr \noalign{\vskip3pt} 0 &(t - b)/2 &0 &(t + b)/2\cr \noalign{\vskip3pt} 0 &0 &n &0\cr 0 &0 &0 &n\cr},] where r, l, t and b are now the right, left, top and bottom boundaries of the picture area, or viewport, expressed in screen coordinates, and n is the full-screen deflection value. Thus a point with [X/W = 1] in picture space plots on the screen with an X coordinate which is a fraction [r/n] of full-screen deflection to the right. [Z/W] is unchanged by V and is used only to control intensity in a technique known as depth cueing.

It is necessary, of course, to arrange for the aspect ratio of the viewport, [(r - l)/( t - b)], to equal that of the window otherwise distortions are introduced. Compound transformations

| top | pdf |

In this section we consider the viewing transformation T of Section[link] and its construction in terms of translation, rotation and scaling, Sections[link] [link]–4[link]. We use T′ to denote a new transformation in terms of the prevailing transformation T.

We note first that any [4 \times 4] matrix of the form [\pmatrix{{U{\bi R}} &{\bf V}\cr {\bf 0}^{T} &{W}\cr},] with U a scalar, may be factorized according to [\pmatrix{{U{\bi R}} &{\bf V}\cr {\bf 0}^{T} &{W}\cr} \simeq \pmatrix{{U{\bi I}} &{\bf 0}\cr {\bf 0}^{T} &{W}\cr} \pmatrix{{U{\bi I}} &{\bf V}\cr {\bf 0}^{T} &{U}\cr} \pmatrix{{U{\bi R}} &{\bf 0}\cr {\bf 0}^{T} &{U}\cr}] and also that multiplying [\pmatrix{{U{\bi R}} &{\bf V}\cr {\bf 0}^{T} &{W}\cr}] by an isotropic scaling matrix, a rotation, or a translation, either on the left or on the right, yields a product matrix of the same form, and its inverse [\pmatrix{{W{\bi R}}^{T} &{{\bi -R}^{T}{\bf V}}\cr {\bf 0}^{T} &{U}\cr}] is also of this form, i.e. any combination of these three operations in any order may be reduced by the above factorization to a rotation about the original origin, a translation (which defines a new origin) and an expansion or contraction about the new origin, applied in that order.

If [\pmatrix{{N{\bi R}} &{\bf 0}\cr {\bf 0}^{T} &{N}\cr}] is a rotation matrix as in Section[link], its application produces a rotation about an axis through the origin defined only in the space in which it is applied. For example, if [\displaylines{{\bi R} = \pmatrix{\cos \theta &\sin \theta &0\cr -\sin \theta &\cos \theta &0\cr 0 &0 &1\cr},\cr \noalign{\vskip3pt} {\bi T}' \pmatrix{{\bf X}\cr {W}\cr} = {\bi T} \pmatrix{{N{\bi R}} &{\bf 0}\cr {\bf 0}^{T} &{N}\cr} \pmatrix{{\bf X}\cr {W}\cr}}] rotates the image about the z axis of data space, whatever the prevailing viewing transformation, T.

Forming [\pmatrix{{N{\bi R}} &{\bf 0}\cr {\bf 0}^{T} &{N}\cr} {\bi T} \pmatrix{{\bf X}\cr {W}\cr}] rotates the image about the z axis of display space, i.e. the normal to the tube face under the usual conventions, whatever the prevailing T. Furthermore, if this rotation is to appear to be about some chosen position in the picture, e.g. the centre, then the window transformation U, Section[link], must place the origin of display space there by setting [F\gt S = R + L = T + B = 0\gt N], in the notation of that section.

If a rotation is to be about a point [\pmatrix{{\bf V}\cr {N}\cr}] then [\eqalign{{\bi T}' =& \pmatrix{{N{\bf I}} &{\bf V}\cr {\bf 0}^{T} &{N}\cr} \pmatrix{{N'{\bi R}} &{\bf 0}\cr {\bf 0}^{T} &{N}'\cr} \pmatrix{{N{\bi I}} &-{\bf V}\cr {\bf 0}^{T} &{N}\cr} {\bi T}\cr \simeq &\pmatrix{{N{\bi R}} &{\bf V} - {{\bi R}{\bf V}}\cr {\bf 0}^{T} &{N}\cr} {\bi T}}] or [\eqalign{{\bi T}' =& {\;\bi T} \pmatrix{{N{\bi I}} &{\bf V}\cr {\bf 0}^{T} &{N}\cr} \pmatrix{{N'{\bi R}} &{\bf 0}\cr {\bf 0}^{T} &{N}'\cr} \pmatrix{{N{\bi I}} &-{\bf V}\cr {\bf 0}^{T} &{N}\cr} \cr\simeq &{\;\bi T} \pmatrix{{N{\bi R}} &{\bf V} - {{\bi R}{\bf V}}\cr {\bf 0}^{T} &{N}\cr}}] according to whether R and V are both defined in display space or both in data space. If the rotation is defined in display space and the position of the centre of rotation is defined in data space, then the first form of T′ must be used, in which V is first computed from [\pmatrix{{\bf V}\cr {N}\cr} = {\bi T} \pmatrix{{\bf U}\cr {W}\cr}] for a rotation centre at [\pmatrix{{\bf U}\cr {W}\cr}] in data space.

For continuous rotations defined in display space it is usually worthwhile to bring the centre of rotation to the origin of display space and leave it there, i.e. to omit the left-most factor in the first expression for T′. Incremental rotations can then be made by further rotational factors on the left without further attention to V. When continuous rotations are implemented by repeated multiplication of T by a rotation matrix, say thirty times a second for a minute or so, the orthogonality of the top-left partition of T may become degraded by accumulation of round-off error and this should be corrected occasionally by one of the methods of Section[link]

It is sometimes a requirement, depending on hardware capabilities, to affect a transformation in display space when access to data space is all that is readily available. In such a case [{\bi T}' = {\bi T}_{1} {\bi T} = {\bi TT}_{2},] where [{\bi T}_{1}] is the required alteration to the prevailing viewing transformation T and [{\bi T}_{2}] is the data-space equivalent, [\eqalignno{ {\bi T}_{2} = {\bi T}^{-1} {\bi T}_{1} {\bi T} &= \pmatrix{U{\bi R} &{\bf V}\cr {\bf 0}^{T} &{W}\cr}^{-1} \pmatrix{U_{1}{\bi R}_{1} &{\bf V}_{1}\cr {\bf 0}^{T} &{W}_{1}\cr} \pmatrix{U{\bi R} &{\bf V}\cr {\bf 0}^{T} &{W}\cr}\cr &\simeq \pmatrix{UU_{1}{\bi R}^{T}{\bi R}_{1}{\bi R} &{\bi R}^{T}(U_{1}{\bi R}_{1}{\bf V} + {W}{\bf V}_{1} - {\bi W}_{1}{\bf V})\cr {\bf 0}^{T} &U{W}_{1}\cr}.}]

An important special case is when [{\bi T}_{1}] is to effect a rotation about the origin of display space without change of scale, so that [{\bf V}_{1} = 0, U_{1} = W_{1} = {W}], for then [{\bi T}_{2} \simeq \pmatrix{U{\bi R}^{T}{\bi R}_{1}{\bi R} &{\bi R}^{T}({\bi R}_{1} - {\bi I}){\bf V}\cr {\bf 0}^{T} &U\cr}.]

If r is the required axis of rotation of [{\bi R}_{1}] in display space then the axis of rotation of [{\bi R}^{T}{\bi R}_{1}{\bi R}] in data space is [{\bf s} = {\bi R}^{T}{\bf r}] since [{\bi R}^{T}{\bi R}_{1}{\bi R}{\bf s} = {\bf s}]. This gives a particularly simple result if [{\bi R}_{1}] is to be a primitive rotation for then s is the relevant row of R, and [{\bi R}^{T}{\bi R}_{1}{\bi R}] can be constructed directly from this and the required angle of rotation. Inverse transformations

| top | pdf |

It is frequently a requirement to be able to identify a feature or position in data space from its position on the screen. Facilities for identifying an existing feature on the screen are in many instances provided by the manufacturer as a `hit' function which correlates the position indicated on the screen by the user (with a tablet or light pen) with the action of drawing and flags the corresponding item in the drawing internally as having been hit. In other instances it may be necessary to be able to indicate a position in data space independently of any drawn feature and this may be done by setting two or more non-parallel sight lines through the displayed volume and finding their best point of intersection in data space.

In Section[link] the relationship between data-space co-ordinates and screen-space coordinates was given as [{\bf S} = {\bi VUT}{\bf X}\hbox{;}] hence data-space coordinates are given by [{\bf X} = {\bi T}^{-1} {\bi U}^{-1} {\bi V}^{-1}{\bf S}.] A line of sight through the displayed volume passing through the point [\pmatrix{x\cr y\cr}] on the screen is the line joining the two position vectors [{\bi S} = \pmatrix{x &x\cr y &y\cr o &n\cr n &n\cr}] in screen-space coordinates, as in Section[link], from which the corresponding two points in data space may be obtained using [{\bi V}^{-1} \simeq \pmatrix{\displaystyle{2n\over r - l} &0 &0 &\displaystyle{-(r + l)\over (r - l)}\cr \noalign{\vskip3pt} 0 &\displaystyle{2n\over t - b} &0 &-\displaystyle{(t + b)\over (t - b)}\cr \noalign{\vskip3pt} 0 &0 &1 &0\cr \noalign{\vskip3pt} 0 &0 &0 &1\cr}] and [{\bi U}^{-1} \simeq \pmatrix{\displaystyle{R - L\over 2(S - E)} &0 &\displaystyle{-C(F - N)\over (F - E)(N - E)} &\displaystyle{(R + L)(N - E) - 2C(N - S)\over 2(N - E)(S - E)}\cr \noalign{\vskip3pt} 0 &\displaystyle{T - B\over 2(S - E)} &\displaystyle{-D(F - N)\over (F - E)(N - E)} &\displaystyle{(T + B)(N - E) - 2D(N - S)\over 2(N - E)(S - E)}\cr \noalign{\vskip3pt} 0 &0 &\displaystyle{-E(F - N)\over (F - E)(N - E)} &\displaystyle{N\over (N - E)}\cr \noalign{\vskip3pt} 0 &0 &\displaystyle{-V(F - N)\over (F - E)(N - E)} &\displaystyle{V\over (N - E)}\cr}] in the notation of Section[link], and [{\bi T}^{-1}] was given in Section[link] If orthographic projection is being used [({E} = - \infty)] then [{\bi U}^{-1}] simplifies to [{\bi U}'^{-1} \simeq \pmatrix{\displaystyle{R - L\over 2} &0 &0 &\displaystyle{R + L\over 2}\cr \noalign{\vskip3pt} 0 &\displaystyle{T - B\over 2} &0 &\displaystyle{T + B\over 2}\cr \noalign{\vskip3pt} 0 &0 &F - N &N\cr \noalign{\vskip3pt} 0 &0 &0 &V\cr}.] Each of these inverse matrices may be suitably scaled to suit the word length of the machine [Section[link] (iii[link])].

Having determined the end points of one sight line in data space the viewing transformation T may then be changed and the required position marked again through the screen in the new orientation. Each such operation generates a pair of points in data space, expressed in homogeneous form, with a variety of values for the fourth coordinate. Each such point must then be converted to three dimensions in the form [(X / W,\; Y / W,\; Z / W)], and for each sight line any (three-dimensional) point [{\bf p}_{A}] on the line and the direction [{\bf q}_{A}] of the line are established. For each sight line a rank 2 projector matrix [{\bi M}_{A}] of order 3 is formed as [{\bi M}_{A} = {\bi I} - {\bf q}_{A}{\bf q}_{A}^{T} / {\bf q}_{A}^{T} {\bf q}_{A}] and the best point of intersection of the sight lines is given by [\left({\textstyle\sum\limits_{a}} {\;\bi M}_{a}\right)^{-1} \left({\textstyle\sum\limits_{a}} {\;\bi M}_{a} {\bf p}_{a}\right),] to which three-vector a fourth coordinate of unity may be applied. The three-axis joystick

| top | pdf |

The three-axis joystick is a device which depends on compound transformations for its exploitation. As it is usually mounted it consists of a vertical shaft, mounted at its lower end, which can rotate about its own length (the Y axis of display space, Section[link]), its angular setting, ϕ, being measured by a shaft encoder in its mounting. At the top of this shaft is a knee-joint coupling to a second shaft. The first angle ϕ is set to zero when the second shaft is in some selected direction, e.g. normal to the screen and towards the viewer, and goes positive if the second shaft is moved clockwise when seen from above. The knee joint itself contains a shaft encoder, providing an angle, ψ, which may be set to zero when the second shaft is horizontal and goes positive when its free end is raised. A knob on the tip of the second shaft can then rotate about an axis along the second shaft, driving a third shaft encoder providing an angle θ. The device may then be used to produce a rotation of the object on the screen about an axis parallel to the second shaft through an angle given by the knob. The necessary transformation is then [\eqalign{ {\bi R} &= \pmatrix{\cos \varphi &0 &-\sin \varphi\cr 0 &1 &0\cr \sin \varphi &0 &\cos \varphi\cr} \pmatrix{1 &0 &0\cr 0 &\cos \psi &\sin \psi\cr 0 &-\sin \psi &\cos \psi\cr}\cr &\quad \times \pmatrix{\cos \theta &-\sin \theta &0\cr \sin \theta &\cos \theta &0\cr 0 &0 &1\cr} \pmatrix{1 &0 &0\cr 0 &\cos \psi &-\sin \psi\cr 0 &\sin \psi &\cos \psi\cr}\cr &\quad \times \pmatrix{\cos \varphi &0 &\sin \varphi\cr 0 &1 &0\cr -\sin \varphi &0 &\cos \varphi\cr}}] which is [\eqalign{ &\left(\matrix{c^{2}\psi s^{2}\varphi + (1 - c^{2}\psi s^{2}\varphi) c\theta &-s\psi c\psi s\varphi (1 - c\theta) - c\psi c\varphi s\theta\cr \noalign{\vskip3pt} -s\psi c\psi s\varphi (1 - c\theta) + c\psi c\varphi s\theta &s^{2}\psi + c^{2}\psi c\theta\cr \noalign{\vskip3pt} -c^{2}\psi s\varphi c\varphi (1 - c\theta) - s\psi s\theta &s\psi c\psi c\varphi (1 - c\theta) - c\psi s\varphi s\theta\cr}\right.\cr \noalign{\vskip5pt} &\left.\matrix{\phantom{-s\psi c\psi s\varphi (1 - c\theta) + c\psi c\varphi s\theta s^{2}\psi + c^{2}} &-c^{2}\psi s\varphi c\varphi (1 - c\theta) + s\psi s\theta\cr \noalign{\vskip3pt} &s\psi c\psi c\varphi (1 - c\theta) + c\psi s\varphi s\theta\cr \noalign{\vskip3pt} &c^{2}\psi c^{2}\varphi + (1 - c^{2}\psi c^{2}\varphi) c\theta\cr}\right)}] in which cos and sin are abbreviated to c and s, which is the standard form with [l = -\cos \psi \sin \varphi], [m = \sin \psi], [n = \cos \psi \cos \varphi]. Other useful rotations

| top | pdf |

If rotations in display space are to be controlled by trackerball or tablet then there are two measures available, an x and a y, which can define an axis of rotation in the plane of the screen and an angle θ. If x and y are suitably scaled coordinates of a pen on a tablet then the rotation [\pmatrix{\displaystyle{y^{2} + x^{2}c\over x^{2} + y^{2}} &\displaystyle{-xy(1 - c)\over x^{2} + y^{2}} &x\sqrt{x^{2} + y^{2}}\cr \noalign{\vskip3pt} \displaystyle{-xy(1 - c)\over x^{2} + y^{2}} &\displaystyle{x^{2} + y^{2}c\over x^{2} + y^{2}} &y\sqrt{x^{2} + y^{2}}\cr \noalign{\vskip3pt} -x\sqrt{x^{2} + y^{2}} &-y\sqrt{x^{2} + y^{2}} &c\cr}] with [c = \sqrt{1 - (x^{2} + y^{2}){^2}}] is about an axis in the xy plane (i.e. the screen face) normal to [(x,y)] and with [\sin \theta = x^{2} + y^{2}]. Applied repetitively this gives a quadratic velocity characteristic. Similarly, if an atom at [(x, y, z, w)] in display space is to be brought onto the z axis by a rotation with its axis in the xy plane the necessary matrix, in homogeneous form, is [\pmatrix{\displaystyle{x^{2}z + y^{2}r\over x^{2} + y^{2}} &\displaystyle{-xy(r - z)\over x^{2} + y^{2}} &-x &0\cr \noalign{\vskip3pt} \displaystyle{-xy(r - z)\over x^{2} + y^{2}} &\displaystyle{x^{2}r + y^{2}z\over x^{2} + y^{2}} &-y &0\cr\noalign{\vskip3pt} x &y &z &0\cr 0 &0 &0 &r\cr}] with [r = \sqrt{x^{2} + y^{2} + z^{2}}]. Symmetry

| top | pdf |

In Section[link] it was pointed out that it is usual to express coordinates for graphical purposes in Cartesian coordinates in ångström units or nanometres. Symmetry, however, is best expressed in crystallographic fractional coordinates. If a molecule, with Cartesian coordinates, is being displayed, and a symmetry-related neighbour is also to be displayed, then the data-space coordinates must be multiplied by [ \pmatrix{{\bi W} &{\bf T}\cr {\bf 0}^{T} &{W}\cr} \pmatrix{{\bi M} &{\bf 0}\cr {\bf 0}^{T} &{1}\cr} {\scr S}\ \pmatrix{{\bi M}^{-1} &{\bf 0}\cr {\bf 0}^{T} &{1}\cr} \pmatrix{{\bi W} &-{\bf T}\cr {\bf 0}^{T} &{W}\cr},] where [\pmatrix{{\bf T}\cr {W}\cr}] are the data-space coordinates of the crystallographic origin, M and [{\bi M}^{-1}] are as in Section[link] and [ \hbox{\scr S}] is a crystallographic symmetry operator in homogeneous coordinates, expressed relative to the same crystallographic origin.

For example, in [P2_{1}] with the origin on the screw dyad along b, [ {\scr S}\ = \pmatrix{-1 &0 &0 &0\cr 0 &1 &0 &{1\over 2}\cr 0 &0 &-1 &0\cr 0 &0 &0 &1\cr}] and [ \pmatrix{{\bi M} &{\bf 0}\cr {\bf 0}^{T} &{1}\cr} \ {\scr S}\ \ \pmatrix{{\bi M}^{-1} &{\bf 0}\cr {\bf 0}^{T} &{1}\cr} = \pmatrix{-1 &0 &0 &0\cr 0 &1 &0 &{1\over 2}b\cr 0 &0 &-1 &0\cr 0 &0 &0 &1\cr}.]

[ {\scr S}] comprises a proper or improper rotational partition, S, in the upper-left [3 \times 3] in the sense that [{\bi MSM}^{-1}] is orthogonal, and with the associated fractional lattice translation in the last column, with the last row always consisting of three zeros and 1 at the 4, 4 position. See IT A (2005[link], Chapters 5.2[link] and 8.1[link] ) for a fuller discussion of symmetry using augmented (i.e. [4 \times 4]) matrices. Modelling transformations

| top | pdf |

The two sections under this heading are concerned only with the graphical aspects of conformational changes. Determination of such changes is considered under Section[link] Rotation about a bond

| top | pdf |

It is a common requirement in molecular modelling to be able to rotate part of a molecule relative to the remainder about a bond between two atoms.

If four atoms are bonded 1–2–3–4 then the dihedral angle in the bond 2–3 is zero if the four atoms are cis planar, and a rotation in the 2–3 bond is, by convention (IUPAC–IUB Commission on Biochemical Nomenclature, 1970[link]), positive if, when looking along the 2–3 bond, the far end rotates clockwise relative to the near end. This is valid for either viewing direction. This sign convention, when applied to the R matrix of Section[link], leads to the following statement.

If one of the two atoms is selected as the near atom and the direction cosines are those of the vector from the near atom to the far atom, and if the matrix is to rotate material attached to the far atom (with the reference axes fixed), then a positive rotation in the foregoing sense is generated by a positive θ.

Rotation about a bond normally involves compounding R with translations in the manner of Section[link] Stacked transformations

| top | pdf |

A flexible molecule may require to be drawn in any of a number of conformations which are related to one another by, for example, rotations about single bonds, changes of bond angles or changes of bond lengths, all of which changes may be brought about by the application of suitable homogeneous transformations during the drawing of the molecule (Section[link]). With suitable organization, this may be done without necessarily altering the coordinates of the atoms in the coordinate list, only the transformations being manipulated during drawing.

The use of transformations in the manner shown below is straightforward for simply connected structures or structures containing only rigid rings. Flexible rings may be similarly handled provided that the matrices employed are consistent with the consequential constraints as described in Section[link], though this requirement may make real-time folding of flexible rings difficult.

Any simply connected structure may be organized as a tree with a node at each branch point and with an arbitrary number of sites of conformational change between one node and the next. We shall call such sites and their associated matrices `conformons'. The technique then depends on the stacking technique in which matrices are stored and later recovered in the reverse order of their storage.

One begins at some reference point deemed to be fixed in data space and at this point one stacks the prevailing viewing transformation. From this reference point one advances through the molecule along the structural tree and as each conformon is encountered its matrix is calculated. The product of the prevailing matrix with the conformon matrix is formed and stacked, and this product becomes the prevailing matrix. This product is constructed with the conformon matrix as a factor on the right, i.e. in data space as defined in Section[link], and is calculated using the coordinates of the molecule in their unmodified form, i.e. before any shape changes are brought about.

This progression leads eventually to an extremity of the tree. At this point drawing is commenced using the prevailing matrix and working backwards towards the fixed root, unstacking (or `popping') a matrix as each conformon is passed until a node is reached, which, in general, will occur only part way back to the root. On reaching such a node drawing is suspended and one advances along the newly found branch as before, stacking matrices, until another extremity is reached when drawing towards the root is resumed. This alternation of stacking matrices while moving away from the root and drawing and unstacking matrices while moving towards the root is continued until the whole tree is traversed.

This process is illustrated schematically in Fig.[link] for a simple tree with one node, numbered 1, and three conformons at a, b and c. One enters the tree with a current viewing transformation T and progresses upwards from the fixed lower extremity. When the conformon at a is encountered, T is stacked and the product [{\bi TM}_{a}] is formed. Continuing up the tree, at node 1 either branch may be chosen; we choose the left and, on reaching b, [{\bi TM}_{a}] is stacked and [{\bi TM}_{a}{\bi M}_{b}] is formed. On reaching the tip drawing down to b is done with this transformation, [{\bi TM}_{a}] is then unstacked and drawing continues with this matrix until node 1 is reached. The other branch is then followed to c whereupon [{\bi TM}_{a}] is again stacked and the product [{\bi TM}_{a}{\bi M}_{c}] is formed. From the tip down as far as c is drawn with this matrix, whereupon [{\bi TM}_{a}] is unstacked and drawing continues down to a, where T is unstacked before drawing the section nearest the root.


Figure | top | pdf |

Schematic representation of a simple branched-chain molecule with a stationary root and two extremities. The positions marked a, b and c are the loci of possible conformational change, here called conformons, and there is a single, numbered branch point.

With this organization the matrices associated with b and c are unaffected by changes in the conformation at a, notwithstanding the fact that changes at a alter the direction of the axis of rotation at b or c.

Two other approaches are also possible. One of these is to start at the tip of the left branch, replace the coordinates of atoms between b and the tip by [{\bi M}_{b}{\bf X}], and later replace all coordinates between the tip and a by [{\bi M}_{a}{\bf X}], with a similar treatment for the other branch. The advantage of this is that no storage is required for stacked matrices, but the disadvantage is that atoms near the tips of the tree have to be reprocessed for every conformon. It also modifies the stored coordinates, which may or may not be desirable.

The second alternative is to draw upwards from the root using T until a is reached, then using [{\bi TM}_{a}] until b is reached, then using [{\bi TM}'_{b}{\bi M}_{a}] to the tip, but in this formulation [{\bi M}'_{b}] must be based on the geometry that exists at b after the transformation [{\bi M}_{a}] has been applied to this region of the molecule, i.e. [{\bi M}'_{b}] is characteristic of the final conformation rather than the initial one. Drawing techniques

| top | pdf | Types of hardware

| top | pdf |

There are two main types of graphical hardware in use for interactive work, in addition to plotters used for batch work. These main types are raster and vector. In raster equipment the screen is scanned as in television, with a grid of points, called pixels, addressed sequentially as the scan proceeds. Associated with each pixel is a word of memory, usually containing something in the range of 1 to 24 bits per pixel, which controls the colour and intensity to be displayed. Many computer terminals have one bit per pixel (said to be `single-plane' systems) and these are essentially monochrome and have no grey scale. Four-plane systems are cheap and popular and commonly provide 4-bit by 4-bit look-up tables between the pixel memory and the monitor with one such table for each of the colours red, green and blue. If these tables are each loaded identically then 16 levels of monochrome grey scale are available, but if they are loaded differently 16 different colours are available simultaneously chosen from a total of 4096 possibilities. Four-plane systems are adequate for many applications where colour is used for coding, but are inadequate if colour is intended also to provide realism, where brilliance and saturation must be varied as well as hue. For these applications eight-plane systems are commonly used which permit 256 colours chosen from 16 million using three look-up tables, though the limitations of these can also be felt and full colour is only regarded as being available in 24-plane systems.

Raster-graphics devices are ideal for drawing objects represented by opaque surfaces which can be endowed with realistic reflecting properties (Max, 1984[link]) and they have been successfully used to give effects of transparency. They are also capable of representing shadows, though these are generally difficult to calculate (see Section[link]). Many devices of this type provide vectorization, area fill and anti-aliasing. Vectorization provides automatically for the loading of relevant pixels on a straight line between specified points. Area fill automatically fills any irregular pre-defined polygon on the screen with a uniform colour with the user specifying only the colour and one point within the polygon. Anti-aliasing is the term used for a technique which softens the staircase effect that may be seen on a line which runs at a small angle to a vertical or horizontal row of pixels.

The main drawback with this type of equipment is that it is slow compared to vector machines. Only relatively simple objects can be displayed with smooth rotation in real time as transformed coordinates have to be converted to pixel addresses and the previous frame needs to be deleted with each new frame unless it is known that each new frame will specify every pixel. However, the technology is advancing rapidly and these restrictions are already disappearing.

Vector machines, on the other hand, are specialized to drawing straight lines between specified points by driving the electron beam along such lines. No time is wasted on blank areas of the screen. Dots may be drawn with arbitrary coordinates, in any order, but areas, if they are to be filled, must be done with a ruling technique which is very seldom done. Images produced by vector machines are naturally transparent in that foreground does not obscure background, which makes them ideal for seeing into representations of molecular structure. Optimization of line drawings

| top | pdf |

A line drawing consisting of n line segments may be specified by anything from [(n + 1)] to 2n position vectors depending on whether the lines are end-to-end connected or independent. Appreciable gains in both processing time and storage requirements may be made in complicated drawings by arranging for line segments to be end-to-end connected as far as possible, and an algorithm for doing this is outlined below. For further details see Diamond (1984a[link]).

Supposing that a list of nodal points (atoms if a covalent skeleton is being drawn) exists within a computer with each node appearing only once and that the line segments to be drawn between them are already determined, then at each node there are, generally, both forward and backward connections, forward connections being those to nodes further down the list. A quantity D is calculated at each node which is the number of forward connections minus the number of backward connections. At the commencement of drawing, the first connected node in the list must have a positive D, the last must have a negative D, the sum of all D values must be zero and the sum of the positive ones is the number of strokes required to draw the drawing, a `stroke' being a sequence of end-to-end connected line segments drawn without interruption. The total number of position vectors required to specify the drawing is then the number of nodes plus the number of strokes plus the number of rings minus one.

Drawing should then be done by scanning the list of nodes from the top looking for a positive D (usually found at the first node), commencing a stroke at this node and decrementing its D value by 1. This stroke is continued from node to node using the specified connections until a negative D is encountered, at which point the stroke is terminated and the D value at the terminating node is incremented by 1. This is done even though this terminating node may also possess some forward connections, as the total number of strokes required is not minimized by keeping a stroke going as far as possible, but by terminating a stroke as soon as it reaches a node at which some stroke is bound to terminate.

The next stroke is initiated by resuming the scan for positive D values at the point in the node list where the previous stroke began. If this scan encounters a zero D value at a node which has not hitherto been drawn to, or drawn from, then the node concerned is isolated and not connected to any other, and such nodes may require to be drawn with some special symbol. The expression already given for the number of vectors required is valid in the presence of isolated nodes if drawing an isolated node is allowed one position vector, this vector not being counted as a stroke.

The number of strokes generated by this algorithm is sensitive to the order in which the nodes are listed, but if this resembles a natural order then the number of strokes generated is usually close to the minimum, which is half the number of nodes having an odd number of connections. For example, the letter E has six nodes, four of which have an odd number of connections, so it may be drawn with two strokes. Representation of surfaces by lines

| top | pdf |

The commonest means of representing surfaces, especially contour surfaces, is to consider evenly spaced serial sections and to perform two-dimensional contouring on each section. Repeating this on serial sections in two other orientations then provides a good representation of the surface in three dimensions when all such contours are displayed. The density is normally cited on a grid with submultiples of a, b and c as grid vectors, inverse linear interpolation being used between adjacent grid points to locate points on the contour. For vector-graphics applications it is expedient to connect such points with straight lines; some equipment may be capable of connecting them with splines though this is burdensome or impossible if real-time rotation of the scene is required. Precalculation of splines stored as short vectors is always possible if the proliferation of vectors is acceptable. For efficient drawing it is necessary for the line segments of a contour to be end-to-end connected, which means that it is necessary to contour by following contours wherever they go and not by scanning the grid. Algorithms which function in this way have been given by Heap & Pink (1969[link]) and Diamond (1982a[link]). Contouring by grid scanning followed by line connection by the methods of the previous section[link] would be possible but less efficient. Further contouring methods are described by Sutcliffe (1980[link]) and Cockrell (1983[link]).

For raster-graphics devices there is little disadvantage in using curved contours though many raster devices now have vectorizing hardware for loading a line of pixels given only the end points. For these devices well shaped contours may be computed readily, using only linear arithmetic and a grid-scanning approach (Gossling, 1967[link]). Others have colour-coded each pixel according to the density, which provides a contoured visual impression without performing contouring (Hubbard, 1983[link]). Representation of surfaces by dots

| top | pdf |

Connolly (Langridge et al., 1981[link]; Connolly, 1983a[link],b[link]) represents surfaces by placing dots on the surface with an approximately uniform superficial density. Connolly's algorithm was developed to display solvent-accessible surfaces of macromolecules and provides for curved concave portions where surface atoms meet. Pearl & Honegger (1983[link]) have developed a similar algorithm, based on a grid, which generates only convex portions which meet in cusps, but is faster to compute than the Connolly surface. Bash et al. (1983[link]) have produced a van der Waals surface algorithm fast enough to permit real-time changes to the structure without tearing the surface.

It has become customary to use a dot representation to display computed surfaces, such as the surface at a van der Waals radius from atomic centres, and to use lines to represent experimentally determined surfaces, especially density contours. Representation of surfaces by shading

| top | pdf |

Many techniques have been developed, mainly for raster-graphics devices, for representing molecular surfaces and these have been very well reviewed by Max (1984[link]).

The simplest technique in this class consists in representing each atom by a uniform disc, or high polygon, which can be colour-coded and area-filled by the firmware of the device. If such atoms are sorted on their z coordinate and drawn in order, furthest ones first, so that nearer ones partly or completely overwrite the further ones then the result is a simple representation of the molecule as seen from the front. This technique is fast and has its uses when a rapid schematic is all that is required. In one sense it is wasteful to process distant atoms when they are going to be overwritten by foreground atoms, but front-to-back processing requires the boundaries of visible parts of partially obscured atoms near the front to be determined before they can be painted or, alternatively, every pixel must be tested before loading to see if it is already loaded. Not only does this approach give a uniform rendering over the whole area of one atom, it also gives a boundary between overlapping atoms with almost equal z values which completes the circle of the nearer atom, though it should be an arc of an ellipse when the atoms are drawn with radii exceeding their covalent radii.

Greater realism is achieved by establishing a z buffer, which is an additional area of memory with one word per pixel, in which is stored the z value of the currently loaded feature in each pixel. Treatments which take account of the sphericity are then possible and correct arcs of intersection for interpenetrating spheres and more complicated entities arise naturally through loading a colour value into a pixel only if the z coordinate is less than that of the currently loaded value. This z buffer and the associated x, y coordinates should be in picture space or screen space rather than display space since only after the application of perspective can points with the same x / w and y / w coordinates obscure one another.

It is usual in such systems to vary the intensity of colour within one atom by darkening it towards the circumference on the basis of the z coordinate. Some systems augment this impression of sphericity by highlighting. The simplest form of highlighting is an extension of the uniform disc treatment in which additional, brighter discs, possibly off centre, are associated with each atom. More general highlighting (Phong, 1975[link]) is computed from four unit vectors, these being the normal to the surface, the direction to a light source, the direction to the viewer and the normalized vector sum of these last two. Intensity levels may then be set as the sum of three terms: a constant, a term proportional to the scalar product of the first two vectors (if positive) and a term proportional to a high power of the scalar product of the first and last vectors; the higher the power the glossier the surface appears to be. This final term normally adds a white term, rather than the surface colour, supposing the light source to be white.

Shadows may also be rendered to give even greater realism. In addition to the z buffer and (x, y) frame buffer a second z buffer for z′ values associated with x′ and y′ is also required. These coordinates are then related by [x' = x + \alpha z], [y' = y + \beta z], [z' = z]. The second buffer is a ray buffer since [x' y'] are the coordinates with which an illuminating ray passing through (xyz) passes through the [z = 0] plane, and z′, stored at x′, y′, records the depth at which this ray encounters material. Thus any two pixels [(x_{1}y_{1}z_{1})] and [(x_{2}y_{2}z_{2})] are on the same illuminating ray if their x′ and y′ values are equal and the one with smaller z′ shadows the other. Processing a pixel at [(x_{1}y_{1}z_{1})] therefore involves first determining its visibility on the basis of the z buffer, as before, then, whether or not it is visible, setting [z'_{1} = z_{1}] and considering the value of z′ currently stored at [x'y'], which we call [z'_{2}].

If [z'_{1}\lt z'_{2}] then [x_{1}y_{1}z_{1}] is in light and must be loaded accordingly. From [z'_{2}] we find the previously processed pixel [(x_{2}y_{2}z_{2})] which is now in shade and which was in light when originally processed, so that the colour value stored at [x_{2} y_{2}] needs to be altered unless the pixel at [x_{2} y_{2}] is now [(x_{2}y_{2}z_{3})] with [z_{3}\lt z_{2}], in which case the pixel [(x_{2}y_{2}z_{2})] which has now become shadowed by [(x_{1}y_{1}z_{1})] has, in the meantime, been obscured by [(x_{2}y_{2}z_{3})] which is not shadowed by [(x_{1}y_{1}z_{1})] and no change is therefore needed. In either event [z'_{1}] then replaces [z'_{2}].

If [z'_{1}\gt z'_{2}] then [(x_{1}y_{1}z_{1})], if visible, is in shade and must be coloured accordingly, and in this case [z'_{2}] is not superseded.

This shadowing scheme corresponds to illumination by a light source at infinity in picture space or, equivalently, with a z coordinate equal to that of the eye in display space. For its implementation x, y and z may be in any convenient coordinate system, e.g. pixel addresses, but if x and y are expressed with the range −1 to 1 and z with the range 0 to 1 corresponding to the window then they may be identified as the quantities [x / w, y / w] and [z/w] of picture space (Section[link]).

If, in the notation of Section[link], the light source is placed at (P, Q, E, V) in display space and a ray leaves it in the direction (p, q, r, V) then [x' = {p\over r} \cdot {2(S - E)\over (R - L)} + {2(S - E)(P - C)\over (N - E)(R - L)} + {2C - R - L\over R - L},] which varies only with beam direction, [\alpha = {2(S - E)(F - N)(P - C)\over (F - E)(N - E)(R - L)}] and similarly for y′ and β. Advanced hidden-line and hidden-surface algorithms

| top | pdf |

Hidden surfaces may be handled quite generally with the z-buffer technique described in the previous section[link] but this technique becomes very inefficient with very complicated scenes. Faster techniques have been developed to handle computations in real time (e.g. 25 frames s−1) on raster machines when both the viewpoint and parts of the environment are moving and substantial complexity is required. These techniques generally represent surfaces by a number of points in the surface, connected by lines to form panels. Many algorithms require these panels to be planar and some require them to be triangular. Of those that permit polygonal panels, most require the polygons to be convex with no re-entrant angles. Yet others are limited to cases where the objects themselves are convex. Some can handle interpenetrating surfaces, others exclude these. Some make enormous gains in efficiency if the objects in the scene are separable by the insertion of planes between them and degrade to lower efficiency if required, for example, to draw a chain. Some are especially suited to vector machines and others to raster machines, the latter capitalizing on the finite resolution of such systems. In all of these the basic entities for consideration are entire panels or edges, and in some cases vertices, point-by-point treatment of the entire surface being avoided until after all decisions are made concerning what is or is not visible.

All of these algorithms strive to derive economies from the notion of `coherence'. The fact that, in a cine context, one frame is likely to be similar to the previous frame is referred to as `frame coherence'. In raster scans line coherence also exists, and other kinds of coherence can also be identified. The presence of any form of coherence may enable the computation to be concerned primarily with changes in the situation, rather than with the totality of the situation so that, for example, computation is required where one edge crosses in front of another, but only trivial actions are involved so long as scan lines encounter the projections of edges in the same order.

The choice of technique from among many possibilities may even depend on the viewpoint if the scene has a statistical anisotropy. For example, the depiction of a city seen from a viewpoint near ground level involves many hidden surfaces. Distant buildings may be hidden many times over. The same scene depicted from an aerial viewpoint shows many more surfaces and fewer overlaps. This difference may swing the balance of advantage between an algorithm which sorts first on z or one which leaves that till last.

These advanced techniques have, so far, found little application in crystallography, but this may change. Ten such techniques are critically reviewed and compared by Sutherland et al. (1974[link]), and three of these are described in detail by Newman & Sproull (1973[link]).

3.3.2. Molecular modelling, problems and approaches

| top | pdf |

This section is concerned with software techniques which permit a set of atomic coordinates for a molecule to be generated ab initio, or to be modified, by reference to some chosen criterion, usually the electron density. Software that can change the shape of a molecule must be cognizant of the connectivity of the molecule and the bonding characteristics of atom types. It must also have means of regaining good stereochemistry if current coordinates are poor in this respect, or of performing its manipulations in ways which conserve essential stereochemical features. Approaches to some of these problems are outlined below. Many of the issues involved, including the topics outlined in Section[link] above, have been excellently reviewed by Hermans (1985[link]), though with little reference to graphical aspects, and a comprehensive treatment of modelling methods based on energies is given by Burkert & Allinger (1982[link]). Connectivity

| top | pdf |

It is necessary to distinguish three different kinds of connectivity, namely structural, logical and drawing connectivities. Structural connectivity consists of the specification of the chemical bonding of the molecule and, as such, is an absolute property of the molecule. Logical connectivity consists of the specification of what part or parts of a molecule are moved, and in what way, if some stereochemical feature is altered. Logical and structural connectivity are closely related and in simple cases coincide, but the distinction is apparent, for example, if the puckering of a five-membered ring is being modelled by permitting folding of the pentagon about a line connecting non-adjacent corners. This line is then a logical connection between two moving parts, but it is not a feature of the structural connectivity.

Drawing connectivity consists of a specification of the lines to be drawn to represent the molecule and often coincides with the structural connectivity. However, stylized drawings, such as those showing the α-carbon atoms of a protein, require to be drawn with lines which are features neither of the logical nor of the structural connectivity. Connectivity tables

| top | pdf |

The simplest means of storing connectivity information is by means of tables in which, for each atom, a list of indices of other atoms to which it is connected is stored. This approach is quite general; it may serve any type of molecular structure and permits structures to be traversed in a variety of ways. In this form, however, it is extravagant on storage because every connection is stored twice, once at each of the nodes it connects. It may, however, provide the starting material for the algorithm of Section[link] and its generality may justify its expense.

From such a list, lists of bonds, bond angles and dihedral angles may readily be derived in which each entry points to two, three or four atoms in the atom list. Lists of these three types form the basis of procedures which adjust the shape of a molecule to reduce its estimated potential energy (Levitt & Lifson, 1969[link]; Levitt, 1974[link]), and of search-and-retrieval techniques (Allen et al., 1979[link]).

Katz & Levinthal (1972[link]) discuss the explicit specification of structural connectivity in terms of a tree structure in which, for each atom, is stored a single pointer to the connected atom nearer to the root, virtual atoms being used to allow ring structures to be treated as trees. An algorithm is also presented which allows such a tree specification to be redetermined if an atom in the tree is newly chosen as the root atom or if the tree itself is modified.

Cohen et al. (1981[link]) have developed methods of handling connectivity in complicated fused- and bridged-ring systems. Implied connectivity

| top | pdf |

In cases where software is required to deal only with a certain class of molecule, it may be possible to exploit the characteristics of that class to define an ordering for lists of atoms such that connectivity is implied by the ordering of items in the list. Such an ordering may successfully define one of the three types of connectivity defined in Section[link] but it is unlikely to be able to meet the needs of all three simultaneously. It may also be at a disadvantage when required to deal with structures not part of the class for which it is designed. Within these limitations, however, it may be exceedingly efficient. Both proteins and nucleic acids are of a class which permits their logical connectivity to be specified entirely by list ordering, and the software described in Section[link] uses no connectivity tables for this purpose. The ordering rules concerned are given by Diamond (1976b[link]).

Drawing connectivity needs explicit specification in such a case; this may be done using only one 16-bit integer per atom, which may be stored as part of the atom list without the need of a separate table. This integer consists of two signed bytes which act as relative pointers in the list, positive pointers implying draw-to, negative pointers implying move-to. As each atom is encountered during drawing the right byte is read and utilized, and the two bytes are swapped before proceeding. This allows up to two bonds drawn to an atom and two bonds drawn from it, four in all, with a minimum of storage (Diamond, 1984a[link]).

Brandenburg et al. (1981[link]) handle drawing connectivity by enlarging the molecular list with duplicate atoms such that each is connected to the next in the list, but moves and draws still need to be distinguished.

Levitt (1971[link]) has developed a syntax for specifying structural connectivity implicitly from a list structure which is very general, though designed with biopolymers in mind, and the work of Katz & Levinthal (1972[link]) includes something similar. Modelling methods

| top | pdf |

Fundamental to the design of any software for molecular modelling are the choices of modelling criteria, and of parameterization. Criteria which may be adopted might include the fitting of electron density, the minimization of an energy estimate or the matching of complementary surfaces between a pair of molecules. Parameterizations which may be adopted include the use of Cartesian coordinates of atoms as independent variables, or of internal coordinates, such as dihedral angles, as independent variables with atomic positions being dependent on these. Systems designed to suit energetic criteria usually use Cartesian coordinates since all aspects of the structure, including bond lengths, must be treated as variables and be allowed to contribute to the energy estimate. Systems designed to fit a model to observed electron density, however, may adequately meet the stereochemical requirements of modelling on either parameterization, and examples of both types appear below.

Inputs to modelling systems vary widely. Systems intended for use mainly with proteins or other polymeric structures usually work with a library of monomers which the software may develop into a polymer. Systems intended for smaller molecules usually develop the molecular structure atom-by-atom rather than a residue at a time, and systems of this kind require a very general form of input. They may accept a list of atom types and coordinates if measurement and display of a known molecule is the objective, or they may accept `sketch-pad' input in the form of a hand-drawn two-dimensional sketch of the type conventional in chemistry, if the objective is the design of a molecule. Sketch-pad input is a feature of some systems with quantum-mechanical capabilities. Methods based on conformational variables

| top | pdf |

Suppose that t represents a vector from the current position of an atom in the model to a target position then (see Section[link], to first order, the observational equations are [t_{IA} = D_{IpA} \theta_{p} + v_{IA}] in which [\boldtheta] represents changes to conformational variables which may include dihedral angles, bond angles, bond lengths, and parameters determining overall position and orientation of the molecule as a whole. If every such parameter is included the model acquires 3n degrees of freedom for n atoms, in which case the methods of the next section[link] are more appropriate, but if bond lengths and some or all bond angles are being treated as constants then the above equation becomes the basis of the treatment. [D_{IPA} = {\partial r_{IA}\over \partial \theta_{P}} = \varepsilon_{Ijk} n_{jP} (r_{kA} - r_{kP})] in which [{\bf n}_{P}] is a unit vector defining the axis of rotation for an angular variable [\theta_{P}], [{\bf r}_{A}] and [{\bf r}_{P}] are position vectors of the atom A and the site of the parameter P, and [{\bf v}_{A}] represents a residual vector.

[\sigma = v_{ia} v_{ia}] is minimized by [{\boldtheta} = {\bi M}^{-1} {\bf V}] in which [\eqalign{ M_{PQ} &= D_{iPa}D_{iQa}\cr V_{P} &= D_{iPa}t_{ia}.}] More generally, if σ represents any scalar quantity which is to be minimized, e.g. an energy, then [\eqalign{ V_{P} &= -{1\over 2} {\partial \sigma\over \partial \theta_{P}}\cr M_{PQ} &= {1\over 2} {\partial^{2} \sigma\over \partial \theta_{P} \partial \theta_{Q}}.}]

It is beyond the scope of this chapter to review the methods available for evaluating [\boldtheta] from these equations. Difficulties may arise from two sources:

  • (i) Inversion of M may be difficult if M is large or ill conditioned and impossible if M is singular.

  • (ii) Successful evaluation of [{\bi M}^{-1}{\bf V}] will not minimize σ in one step if t is not linearly dependent on [\boldtheta] or, equivalently, [\partial^{2}\sigma / \partial \theta_{P}\partial \theta_{Q}] is not constant, and substantial changes [\boldtheta] are involved. Iteration is then necessary.

Difficulties of the first kind may be overcome by gradient methods, for example the conjugate gradient method without searches if M is available or with searches if it is not available, or they may be overcome by methods based on eigenvalue decompositions. If non-linearity is serious less dependence should be placed on M and gradient methods using searches are more valuable. In this connection Diamond (1966[link]) introduced a sliding filter technique which produced rapid convergence in extreme conditions of non-linearity. These topics have been reviewed elsewhere (Diamond, 1981[link], 1984b[link]) and are the subject of many textbooks (Walsh, 1975[link]; Gill et al., 1981[link]; Luenberger, 1984[link]).

Warme et al. (1972[link]) have developed a similar system using dihedral angles as variables and a variety of alternative optimization algorithms.

The modelling of flexible rings or lengths of chain with two or more fixed parts is sometimes held to be a difficulty in methods using conformational variables, although a simple two-stage solution does exist. The principle involved is the sectioning of the space of the variables into two orthogonal subspaces of which the first is used to satisfy the constraints and the second is used to perform the optimization subject to those constraints.

The algebra of the method may be outlined as follows, and is given in more detail by Diamond (1971[link], 1980a[link],b[link]). Parametric shifts [{\boldtheta}_{1}] which satisfy the constraints are solutions of [{\bf V}_{1} = {\bi M}_{1} {\boldtheta}_{1}] in which [{\bf V}_{1}] and [{\bi M}_{1}] depend only on the target vectors, [{\bf t}_{1}], of the atoms with constrained positions and on the corresponding derivatives. We then find a partitioned orthogonal matrix [({\bi A}_{1}{\bi B}_{1})] satisfying [({\bi A}_{1}{\bi B}_{1}) = ({\bi E}_{\lambda}{\bi E}_{0}) \pmatrix{{\bi R}_{\lambda} &{\bi 0}\cr {\bi 0} &{\bi R}_{0}\cr}] in which [{\bi E}_{\lambda}] are the eigenvectors of [{\bi M}_{1}] having positive eigenvalues, [{\bi E}_{0}] are those having zero eigenvalues, and [{\bi R}_{\lambda}] and [{\bi R}_{0}] are arbitrary orthogonal matrices. Then [\openup-3pt\displaylines{\eqalign{\pmatrix{{\bi A}_{1}^{T}\cr {\bi B}_{1}^{T}\cr} {\bf V}_{1} &= \pmatrix{{\bi A}_{1}^{T}\cr {\bi B}_{1}^{T}\cr} {\bi M}_{1}({\bi A}_{1}{\bi B}_{1}) \pmatrix{{\bi A}_{1}^{T}\cr {\bi B}_{1}^{T}\cr} {\boldtheta}_{1}\cr \noalign{\vskip3pt} &= \pmatrix{{\bi A}_{1}^{T}{\bi M}_{1}{\bi A}_{1} &{\bi 0}\cr {\bi 0} &{\bi 0}\cr} \pmatrix{{\bi A}_{1}^{T}\cr {\bi B}_{1}^{T}\cr} {\boldtheta}_{1}\cr} \cr  {\bi A}_{1}^{T}{\boldtheta}_{1} = ({\bi A}_{1}^{T}{\bi M}_{1}{\bi A}_{1})^{-1} {\bi A}_{1}^{T}{\bf V}_{1}}] in which the matrix to be inverted is positive definite. [{\bi A}_{1}], however, is rectangular so that multiplying on the left by [{\bi A}_{1}] does not necessarily serve to determine [{\boldtheta}_{1}], but we may write [{\boldtheta}_{1} = ({\bi A}_{1}{\bi B}_{1}) \pmatrix{{\boldvarphi}_{1}\cr {\boldpsi}_{1}\cr}] giving [\displaylines{\pmatrix{{\bi A}_{1}^{T}\cr {\bi B}_{1}^{T}\cr} {\bf V}_{1} = \pmatrix{{\bi A}_{1}^{T}{\bi M}_{1}{\bi A}_{1} &{\bi 0}\cr {\bi 0} &{\bi 0}\cr} \pmatrix{{\boldvarphi}_{1}\cr {\boldpsi}_{1}\cr}\cr \noalign{\vskip3pt} {\boldvarphi}_{1} = ({\bi A}_{1}^{T}{\bi M}_{1}{\bi A}_{1})^{-1} {\bi A}_{1}^{T}{\bf V}_{1}}] and [{\boldpsi}_{1}] is indeterminate and free to adopt any value. We therefore adopt [{\boldtheta}_{1} = {\bi A}_{1}{\boldvarphi}_{1} = {\bi A}_{1}({\bi A}_{1}^{T}{\bi M}_{1}{\bi A}_{1})^{-1} {\bi A}_{1}^{T}{\bf V},] which is the smallest vector of parametric shifts which will satisfy the constraints, and allow [{\boldpsi}_{1}] to be determined by the remaining observational equations in which the target vectors, t, are now modified to [{\bf t}_{2}] according to [{\bf t}_{2} = {\bf t} - {\bi D}_{2}{\boldtheta}_{1},] [{\bi D}_{2}] and [{\bf t}_{2}] being the derivatives and effective target vectors for the unconstrained atoms. We then solve [{\bf V}_{2} = {\bi M}_{2}{\boldtheta}_{2}] in which [{\boldtheta}_{2}] is required to be of the form [{\boldtheta}_{2} = {\bi B}_{1}{\boldpsi}_{1}] giving [{\boldtheta}_{2} = {\bi B}_{1} ({\bi B}_{1}^{T}{\bi M}_{2}{\bi B}_{1})^{-1} {\bi B}_{1}^{T}{\bf V}_{2}] and apply the total shifts [{\boldTheta} = {\boldtheta}_{1} + {\boldtheta}_{2}] to obtain a structure which is optimized within the restrictions imposed by the constraints.

It may happen that [{\bi B}_{1}^{T} {\bi M}_{2} {\bi B}_{1}] is itself singular because there are insufficient data in the vector [{\bf t}_{2}] to control the structure and the parametric shifts contained in [{\boldtheta}_{2}] fully. In this event the same process may be applied again, basing the solution for [{\boldtheta}_{2}] on [\openup3pt\pmatrix{{\bi A}_{2}^{T}\cr {\bi B}_{2}^{T}\cr} {\bi B}_{1}^{T}{\bi M}_{2}{\bi B}_{1} ({\bi A}_{2}{\bi B}_{2})] so that the vectors in [{\bi B}_{2}] represent the degrees of freedom which remain uncommitted. This method of application of constraints by subspace sectioning may be nested to any depth and is completely general.

A valid matrix [{\bi A}_{1}] may be found from [{\bi M}_{1}] by using the fact that the columns of [{\bi M}_{1}] are all linear combinations of the columns of [{\bi E}_{\lambda}] and are void of any contribution from [{\bi E}_{0}]. It follows that [{\bi A}_{1}] may be found by using the columns of [{\bi M}_{1}] as priming vectors in the Gram–Schmidt process [Section[link] (i[link])] until the normalizing step involves division by zero. [{\bi A}_{1}] is then complete if all the columns of [{\bi M}_{1}] have been tried. [({\bi A}_{1}{\bi B}_{1})] may then be completed by using arbitrary vectors as primers.

Manipulation of a ring of n atoms may be achieved by treating it as a chain of [(n + 2)] atoms [having [(n + 1)] bond lengths, n bond angles and [(n - 1)] dihedral angles] in which atom 1 is required to coincide with atom [(n + 1)] and atom 2 with [(n + 2)]. [{\bf t}_{1}] then contains two vectors, namely the lack-of-closure vectors at these points, and is typically zero. [{\bi A}_{1}] is then found to have five columns corresponding to the five degrees of freedom of two points of fixed separation; [\boldtheta_{1}] contains only zeros if the ring is initially closed, and contains ring-closure corrections if, through non-linearity or otherwise, the ring has opened. [{\bi B}_{1}] contains [(p - 5)] columns if the chain of [(n + 2)] points has p variable parameters. It follows, if bond lengths and bond angles are treated as constants, that the seven-membered ring is the smallest ring which is flexible, that the six-membered ring (if it can be closed with the given bond angles) has no flexibility (though it may have discrete alternatives) and that it may be impossible to close a five-membered ring. Therefore some variation of bond angles and/or bond lengths is essential for the modelling of flexible five- and six-membered rings. Treating the ring as a chain of [(n + 1)] atoms is less satisfactory as there is then no control over the bond angle at the point of ring closure.

A useful concept for the modelling of flexible five-membered rings with near-constant bond angles is the concept of the pseudorotation angle P, and amplitude [\theta_{m}], for which the jth dihedral angle is given by [\theta_{j} = \theta_{m} \cos \left(P + {4\pi j\over 5}\right).] This formulation has the property [\textstyle{\sum}_{j = 0}^{4} \theta_{j} = 0], which is not exactly true; nevertheless, [\theta_{j}] values measured from observed conformations comply with this formulation within a degree or so (Altona & Sundaralingam, 1972[link]).

Software specialized to the handling of condensed ring systems has been developed by van der Lieth et al. (1984[link]) (Section[link]) and by Cohen et al. (1981[link]) (Section[link]). Methods based on positional coordinates

| top | pdf |

Modelling methods in which atomic coordinates are the independent variables are mathematically simpler than those using angular variables especially if the function to be minimized is a quadratic function of interatomic distances or of distances between atoms and fixed points. The method of Dodson et al. (1976[link]) is representative of this class and it may be outlined as follows. If d is a column vector containing ideal values of the scalar distances from atoms to fixed target points or to other atoms, and if l is a column vector containing the prevailing values of these quantities obtained from the model, then [{\bf d} = {\bf l} + {\bi D}\bolddelta {\bf x} + \boldvarepsilon ] in which the column matrix [{\bolddelta}{\bf x}] contains alterations to the atomic coordinates, [\boldvarepsilon] contains residual discrepancies and D is a large sparse rectangular matrix containing values of [\partial l/\partial x], of which there are not more than six non-zero values on any row, consisting of direction cosines of the line of which l is the length. [\boldvarepsilon^{T}{\bi W} \boldvarepsilon] is then minimized by setting [{\bi D}^{T}{\bi W} ({\bf d} - {\bf l}) = {\bi D}^{T}{\bi WD}\bolddelta {\bf x},] which they solve by the method of conjugate gradients without searches. This places reliance on the linearity of the observational equations (Diamond, 1984b[link]). It also works entirely with the sparse matrix [{\bi W}^{1/2}{\bi D}], the dense matrix [{\bi D}^{T}{\bi WD}], and its inverse, being never calculated.

The method is extremely efficient in annealing a model structure for which an initial position for every atom is available, especially if the required shifts are within the quasi-linear region, but is less effective when large dihedral-angle changes are involved or when many atoms are to be placed purely by interpolation between a few others for which target positions are available. Interbond angles are controlled by assigning d values to second-nearest-neighbour distances; this is effective except for bond angles near 180° so that, in particular, planar groups require an out-of-plane dummy atom to be included which has no target position of its own but does have target values of distances between itself and atoms in the planar group. The method requires a d value to be supplied for every type of nearest- and next-nearest-neighbour distance in the structure, of which there are many, together with W values which are the inverse variances of the distances concerned as assessed by surveys of the corresponding distances in small-molecule structures, or from estimates of their accuracy, or from estimates of accuracy of the target positions.

Hermans & McQueen (1974[link]) published a similar method which differs in that it moves only one atom at a time, in the environment of its neighbours, these being considered fixed while the central atom is under consideration. This is inefficient in the sense that in any one cycle one atom moves only a small fraction (∼3%) of the distance it will ultimately be required to move, but individual atom cycles are so cheap and simple that many cycles can be afforded. The method was selected for inclusion in Frodo by Jones (1978[link]) (Section[link]) and is an integral part of the GRIP system (Tsernoglou et al., 1977[link]; Girling et al., 1980[link]) (Section[link]) for which it was designed. Approaches to the problem of multiple minima

| top | pdf |

Modelling methods which operate by minimizing an objective function of the coordinates (whether conformational or positional) suffer from the fact that any realistic objective function representing the potential energy of the structure is likely to have many minima in the space of the variables for any but the simplest problems. No general system has yet been devised that can ensure that the global minimum is always found in such cases, but we indicate here two approaches to this problem.

The first approach uses dynamics to escape from potential-energy minima. Molecular-mechanics simulations allow each atom to possess momentum as well as position and integrate the equations of motion, conserving the total energy. By progressively removing energy from the simulation by scaling down the momentum vectors some potential-energy minimum may be found. Conversely, a minimization of potential energy which has led to a minimum thought not to be the global minimum may be continued by introducing atomic momenta sufficient to overcome potential-energy barriers between minima, and subsequently attenuate the momenta again. In this way a number of minima may be found (Levitt & Warshel, 1975[link]). It is equivalent to initializing a potential-energy minimization from a number of different conformations but it has the property that the minima so found are separated by energy barriers for which an upper limit is known so that the possibility exists of exploring transition pathways.

A second approach (Purisima & Scheraga, 1986[link]) is relatively new. If the objective function to be minimized can be expressed in terms of interatomic distances, and if each atom is given coordinates in a space of [n - 1] dimensions for n atoms, then a starting structure may be postulated for which the interatomic distances all take their ideal values and the objective function is then necessarily at an absolute minimum. This multidimensional structure is then projected into a space of fewer dimensions, within which it is again optimized with respect to the objective function. The dimensionality of the model is thus progressively reduced until a three-dimensional model is attained at a low energy. This means that the minimum so attained in three dimensions is approached from beneath, having previously possessed a lower value in a higher-dimensional space. This, in itself, does not guarantee that the three-dimensional minimum-energy structure so found is at the global minimum, but it is not affected by energy barriers between minima in the same way, and it does appear to reach very low minima, and frequently the global one. Because it is formulated entirely in terms of interatomic distances it offers great promise for modelling molecules on the basis of data from nuclear magnetic resonance.

3.3.3. Implementations

| top | pdf |

In this section the salient characteristics of a number of systems are described. Regrettably, it cannot claim to be a complete guide to all existing systems, but it probably describes a fairly representative sample. Some of these systems have arisen in academia and these are freely described. Some have arisen in or been adopted by companies which now market them, and these are described by reference to the original publications. Other marketed systems for which originators' published descriptions have not been found are not described. Yet other systems have been developed, for example, by companies within the chemical and pharmaceutical industries for their own use, and these have generally not been described in what follows since it is assumed that they are not generally available, even where published descriptions exist.

Software concerned especially with molecular dynamics has not been included unless it also provides static modelling capability, since this is a rapidly growing field and it has been considered to be beyond the intended scope of this chapter. Systems for which outline descriptions have already been given (Levitt & Lifson, 1969[link]; Levitt, 1974[link]; Diamond, 1966[link]; Warme et al., 1972[link]; Dodson et al., 1976[link]; Hermans & McQueen, 1974[link]) are not discussed further.

For some of the earliest work Levinthal (1966[link]) still makes interesting reading and Feldmann (1976[link]) is still an excellent review of the technical issues involved. The issues have not changed, the algorithms there described are still valuable, only the manner of their implementation has moved on as hardware has developed. A further review of the computer generation of illustrations has been given by Johnson (1980[link]). Excellent bibliographies relating to these sections have been given by Morffew (1983[link], 1984[link]), which together contain over 250 references including their titles.

The following material is divided into three sections. The first is concerned primarily with display rather than modelling though some of these systems can modify a model, the second is concerned with molecular modelling with reference to electron density and can develop a model ab initio, and the third is concerned with modelling with reference to other criteria.

Where software names are known to be acronyms constructed from initial letters, or where the original authors have used capitals, the names are capitalized here. Otherwise names are lower case with an initial capital.

While it is recognised that many of the systems here described are now of mainly historical interest, most have been retained for the second edition, some have been updated and some new paragraphs have been added. Systems for the display and modification of retrieved data

| top | pdf |

One of the earliest systems designed for information retrieval and display was that described by Meyer (1970[link], 1971[link]) which used television raster technology and enabled the contents of the Brookhaven Protein Data Bank (Meyer, 1974[link]; Bernstein et al., 1977[link]) to be studied visually by remote users. It also enabled a rigid two-ring molecule to be solved from packing considerations alone (Hass et al., 1975[link]; Willoughby et al., 1974[link]). Frames for display were written digitally on a disk and the display rate was synchronized to the disk rotation. With the reduction in the cost of core storage, contemporary systems use large frame buffer memories thus avoiding synchronization problems and permitting much richer detail than was possible in 1970. A majority of the systems in this section use raster techniques which preclude real-time rotation except for relatively simple drawings, though GRAMPS is an exception (O'Donnell & Olson, 1981[link]; Olson, 1982[link]) (Section[link]). ORTEP

| top | pdf |

This program, the Oak Ridge Thermal Ellipsoid Program, due to Johnson (1970[link], 1976[link]) was developed originally for the preparation of line drawings on paper though versions have since been developed to suit raster devices with interactive capability.

The program draws molecules in correct perspective with each atom represented by an ellipsoid which is the equi-probability surface for the atomic centre, as determined by anisotropic temperature factor refinement, the principal axes of which are displayed. Bonds are represented by cylindrical rods connecting the atoms which in the drawing are tapered by the perspective.

In line-drawing versions the problem of hidden-line suppression is solved analytically, whereas the later versions for raster devices draw the furthest elements of the picture first and either overwrite these with nearer features of the scene if area painting is being done or use the nearer features as erase templates if line drawings are being made. Feldmann's system

| top | pdf |

R. J. Feldmann and co-workers (Feldmann, 1983[link]) at the National Institutes of Health, Bethesda, Maryland, USA, were among the first to develop a suite of programs to display molecular structure using colour raster-graphics techniques. Their system draws with coloured shaded spheres, usually with one sphere to represent each atom, but alternatively the spheres may represent larger moieties like amino acids or whole proteins if lower-resolution representations are required. These workers have made very effective use of colour. Conventionally, oxygens have been modelled in red, but this system allows charged oxygens to be red and uncharged ones to be pink, with a similar treatment in blue for charged and uncharged nitrogens. By such means they have been able to give immediacy to the hydrophobic and electrostatic properties of molecular surfaces, and have used these characteristics effectively in studies of the binding possibilities of benzamidine derivatives to trypsin (Feldmann et al., 1978[link]).

The algorithm developed by Porter (1978[link]) for shading spheres to be darkened near their peripheries also computes the proper appearance of the line of intersection of two spheres wherever interpenetration occurs, in contrast to some simpler systems which draw a complete disc for whichever sphere is forward of the other. Provided that all opaque spheres are drawn first, the system is also capable of representing transparent spheres by darkening the colour of the existing background inside, and especially near the edge of, discs representing transparent foreground spheres.

Other systems that produce space-filling pictures of a similar general character have been produced by Motherwell (1978[link]), by Sundaram & Radhakrishnan (1979[link]) and by Lesk (next section[link]). Lesk & Hardman software

| top | pdf |

The complexity of macromolecules is a formidable obstacle to perceiving the basic features of their construction and the stylized drawings produced by this software following the artistry of Richardson (1977[link], 1981[link], 1985[link]) enables the internal organization of such molecules to be appreciated readily. The software is capable of mixing several styles of representation, among them the Richardson style of cylinders for α-helices, arrows for β-strands and ribbons for less-organized regions, or the creased-ribbon technique for the whole chain, or a ball-and-stick representation of atoms and bonds, or space-filling spheres. All these styles are available simultaneously in a single picture with depth cueing, colour and shading, and hidden-feature suppression as appropriate. It is also able to show a stylized drawing of a complete molecule together with a magnified part of it in a more detailed style. See Lesk & Hardman (1982[link], 1985[link]). GRAMPS

| top | pdf |

This system, due to O'Donnell & Olson (O'Donnell & Olson, 1981[link]; Olson, 1982[link]) provides a high-level graphics language and its associated interpretive software. It provides a general means of defining objects, drawable by line drawings, in such a way that these may be logically connected in groups or trees using a simple command language. Such a system may, for example, define a subunit protein of an icosahedral virus and define icosahedral symmetry, in such a way that modification of one subunit is expressed simultaneously in all subunits whilst preserving the symmetry, and simultaneously allowing the entire virus particle to be rotated. Such logical and functional relationships are established by the user through the medium of the GRAMPS language at run time, and a great diversity of such relationships may be created. The system is thus not limited to any particular type of structure, such as linear polymers, and has proved extremely effective as a means of providing animation for the production of cine film depicting viral and other structures. GRAMPS runs on all Silicon Graphics workstations under IRIX 4.0 or above. Takenaka & Sasada's system

| top | pdf |

Takenaka & Sasada (1980[link]) have described a system for the manipulation and display of molecular structures, including packing environments in the crystal, using a minicomputer loosely coupled to a mainframe. Their system is also capable of model building by the addition of groups of one or more atoms with a facility for monitoring interaction distances while doing so. MIDAS

| top | pdf |

This system, due to Langridge and co-workers (Gallo et al., 1983[link]; Ferrin et al., 1984[link]) is primarily concerned with the display of existing structures rather than with the establishment of new ones, but it may modify such structures by bond rotations under manual control. It is of particular value in the study of molecular interactions since two or more molecules may be manipulated simultaneously and independently. Visual docking of molecules is greatly facilitated by the display of van der Waals surfaces, which may be computed in real time so that the turning of a bond in the underlying structure does not tear the surface (Bash et al., 1983[link]). Insight

| top | pdf |

This system, originally due to Dayringer et al. (1986[link]), has a functionality similar to MIDAS. It has been replaced by Insight II (current version 2.3.5). It appears to be well suited to the study of intermolecular relationships in docking and in structural comparisons, and it is able to make modifications to structures. Objects for display may be molecular or non-molecular, the former having an atomic substructure and the latter consisting of a vector list which may not be subdivided into referrable components. Map fitting with the current version has been reported. PLUTO

| top | pdf |

PLUTO was developed by Motherwell (1978[link]) at the Cambridge Crystallographic Data Centre (CCDC) for the display of molecular structures and crystal-packing diagrams, including an option for space-filling model style with shadowing. The emphasis was on a free format command and data structure, and the ability to produce ball-and-spoke drawings with line shadowing suitable for reproduction in journal publication. Many variant versions have been produced, with essentially the 1978 functionality, its popularity deriving from its ease of use and the provision of default options for establishing connectivity using standard bonding radii. It was distributed as part of the CCDC software associated with the Cambridge Structural Database, with an interface for reading entries from the database.

In 1993 Motherwell and others at the CCDC added an interactive menu and introduced colour and PostScript output. New features were introduced to allow interactive examination of intermolecular contacts, particularly hydrogen-bonded networks, and sections through packing diagrams (Cambridge Structural Database, 1994[link]). MDKINO

| top | pdf |

This system, due to Swanson et al. (1989[link]), provides for the extraction and visualization of selected regions from molecular-dynamics simulations. It permits stereo viewing, interactive geometric interrogation and both forwards and backwards display of motion. Molecular-modelling systems based on electron density

| top | pdf |

Systems described in this section require real-time rotation of complicated transparent scenes and all used vector-graphics technology in their original implementations for that reason, though many are now available for raster machines. In every case the graphics are the means of communication between the user and software possessing high functionality, capable of building a representation of a molecule ab initio and to alter it, change its shape and position it optimally in relation to an electron-density map, with due attention being paid to stereochemical considerations, by one or more of several approaches. CHEMGRAF

| top | pdf |

Katz & Levinthal (1972[link]) have developed a powerful modelling and display system for macromolecules known as CHEMGRAF. This system permits the definition of many atom types which includes bonding specifications, so that, for example, four types of carbon atom are included in the basic list and others may be added. A molecular fragment with an unsatisfied valency (by which it might later be attached to another such group) would have that feature represented by a `vanishing virtual' atom which removes the need for any organizational distinction between such fragments and complete molecules. Fragments, such as amino-acid residues, may be assembled from atoms, and molecules may be assembled from atoms and/or from such fragments invoked by name, by the superposition and elimination of the relevant vanishing virtuals. The assembly process includes the development of a connectivity tree for the molecule and provision is made for the `turning' or reconstruction of such trees if the combination of such fragments redefines the root atom of one or more of the fragments. The system also provides for ring closure. Model building initially uses fixed bond lengths and angles, varying only the dihedral angles in single bonds, but has a library of preformed rings which could not otherwise be modelled on the simple basis. The results of such modelling may then be subjected to an energy-minimization routine using a steepest-descent method in the space of the dihedral angles and referring to the Lennard–Jones potential for non-bonded atom pairs. Atoms are first sorted into contiguous cubes so that all neighbours of any atom may be found by searching not more than 27 cubes.

The system is also capable of modelling by reference to electron density either by the translation and rotation of molecular fragments and the rotation of rotatable bonds within them or by the automatic linking of peaks in an electron-density map which are separated by less than, say, 1.8 Å, which is an important aid to interpretation when the resolution is sufficiently high. GRIP

| top | pdf |

This system, developed by Professor F. P. Brooks, Dr W. V. Wright and associates at the University of North Carolina, Chapel Hill, NC, USA, was designed for biopolymers and was the first to enable a protein electron-density map to be interpreted ab initio without the aid of mechanical models (Tsernoglou et al., 1977[link]). Girling et al. (1980[link]) give a more recent example of its use.

In its 1975 version GRIP is a three-machine system. Centrally there is a minicomputer which receives inputs from the user and controls a vector display with high-speed matrix-multiplication capability. The third machine is a mainframe computer with high-speed communication with the minicomputer.

The system develops a polymer chain from a library of monomers and manipulates it through bond rotations or free rotations of fragments explicitly specified by the user, with the aid of dials which may be coupled to bonds for the purpose. Bond rotations in the main chain either rotate part of the molecule relative to the remainder, which may have undesirable long-range effects, or the scope of the rotation is artificially limited with consequential discontinuities arising in the chain. Such discontinuities are removed or alleviated by the mainframe computer using the method of Hermans & McQueen (1974[link]), which treats atomic position vectors, rather than bond rotations, as independent variables.

The system made pioneering use of a two-axis joystick to control orientation and a three-translation joystick to control position. Barry, Denson & North's systems

| top | pdf |

These systems (Barry & North, 1971[link]; North et al., 1981[link]; North, 1982[link]) are examples of pioneering work done with minicomputers before purpose-built graphics installations became widespread; examples of their use are given by Ford et al. (1974[link]), Potterton et al. (1983[link]) and Dodson et al. (1982[link]). They have the ability to develop a polymer chain in sections of several residues, each of which may subsequently be adjusted to remove any misfit errors where the sections overlap. Manipulations are by rotation and translation of sections and by bond rotations within sections. These movements are directly controlled by the user, who may simultaneously observe on the screen the agreement with electron density, or calculated estimates of potential or interaction energy, or a volume integral of the product of observed and model densities, or predicted shifts of proton magnetic resonance spectra. Thus models which are optimal by various criteria may be constructed, but there is no optimizer directly controlling the rotational adjustments which are determined by the user.

One of the earliest applications of them (Beddell, 1970[link]) was in the fitting of substrate molecules to the active site of lysozyme using difference electron densities; however, the systems also permitted the enzyme–substrate interaction to be studied simultaneously and to be taken into account in adjusting the model. MMS-X

| top | pdf |

The Molecular Modelling System-X (MMS-X) is a system of purpose-built hardware developed by Barry, Marshall and others at Washington University, St Louis. Associated with it are several sets of software. The St Louis software consists of a suite of programs rather than one large one and provides for the construction of a polymer chain in helical segments which may be adjusted bodily to fit the electron density, and internally also if the map requires this too. Non-helical segments are built helically initially and unwound by user-controlled rotations in single bonds. The fitting is done to visual criteria. An example of the use of this system is given by Lederer et al. (1981[link]).

Miller et al. (1981[link]) have described an alternative software system for the same equipment. Functions invoked from a keyboard allow dials to be coupled to dihedral angles in the structure. Their system communicates with a mainframe computer which can deliver small blocks of electron density to be contoured and stored locally by the graphics system; this provides freedom of choice of contour level at run time. An example of the use of this system is given by Abad-Zapatero et al. (1980[link]). Texas A&M University system

| top | pdf |

This system (Morimoto & Meyer, 1976[link]), a development of Meyer's earlier system (Section[link]), uses vector-graphics technology and a minicomputer and is free of the timing restrictions of the earlier system. The system allows control dials to be dynamically coupled by software to rotations or translations of parts of the structure, thus permitting the re-shaping or re-positioning of the model to suit an electron-density map which may be contoured and managed by the minicomputer host. The system may be used to impose idealized geometry, such as planar peptides in proteins, or it may work with non-idealized coordinates.

The system was successfully applied to the structures of rubredoxin and the extracellular nuclease of Staphylococcus aureus (Collins et al., 1975[link]) and to binding studies of sulfonamides to carbonic anhydrase (Vedani & Meyer, 1984[link]). In addition, two of the first proteins to be constructed without the aid of a `Richards' Box' were modelled on this system: monoclinic lysozyme in 1976 (Hogle et al., 1981[link]) and arabinose binding protein in 1978 (Gilliland & Quiocho, 1981[link]). Bilder

| top | pdf |

This system (Diamond, 1980a[link],c[link], 1982b[link]) runs on a minicomputer independent of any mainframe. It builds a polymer chain from a library of residues and adapts it by internal rotations and overall positioning in much the same way as previous systems described in this section. Like them, it can provide user-controlled bond rotations, but its distinctive feature is that it has an optimizer within the minicomputer which will determine optimal combinations of bond rotations needed to meet the user's declared objectives. Such objectives are normally target positions for atoms set by the user by visual reference to the density, using the method of Section[link], but they may include target values for angles. These latter may either declare a required shape that is to take precedence over positional requirements, which are then achieved as closely as the declared shape allows, or they may be in least-squares competition with the positional requests. The optimizer also recognizes the constraints imposed by chain continuity and enables an internal section of the main chain to be modified without breaking its connection to the rest of the molecule. Similar techniques also allow ring systems to adopt various conformations, by bond rotation, without breaking the ring, simultaneously permitting the ring to have target positions. The optimizer is unperturbed by under-determined situations, providing a minimum-disturbance result in such cases. All these properties of the optimizer are generated without recourse to any `special cases' by a generalization of the subspace section technique which was used to maintain chain continuity in a `real-space-refinement' program (Diamond, 1971[link]). This is based entirely on the rank of the normal matrix that arises during optimization, which may serve to satisfy a constraint such as chain continuity or ring closure and simultaneously to establish what degrees of freedom remain to be controlled by other criteria. In Bilder this is achieved without establishing eigenvalues or eigenvectors. The method is described in outline in Section[link] and in detail by Diamond (1980a[link],b[link]).

The angular variables used normally comprise all single bonds but may include others, such as the peptide bond with or without a target of 180°. Thus this bond may be completely rigid, elastic, or completely free. Any interbond angles may also be parameterized but at some cost in storage. The normal mode of working is to develop a single chain for the entire length of the molecule, but if cumulative error makes fitting difficult a fresh chain may be started at any stage. Bilder may itself reconnect such chains at a later stage.

Construction and manipulation operates on a few residues at a time within the context of a polymer chain, but any or all of the rest of the molecule, or other molecules, may be displayed simultaneously.

Contouring is done in advance to produce a directoried file of contoured bricks of space, each brick containing up to 20 independently switchable elements which need not all be from the same map. Choice of contour level and displayed volume is thus instantaneous within the choices prepared.

The system is menu driven from a tablet, only file assignments and the like requiring the keyboard, and it offers dynamic parallax as an aid to 3D perception (Diamond et al., 1982[link]). Bloomer et al. (1978[link]), Phillips (1980[link]), and Evans et al. (1981[link]) give examples of its use. Frodo

| top | pdf |

This system, due to Jones (Jones, 1978[link], 1982[link], 1985[link]; Jones & Liljas, 1984[link]), in its original implementation was a three-machine system comprising graphics display, minicomputer and mainframe, though more recent implementations combine the last two functions in a `midi'. Its capabilities are similar to those of Bilder described above, but its approach to stereochemical questions is very different. Where Bilder does not allow an atom to be moved out of context (unless it comprises a `chain' of one atom) Frodo will permit an atom or group belonging to a chain to be moved independently of the other members of the chain and then offers regularization procedures based on the method of Hermans & McQueen (1974[link]) to regain good stereochemistry. During this regularization, selected atoms may be fixed, remaining atoms then adjusting to these. A peptide, for example, may be inverted by moving the carbonyl oxygen across the peptide and fixing it, relying on the remaining atoms to rearrange themselves. (Bilder would do the equivalent operation by cutting the chain nearby, turning the peptide explicitly, reconnecting the chain and optimizing to regain chain continuity.) The Frodo approach is easy to use especially when large displacements of an existing structure are called for, but requires that ideal values be specified for all bond lengths, angles and fixed dihedrals since the system may need to regain such values in a distorted situation. Bilder, in contrast, never changes such features and so need not know their ideal values.

Frodo may work either with consecutive residues of a polymer chain, useful for initial building, or with a volume centred on a chosen position, which is ideal for adjusting interacting side chains which are close in space but remote in sequence.

In recent implementations Frodo can handle maps both in density grid form and in contour form and permits on-line contouring. It has also been developed (Jones & Liljas, 1984[link]) to allow the automatic adjustment of the position and orientation of small rigid groupings by direct reference to electron density in the manner of Diamond (1971[link]) but without the maintenance of chain continuity, which is subsequently reintroduced by regularization.

Horjales and Cambillau (Cambillau & Horjales, 1987[link]; Cambillau et al., 1984[link]) have also provided a development of Frodo which allows the optimization of the interaction of a ligand and a substrate with both molecules being treated as flexible. Guide

| top | pdf |

Brandenburg et al. (1981[link]) have described a system which enables representations of macromolecules to be modified with reference to electron density. Such modifications include rotation about single bonds under manual control, or the movement with six degrees of freedom, also under manual control, of any part or parts of the molecule relative to the remainder. The latter operation may necessitate subsequent regularization of the structure if the moved and unmoved parts are chemically connected, and this is done as a separate operation on a different machine. The system also has the capability of displaying several molecules and of manually superimposing these on each other for comparison purposes. HYDRA

| top | pdf |

This program, due to Hubbard (1985[link]) (and, more recently, to Molecular Simulations) has several functional parts, referred to as `heads', which all use the same data structure. The addition of further heads may be accomplished, knowing the data structure, without the need to know anything of the internal workings of existing heads.

The program contains extensive features for the display, analysis and modelling of molecular structure with particular emphasis on proteins. Display options include dotted surfaces, molecular skeletons, protein cartoons and a variety of van der Waals, ball-and-stick, and other raster-graphics display techniques such as ray tracing and shaded molecular surfaces. Protein analysis features include the analysis of hydrogen bonding, and of secondary and domain structure, as well as computational assessment of deviations from accepted protein structural characteristics such as abnormal main-chain or side-chain conformations and solvent exposure of hydrophobic amino acids. A full set of protein modelling facilities are provided including homology modelling and the `docking' of substrate molecules. The program contains extensive tools for interactive modelling of structures from NMR or X-ray crystallographic data, and provides interfaces to molecular-mechanics and dynamics calculations. There are also database searching facilities to analyse and compare features of protein structure, and it is well suited to the making of cine films. O

| top | pdf |

Jones et al. (1991[link]) have developed a modelling system for proteins with a radically different approach to any of the foregoing, in that they begin by reducing the available electron-density map to a skeletal representation (Greer, 1974[link]; Williams, 1982[link]) which consists of a line running through the density close to its maximal values, this being the basis of a chain trace. Provisional α-carbon positions are also estimated at this stage. A database of known structures is then scanned for pentapeptides which may be superimposed on five successive positions in the chain trace, the best fit so found being taken to provide coordinates for the three central residues of the developing model. The process advances by three residues at each step, the first and last residues of the pentapeptide being used only to ensure that the central residues are built in a manner compatible with what precedes and follows.

The process ensures that conformations so built are free from improbable conformations, and the whole forms an adequate starting structure for molecular-dynamics procedures, even though some imperfect geometry is to be expected where each tripeptide joins the next. Molecular-modelling systems based on other criteria

| top | pdf |

Systems described within this section mostly have some form of energy minimization as their objective but some are purely geometrical. The optimization of molecules through empirical force fields has been reviewed by Allinger (1976[link]), Burkert & Allinger (1982[link]) and Boyd & Lipkowitz (1982[link]). Some of these systems are in the academic domain, others are commercial. Most have capabilities exceeding the features referred to here and, of necessity, the list cannot be complete. No attempt at comparative evaluations is attempted or implied. Molbuild , Rings , PRXBLD and MM2/MMP2

| top | pdf |

Liljefors (1983[link]) has described a system for constructing representations of organic molecules. The system develops the molecule with plausible geometry and satisfied valencies at all stages of the development with explicit recognition of lone pairs and the various possible hybridization states. Growth is generally by substitution in which a substituent and the atom it is to replace are both nominated from the screen. The bond which is reconstructed in a substitution is generally a single bond. Double and triple bonds are introduced by the substitution of moieties containing them. Atom types may be changed after incorporation in the growing molecule, so that although the menu of substituents includes —CH3 but not —NH2 the latter may be obtained by incorporating —CH3, then changing C to N and one of the hydrogens to a lone pair. Facilities are also provided for cyclization and acyclization.

van der Lieth et al. (1984[link]) have described an extension to this that is specialized to the construction of fused-ring systems. It permits the joining of rings by fusion of a bond, in which two adjacent atoms in one ring are superposed on two in another. It also permits the construction of spiro links in which one atom is common to two rings, or the construction of bridges, or the polymerization of ring systems to form, for example, oligosaccharides. Again the satisfaction of valencies is maintained during building and the geometry of the result is governed by superposition of relevant atoms in the moieties involved.

PRXBLD is a molecular model-building program which accepts two-dimensional molecular drawings in a manner similar to Script (Section[link]) and constructs approximate three-dimensional coordinates from these. It is the model-building component of SECS (Simulation and Evaluation of Chemical Synthesis) (Wipke et al., 1977[link]; Wipke & Dyott, 1974[link]; Wipke, 1974[link]). See also Anderson (1984[link]).

All three of these programs produce output which is acceptable as input to MM2(82)/MMP2 which are developments of Allinger's geometrical optimization based on molecular mechanics (Allinger, 1976[link]). Script

| top | pdf |

This system, described by Cohen et al. (1981[link]), is specialized for fused-ring systems, especially steroids, but is not limited to these classes. The system allows the user to draw on the screen (with a light pen or equivalent) a two-dimensional representation of a molecule using single lines for single bonds, double lines for double bonds, and wedges to indicate out-of-plane substituents. The software can then enumerate the possible distinct conformers, each of which is expected to be near an energy minimum on the conformational potential surface. Each conformer may then be annealed to reach an energy minimum using an energy estimate based on bond lengths, bond angles, torsion angles and van der Waals, electrostatic and hydrogen-bonding terms. An example is given of the identification of an unusual conformer as the most stable one from twelve possibilities for a four-ring system.

The program is a development of similar work by Cohen (1971[link]) in which the molecule was defined in terms of a tree structure and an optimizer based on search techniques rather than gradient vectors was used. The method included van der Waals terms and hence estimated energy differences between stereoisomers in condensed ring systems arising from steric hindrance. CHARMM

| top | pdf |

This system, due to Brooks et al. (1983[link]), is primarily concerned with molecular dynamics but it includes the capability of model-building proteins and nucleic acids from sequence information and values of internal coordinates (bond lengths, bond angles and dihedral angles). The resulting structure (or a given structure) may then be optimized by minimizing an empirical energy function which may include electrostatic and hydrogen-bonding terms as well as the usual van der Waals energy and a Hookean treatment of the covalent skeleton. Hydrogen atoms need not be handled explicitly, groups such as —CH2— being treated as single pseudo atoms, and this may be advisable for large structures. For small or medium proteins hydrogens may be treated explicitly and their initial positions may be determined by CHARMM if they are not otherwise known. Commercial systems

| top | pdf |

A number of very powerful molecular-modelling systems are now available commercially and we mention a few of these here. Typically, each consists of a suite of programs sharing a common data structure so that the components of a system may be acquired selectively.

The Chem-X system, from Chemical Design Ltd, enables models to be developed from sketch-pad input, provides for their geometrical optimization and interfaces the result to Gaussian80 for quantum-mechanical calculations.

MACCS , from Molecular Design Ltd, and related software (Allinger, 1976[link]; Wipke et al., 1977[link]; Potenzone et al., 1977[link]) has similar features and also has extensive database-maintenance facilities including data on chemical reactions.

Sybyl , from Tripos Associates (van Opdenbosch et al., 1985[link]), also builds from sketches with a standard fragment library, and provides interfaces to quantum-mechanical routines, to various databases and to MACCS.

Insight II (Section[link]) is available from Biosym and GRAMPS (Section[link]) is available from T. J. O'Donnell Associates.


Abad-Zapatero, C., Abdel-Meguid, S. S., Johnson, J. E., Leslie, A. G. W., Rayment, I., Rossmann, M. G., Suck, D. & Tsukihara, T. (1980). Structure of southern bean mosaic virus at 2.8 Å resolution. Nature (London), 286, 33–39.
Abi-Ezzi, S. S. & Bunshaft, A. J. (1986). An implementer's view of PHIGS. IEEE Comput. Graphics Appl. Vol. 6, Part 2.
Aharonov, Y., Farach, H. A. & Poole, C. P. (1977). Non-linear vector product to describe rotations. Am. J. Phys. 45, 451–454.
Allen, F. H., Bellard, S., Brice, M. D., Cartwright, B. A., Doubleday, A., Higgs, H., Hummelink, T., Hummelink-Peters, B. G., Kennard, O., Motherwell, W. D. S., Rodgers, J. R. & Watson, D. G. (1979). The Cambridge Crystallographic Data Centre: computer-based search, retrieval, analysis and display of information. Acta Cryst. B35, 2331–2339.
Allinger, N. L. (1976). Calculation of molecular structure and energy by force field methods. Adv. Phys. Org. Chem. 13, 1–82.
Altona, C. & Sundaralingam, M. (1972). Conformational analysis of the sugar ring in nucleosides and nucleotides. A new description using the concept of pseudorotation. J. Am. Chem. Soc. 94(23), 8205–8212.
American National Standards Institute, American National Standard for Information Processing Systems – Computer Graphics – Graphical Kernel System (GKS) Functional Description (1985). ISO 7942, ISO Central Secretariat, Geneva, Switzerland.
American National Standards Institute, American National Standard for Information Processing Systems – Computer Graphics – Programmer's Hierarchical Graphics System (PHIGS) Functional Description, Archive File Format, Clear-Text Encoding of Archive File (1988). ANSI X3.144–1988. ANSI, New York, USA.
Anderson, S. (1984). Graphical representation of molecules and substructure-search queries in MACCS. J. Mol. Graphics, 2, 83–90.
Arnold, D. B. & Bono, P. R. (1988). CGM and CGI: metafile and interface standards for computer graphics. Berlin: Springer-Verlag.
Barry, C. D. & North, A. C. T. (1971). The use of a computer-controlled display system in the study of molecular conformations. Cold Spring Harbour Symp. Quant. Biol. 36, 577–584.
Bash, P. A., Pattabiraman, N., Huang, C., Ferrin, T. E. & Langridge, R. (1983). Van der Waals surfaces in molecular modelling: implementation with real-time computer graphics. Science, 222, 1325–1327.
Beddell, C. J. (1970). An X-ray crystallographic study of the activity of lysozyme. DPhil thesis, University of Oxford, England.
Bernstein, F. C., Koetzle, T. F., Williams, G. J. B., Meyer, E. F., Brice, M. D., Rodgers, J. R., Kennard, O., Shimanouchi, T. & Tasumi, M. (1977). The Protein Data Bank: a computer-based archival file for macromolecular structures. J. Mol. Biol. 112, 535–542.
Bloomer, A. C., Champness, J. N., Bricogne, G., Staden, R. & Klug, A. (1978). Protein disk of tobacco mosaic virus at 2.8 Å resolution showing the interactions within and between subunits. Nature (London), 276, 362–368.
Boyd, D. B. & Lipkowitz, K. B. (1982). Molecular mechanics, the method and its underlying philosophy. J. Chem. Educ. 59, 269–274.
Brandenburg, N. P., Dempsey, S., Dijkstra, B. W., Lijk, L. J. & Hol, W. G. J. (1981). An interactive graphics system for comparing and model building of macromolecules. J. Appl. Cryst. 14, 274–279.
Brooks, B. R., Brucolleri, R. E., Olafson, B. D., States, D. J., Swaminathan, S. & Karplus, M. (1983). CHARMM: a program for macromolecular energy, minimization, and dynamics calculations. J. Comput. Chem. 4, 187–217.
Brown, M. D. (1985). Understanding PHIGS. Template, Megatek Corp., San Diego, California, USA.
Burkert, U. & Allinger, N. L. (1982). Molecular mechanics. ACS Monogr. No. 177.
Cambillau, C. & Horjales, E. (1987). TOM: a FRODO subpackage for protein-ligand fitting with interactive energy minimization. J. Mol. Graphics, 5, 174–177.
Cambillau, C., Horjales, E. & Jones, T. A. (1984). TOM, a display program for fitting ligands into protein receptors and performing interactive energy minimization. J. Mol. Graphics, 2, 53–54.
Cambridge Structural Database (1994). Cambridge Crystallographic Data Centre, 12 Union Road, Cambridge, England.
Cockrell, P. R. (1983). A new general purpose method for large volume production of contour charts. Comput. Graphics Forum, 2, 35–47.
Cohen, N. C. (1971). GEMO: a computer program for the calculation of the preferred conformations of organic molecules. Tetrahedron, 27, 789–797.
Cohen, N. C., Colin, P. & Lemoine, G. (1981). Script: interactive molecular geometrical treatments on the basis of computer-drawn chemical formula. Tetrahedron, 37, 1711–1721.
Collins, D. M., Cotton, F. A., Hazen, E. E., Meyer, E. F. & Morimoto, C. N. (1975). Protein crystal structures: quicker, cheaper approaches. Science, 190, 1047–1053.
Connolly, M. L. (1983a). Solvent-accessible surfaces of proteins and nucleic acids. Science, 221, 709–713.
Connolly, M. L. (1983b). Analytical molecular surface calculation. J. Appl. Cryst. 16, 548–558.
Dam, A. van (1988). PHIGS+ functional description, revision 3.0. Comput. Graphics, 22, 125–218.
Dayringer, H. E., Tramontano, A., Sprang, S. R. & Fletterick, R. J. (1986). Interactive program for visualization and modelling of proteins, nucleic acids and small molecules. J. Mol. Graphics, 4, 82–87.
Diamond, R. (1966). A mathematical model-building procedure for proteins. Acta Cryst. 21, 253–266.
Diamond, R. (1971). A real-space refinement procedure for proteins. Acta Cryst. A27, 436–452.
Diamond, R. (1976a). On the comparison of conformations using linear and quadratic transformations. Acta Cryst. A32, 1–10.
Diamond, R. (1976b). Model building techniques for macromolecules. In Crystallographic computing techniques, edited by F. R. Ahmed, K. Huml & B. Sedlacek, pp. 336–343. Copenhagen: Munksgaard.
Diamond, R. (1980a). BILDER: a computer graphics program for biopolymers and its application to the interpretation of the structure of tobacco mosaic virus protein discs at 2.8 Å resolution. In Biomolecular structure, conformation, function and evolution, Vol. 1, edited by R. Srinivasan, pp. 567–588. Oxford: Pergamon Press.
Diamond, R. (1980b). Some problems in macromolecular map interpretation. In Computing in crystallography, edited by R. Diamond, S. Ramaseshan & K. Venkatesan, pp. 21.01–21.19. Bangalore: Indian Academy of Sciences for the International Union of Crystallography.
Diamond, R. (1980c). Inter-active graphics. In Computing in crystallography, edited by R. Diamond, S. Ramaseshan & K. Venkatesan, pp. 27.01–27.16. Bangalore: Indian Academy of Sciences for the International Union of Crystallography.
Diamond, R. (1981). A review of the principles and properties of the method of least squares. In Structural aspects of biomolecules, edited by R. Srinivasan & V. Pattabhi, pp. 81–122. Delhi: Macmillan India Ltd.
Diamond, R. (1982a). Two contouring algorithms. In Computational crystallography, edited by D. Sayre, pp. 266–272. Oxford University Press.
Diamond, R. (1982b). BILDER: an interactive graphics program for biopolymers. In Computational crystallography, edited by D. Sayre, pp. 318–325. Oxford University Press.
Diamond, R. (1984a). Applications of computer graphics in molecular biology. Comput. Graphics Forum, 3, 3–11.
Diamond, R. (1984b). Least squares and related optimisation techniques. In Methods and applications in crystallographic computing, edited by S. R. Hall & T. Ashida, pp. 174–192. Oxford University Press.
Diamond, R. (1988). A note on the rotational superposition problem. Acta Cryst. A44, 211–216.
Diamond, R. (1989). A comparison of three recently published methods for superimposing vector sets by pure rotation. Acta Cryst. A45, 657.
Diamond, R. (1990a). On the factorisation of rotations with special reference to diffractometry. Proc. R. Soc. London Ser. A, 428, 451–472.
Diamond, R. (1990b). Chirality in rotational superposition. Acta Cryst. A46, 423.
Diamond, R., Wynn, A., Thomsen, K. & Turner, J. (1982). Three-dimensional perception for one-eyed guys, or, the use of dynamic parallax. In Computational crystallography, edited by D. Sayre, pp. 286–293. Oxford University Press.
Dodson, E. J., Isaacs, N. W. & Rollett, J. S. (1976). A method for fitting satisfactory models to sets of atomic positions in protein structure refinements. Acta Cryst. A32, 311–315.
Dodson, G. G., Eliopoulos, E. E., Isaacs, N. W., McCall, M. J., Niall, H. D. & North, A. C. T. (1982). Rat relaxin: insulin-like fold predicts a likely receptor binding region. Int. J. Biol. Macromol. 4, 399–405.
Enderle, G., Kansy, K. & Pfaff, G. (1984). Computer graphics programming, GKS – the graphics standard. Berlin: Springer-Verlag.
Evans, P. R., Farrants, G. W. & Hudson, P. J. (1981). Phosphofructokinase: structure and control. Philos. Trans. R. Soc. London Ser. B, 293, 53–62.
Feldmann, R. J. (1976). The design of computing systems for molecular modeling. Annu. Rev. Biophys. Bioeng. 5, 477–510.
Feldmann, R. J. (1983). Directions in macromolecular structure representation and display. In Computer applications in chemistry, edited by S. R. Heller & R. Potenzone Jr, pp. 9–18. Amsterdam: Elsevier.
Feldmann, R. J., Bing, D. H., Furie, B. C. & Furie, B. (1978). Interactive computer surface graphics approach to the study of the active site of bovine trypsin. Proc. Natl Acad. Sci. Biochemistry, 75, 5409–5412.
Ferrin, T. E., Huang, C., Jarvis, L. & Langridge, R. (1984). Molecular inter-active display and simulation: MIDAS. J. Mol. Graphics, 2, 55.
Foley, J. D., van Dam, A., Feiner, S. K. & Hughes, J. F. (1990). Computer graphics principles and practice, 2nd edition. New York: Addison Wesley.
Ford, L. O., Johnson, L. N., Machin, P. A., Phillips, D. C. & Tjian, R. (1974). Crystal structure of a lysozyme-tetrasaccharide lactone complex. J. Mol. Biol. 88, 349–371.
Gallo, L., Huang, C. & Ferrin, T. (1983). UCSF MIDAS, molecular interactive display and simulation, users' guide. Computer Graphics Laboratory, School of Pharmacy, University of California, San Francisco, USA.
Gill, P. E., Murray, W. & Wright, M. H. (1981). Practical optimization. Orlando, Florida: Academic Press.
Gilliland, G. L. & Quiocho, F. A. (1981). Structure of the L-arabinose-binding protein from Escherichia coli at 2.4 Å resolution. J. Mol. Biol. 146, 341–362.
Girling, R. L., Houston, T. E., Schmidt, W. C. Jr & Amma, E. L. (1980). Macromolecular structure refinement by restrained least-squares and interactive graphics as applied to sickling deer type III hemoglobin. Acta Cryst. A36, 43–50.
Gossling, T. H. (1967). Two methods of presentation of electron-density maps using a small-store computer. Acta Cryst. 22, 465–468.
Greer, J. (1974). Three-dimensional pattern recognition: an approach to automated interpretation of electron density maps of proteins. J. Mol. Biol. 82, 279–302.
Harris, M. R., Geddes, A. J. & North, A. C. T. (1985). A liquid crystal stereo-viewer for molecular graphics. J. Mol. Graphics, 3, 121–122.
Hass, B. S., Willoughby, T. V., Morimoto, C. N., Cullen, D. L. & Meyer, E. F. (1975). The solution of the structure of spirodienone by visual packing analysis. Acta Cryst. B31, 1225–1229.
Heap, B. R. & Pink, M. G. (1969). Three contouring algorithms, DNAM Rep. 81. National Physical Laboratory, Teddington, England.
Hermans, J. (1985). Rationalization of molecular models. In Methods in enzymology, Vol. 115. Diffraction methods for biological molecules, Part B, edited by H. W. Wyckoff, C. H. W. Hirs & S. N. Timasheff, pp. 171–189. Orlando, Florida: Academic Press.
Hermans, J. & McQueen, J. E. (1974). Computer manipulation of (macro) molecules with the method of local change. Acta Cryst. A30, 730–739.
Hogle, J., Rao, S. T., Mallikarjunan, M., Beddell, C., McMullan, R. K. & Sundaralingam, M. (1981). Studies of monoclinic hen egg white lysozyme. Structure solution at 4 Å resolution and molecular-packing comparisons with tetragonal and triclinic lysozymes. Acta Cryst. B37, 591–597.
Hopgood, F. R. A., Duce, D. A., Gallop, J. R. & Sutcliffe, D. C. (1986). Introduction to the graphical kernel system, 2nd ed. London: Academic Press.
Hubbard, R. E. (1983). Colour molecular graphics on a microcomputer. J. Mol. Graphics, 1, 13–16, C3–C4.
Hubbard, R. E. (1985). The representation of protein structure. In Computer aided molecular design, pp. 99–106. Proceedings of a two-day conference, London, October 1984. London: Oyez Scientific.
International Standards Organisation, International Standard Information Processing Systems – Computer Graphics – Graphical Kernel System for Three Dimensions (GKS-3D), Functional Description (1988). ISO Document No. 8805:1988(E). American National Standards Institute, New York, USA.
International Tables for Crystallography (2005). Vol. A. Space-group symmetry, edited by T. Hahn. Heidelberg: Springer.
IUPAC–IUB Commission on Biochemical Nomenclature (1970). Abbreviations and symbols for the description of the conformation of polypeptide chains. J. Biol. Chem. 245, 6489–6497.
Johnson, C. K. (1970). Drawing crystal structures by computer. In Crystallographic computing, edited by F. R. Ahmed, pp. 227–230. Copenhagen: Munksgaard.
Johnson, C. K. (1976). ORTEPII. A Fortran thermal-ellipsoid plot program for crystal structure illustrations. Report ORNL-5138. Oak Ridge National Laboratory, Tennessee, USA.
Johnson, C. K. (1980). Computer-generated illustrations. In Computing in crystallography, edited by R. Diamond, S. Ramaseshan & K. Venkatesan, pp. 26.01–26.10. Bangalore: Indian Academy of Sciences for the International Union of Crystallography.
Jones, T. A. (1978). A graphics model building and refinement system for macromolecules. J. Appl. Cryst. 11, 268–272.
Jones, T. A. (1982). FRODO: a graphics fitting program for macromolecules. In Computational crystallography, edited by D. Sayre, pp. 303–317. Oxford University Press.
Jones, T. A. (1985). Interactive computer graphics: FRODO. In Methods in enzymology, Vol. 115. Diffraction methods for biological molecules, Part B, edited by H. W. Wyckoff, C. H. W. Hirs & S. N. Timasheff, pp. 157–171. Orlando, Florida: Academic Press.
Jones, T. A. & Liljas, L. (1984). Crystallographic refinement of macromolecules having non-crystallographic symmetry. Acta Cryst. A40, 50–57.
Jones, T. A., Zou, J.-Y., Cowan, S. W. & Kjeldgaard, M. (1991). Improved methods for building protein models in electron density maps and the location of errors in these models. Acta Cryst. A47, 110–119.
Kabsch, W. (1976). A solution for the best rotation to relate two sets of vectors. Acta Cryst. A32, 922–923.
Kabsch, W. (1978). A discussion of the solution for the best rotation to relate two sets of vectors. Acta Cryst. A34, 827–828.
Katz, L. & Levinthal, C. (1972). Interactive computer graphics and representation of complex biological structures. Annu. Rev. Biophys. Bioeng. 1, 465–504.
Kearsley, S. K. (1989). On the orthogonal transformation used for structural comparisons. Acta Cryst. A45, 208–210.
Langridge, R., Ferrin, T. E., Kuntz, I. D. & Connolly, M. L. (1981). Real-time color graphics in studies of molecular interactions. Science, 211, 661–666.
Lederer, F., Glatigny, A., Bethge, P. H., Bellamy, H. D. & Mathews, F. S. (1981). Improvement of the 2.5 Å resolution model of cytochrome b562 by re-determining the primary structure and using molecular graphics. J. Mol. Biol. 148, 427–448.
Lesk, A. M. & Hardman, K. D. (1982). Computer-generated schematic diagrams of protein structures. Science, 216, 539–540.
Lesk, A. M. & Hardman, K. D. (1985). Computer-generated pictures of proteins. In Methods in enzymology, Vol. 115. Diffraction methods for biological molecules, Part B, edited by H. W. Wyckoff, C. H. W. Hirs & S. N. Timasheff, pp. 381–390. Orlando, Florida: Academic Press.
Levinthal, C. (1966). Molecular model-building by computer. Sci. Am. 214, 42–52.
Levitt, M. (1971). PhD Dissertation, ch. 2. University of Cambridge, England.
Levitt, M. (1974). Energy refinement of hen egg-white lysozyme. J. Mol. Biol. 82, 393–420.
Levitt, M. & Lifson, S. (1969). Refinement of protein conformations using a macromolecular energy minimization procedure. J. Mol. Biol. 46, 269–279.
Levitt, M. & Warshel, A. (1975). Computer simulation of protein folding. Nature (London), 253, 694–698.
Lieth, C. W. van der, Carter, R. E., Dolata, D. P. & Liljefors, T. (1984). RINGS – a general program to build ring systems. J. Mol. Graphics, 2, 117–123.
Liljefors, T. (1983). MOLBUILD – an interactive computer graphics interface to molecular mechanics. J. Mol. Graphics, 1, 111–117.
Luenberger, D. G. (1984). Linear and nonlinear programming. Reading, Massachusetts: Addison Wesley.
Mackay, A. L. (1984). Quaternion transformation of molecular orientation. Acta Cryst. A40, 165–166.
McLachlan, A. D. (1972). A mathematical procedure for superimposing atomic coordinates of proteins. Acta Cryst. A28, 656–657.
McLachlan, A. D. (1979). Gene duplications in the structural evolution of chymotrypsin. Appendix: Least squares fitting of two structures. J. Mol. Biol. 128, 49–79.
McLachlan, A. D. (1982). Rapid comparison of protein structures. Acta Cryst. A38, 871–873.
Max, N. L. (1984). Computer representation of molecular surfaces. J. Mol. Graphics, 2, 8–13, C2–C4.
Meyer, E. F. (1970). Three-dimensional graphical models of molecules and a time-slicing computer. J. Appl. Cryst. 3, 392–395.
Meyer, E. F. (1971). Interactive computer display for the three dimensional study of macromolecular structures. Nature (London), 232, 255–257.
Meyer, E. F. (1974). Storage and retrieval of macromolecular structural data. Biopolymers, 13, 419–422.
Miller, J. R., Abdel-Meguid, S. S., Rossmann, M. G. & Anderson, D. C. (1981). A computer graphics system for the building of macromolecular models into electron density maps. J. Appl. Cryst. 14, 94–100.
Morffew, A. J. (1983). Bibliography for molecular graphics. J. Mol. Graphics, 1, 17–23.
Morffew, A. J. (1984). Bibliography for molecular graphics, 1983/84. J. Mol. Graphics, 2, 124–128.
Morimoto, C. N. & Meyer, E. F. (1976). Information retrieval, computer graphics, and remote computing. In Crystallographic computing techniques, edited by F. R. Ahmed, K. Huml & B. Sedlacek, pp. 488–496. Copenhagen: Munksgaard.
Motherwell, W. D. S. (1978). Pluto – a program for displaying molecular and crystal structures. Cambridge Crystallographic Data Centre, 12 Union Road, Cambridge, England.
Newman, W. M. & Sproull, R. F. (1973). Principles of inter-active computer graphics. New York: McGraw-Hill.
North, A. C. T. (1982). Use of interactive computer graphics in studying molecular structures and interactions. Chem. Ind. pp. 221–225.
North, A. C. T., Denson, A. K., Evans, A. C., Ford, L. O. & Willoughby, T. V. (1981). The use of an interactive computer graphics system in the study of protein conformations. In Biomolecular structure, conformation, function and evolution, Vol. 1, edited by R. Srinivasan, pp. 59–72. Oxford: Pergamon Press.
O'Donnell, T. J. & Olson, A. J. (1981). GRAMPS – a graphics language interpreter for real-time, interactive, three-dimensional picture editing and animation. Comput. Graphics, 15, 133–142.
Olson, A. J. (1982). GRAMPS: a high level graphics interpreter for expanding graphics utilization. In Computational crystallography, edited by D. Sayre, pp. 326–336. Oxford University Press.
Opdenbosch, N. van, Cramer, R. III & Giarrusso, F. F. (1985). Sybyl, the integrated molecular modelling system. J. Mol. Graphics, 3, 110–111.
Pearl, L. H. & Honegger, A. (1983). Generation of molecular surfaces for graphic display. J. Mol. Graphics, 1, 9–12, C2.
Phillips, S. E. V. (1980). Structure and refinement of oxymyoglobin at 1.6 Å resolution. J. Mol. Biol. 142, 531–554.
Phong, B. T. (1975). Illumination for computer generated images. Commun. ACM, 18, 311–317.
Porter, T. K. (1978). Spherical shading. Comput. Graphics, 12, 282–285.
Potenzone, R., Cavicchi, E., Weintraub, H. J. R. & Hopfinger, A. J. (1977). Molecular mechanics and the CAMSEQ processor. Comput. Chem. 1, 187–194.
Potterton, E. A., Geddes, A. J. & North, A. C. T. (1983). Attempts to design inhibitors of dihydrofolate reductase using interactive computer graphics with real time energy calculations. In Chemistry and biology of pteridines, edited by J. A. Blair, pp. 299–303. Berlin, New York: Walter de Gruyter.
Purisima, E. O. & Scheraga, H. A. (1986). An approach to the multiple-minima problem by relaxing dimensionality. Proc. Natl Acad. Sci. USA, 83, 2782–2786.
Richardson, J. S. (1977). β-Sheet topology and the relatedness of proteins. Nature (London), 268, 495–500.
Richardson, J. S. (1981). The anatomy and taxonomy of protein structure. Adv. Protein Chem. 34, 167–339.
Richardson, J. S. (1985). Schematic drawings of protein structures. In Methods in enzymology, Vol. 115. Diffraction methods for biological molecules, Part B, edited by H. W. Wyckoff, C. H. W. Hirs & S. N. Timasheff, pp. 359–380. Orlando, Florida: Academic Press.
Sundaram, K. & Radhakrishnan, R. (1979). A computer program for topographic analysis of biomolecular systems. Comput. Programs Biomed. 10, 34–42.
Sutcliffe, D. C. (1980). Contouring over rectangular and skewed rectangular grids – an introduction. In Mathematical methods in computer graphics and design, edited by K. W. Brodie, pp. 39–62. London: Academic Press.
Sutherland, I. E., Sproull, R. F. & Schumacker, R. A. (1974). A characterization of ten hidden surface algorithms. Comput. Surv. 6, 1–55.
Swanson, S. M., Wesolowski, T., Geller, M. & Meyer, E. F. (1989). Animation: a useful tool for protein molecular dynamicists, applied to hydrogen bonds in the active site of elastase. J. Mol. Graphics, 7, 240–242, 223–224.
Takenaka, A. & Sasada, Y. (1980). Computer manipulation of crystal and molecular models. J. Crystallogr. Soc. Jpn, 22, 214–225. [In Japanese.]
Thomas, D. J. (1993). Toward more reliable printed stereo. J. Mol. Graphics, 11, 15–22.
Tsernoglou, D., Petsko, G. A., McQueen, J. E. & Hermans, J. (1977). Molecular graphics: application to the structure determination of a snake venom neurotoxin. Science, 197, 1378–1381.
Vedani, A. & Meyer, E. F. (1984). Structure–activity relationships of sulfonamide drugs and human carbonic anhydrase C: modelling of inhibitor molecules into receptor site of the enzyme with an interactive computer graphics display. J. Pharm. Sci. 73, 352–358.
Walsh, G. R. (1975). Methods of optimization. London: John Wiley.
Warme, P. K., Go, N. & Scheraga, H. A. (1972). Refinement of X-ray data of proteins. 1. Adjustment of atomic coordinates to conform to a specified geometry. J. Comput. Phys. 9, 303–317.
Williams, T. V. (1982). Thesis. University of North Carolina at Chapel Hill, NC, USA.
Willoughby, T. V., Morimoto, C. N., Sparks, R. A. & Meyer, E. F. (1974). Mini-computer control of a stereo graphics display. J. Appl. Cryst. 7, 430–434.
Wipke, W. T. (1974). Computer assisted three-dimensional synthetic analysis. In Computer representation and manipulation of chemical information, edited by W. T. Wipke, S. R. Heller, R. J. Feldmann & E. Hyde, pp. 147–174. New York: John Wiley.
Wipke, W. T., Braun, H., Smith, G., Choplin, F. & Sieber, W. (1977). SECS – simulation and evaluation of chemical synthesis: strategy and planning. ACS Symp. Ser. 61, 97–125.
Wipke, W. T. & Dyott, T. M. (1974). Simulation and evaluation of chemical synthesis. Computer representation and manipulation of stereochemistry. J. Am. Chem. Soc. 96, 4825–4834.

to end of page
to top of page