SAUC

Access to the source of SAUC

This program and related scripts are available from github at https://github.com/yayahjb/sauc or as a zip file from https://github.com/yayahjb/sauc/archive/master.zip.
The information below is available for download from arxiv.org/abs/1307.1811.

Revison 1.0

Revision 0.9 of 11 August 2015 added support for searching cell from the Cambridge Structural Database from Cambridge Crystallographic Data Centre as a development effort in support of image identification for synchrotrons. That version was experimental. Support for specifying the sphere radius as a percentage and for specifying a limit on the number of hits are provided.

Revision 0.8 of 24 April 2014 had revised output, following the suggestions of Graeme Winter and the good example of Nearest-Cell (Ramraj et al., 2011) in giving some of the provenance of the cell and organizing long output lists into collapsed lists of families. Unlike Nearest-Cell we have chosen to organize the families on the PDB HEADER field, rather than the sequence. For clarity, many uses of the term "algorithm" have been changed to "metric". The output of the nearest cell search has been changed to include the distance and to conform to the style of the style of the Sphere search output. The NCDist metric algorithm has been updated to the most current release. -- MA & HJB

Introduction

(Andrews & Bernstein, 2012) introduced a topological embedding of the Niggli "cone" of reduced cells with the goal of calculating a meaningful distance between unit cells. In the second paper of this series, the embedding was used to determine likely Bravais lattices for a unit cell. Here we apply the embedding to searching within a database for lattices "close" to the lattice of a given probe cell.

A crystallographic cell is a representation of a lattice, but each lattice can be represented just as well by any of an infinite number of such unit cells. Searching for matches to an experimentally determined crystallographic unit cell in a large collection of previously determined unit cells is a useful verification step in synchrotron data collection and can be a screen for "similar" substances (Ramraj et al., 2011) (Mighell, 2002), but it is more useful to search for a match to the lattice represented by the experimentally determined cell, which may involve many more cells. For identification of substances with small cells, a unit cell match may be sufficient for unique identification (Mighell, 2001).

Due to experimental error and multiple cells representing the same lattice and differing choices of lattice centering, simple searches based on raw cell edges and angles can miss similarities. A database of lattices using the G⁶ representation of the Niggli-reduced cell as the search key provides a more robust and complete search. Searching is implemented by finding the distances from the probe cell to related cells using a topological embedding of the cone of Niggli reduced cells in G⁶. Comparison of results to those from older cell-based search algorithms suggests significant value in the new approach.

History

Tabulations of data for the identification of minerals dates to the 18th and 19th centuries. Data collected included interfacial angles of crystals (clearly related to unit cell parameters) and optical effects. See the historical review in (Burchard, 1998). With the discovery of x-ray diffraction, those tables were supplanted by new collections. Early compilations that included unit cell parameters arranged for material identification were "Crystal Structures" (Wyckoff, 1931), "Crystal Data Determinative Tables" (Donnay, 1943), and Handbook for Metals and Alloys (Pearson, 1958). Early computerized searches were created by JCPDS in the mid-1960's (Johnson, 2013) and the Cambridge Structural Data file and its search programs (Allen et al., 1973).

Those first searches were sensitive to the issues of differing equivalent presentations of the same lattice. The first effective algorithm for resolving that issue was (Andrews et al., 1980) using the V7 algorithm (NIH/EPA, 1980). Subsequently, other programs using the V7 algorithm have been described (see Table 1). The V7 algorithm has the advantage over simple Niggli-reduction based cell searches of being stable under experimental error. However, sensitivity to a change in an angle is reduced as that angle nears 90 degrees.

Background

An effective search method must find ways to search for related unit cells, even when they appear to be tabulated in ways that make them seem different. A trivial example is:
a = 10.0, b = 10.01, c = 20, α = 65, β = 75, γ = 90
versus
a = 10.0, b = 10.05, c = 20, α = 75, β = 65, γ = 90.

Clearly, these unit cells are almost identical, but simple tabulations might separate them. A somewhat more complex example includes the following primitive cells:
a = 3.1457, b = 3.1457, c = 3.1541, α = 60.089, β = 60.0887, γ = 60.104
versus
a = 3.1456, b = 3.1458, c = 3.1541, α = 90.089, β = 119.907, γ = 119.898.

Here the relationship is not as obvious. The embedding of (Andrews & Bernstein, 2012) can be used to show that the distance between these two cells is quite small in G⁶ (0.004 Ångstrom units squared in G⁶).

Implementation - Distance

