Volume 67 Received 3 December 2010  Exact directspace asymmetric units for the 230 crystallographic space groups^{a}Physical Biosciences Division, Lawrence Berkeley National Laboratory, 1 Cyclotron Road, BLDG 64R0121, Berkeley, California, 947208118, USA,^{b}UC Leads Summer Research Program, University of California, Berkeley, California, 94720, USA, and ^{c}Bioscience Division, Los Alamos National Laboratory, B8, MS M888, Los Alamos, New Mexico, 87545, USA It is well known that the directspace asymmetric unit definitions found in the International Tables for Crystallography, Volume A, are inexact at the borders. Face and edgespecific subconditions have to be added to remove parts redundant under symmetry. This paper introduces a concise geometric notation for asymmetric unit conditions. The notation is the foundation for a reference table of exact directspace asymmetric unit definitions for the 230 crystallographic spacegroup types. The changeofbasis transformation law for the conditions is derived, which allows the information from the reference table to be used for any spacegroup setting. We also show how the vertices of an asymmetric unit can easily be computed from the information in the reference table. Keywords: asymmetric unit; direct space; space groups. 
In the presence of symmetry, the concept of an asymmetric unit (also known as fundamental region in mathematics) is important for many practical applications, for example to avoid timeconsuming redundant calculations or to suppress redundant output. International Tables for Crystallography, Volume A (ITA) (Hahn, 2005) defines the directspace asymmetric unit of a crystallographic space group (DAU) as `the smallest part of space from which, by application of all symmetry operations of the space group, the whole of space is filled exactly' (ITA §2.2.8). This paper focuses on definitions of exact DAUs. These are refinements of the ITA conditions, which are sets of inequalities for each space group that must be true simultaneously for a point with fractional coordinates x, y, z to be inside the DAU, for example ; ; for space group P2. The ITA conditions define the DAU shapes but are inexact for the borders. For example, the ITA P2 conditions are true for all eight vertices of the DAU parallelepiped, but according to the definition in ITA §2.2.8 only two of these points can be in the exact asymmetric unit. To make a DAU exact, subconditions have to be added to the shape conditions, specific to faces and edges. Koch & Fischer (1974) published exact DAU definitions for the cubic space groups. In GrosseKunstleve et al. (2003) we presented an overview of an online gallery of exact DAUs for all 230 crystallographic space groups. Chapter 1.5 of Shmueli (2008) and the KVEC server at http://www.cryst.ehu.es also offer exact DAU definitions, but the DAU shapes are partially incompatible with those of ITA. In this paper we introduce a concise geometric notation which is the foundation for a reference table of exact DAUs, using the same definitions as in our previous work, which are fully compatible with those of ITA.
This section defines a concise geometric notation that has greatly accelerated the progress of this work. As will become apparent below, the notation enables a systematic, intuitive labelling of planes that define an exact DAU.
Similar to the ITA approach, a DAU shape is defined by a list of inequalities. We work with the general form
or
h, k, l are Miller indices that define the normal vector of a plane, c is a scalar constant which determines the distance of the plane from the origin, and x, y, z are fractional coordinates in direct space. We call both equations a cut since the geometric interpretation is a division of direct space into two halves. The lefthand side of the equations is exactly zero for points inside the cut plane. The inequalities are defined to be true for points x, y, z inside the DAU. Equation (1) is used if a region of the cut plane is inside the DAU and equation (2) is used if the entire plane is outside. To facilitate a concise representation of DAU definitions, we introduce a cut notation. The general form is
or
corresponding to equations (1) and (2), respectively. To obtain intuitive labels for DAU cut planes, we use the geometric cut symbols defined in Table 1, for example tx_{0} = cut((2, 1, 1), 0). Relationships between cuts can be formalized via cut expressions using unary and binary operators defined as follows:
The variable s is a scalar value. Each of the operators defined in equations (5)(8) has a simple geometric interpretation. The `' operator defined by equation (5) corresponds to a reversal of `inside' and `outside'. The `' operator defined by equation (6) acts like a centre of inversion at the origin; see Figs. 1(b) and 1(c) for an example. The multiplication and division operators defined by equations (7) and (8) provide a notation for parallel shifts, as highlighted by Fig. 1(a).

 Figure 1 Illustrations of selected cut planes with geometric cut symbols x_{d}, p_{d}, m_{d}, h_{d} and k_{d}. The (x, y, 0) plane of a unit cell is outlined with thin lines. The unitcell origin is labelled with 0, the basis vectors with a and b. The traces of cut planes are indicated with thick lines; small attached triangles indicate the `inside' direction. (a) Geometric interpretation of equations (7) and (8) using the x_{d} flock as an example. (b) Cut planes in the p_{d} and m_{d} flocks as they appear in a tetragonal system. The p_{2} and p_{2} cut planes illustrate the geometric interpretation of equation (6). (c) Cut planes in the p_{d}, m_{d}, h_{d} and k_{d} flocks as they appear in a trigonal or hexagonal system. 
The DAU conditions of ITA have a straightforward correspondence to our cut definition. We call the ITA conditions shape cuts. We employ the concept of context to avoid redundancy in the definition of subconditions specific to a given DAU face by appending the subconditions to the corresponding shape cut, surrounded by parentheses; such a cut is a face cut. Similarly, subconditions specific to a given edge are appended to a corresponding face cut, again surrounded by parentheses, and are called edge cuts. In some cases, the DAU choices of ITA necessitate the combination of cuts via logical conjunction or disjunction. Following common practice, we chose the symbol `&' for conjunction and `' for disjunction. To give an example, the cut expression
appears for space group (No. 112), using the geometric cut notation of Table 1. Here x_{0} is a shape cut. The expression in the outer pair of parentheses is a face cut, composed of the logical conjunction z_{4} & z_{0}. The expression in the inner pair of parentheses (y_{0}) is an edge cut. As an example, a full stepbystep interpretation of equation (9) is shown in Appendix A.
The symbols in Table 1 include seven main flocks of parallel planes: x_{d}, y_{d}, z_{d}, p_{d}, m_{d}, h_{d}, k_{d}. The position of a cut plane relative to the origin of the coordinate system is indicated with the index d = 1/c, with c as defined in equations (3) and (4), except if c = 0 or c = 3/4. Fig. 1 illustrates the geometric interpretation of the main geometric cut symbols. A large majority of the cut planes needed in the DAU definitions presented below can be labelled intuitively with these symbols. The remaining symbols in Table 1 were introduced primarily to condense the DAU definitions in Table 2 below.

