International
Tables for Crystallography Volume B Reciprocal space Edited by U. Shmueli © International Union of Crystallography 2006 
International Tables for Crystallography (2006). Vol. B, ch. 3.3, pp. 360384
doi: 10.1107/97809553602060000561 Chapter 3.3. Molecular modelling and graphics ^{a}MRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England This chapter is in three parts. The first of these (Section 3.3.1) 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) 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) 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. 
It is usual, for purposes of molecular modelling and of computer graphics, to adopt a Cartesian coordinate system using mutually perpendicular axes in a righthanded 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 unitcell 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 in which formulations using co and contravariant forms are presented.
The relationship between these systems may be written 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 and the third parallel to c and is in which
ϕ is equal to the volume of the unit cell divided by abc, and is unchanged by cyclic permutation of α, β and γ and of , and . 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 and is
A third form, suitable only for rhombohedral cells, is in which 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 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 (as delivered to the display hardware) which controls the left–right positioning of the point within the picture. A point with is in the picture, normally, and those with are outside it, but see Section 3.3.1.3.5.
There are many reasons why homogeneous coordinates may be adopted, among them the following:
For analytical purposes it is convenient to regard homogeneous transformations in terms of partitioned matrices where M is a matrix, V and X are threeelement column vectors, U is a threeelement row vector and N and W are scalars.
Matrices and vectors which are equivalent under the considerations of (iii) above will be related by the sign ≃ in what follows.
Hardware systems which use true floatingpoint representations have less need of homogeneous coordinates and for these N and W may normally be set to unity.
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 lowercase subscripts only. Thus the equation is to be read `For any I, is summed over j'.
Subscripts using the letter i or later in the alphabet will relate to the usual three dimensions and imply a threeterm 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, , which is 1 if and zero otherwise, and the tensor which is 1 if I, J and K are a cyclic permutation of 1, 2, 3, −1 if an anticyclic permutation, and zero otherwise.
A useful identity is then 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.
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) and described and illustrated by Hopgood et al. (1986) and Enderle et al. (1984). 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 twodimensional. A threedimensional extension known as GKS3D, defined in International Standards Organisation, International Standard Information Processing Systems – Computer Graphics – Graphical Kernel System for Three Dimensions (GKS3D), Functional Description (1988) became an ISO standard in 1988. Perhaps of greatest interest to crystallographers, however, is the Programmers' Hierarchical Interactive Graphics System (PHIGS) (Brown, 1985; AbiEzzi & Bunshaft, 1986) 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 GKS3D 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, ClearText Encoding of Archive File (1988). PHIGS has also been extended to support the capability of rastergraphics machines to represent reflections, shadows, seethrough effects etc. in a version known as PHIGS+ (van Dam, 1988).
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 filestorage, or metafile, form, and for the interface between the deviceindependent and devicedependent parts of a graphics package. Arnold & Bono (1988) describe the ANSI and ISO Computer Graphics Metafile standard which provides for the definition of (twodimensional) images. The definition of threedimensional scenes requires the use of (PHIGS) archive files.
It is a basic requirement for any graphics or molecularmodelling 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.
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 , and if these components are , and if a second set of axes X′, Y′, Z′ is similarly established, with the same origin and chirality, and if v has components on these axes then in which is the cosine of the angle between the ith primed axis and the jth unprimed axis. Evidently the elements 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 since elements of the product 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 and if these vectors are transformed by the matrix R as above, then the transformed volume V′ is But the determinant of R is given by so that 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 (1.1.4.32 ) and is or 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 righthanded 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 which is commonly employed in fourcircle diffractometers for which , and . In terms of the fixedaxes–movingobject conceptualization this corresponds to a rotation about Z followed by about Y followed by about Z. In the familiar diffractometer example, when 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 . In general, when rotating parts are mounted on rotating parts the rotation closest to the moved object must be applied first, forming the rightmost factor in any multiple transformation, with the rotation closest to the fixed part as the leftmost 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 consisting of the antisymmetric part of R, has elements times the direction cosines l, m, n, which establishes the direction immediately, and normalization using determines . Furthermore, the trace is so that the quadrant of θ is also fixed. This method fails, however, if the matrix is symmetrical, which occurs if . In this case only the direction of the axis is required, which is given by for nonzero elements, or etc., with the signs chosen to satisfy etc.
The Eulerian form may be factorized by noting that . There is then freedom to choose the sign of , but the choice then fixes the quadrants of and through the elements in the last row and column, and the primitives may then be constructed. These expressions for and fail if , in which case the rotation reduces to a primitive rotation about Z with angle , or .
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 quasilinearly 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 is determinate.
Quasilinear 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 , and , whilst for larger θ linearized iterative techniques for finding the primitive rotations are likely to be convergent and well conditioned.
The threedimensional space of the angles and in either case is nonlinearly related to θ. In the Eulerian case the worst nonlinearities occur at the origin of ϕspace. Equally severe nonlinearities occur in the quasilinear 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 nonequivalent 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 nonequivalence arising from the noncommutation 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 then 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 . Using also , which may be deemed positive without loss of generality,
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], , and , 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 , rather than , 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 , , with and . Then the matrix is orthogonal and the variables u, v, w are independent, equivalent and unbounded, and, unlike the previous form, small rotations are quasilinear on these variables. As examples, gives 90° about X, gives 120° about [111].
R then transforms a vector d according to
Multiplying two such matrices together allows us to establish the manner in which the rotation vectors and combine. for a rotation followed by , 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 and are parallel this reduces to the formula for the tangent of the sum of two angles, and that if 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 and are applied successively, first, then their combined rotation is
Note the irregular pattern of signs in the numerator.
Similar ideas, using a vector of magnitude , are developed in Aharonov et al. (1977).
The third form of orthogonal matrix uses four variables, λ, μ, ν and σ, which comprise a fourdimensional vector , such that , , with and . In terms of these variables Two further matrices S and T may be defined (Diamond, 1988), which are themselves orthogonal (though S has determinant −1) and which have the property that so that, for example, if homogeneous coordinates are being employed (Section 3.3.1.1.2) 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 arising from a concatenation of n rotations is in which 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).
Finally, an exact rotation of the vector d may be obtained without using matrices at all by writing in which and is the initial position which is to be rotated. Here is a vector with direction cosines l, m and n, and magnitude equal to the required rotation angle in radians (Diamond, 1966). This method is particularly efficient when 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 threedimensional analogue of the power series for sin θ and cos θ and has the same convergence properties.
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) are concerned with pure rotation, ignoring any strain that may be present, and give the best rigidbody 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 ) to (v) 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) and (vii) 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 and, by choice of origin, for weights W. The quadratic residual to be minimized is and we define the matrix and use l for the direction cosines of the rotation axis.
There are several ways of deriving a strictly orthogonal matrix from a given approximately orthogonal matrix, among them the following.

If R is the orthogonal matrix given in Section 3.3.1.2.1 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
Consideration of the determinant shows that the sum of the three eigenvalues is and that their product is unity. Hence the three eigenvalues are 1, and . 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 3.3.1.2.1 (q.v.) according to which is solved by any vector of the form for any real vector v, where l is the normalized axis vector, , , . 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 and remains an eigenvector. Using superscript signs to denote the sign of θ in the eigenvalue with which each vector is associated, the matrix has the properties that and 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 and .
A convenient form for U, symmetrical in the elements of l, is obtained by setting and is in which the normalizing denominator is given by
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), and Foley et al. (1990) give a comprehensive account of the field, including recent developments, especially those arising from the development of rastergraphics technologies.
Typically, the coordinates, X, of points in an object to be drawn are held in homogeneous Cartesian form as described in Section 3.3.1.1.2. 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 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 displayspace coordinates as input and generates vectors (X, Y, Z, W) for which and for points on the left, right, top and bottom boundaries of the window and for which takes particular values on the front and back planes of the window, is said to be a windowing transformation . In machines for which controls intensity depth cueing, the range of corresponding to the window is likely to be 0 to 1 rather than −1 to 1. Coordinates obtained by multiplying displayspace coordinates by U are termed picturespace coordinates. Mathematically, U is a matrix like any other, but functionally it is special. Declaring a transformation to be a windowing transformation implies that only resulting points having and positive 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 fullscreen deflection, where n is declared by the manufacturer. Screen coordinates are obtained from picture coordinates with a viewport transformation , V.^{1}
The transformation evidently corresponds to the addition of the vector to the components of X or of to the components of . ( 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, ), with V scaled to correspond to this choice, and loading the transformation matrix as indicated above.
Rotation about the origin is achieved by in which R is an orthogonal 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.
The transformation scales the vector (X, W) by the factor S. For integer working and , N should be set to the largest representable integer. For the product SN should be the largest representable integer, N being reduced accordingly.
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 lefthanded system in that is negative. Since it is usual in crystallographic work to use righthanded axial systems it is necessary to incorporate a matrix of the form either as the leftmost factor in the matrix T or as the rightmost factor in the windowing transformation U (see Section 3.3.1.3.1). 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. Displayspace 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 , 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 when . 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. 3.3.1.1.

The relationship between displayspace coordinates (X, Y, Z, W) and picturespace 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 values are not linear on , 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 in the screen plane. 
Since is a displayspace 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 and C, the weights being and , respectively. This provides perspective because the weighted mean is at the point where the straight line from to the eye intersects the screen. This then has to be mapped into the LtoR interval, so that picturespace coordinates are given by which provides for and to be unity on the picture boundaries, which is usually a requirement of the clipping hardware, and for , zero being for the nearplane boundary. Even though is not linear on , straight lines and planes in display space transform to straight lines and planes in picture space, the nonlinearity affecting only distances. Thus vectordrawing machines are not disadvantaged by the introduction of perspective.
Note that the dimensionality of must equal that of and that this may be regarded as length or as a pure number, but that in either case 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 lefthanded 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 , 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).
If data space is referred to righthanded axes, the viewing transformation T involves only proper rotations and the hardware uses a lefthanded 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 and then let , choosing some positive K to suit the word length of the machine [see Section 3.3.1.1.2 (iii)]. The result is 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 where U and U′ are as above and P is a perspective transformation given by 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 with 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 , , P and .
Assuming that left and righteye views are to be presented through the same viewport (next section) 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 in which U‴ is the matrix U obtained by setting to correspond to the point midway between the viewer's eyes and in which (c, 0, 0, V) is the position of the right eye relative to the mean eye position, and the lefteye view is obtained by negating c.
Stereo is often approximated by introducing a rotation about the Y axis of to the views or to one of them. The first corresponds to with . The main difference is in the resulting Z value, which only affects depth cueing and z clipping. The X translation which arises if is also suppressed, but this is not likely to be noticeable. σ is often treated as a constant, such as .
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 electrooptic liquidcrystal shutter as described by Harris et al. (1985). 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) and in Thomas (1993), the second of which generalizes the treatment to allow for the possible presence of an optical system.
The window transformation of the previous two sections has been constructed to yield picture coordinates (X, Y, Z, W) (formerly called x, y, z, w) such that a point having or 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. 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 fullscreen deflection value. Thus a point with in picture space plots on the screen with an X coordinate which is a fraction of fullscreen deflection to the right. 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, , to equal that of the window otherwise distortions are introduced.
In this section we consider the viewing transformation T of Section 3.3.1.3.1 and its construction in terms of translation, rotation and scaling, Sections 3.3.1.3.2 –4. We use T′ to denote a new transformation in terms of the prevailing transformation T.
We note first that any matrix of the form with U a scalar, may be factorized according to and also that multiplying 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 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 is a rotation matrix as in Section 3.3.1.3.3, its application produces a rotation about an axis through the origin defined only in the space in which it is applied. For example, if rotates the image about the z axis of data space, whatever the prevailing viewing transformation, T.
Forming 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 3.3.1.3.5, must place the origin of display space there by setting , in the notation of that section.
If a rotation is to be about a point then or 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 for a rotation centre at 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 leftmost 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 topleft partition of T may become degraded by accumulation of roundoff error and this should be corrected occasionally by one of the methods of Section 3.3.1.2.3.
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 where is the required alteration to the prevailing viewing transformation T and is the dataspace equivalent,
An important special case is when is to effect a rotation about the origin of display space without change of scale, so that , for then
If r is the required axis of rotation of in display space then the axis of rotation of in data space is since . This gives a particularly simple result if is to be a primitive rotation for then s is the relevant row of R, and can be constructed directly from this and the required angle of rotation.
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 nonparallel sight lines through the displayed volume and finding their best point of intersection in data space.
In Section 3.3.1.3.1 the relationship between dataspace coordinates and screenspace coordinates was given as hence dataspace coordinates are given by A line of sight through the displayed volume passing through the point on the screen is the line joining the two position vectors in screenspace coordinates, as in Section 3.3.1.3.7, from which the corresponding two points in data space may be obtained using and in the notation of Section 3.3.1.3.5, and was given in Section 3.3.1.3.8. If orthographic projection is being used then simplifies to Each of these inverse matrices may be suitably scaled to suit the word length of the machine [Section 3.3.1.1.2 (iii)].
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 , and for each sight line any (threedimensional) point on the line and the direction of the line are established. For each sight line a rank 2 projector matrix of order 3 is formed as and the best point of intersection of the sight lines is given by to which threevector a fourth coordinate of unity may be applied.
The threeaxis 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 3.3.1.3.1), its angular setting, ϕ, being measured by a shaft encoder in its mounting. At the top of this shaft is a kneejoint 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 which is in which cos and sin are abbreviated to c and s, which is the standard form with , , .
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 with is about an axis in the xy plane (i.e. the screen face) normal to and with . Applied repetitively this gives a quadratic velocity characteristic. Similarly, if an atom at 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 with .
In Section 3.3.1.1.1 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 symmetryrelated neighbour is also to be displayed, then the dataspace coordinates must be multiplied by where are the dataspace coordinates of the crystallographic origin, M and are as in Section 3.3.1.1.1 and is a crystallographic symmetry operator in homogeneous coordinates, expressed relative to the same crystallographic origin.
For example, in with the origin on the screw dyad along b, and
comprises a proper or improper rotational partition, S, in the upperleft in the sense that 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, Chapters 5.2 and 8.1 ) for a fuller discussion of symmetry using augmented (i.e. ) matrices.
The two sections under this heading are concerned only with the graphical aspects of conformational changes. Determination of such changes is considered under Section 3.3.2.2.
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), 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 3.3.1.2.1, 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 3.3.1.3.8.
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 3.3.1.3.8). 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 3.3.2.2.1, though this requirement may make realtime 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 3.3.1.3.1, 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. 3.3.1.2 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 is formed. Continuing up the tree, at node 1 either branch may be chosen; we choose the left and, on reaching b, is stacked and is formed. On reaching the tip drawing down to b is done with this transformation, is then unstacked and drawing continues with this matrix until node 1 is reached. The other branch is then followed to c whereupon is again stacked and the product is formed. From the tip down as far as c is drawn with this matrix, whereupon is unstacked and drawing continues down to a, where T is unstacked before drawing the section nearest the root.

Schematic representation of a simple branchedchain 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 , and later replace all coordinates between the tip and a by , 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 until b is reached, then using to the tip, but in this formulation must be based on the geometry that exists at b after the transformation has been applied to this region of the molecule, i.e. is characteristic of the final conformation rather than the initial one.
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 `singleplane' systems) and these are essentially monochrome and have no grey scale. Fourplane systems are cheap and popular and commonly provide 4bit by 4bit lookup 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. Fourplane 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 eightplane systems are commonly used which permit 256 colours chosen from 16 million using three lookup tables, though the limitations of these can also be felt and full colour is only regarded as being available in 24plane systems.
Rastergraphics devices are ideal for drawing objects represented by opaque surfaces which can be endowed with realistic reflecting properties (Max, 1984) 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 3.3.1.5.5). Many devices of this type provide vectorization, area fill and antialiasing. Vectorization provides automatically for the loading of relevant pixels on a straight line between specified points. Area fill automatically fills any irregular predefined polygon on the screen with a uniform colour with the user specifying only the colour and one point within the polygon. Antialiasing 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.
A line drawing consisting of n line segments may be specified by anything from to 2n position vectors depending on whether the lines are endtoend 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 endtoend connected as far as possible, and an algorithm for doing this is outlined below. For further details see Diamond (1984a).
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 endtoend 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.
The commonest means of representing surfaces, especially contour surfaces, is to consider evenly spaced serial sections and to perform twodimensional 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 vectorgraphics 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 realtime 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 endtoend 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) and Diamond (1982a). Contouring by grid scanning followed by line connection by the methods of the previous section would be possible but less efficient. Further contouring methods are described by Sutcliffe (1980) and Cockrell (1983).
For rastergraphics 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 gridscanning approach (Gossling, 1967). Others have colourcoded each pixel according to the density, which provides a contoured visual impression without performing contouring (Hubbard, 1983).
Connolly (Langridge et al., 1981; Connolly, 1983a,b) represents surfaces by placing dots on the surface with an approximately uniform superficial density. Connolly's algorithm was developed to display solventaccessible surfaces of macromolecules and provides for curved concave portions where surface atoms meet. Pearl & Honegger (1983) 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) have produced a van der Waals surface algorithm fast enough to permit realtime 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.
Many techniques have been developed, mainly for rastergraphics devices, for representing molecular surfaces and these have been very well reviewed by Max (1984).
The simplest technique in this class consists in representing each atom by a uniform disc, or high polygon, which can be colourcoded and areafilled 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 fronttoback 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) 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 , , . The second buffer is a ray buffer since are the coordinates with which an illuminating ray passing through (xyz) passes through the plane, and z′, stored at x′, y′, records the depth at which this ray encounters material. Thus any two pixels and 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 therefore involves first determining its visibility on the basis of the z buffer, as before, then, whether or not it is visible, setting and considering the value of z′ currently stored at , which we call .
If then is in light and must be loaded accordingly. From we find the previously processed pixel which is now in shade and which was in light when originally processed, so that the colour value stored at needs to be altered unless the pixel at is now with , in which case the pixel which has now become shadowed by has, in the meantime, been obscured by which is not shadowed by and no change is therefore needed. In either event then replaces .
If then , if visible, is in shade and must be coloured accordingly, and in this case 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 and of picture space (Section 3.3.1.3.1).
If, in the notation of Section 3.3.1.3.5, 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 which varies only with beam direction, and similarly for y′ and β.
Hidden surfaces may be handled quite generally with the zbuffer technique described in the previous section 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 reentrant 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, pointbypoint 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), and three of these are described in detail by Newman & Sproull (1973).
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 3.3.1.4 above, have been excellently reviewed by Hermans (1985), though with little reference to graphical aspects, and a comprehensive treatment of modelling methods based on energies is given by Burkert & Allinger (1982).
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 fivemembered ring is being modelled by permitting folding of the pentagon about a line connecting nonadjacent 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.
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 3.3.1.5.2 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; Levitt, 1974), and of searchandretrieval techniques (Allen et al., 1979).
Katz & Levinthal (1972) 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) have developed methods of handling connectivity in complicated fused and bridgedring systems.
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 3.3.2.1 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 3.3.3.2.6 uses no connectivity tables for this purpose. The ordering rules concerned are given by Diamond (1976b).
Drawing connectivity needs explicit specification in such a case; this may be done using only one 16bit 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 drawto, negative pointers implying moveto. 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).
Brandenburg et al. (1981) 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) 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) includes something similar.
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 atombyatom 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 `sketchpad' input in the form of a handdrawn twodimensional sketch of the type conventional in chemistry, if the objective is the design of a molecule. Sketchpad input is a feature of some systems with quantummechanical capabilities.
Suppose that t represents a vector from the current position of an atom in the model to a target position then (see Section 3.3.1.1.3), to first order, the observational equations are in which 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 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. in which is a unit vector defining the axis of rotation for an angular variable , and are position vectors of the atom A and the site of the parameter P, and represents a residual vector.
is minimized by in which More generally, if σ represents any scalar quantity which is to be minimized, e.g. an energy, then
It is beyond the scope of this chapter to review the methods available for evaluating from these equations. Difficulties may arise from two sources:
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 nonlinearity is serious less dependence should be placed on M and gradient methods using searches are more valuable. In this connection Diamond (1966) introduced a sliding filter technique which produced rapid convergence in extreme conditions of nonlinearity. These topics have been reviewed elsewhere (Diamond, 1981, 1984b) and are the subject of many textbooks (Walsh, 1975; Gill et al., 1981; Luenberger, 1984).
Warme et al. (1972) 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 twostage 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, 1980a,b). Parametric shifts which satisfy the constraints are solutions of in which and depend only on the target vectors, , of the atoms with constrained positions and on the corresponding derivatives. We then find a partitioned orthogonal matrix satisfying in which are the eigenvectors of having positive eigenvalues, are those having zero eigenvalues, and and are arbitrary orthogonal matrices. Then in which the matrix to be inverted is positive definite. , however, is rectangular so that multiplying on the left by does not necessarily serve to determine , but we may write giving and is indeterminate and free to adopt any value. We therefore adopt which is the smallest vector of parametric shifts which will satisfy the constraints, and allow to be determined by the remaining observational equations in which the target vectors, t, are now modified to according to and being the derivatives and effective target vectors for the unconstrained atoms. We then solve in which is required to be of the form giving and apply the total shifts to obtain a structure which is optimized within the restrictions imposed by the constraints.
It may happen that is itself singular because there are insufficient data in the vector to control the structure and the parametric shifts contained in fully. In this event the same process may be applied again, basing the solution for on so that the vectors in 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 may be found from by using the fact that the columns of are all linear combinations of the columns of and are void of any contribution from . It follows that may be found by using the columns of as priming vectors in the Gram–Schmidt process [Section 3.3.1.2.3 (i)] until the normalizing step involves division by zero. is then complete if all the columns of have been tried. 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 atoms [having bond lengths, n bond angles and dihedral angles] in which atom 1 is required to coincide with atom and atom 2 with . then contains two vectors, namely the lackofclosure vectors at these points, and is typically zero. is then found to have five columns corresponding to the five degrees of freedom of two points of fixed separation; contains only zeros if the ring is initially closed, and contains ringclosure corrections if, through nonlinearity or otherwise, the ring has opened. contains columns if the chain of points has p variable parameters. It follows, if bond lengths and bond angles are treated as constants, that the sevenmembered ring is the smallest ring which is flexible, that the sixmembered 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 fivemembered ring. Therefore some variation of bond angles and/or bond lengths is essential for the modelling of flexible five and sixmembered rings. Treating the ring as a chain of 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 fivemembered rings with nearconstant bond angles is the concept of the pseudorotation angle P, and amplitude , for which the jth dihedral angle is given by This formulation has the property , which is not exactly true; nevertheless, values measured from observed conformations comply with this formulation within a degree or so (Altona & Sundaralingam, 1972).
Software specialized to the handling of condensed ring systems has been developed by van der Lieth et al. (1984) (Section 3.3.3.3.1) and by Cohen et al. (1981) (Section 3.3.3.3.2).
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) 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 in which the column matrix contains alterations to the atomic coordinates, contains residual discrepancies and D is a large sparse rectangular matrix containing values of , of which there are not more than six nonzero values on any row, consisting of direction cosines of the line of which l is the length. is then minimized by setting which they solve by the method of conjugate gradients without searches. This places reliance on the linearity of the observational equations (Diamond, 1984b). It also works entirely with the sparse matrix , the dense matrix , 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 quasilinear region, but is less effective when large dihedralangle 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 secondnearestneighbour distances; this is effective except for bond angles near 180° so that, in particular, planar groups require an outofplane 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 nextnearestneighbour 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 smallmolecule structures, or from estimates of their accuracy, or from estimates of accuracy of the target positions.
Hermans & McQueen (1974) 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) (Section 3.3.3.2.7) and is an integral part of the GRIP system (Tsernoglou et al., 1977; Girling et al., 1980) (Section 3.3.3.2.2) for which it was designed.
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 potentialenergy minima. Molecularmechanics 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 potentialenergy 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 potentialenergy barriers between minima, and subsequently attenuate the momenta again. In this way a number of minima may be found (Levitt & Warshel, 1975). It is equivalent to initializing a potentialenergy 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) 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 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 threedimensional 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 higherdimensional space. This, in itself, does not guarantee that the threedimensional minimumenergy 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.
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; Levitt, 1974; Diamond, 1966; Warme et al., 1972; Dodson et al., 1976; Hermans & McQueen, 1974) are not discussed further.
For some of the earliest work Levinthal (1966) still makes interesting reading and Feldmann (1976) 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). Excellent bibliographies relating to these sections have been given by Morffew (1983, 1984), 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.
One of the earliest systems designed for information retrieval and display was that described by Meyer (1970, 1971) which used television raster technology and enabled the contents of the Brookhaven Protein Data Bank (Meyer, 1974; Bernstein et al., 1977) to be studied visually by remote users. It also enabled a rigid tworing molecule to be solved from packing considerations alone (Hass et al., 1975; Willoughby et al., 1974). 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 realtime rotation except for relatively simple drawings, though GRAMPS is an exception (O'Donnell & Olson, 1981; Olson, 1982) (Section 3.3.3.1.4).
This program, the Oak Ridge Thermal Ellipsoid Program, due to Johnson (1970, 1976) 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 equiprobability 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 linedrawing versions the problem of hiddenline 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.
R. J. Feldmann and coworkers (Feldmann, 1983) 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 rastergraphics 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 lowerresolution 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).
The algorithm developed by Porter (1978) 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 spacefilling pictures of a similar general character have been produced by Motherwell (1978), by Sundaram & Radhakrishnan (1979) and by Lesk (next section).
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, 1981, 1985) 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 lessorganized regions, or the creasedribbon technique for the whole chain, or a ballandstick representation of atoms and bonds, or spacefilling spheres. All these styles are available simultaneously in a single picture with depth cueing, colour and shading, and hiddenfeature 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, 1985).
This system, due to O'Donnell & Olson (O'Donnell & Olson, 1981; Olson, 1982) provides a highlevel 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 (1980) 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.
This system, due to Langridge and coworkers (Gallo et al., 1983; Ferrin et al., 1984) 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).
This system, originally due to Dayringer et al. (1986), 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 nonmolecular, 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 was developed by Motherwell (1978) at the Cambridge Crystallographic Data Centre (CCDC) for the display of molecular structures and crystalpacking diagrams, including an option for spacefilling model style with shadowing. The emphasis was on a free format command and data structure, and the ability to produce ballandspoke 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 hydrogenbonded networks, and sections through packing diagrams (Cambridge Structural Database, 1994).
Systems described in this section require realtime rotation of complicated transparent scenes and all used vectorgraphics 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 electrondensity map, with due attention being paid to stereochemical considerations, by one or more of several approaches.
Katz & Levinthal (1972) 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 aminoacid 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 energyminimization routine using a steepestdescent method in the space of the dihedral angles and referring to the Lennard–Jones potential for nonbonded 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 electrondensity map which are separated by less than, say, 1.8 Å, which is an important aid to interpretation when the resolution is sufficiently high.
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 electrondensity map to be interpreted ab initio without the aid of mechanical models (Tsernoglou et al., 1977). Girling et al. (1980) give a more recent example of its use.
In its 1975 version GRIP is a threemachine system. Centrally there is a minicomputer which receives inputs from the user and controls a vector display with highspeed matrixmultiplication capability. The third machine is a mainframe computer with highspeed 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 longrange 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), which treats atomic position vectors, rather than bond rotations, as independent variables.
The system made pioneering use of a twoaxis joystick to control orientation and a threetranslation joystick to control position.
These systems (Barry & North, 1971; North et al., 1981; North, 1982) are examples of pioneering work done with minicomputers before purposebuilt graphics installations became widespread; examples of their use are given by Ford et al. (1974), Potterton et al. (1983) and Dodson et al. (1982). 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) 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.
The Molecular Modelling SystemX (MMSX) is a system of purposebuilt 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. Nonhelical segments are built helically initially and unwound by usercontrolled 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).
Miller et al. (1981) 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 AbadZapatero et al. (1980).
This system (Morimoto & Meyer, 1976), a development of Meyer's earlier system (Section 3.3.3.1), uses vectorgraphics 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 reshaping or repositioning of the model to suit an electrondensity 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 nonidealized coordinates.
The system was successfully applied to the structures of rubredoxin and the extracellular nuclease of Staphylococcus aureus (Collins et al., 1975) and to binding studies of sulfonamides to carbonic anhydrase (Vedani & Meyer, 1984). 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) and arabinose binding protein in 1978 (Gilliland & Quiocho, 1981).
This system (Diamond, 1980a,c, 1982b) 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 usercontrolled 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 3.3.1.3.9, 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 leastsquares 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 underdetermined situations, providing a minimumdisturbance 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 `realspacerefinement' program (Diamond, 1971). 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 3.3.2.2.1 and in detail by Diamond (1980a,b).
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). Bloomer et al. (1978), Phillips (1980), and Evans et al. (1981) give examples of its use.
This system, due to Jones (Jones, 1978, 1982, 1985; Jones & Liljas, 1984), in its original implementation was a threemachine 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) 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 online contouring. It has also been developed (Jones & Liljas, 1984) 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) but without the maintenance of chain continuity, which is subsequently reintroduced by regularization.
Horjales and Cambillau (Cambillau & Horjales, 1987; Cambillau et al., 1984) 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.
Brandenburg et al. (1981) 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.
This program, due to Hubbard (1985) (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, ballandstick, and other rastergraphics 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 mainchain or sidechain 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 Xray crystallographic data, and provides interfaces to molecularmechanics 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.
Jones et al. (1991) 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 electrondensity map to a skeletal representation (Greer, 1974; Williams, 1982) 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 moleculardynamics procedures, even though some imperfect geometry is to be expected where each tripeptide joins the next.
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), Burkert & Allinger (1982) and Boyd & Lipkowitz (1982). 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.
Liljefors (1983) 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 —CH_{3} but not —NH_{2} the latter may be obtained by incorporating —CH_{3}, 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) have described an extension to this that is specialized to the construction of fusedring 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 modelbuilding program which accepts twodimensional molecular drawings in a manner similar to Script (Section 3.3.3.3.2) and constructs approximate threedimensional coordinates from these. It is the modelbuilding component of SECS (Simulation and Evaluation of Chemical Synthesis) (Wipke et al., 1977; Wipke & Dyott, 1974; Wipke, 1974). See also Anderson (1984).
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).
This system, described by Cohen et al. (1981), is specialized for fusedring 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 twodimensional representation of a molecule using single lines for single bonds, double lines for double bonds, and wedges to indicate outofplane 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 hydrogenbonding terms. An example is given of the identification of an unusual conformer as the most stable one from twelve possibilities for a fourring system.
The program is a development of similar work by Cohen (1971) 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.
This system, due to Brooks et al. (1983), is primarily concerned with molecular dynamics but it includes the capability of modelbuilding 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 hydrogenbonding 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 —CH_{2}— 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.
A number of very powerful molecularmodelling 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 ChemX system, from Chemical Design Ltd, enables models to be developed from sketchpad input, provides for their geometrical optimization and interfaces the result to Gaussian80 for quantummechanical calculations.
MACCS , from Molecular Design Ltd, and related software (Allinger, 1976; Wipke et al., 1977; Potenzone et al., 1977) has similar features and also has extensive databasemaintenance facilities including data on chemical reactions.
Sybyl , from Tripos Associates (van Opdenbosch et al., 1985), also builds from sketches with a standard fragment library, and provides interfaces to quantummechanical routines, to various databases and to MACCS.
Insight II (Section 3.3.3.1.7) is available from Biosym and GRAMPS (Section 3.3.3.1.4) is available from T. J. O'Donnell Associates.
References
AbadZapatero, C., AbdelMeguid, 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.AbiEzzi, 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). Nonlinear 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., HummelinkPeters, B. G., Kennard, O., Motherwell, W. D. S., Rodgers, J. R. & Watson, D. G. (1979). The Cambridge Crystallographic Data Centre: computerbased 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, ClearText Encoding of Archive File (1988). ANSI X3.144–1988. ANSI, New York, USA.
Anderson, S. (1984). Graphical representation of molecules and substructuresearch 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: SpringerVerlag.
Barry, C. D. & North, A. C. T. (1971). The use of a computercontrolled 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 realtime computer graphics. Science, 222, 1325–1327.
Beddell, C. J. (1970). An Xray 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 computerbased 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 proteinligand 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 computerdrawn 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). Solventaccessible 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 modelbuilding procedure for proteins. Acta Cryst. 21, 253–266.
Diamond, R. (1971). A realspace 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). Interactive 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). Threedimensional perception for oneeyed 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: insulinlike 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: SpringerVerlag.
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 interactive 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 lysozymetetrasaccharide 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 Larabinosebinding 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 leastsquares 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 electrondensity maps using a smallstore computer. Acta Cryst. 22, 465–468.
Greer, J. (1974). Threedimensional 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 stereoviewer 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 molecularpacking 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 twoday conference, London, October 1984. London: Oyez Scientific.
International Standards Organisation, International Standard Information Processing Systems – Computer Graphics – Graphical Kernel System for Three Dimensions (GKS3D), Functional Description (1988). ISO Document No. 8805:1988(E). American National Standards Institute, New York, USA.
International Tables for Crystallography (2005). Vol. A. Spacegroup 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 thermalellipsoid plot program for crystal structure illustrations. Report ORNL5138. Oak Ridge National Laboratory, Tennessee, USA.
Johnson, C. K. (1980). Computergenerated 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 noncrystallographic 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). Realtime 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 b_{562} by redetermining the primary structure and using molecular graphics. J. Mol. Biol. 148, 427–448.
Lesk, A. M. & Hardman, K. D. (1982). Computergenerated schematic diagrams of protein structures. Science, 216, 539–540.
Lesk, A. M. & Hardman, K. D. (1985). Computergenerated 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 modelbuilding 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 eggwhite 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). Threedimensional graphical models of molecules and a timeslicing 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., AbdelMeguid, 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 interactive computer graphics. New York: McGrawHill.
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 realtime, interactive, threedimensional 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 multipleminima 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 Xray 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). Minicomputer control of a stereo graphics display. J. Appl. Cryst. 7, 430–434.
Wipke, W. T. (1974). Computer assisted threedimensional 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.