The program SAUC is structured to allow use of several alternative metrics for searching among cells in an attempt to identify cells representing similar lattices. To simplify comparisons among results with the different metrics, all have been linearized and normalized, i.e. converted to Ångstrom units and scaled to be commensurate with the L₂ norm given below:

A simple L₁ or L₂ norm based on
[a, b, c, α(b + c)/2, β(a + c)/2, γ(a + b)/2]
with the distance scaled by 1/√(6) in the case of the L₁ norm and unscaled in case of the L₂ norm. The angles as assumed to be in radians and the edges in Ångstroms. The angles were converted to Ångstroms by multiplying by the average to the relevant edge lengths.

The square root of the BGAOL Niggli cone embedding distance NCDist based on
[a², b², c², 2bc cos(α), 2ac cos(β), 2ab cos(γ)].
Before taking the square root, the distances are scaled by √(6) divided by the average length of the cell edges. The overall square root linearizes the metric to Ångstrom units.

The V7 distances based on individual components linearized to Ångstrom units
[a, b, c, 1/a^∗, 1/b^∗, 1/c^∗,V^1/3]
and scaled by √(6/7). V is the volume.

These metrics are applied to reduced primitive cells [a, b, c, α, β, γ] and, when the reciprocal cell [a^∗, b^∗, c^∗, α^∗, β^∗, γ^∗] is needed for the V7 metric, that cell is also reduced.

In order to facilitate comparisons to older searches that just consider simple ranges in [a, b, c, α, β, γ], an option for such searches was also included in SAUC.

Validity of using the square root

The square root satisfies the stated requirements. It is monotone, and
√(u + v) ≤ √(u) + √(v)
↔ u + v ≤ (√(u) + √(v))² = u + v + 2√(uv)
which is clearly true.

Implementation - Searching

Range searching in amapped embedding needs to be done using a nearest-neighbor algorithm (or "post-office problem" algorithm (Knuth, 1973)). Exact matches are unlikely since most unit cells representing lattices in a database are experimental, and probe cells are also likely to be experimental data. Several efficient algorithms are available; we have used an implementation of neartree (Andrews, 2001).

The raw unit cell data is loaded into the tree once and serialized to a dump file on disk; subsequent searches do not need to wait for the O(Nlog(N)) tree build, which for the 70,000+ cells from the PDB can take half an hour in the BGAOL NCDist metric. The linearization makes the search space more compact and reduces the tree depth, thereby speeding searches. Because the PDB unit cell database contains many identical cells, we modified NearTree to handle the duplicates in auxiliary lists, further reducing the tree depth and speeding searches.

Comparison of Search Methods

The simplest approach to lattice searching is a simple box search on ranges in unit cell a, b and c and possibly on α, β, and γ, as for example in the "cell dimensions" option in the RCSB advanced search at http://www.rcsb.org/pdb/search/advSearch.do for the Protein Data Bank (Berman et al., 2000). In the following examples, we will call that type of search "Range". For the reasons discussed above, such simple searches can fail to find unit cells representing similar lattices but with very different edges that actually represent similar lattices. Such searches are best characterized as cell searches, rather than as lattice searches.

Searching on primitive reduced cells greatly improves the reliability of a search, as for example in (Ramraj et al., 2011) at http://www.strubi.ox.ac.uk/nearest-cell/nearest-cell.cgi, which uses a metric based on the reduced cell and all permutations of axes.While an improvement over simple range searches as discussed above, such searches can also miss similar lattices if the number of alternate lattice presentations considered is not complete. One way to reduce such gaps in searches is to use only parameters that do not depend on the choice of reduced presentation. The (Andrews et al., 1980) approach using 7 parameters (three reduced cell edges, three reduced reciprocal cell edges and the volume), "V7", helps, but has difficulty distinguishing cells with angles near 90 degrees. The NCDist approach used here, derived from (Andrews & Bernstein, 2012) both fills in the gaps and handles angles near to 90 degrees.