In many situations it is essential to be able to transform variables from one basis system to another. Giacovazzo (1992) includes a table of transformation laws (Table 2.E.1) for commonly used variables, for example fractional coordinates, Miller indices or anisotropic displacement parameters. This list can be extended by a transformation law for DAU definitions based on equations (1) and (2). Borrowing the conventions of ITA, let () be a changeofbasis matrix with a (3 × 3) rotation part and translation vector , and let () be its inverse. A column vector of fractional coordinates in a first basis system is transformed to coordinates in a second basis system via
We also define the row vector = (h, k, l) in the first basis system. The corresponding in the second basis system is given by
The determination of the scalar constant is based on the rationale that
must hold for all solutions of
Setting , substituting equations (10) and (11), and solving for yields the second part of the transformation law for DAU cuts:
Given a list of shape cuts, the DAU vertices can be computed by solving equation (13) for all unique ordered triplets of cuts. Let and be the cut normal vectors of such a triplet. The three cut planes intersect in a point if the determinant of
is not zero. Under this condition the point is found by solving = 0:
is a vertex of the DAU if all inequalities given by the shape cuts are also simultaneously true. If more than three planes intersect in a given vertex it is obtained multiple times and duplicates are discarded. We note that the largest number of shape cuts using the ITA definitions is nine, for space group (No. 230). In this case the determinant of is evaluated 84 times, equation (16) is evaluated 56 times and the final number of unique vertices is nine, in accordance with ITA.
The exact conditions shown in Table 2 are validated with a sampling procedure to establish that the DAU is neither too small nor too large. The procedure is intentionally unsophisticated to maximize robustness. It is intrinsically highly inefficient, which is compounded by the use of a dynamically typed scripting language for its implementation. Nonetheless, given current computing hardware, the entire Table 2 can be revalidated in less than 2 min.
The first part of the validation procedure samples the DAU conditions using two grids over the unit cell, given a userdefined number of sampling points N per unit in fractional coordinate space. To simplify this presentation, without loss of generality, we assume that N is identical in all three dimensions. N is always chosen to be even. The first ugrid covers the unit cell from 0 to N  1, corresponding to the range [0.0, 1.0[ in fractional coordinate space. All ugrid points are initialized with zero. The second rgrid covers space more redundantly from N/2 to N, corresponding to the range [0.5, 1.0]. The vertex determination of §3.2 is used to assure that the DAU to be validated falls entirely into the rgrid. For each rgrid point, the inequalities defined by the DAU cuts are evaluated. A value of one is assigned if the point is inside the DAU (all inequalities are true) and zero otherwise. If the point is inside the DAU, the crystallographic unit translations, in the form of the modulus operation, are applied to the grid indices of the point to determine the symmetryequivalent grid point in the ugrid, which is then also set to one. If it was set already, an error message reports that the point is redundant.
At the end of the first part of the validation procedure the ugrid has a value of one for all grid points inside the DAU and zero for all points outside; note that the ugrid has disconnected regions of grid points with value one if the DAU has points with negative coordinates. The second part of the validation procedure visits each point in the ugrid. The symmetry operations of the space group, taking the crystallographic unit translations and any centring translations into account, are applied to enumerate all equivalent points in the ugrid. If a point is flagged as inside the DAU, all equivalent points must be flagged as outside; otherwise an error message reports that the DAU has redundant points. For each point flagged as outside the DAU, one equivalent point must be flagged as inside; otherwise an error message reports that the point has no equivalent in the DAU.
If no error messages are shown, the validation procedure establishes conclusively that the DAU conditions have complete coverage and that the covered space is nonredundant under symmetry. The only critical parameter is the number N of sampling points per unit in fractional space. Based on an inspection of the locations of the symmetry elements, we found that N = 24 is sufficiently large for all space groups. However, as a final validation we also ran the procedure for all space groups with N = 72, which takes about 45 min on a current 48core system.
The exact DAU conditions shown in Table 2 were determined manually. Progress was greatly accelerated by visual tools developed specifically for this purpose. A full presentation of these tools is beyond the scope of this paper [GrosseKunstleve et al. (2003) includes pointers to the openly available implementation]. The main idea is to colourcode pairs of redundant points on the DAU surface as they are detected in the sampling procedure described in §3.3; for example, the first point is coloured dark blue and the equivalent redundant point light blue. A very simple colourselection procedure using only a small palette of colours was found to be sufficient in practice. An example is shown in Fig. 2. We added the face or edgespecific cuts one at a time, updating the visualization after each step. In this way we could determine exact DAU definitions in a matter of a few minutes for most space groups.
 Figure 2 Visualization of redundant pairs of points at the surface of the DAU of space group P4_{2} (No. 77). Colourcoded pairs of redundant points on the DAU surface are shown as they are detected in the sampling procedure described in §3.3. For example, the first point is coloured dark blue and the equivalent redundant point light blue. With the help of the colours it is immediately obvious how the redundant points are related and where to place the missing face cuts to obtain the exact DAU. 
Table 2 defines exact DAUs for 230 reference settings, chosen to be compatible with the reference settings used in the IUCr symCIF dictionary (Brown, 2005). Using the changeofbasis transformation law of §3.1 in combination with the algorithms of GrosseKunstleve (1999), it is possible to automatically obtain an exact DAU for any setting.
Koch & Fischer (1974) and ITA §2.8 explain that the shape for a DAU is not uniquely determined and that the best choice is application specific. Similarly, the face and edgespecific subconditions required for an exact DAU are also not uniquely determined. The choices we made for Table 2 aim at obtaining compact sets of subconditions, which is also expected to minimize the runtime needed for evaluating if a given point is inside the DAU. For the cubic space groups, we attempted to adopt the subconditions of Koch & Fischer (1974) but it turned out to be challenging in some cases. In six cases (spacegroup numbers 195, 198, 210, 220, 227, 228) the ITA shape conditions are incompatible with those of Koch & Fischer (1974). In some other cases their subconditions lead to complicated cut expressions. Using the approach of §3.4 it was only a small effort to determine simpler alternatives for Table 2.
For eight enantiomorphic space groups (the numbers are listed in the caption of Table 2) the exact DAU is defined through a changeofbasis transformation of the DAU of the enantiomorphic mate. The three remaining enantiomorphic pairs of space groups cannot be handled in this way because the ITA shape DAU conditions are pairwise incompatible. The changeofbasis matrices in Table 2 are expressed using the notation as defined in Zwart et al. (2008).
Table 2 is the first complete and uniform definition of exact DAUs for all 230 spacegroup types. The table is concise owing to the geometric cut notation introduced in this work. At the same time, the cut expressions lend themselves to automatic processing, with results as demonstrated already in GrosseKunstleve et al. (2003). In the meantime we have found other practical uses in the context of the PHENIX suite (Adams et al., 2010), such as the search for interactions between pairs of atoms (GrosseKunstleve et al., 2004) and a bulksolventmask determination procedure.
In this work we have used a manual approach for the determination of the face and edgespecific subconditions required for exact DAUs. We believe an algorithmic approach is possible but will require significantly more initial effort than our manual approach. The cut plane formalism presented here could serve as a basis for future automation work.
Equation (9) in §2, which appears for space group (No. 112) in Table 2, was shown as an example of a geometric cut expression:
The shape cut in this example is x_{0}. According to Table 1 and employing equation (7), this geometric cut symbol expands to cut ((1,0,0),0). Use of equation (1) yields , which simplifies to . The outer pair of parentheses encloses a face cut expression that applies only if x = 0 [see text following equation (8) in §2]. The first part of the face cut expression, z_{4}, translates to [lookup in Table 1, use of equations (8) and (1), and simplification]. The second part of the face cut expression, z_{0}, translates to . The logical conjunction symbol `&' (defined in §2) indicates that a point in the plane is in the DAU only if both and , with and in the Boolean sense. The inner pair of parentheses encloses an edge cut expression specific to the (0, y, 0) line defined by the conditions x = 0 and z = 0. Lookup in Table 1, use of equations (7), (5) and (1), and simplification lead to the subcondition . In combination with the y_{0} shape cut of space group , this means that only the point (0, 0, 0) on the (0, y, 0) line is in the DAU.
Graphical illustrations of the DAU conditions are available at http://cci.lbl.gov/asu_gallery/ . An expanded DAU notation that is more similar to the notation of ITA is shown along with the graphical illustrations.
We thank Michael M. J. Treacy for sending us an electronic file with a table of the DAU shape conditions of ITA. We thank the anonymous referees for corrections and suggestions that have led us to an improved presentation. We gratefully acknowledge the financial support of NIH/NIGMS through grant Nos. 5P01GM063210 and 1R01GM071939. Our work was supported in part by supplemental funding from the American Recovery and Reinvestment Act (ARRA) to NIH/NIGMS grant No. P01GM063210 and by the US Department of Energy under contract Nos. DEAC0376SF00098 and DEAC0205CH11231.7237.
Adams, P. D. et al. (2010). Acta Cryst. D66, 213221.
Brown, I. D. (2005). ftp://ftp.iucr.org/cifdics/cif_sym_1.0.1.dic .
Giacovazzo, C. (1992). Fundamentals of Crystallography. IUCr/Oxford University Press.
GrosseKunstleve, R. W. (1999). Acta Cryst. A55, 383395.
GrosseKunstleve, R. W., Afonine, P. V. & Adams, P. D. (2004). Newsletter of the IUCr Commission on Crystallographic Computing, 4, 1936.
GrosseKunstleve, R. W., Wong, B. & Adams, P. D. (2003). Newsletter of the IUCr Commission on Crystallographic Computing, 2, 1016.
Hahn, T. (2005). International Tables for Crystallography, Vol. A. Heidelberg: Springer.
Koch, E. & Fischer, W. (1974). Acta Cryst. A30, 490496.
Shmueli, U. (2001). International Tables for Crystallography, Vol. B, 2nd ed. Dordrecht: Kluwer.
Shmueli, U. (2008). International Tables for Crystallography, Vol. B, 3rd ed. Heidelberg: Springer.
Zwart, P. H., GrosseKunstleve, R. W., Lebedev, A. A., Murshudov, G. N. & Adams, P. D. (2008). Acta Cryst. D64, 99107.