Indexing

Kabsch, W.

doi:10.1107/97809553602060000676

International
Tables for
Crystallography
Volume F
Crystallography of biological macromolecules
Edited by M. G. Rossmann and E. Arnold

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. F. ch. 11.3, p. 220 | 1 | 2 |

Section 11.3.2.7. Indexing

W. Kabsch^a ^*

^a Max-Planck-Institut für medizinische Forschung, Abteilung Biophysik, Jahnstrasse 29, 69120 Heidelberg, Germany
Correspondence e-mail: kabsch@mpimf-heidelberg.mpg.de

11.3.2.7. Indexing

| top | pdf |

Once a basis $[{\bf b}_{1}, {\bf b}_{2}, {\bf b}_{3}]$ of the lattice is available, integral indices $[h_{i}, k_{i}, l_{i}]$ must be assigned to each reciprocal-lattice vector $[{\bf p}_{0i}^{*}\ (i = 1, \ldots, n)]$ . Using the integers nearest to $[{\bf p}_{0i}^{*} \cdot {\bf b}_{k}\ (k = 1,2,3)]$ as indices of the reciprocal-lattice vectors $[{\bf p}_{0i}^{*}]$ could easily lead to a misindexing of longer vectors because of inaccuracies in the basis vectors $[{\bf b}_{k}]$ and the initial values of the parameters describing the instrumental setup. A more robust solution of the indexing problem is provided by the local indexing method which assigns only small index differences $[h_{i} - h_{j}, k_{i} - k_{j}, l_{i} - l_{j}]$ between pairs of neighbouring reciprocal-lattice vectors (Kabsch, 1993).

The reciprocal-lattice points can be considered as the nodes of a tree. The tree connects the n points to each other with the connections as its branches. The length $[\ell_{ij}]$ of a possible branch between nodes i and j is defined here as $[\eqalign{\ell_{ij} &= 1 - \exp\left(-2 {\textstyle\sum\limits_{k = 1}^{3}}\left\{[\max(|\xi_{k}^{ij} - h_{k}^{ij}| - \varepsilon,0)/\varepsilon]^{2}\right.\right.\cr&\quad\left. +\; [\max(|h_{k}^{ij}| - \delta,0)]^{2}\right\}\bigg)\cr \xi_{k}^{ij} &= ({\bf p}_{0i}^{*} - {\bf p}_{0j}^{*}) \cdot {\bf b}_{k}, \quad h_{k}^{ij} = \hbox{ nearest integer of }\xi_{k}^{ij}, \quad k = 1,2,3.}]$ Reliable index differences are indicated by short branches; in fact, $[\ell_{ij}]$ is 0 if none of the indices $[h_{k}^{ij}]$ is absolutely larger than δ and the $[\xi_{k}^{ij}]$ are integer values to within ɛ. Typical values of ɛ and δ are $[\varepsilon = 0.05]$ and $[\delta = 5]$ . Defining the length of a tree as the sum of the lengths of its branches, a shortest tree among all $[n^{n-2}]$ possible trees is determined by the elegant algorithm described by Dijkstra (1976). Starting with arbitrary indices 0, 0, 0 for the root node, the local indexing method then consists of traversing the shortest tree and thereby assigning each node the indices of its predecessor plus the small index differences between the two nodes.

During traversal of the tree, each node is also given a subtree number. Starting with subtree number 1 for the root node, each successor node is given the same subtree number as its predecessor if the length of the connecting branch is below a minimal length $[\ell_{\min}]$ . Otherwise its subtree number is incremented by 1. Thus all nodes in the same subtree have internally consistent reflection indices. Defining the size of a subtree by the number of its nodes, aliens are usually found in small subtrees. Finally, a constant index offset is determined such that the centroids of the observed reciprocal-lattice points $[{\bf p}_{0i}^{*}]$ belonging to the largest subtree and their corresponding grid vectors $[\sum\nolimits_{k = 1}^{3}h_{k}^{i}{\bf b}_{k}^{*}]$ are as close as possible. This offset is added to the indices of each reciprocal-lattice point.

References

Dijkstra, E. W. (1976). A discipline of programming, pp. 154–167. New Jersey: Prentice-Hall.Google Scholar

Kabsch, W. (1993). Automatic processing of rotation diffraction data from crystals of initially unknown symmetry and cell constants. J. Appl. Cryst. 26, 795–800.Google Scholar

International Tables for Crystallography (2006). Vol. F. ch. 11.3, p. 220