Consider, for example, the unit cells of phospholipase A₂ discussed by (Le Trong & Stenkamp, 2007). They present three alternate cells from three different PDB entries that are actually for the same structure:
[57.98, 57.98, 57.98, 92.02, 92.02, 92.02] from entry 1FE5 (Singh et al., 2001) in space group R32,
[80.36, 80.36, 99.44, 90, 90, 120] from entry 1U4J (Singh et al., 2005) in space group R3 and
[80.949, 80.572, 57.098, 90.0, 90.35, 90.0] from entry 1G2X (Singh et al., 2004) in space group C2. No simple Range search can bring these three cells together. For example, if we use the PDB advanced cell dimensions search around the cell from IU4J with edge ranges of +-3 Ångstroms and angle ranges of +-1 degree, we get 28 hits: 1CG5, 1CNV, 1FW2, 1G0Z, 1GS7, 1GS8, 1HAU, 1ILD, 1ILZ, 1IM0, 1LR0, 1NDT, 1OE1, 1OE2, 1OE3, 1QD5, 1U4J, 2BM3, 2BO0, 2H8A, 2HZ5, 2OHG, 2REW, 2WCE, 3I06, 3KKU, 3Q98, 3RP2, of which only three actually have cells close to the target using the linearized NCDist metric : 2WCE at 2.96 Ångstroms, 1G0Z at 0 Ångstroms, and 1U4J, the target itself. The remaining cells are, as we will see, rejected under the Nearest-Cell and the V7 metric. The simple Range searches are not appropriate to this problem.

Table 2 shows partial results from a lattice search using Nearest-Cell, and a V7 search using SAUC and a NCDist search using SAUC. We have restricted the searches to NCDist distances ≤ 3.5 Ångstroms. The Nearest-Cell metric appears to be in Ų. The column with the square root of the Nearest- Cell metric facilitates comparison with the linearized SAUC V7 and NCDist metrics. The searches showed consistent behavior: The three cells noted by (Le Trong & Stenkamp, 2007) are found in the same relative positions by all three searches. All cells found by Nearest-Cell are also found by both V7 and NCDist. Of the 42 structures found by all three metrics within 3.5 Ångstroms under the NCDist metric, four (1G0Z, 1G2X, 1DPY and 1FE5) are E.C. class 3.1.1.4 Phospholipase A2 structures, and three (1PKR, 1SGC and 1VRI) are other hydrolases (E. C. classes 3.4.21.7, 3.4.21.80, and 3.4.19.2, respectively) However, ten cells found by V7 and NCDist were not found by Nearest-Cell (2OSN, 2CMP, 3MIJ, 2SGA, 2YZU, 3SGA, 4SGA, 5SGA, 1CDC and 2CVK). Of those ten, one (2OSN) is an E.C class 3.1.1.4 Phospholipase A2 structure and four (2SGA, 3SGA, 4SGA and 5SGA are hydrolases, specifically E.C. class 3.4.21.80 Proteinase A. Two of the ten (2YZU and 2CVK) are thioredoxin, for which the ProMOL (Craig et al., submitted) motif finder shows significant active site homologies to multiple hydorolase motifs (2YZU has site homologies to 132L, 135L and 1LZ1 in E.C. class 3.2.1.17 and to 4HOH in E.C. class 3.1.27.3, 2CVK to 1AMY in E.C. class 3.2.1.1, to 1BF2 in E.C. class 3.2.1.68, to 1EYI in class 3.2.3.11, etc.). For 1CDC, a "metastable structure of CD2", proMOL shows an active site homology to 1ALK of E.C. class 3.1.3.1, another hydrolase.

The significant gaps in the Nearest-Cell search do not appear to be a problem of the distance for the Nearest-Cell search having been cut off at a too-small value. For the common hits between the square root of the Nearest-Cell metric and the linearized NCDist metric, a linear fit is excellent, with R² = 0.89 and no points are very far from the line. The agreement of the linearized V7 to the other two metrics is much noisier because of loss of sensitivity of the V7 metric for angles near 90 degrees and the inherent difficulty the V7 metric has in discriminating between the + + + and - - - parts of the Niggli cone. For example, 1GUT (Schüttelkopf et al., 2002) is at distances 1.2 and 3.7 from 1UJ4 in the Nearest-Cell and linearized NCDist metrics, respectively, but only 0.1 in the V7 metric. The 1GUT cell is

[78.961, 82.328, 57.031, 90.00, 93.44, 90.00] in C 1 2 1, Z=24, with a primitive cell

[57.031, 57.0367, 57.0367, 92.3918, 92.3804, 92.3804] which corresponds to a G⁶ vector

[3252.53, 3253.18, 3253.18,-271.53,-270.208,-270.208] and a linearized V7 vector

[52.8004, 52.8057, 52.8057, 52.7101, 52.7101, 52.7053, 52.7569]. The 1U4J cell is

[80.36, 80.36, 99.44, 90, 90, 120] in R3, Z=18, with a primitive cell

[57.02, 57.02, 57.02, 89.605, 89.605, 89.605] which corresponds to a G⁶ vector

[3251.28, 3251.28, 3251.28, 44.8265, 44.8265, 44.8265] and a linearized V7 vector

[52.7902, 52.7902, 52.7902, 52.7878, 52.7878, 52.7878, 52.789]

This is almost identical to the 1GUT V7 vector, even though the corresponding primitive cells and G⁶ cells differ significantly.

Tables

References

Allen, F. H., Kennard, O., Motherwell, W. D. S., Town, W. G. & Watson, D. G. (1973). Journal of Chemical Documentation, 13(3), 119 -- 123.
Andrews, L. (2001). C/C++ Users Journal, 19, 40 -- 49. http://sf.net/projects/ neartree.
Andrews, L. C. & Bernstein, H. J. (2012). arXiv preprint arXiv:1203.5146. arxiv.org/abs/1203.5146.
Andrews, L. C. & Bernstein, H. J. (2013). arXiv preprint arXiv:1305.6561. arxiv.org/abs/1305.6561.
Andrews, L. C., Bernstein, H. J. & Pelletier, G. A. (1980). Acta Crystallogr. A36, 248 -- 252. Berman, H. M., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T. N., Weissig, H., Shindyalov, I. N. & Bourne, P. E. (2000). Nucleic Acids Res. 28, 235 -- 242.
Bernstein, F. C., Koetzle, T. F., Williams, G. J. B., Meyer, Jr., E. F., Brice, M. D., Rodgers, J. R., Kennard, O., Shimanouchi, T. & Tasumi, M. (1977). J. Mol. Biol. 112, 535 -- 542.
Burchard, U. (1998). The Mineralogical Record, 29(6), 517 -- 583.
Craig, P. A., Hanson, B., Westin, C., Rosa, M., Bernstein, H. J., Grier, A., Osipovitch, M., MacDonald, M., Dodge, G., Boli, P. M., Corwin, C. W. & Kessler, H. (submitted). B. M. C. Bioinformatics.
Donnay, J. D. H. (1943). The American Minerologist, 28, 313.
Johnson, G. G. (2013). Private Communication.
Knuth, D. E. (1973). Sorting and Searching (The Art of Computer Programming volume 3). Addison Wesley, Reading, MA.
Le Trong, I. & Stenkamp, R. E. (2007). Acta Crystallogr. D63, 548 -- 549.
Mighell, A. D. (2001). Journal of Research - National Institute of Standards and Technology, 106(6), 983 -- 996.
Mighell, A. D. (2002). Journal of Research - National Institute of Standards and Technology, 107(5), 425 -- 430.
NIH/EPA (1980). User's Manual NIH-EPA Chemical Information System, chap. User's Guide to CRYST The X-Ray Crystallographic Search System. National Institutes of Health, Environmental Protections Agency.
Pearson, W. B. (1958). Handbook of Lattice Spacings and Structures of Metals and Alloys. International Series of Monographs on Metal and Physics and Physical Metallurgy, G. V. Raynor (ed.). Pergamon Press.
Ramraj, V., Esnouf, R. & Diprose, J. (2011). Nearest-Cell A fast and easy tool for locating crystal matches in the PDB. Tech. rep. Division of Structural Biology, University of Oxford. http://www.strubi.ox.ac.uk/nearest-cell/nearest-cell.cgi.
Schüttelkopf, A. W., Harrison, J. A., Boxer, D. H. & Hunter, W. N. (2002). Journal of Biological Chemistry, 277(17), 15013 -- 15020.
Singh, G., Gourinath, S., Saravanan, K., Sharma, S., Bhanumathi, S., Betzel, C., Srinivasan, A. & Singh, T. P. (2004). Acta Crystallogr. F61(1), 8 -- 13.
Singh, G., Gourinath, S., Sarvanan, K., Sharma, S., Bhanumathi, S., Betzel, C., Yadav, S., Srinivasan, A. & Singh, T. P. (2005). J. Struct. Biol. 149(3), 264 -- 272.
Singh, G., Gourinath, S., Sharma, S., Paramasivam, M., Srinivasan, A. & Singh, T. P. (2001). J. Mol. Biol. 307(4), 1049 -- 1059.
Thomas, I. R., Bruno, I. J., Cole, J. C., Macrae, C. F., Pidcock, E. & Wood, P. A. (2010). J. Appl. Crystallogr. 43(2), 362 -- 366.
Toby, B. (1994). Private Communication.
Wyckoff, R. W. G. (1931). The structure of crystals. No. 19. The Chemical Catalog Company. inc.