The charge-flipping algorithm in crystallography

Palatinus, L.

doi:10.1107/S2052519212051366

lead articles

STRUCTURAL SCIENCE
CRYSTAL ENGINEERING
MATERIALS

ISSN: 2052-5206

Volume 69| Part 1| February 2013| Pages 1-16

doi:10.1107/S2052519212051366

Free

The charge-flipping algorithm in crystallography

Lukáš Palatinus ^a ^*

^aInstitute of Physics of the ASCR, v.v.i., Na Slovance 2, 18221 Prague, Czech Republic
^*Correspondence e-mail: palat@fzu.cz

(Received 31 October 2012; accepted 19 December 2012; online 19 January 2013)

The charge-flipping algorithm (CFA) is a member of the diverse family of dual-space iterative phasing algorithms. These algorithms use alternating modifications in direct and reciprocal space to find a solution to the phase problem. The current state-of-the-art CFA is reviewed and it is put in the context of related dual-space algorithms with relevance for crystallography. The CFA has found applications in many crystallographic problems. The principal applications in various fields are described with sections devoted to routine structure solution, the solution of complex structures from powder diffraction data, the solution of incommensurately modulated crystals and quasicrystals, macromolecular crystallography and single-particle imaging.

Keywords: charge-flipping algorithm; dual-space methods; structure solution.

1. Introduction

Structural crystallography is celebrating its centennial. During the 100 years since its birth it has evolved into a rich science with many subfields. Nevertheless, the bulk of the crystallographic work is still the determination of atomic positions in the structures of crystals. Also, despite the enormous progress of alternative methods, the most successful method for structure analysis remains the analysis of diffraction data.

After the first structure solutions which used symmetry arguments and trial-and-error methods, the Patterson method became the first systematically used approach to structure solution. When the statistical relationships between the reflection intensities and their phases were discovered by Cochran, Sayre, Karle, Hauptman and many others in the 1950s and 1960s, a rich field of direct methods was developed (see e.g. Giacovazzo, 1998 , for an overview of the subject). The continuous development and growing power of direct methods made them a leading tool for ab initio structure solution, and their dominance seemed to be incontestable.

The development of crystallographic methods obtained an important new impulse with the advent of powerful desktop computers. Suddenly computationally expensive approaches became available to everybody, and methods could be developed that make heavy use of computationally demanding techniques, such as Fourier transform. The fruits of this revolution are numerous. Direct methods were combined with density modifications in direct space to produce the `Shake-and-Bake' (SnB) method (Weeks et al., 1993 ). A flavour of direct methods based on Patterson-function arguments was developed (Rius, 1993 ) and later transformed into an algorithm cycling between direct and Fourier space (Rius et al., 2007 ; Rius & Frontera, 2008 ; Rius, 2012 ). The `revenge of the Patterson function' was announced (Burla et al., 2004 , 2006 ), combining the superposition minimum function method (Buerger, 1959 ) with new analysis and computer power, and applying the method to ab initio phasing of macromolecular crystals. Yet another algorithm called VLD (Burla, Giacovazzo & Polidori, 2010 ; Burla, Giacovazzo & Polidori, 2011 ; Burla, Carrozzini et al., 2011 ; Burla, Carrozzini et al., 2012 ) is based on an iterative application of difference-Fourier synthesis and real-space density modification techniques.

Next to all these algorithms, a class of so-called dual-space algorithms emerged. This name might be somewhat confusing, because many if not all of the algorithms mentioned in the previous paragraph are in a certain sense dual-space. However, in the dual-space algorithms sensu stricto neither of the two spaces play a dominant role – neither the operation in direct space nor in the Fourier space is, even in principle, capable of solving the structure alone. In contrast, in direct methods and all their flavors, the relationships derived in Fourier space play the key role and Patterson methods are predominantly direct-space methods. VLD is an algorithm based on the iterative modification of the trial density map using suitable Fourier synthesis, which makes it related to the dual-space algorithms. However, the key step in VLD is the use of special coefficients of the difference-Fourier synthesis (Burla, Caliandro et al., 2010 ) that provide some structural information even if the original density map used for the difference synthesis is random. The expressions for these difference Fourier coefficients contain a `flipping term'. The name of this term can be a source of some confusion, but it applies to Fourier coefficients and it is not related to the charge-flipping operation intrinsic to the charge-flipping algorithm. VLD is an interesting algorithm that shares several concepts with the dual space-algorithms, but its key concept is different and it thus does not belong to the class of dual-space algorithms sensu stricto. Naturally, it is possible to mix the concepts of various `pure' structure-solution methods to obtain new, more efficient hybrid algorithms.

The iterative dual-space phasing algorithms have gained considerable interest in the crystallographic community over the last few years. Among them the best known is the charge-flipping algorithm (CFA; Oszlányi & Sütő, 2004 ). While not the first published algorithm of this kind, it sparked considerable interest in iterative dual-space methods for structure solution and has marked the beginning of a broad interest and development of this field in crystallography.

This review summarizes the development of the crystallographic dual-space algorithms both prior to and after the publication of the CFA, describes the CFA and related algorithms, and gives an overview of the applications of these algorithms to crystallographic problems. The text is organized as follows. First a general overview of dual-space algorithms in phase retrieval is presented with focus on algorithms relevant for crystallography. Then a detailed description of CFA and its variants is provided, followed by sections on two important special topics: symmetry and missing data. Then the software available for applications of CFA is described, and, finally, applications of the algorithm are described in sections devoted to general structure solution, modulated structures, powder diffraction data, macromolecules and single-particle reconstruction.

2. Dual-space algorithms in phase retrieval

The problem of phase retrieval is omnipresent in various fields of physics and engineering. The problem is usually formulated in the general space of square-integrable functions, but for our purposes let us limit the definition to a discretely sampled signal in Euclidean space Eⁿ of dimension n (n = 3 for a typical crystal structure). Let $[\rho = \{\rho_i,i = 1\ldots N_p\}]$ be a (generally complex-valued) function sampled on a discrete n-dimensional grid comprising N_p pixels. Let $[\hat{\rho}]$ be its (discrete) Fourier transform. Let $[M = \left\{{\bf h}_j, j = 1\ldots N_h\right\}]$ be the set of indices $[{\bf h}_j]$ , for which Fourier magnitudes $[|F^o({\bf h}_j)| = |F_j^o|]$ are known from experiment. Then the phase retrieval problem can be formulated as: find $[\rho]$ or an approximation to $[\rho]$ , given the set of known Fourier magnitudes (magnitude constraint) and some additional information about $[\rho]$ . This additional information can be the support (i.e. a subset of $[\rho_i]$ is assumed to be zero), positivity ( $[\rho_i\gt0]$ for all i), atomicity (the signal in $[\rho]$ is composed of a set of discrete peaks) or any other piece of information. Since this additional information is in all practical applications defined in the direct space of $[\rho]$ , not in its Fourier space, it will be denoted as a direct-space constraint. The set of all $[\rho]$ that fulfill the constraint is called the constraint set. Let us denote by S the set of all $[\rho]$ matching this direct-space constraint, and by R the set of all $[\rho]$ such that $[|\hat{\rho}_j| = |F_j^o|]$ , $[j = 1\ldots N_h]$ , i.e. matching the magnitude constraint. Then the phase retrieval problem can be simply stated as: find some $[\rho]$ from $[S \cap R]$ . If such $[\rho]$ exists, the problem is called consistent. If the intersection of S and R is empty, the problem does not have a solution and is called inconsistent. In such a case, it may still be useful to search for $[\rho]$ such that the sum of its distances to the nearest points in S and R is minimal.

A similar problem is encountered in convex optimization theory. The basic formulation of the problem is the same as above, but the two constraints are not specifically the magnitude and direct-space constraint. Instead, a general pair of constraints is considered, with the important property of convexity. A constraint set A is convex if for any two elements of the constraint set the following statement is valid

$[\rho, \rho' \in A \Rightarrow \rho + c(\rho'-\rho) \in A,\,{\rm for }\, c \in \langle 0\semi 1\rangle .\eqno(1)]$

The convexity of the constraints allows important conclusions to be made about the properties and convergence of algorithms proposed for the solution of the convex feasibility problem. Algorithms exist that always converge to a solution of this problem. Unfortunately, the magnitude constraint central to the phase-retrieval problem is obviously non-convex, and the results of the convex optimization theory cannot be carried over to the phase retrieval problem. Nevertheless, it is useful to compare the algorithms developed in these two frameworks. Analysis of the convex versions of the algorithms gives valuable insight into the relationships between various algorithms proposed in phase retrieval.

Before the algorithms relevant for crystallography are summarized, we describe the specific forms of the magnitude and direct-space constraints. The basic form of the magnitude constraint set was defined above as the set of all $[\rho]$ such that $[\hat{\rho}_j = |F^o_j|]$ for all $[{\bf h}_j\in M]$ . The recipe to transform an arbitrary function $[\rho]$ into a function that belongs to the constraint set is called projection operator or projector. The basic projector onto the magnitude constraint set can be defined as follows

$[F_j^{\rm new} = \cases{ {|F_j^o|\over |F_j^{\rm old}|}F_j^{\rm old}\,\,\, \,\,{\rm if }\, {\bf h}_j\in M \cr F_j^{\rm old} \,\,\,\quad\quad{\rm if }\, {\bf h}_j \,\,\notin\,\, M }. \eqno(2)]$

$[\rho^{\rm new}]$ is then obtained as a Fourier transform of {F^new_j}. In other words, the new $[\rho]$ is obtained from the old by replacing the known Fourier magnitudes with the observed ones, keeping all phases and the unknown Fourier magnitudes intact. However, alternative variants of this basic scheme have been proposed and used. Elser (2003b) proposed to place an upper bound on the magnitude of unknown Fourier coefficients

$[F_i^{\rm new} = \cases{ {|F_j^{o}|\over |F_j^{\rm old}|}F_j^{\rm old}\,\,\,\, \quad {\rm if }\, {\bf h}_j\in M \cr c{|F_j^{\rm bound}|\over |F_j^{\rm old}|}F_j^{\rm old}\,\, \,{\rm if }\, {\bf h}_j\, \notin\, M \, {\rm and }\, |F_j^{\rm old}|\,\gt\, c|F_j^{\rm bound}| \cr F_j^{\rm old} \,\,\quad\quad\quad\, {\rm otherwise}} .\eqno(3)]$

In crystallography, suitable $[|F_j^{\rm bound}|]$ can be conveniently estimated from the Wilson plot. For normalized Fourier magnitudes (E values), F^bound = 1 for all j. If c goes to infinity, this operator transforms to equation (2). Another special instance of this operator is the case c = 0

$[F_j^{\rm new} = \cases{ {|F_j^{o}|\over |F_j^{\rm old}|}F_j^{\rm old}\,\,\,\,\, {\rm if }\, {\bf h}_j\in M \cr 0 \,\,\,\,\,\quad\quad\,\,\,\,\,{\rm if} \, {\bf h}_j\,\,\notin\,\, M }. \eqno(4)]$

Yet another variant has been devised for practical applications. The Fourier magnitudes [|F^o|] are known only for associated scattering vectors up to a certain length h_max. The sphere of known [|F^o|] is denoted as the resolution sphere. In practical applications, the set M of scattering vectors with known Fourier magnitudes rarely covers all vectors in the resolution sphere. For example, the scattering at very low or zero angle can almost never be measured directly. Such missing data inside the resolution sphere require a treatment different from unmeasured data at high resolution. For this purpose, a combination of projector (3) for data inside the resolution sphere and (6) outside the resolution sphere is useful

$[F_j^{\rm new} = \cases {{|F_j^{o}|\over |F_j^{\rm old}|}F_j^{\rm old}\,\,\,\,\,\,\,\,\,\, {\rm if }\, {\bf h}_j\in M \cr c{|F_j^{\rm bound}|\over |F_j^{\rm old}|}F_j^{\rm old}\,\,\, {\rm if }\, {\bf h}_j\,\,\notin \,\,M , \, h_j\,\lt\, h_{\rm max}, \,{\rm and }\, |F_j^{\rm old}|\,\gt\, c|F_j^{\rm bound}| \cr F_j^{\rm old} \qquad\quad\,\,\, {\rm if }\, {\bf h}_j\,\,\notin\,\, M , \, h_j\,\lt\, h_{\rm max}, {\rm and }\, |F_j^{\rm old}|\lt c|F_j^{\rm Wilson}|\cr 0 \,\,\,\quad\quad\qquad{\rm otherwise}}. \eqno(5)]$

Again, the constant c can be set infinite, in which case the second condition is never met and the rule reduces to leaving all unmeasured magnitudes inside the resolution sphere unchanged, and setting everything outside the resolution sphere to zero.

Equation (5) has a very important special case, namely $[c = \infty]$ and h_max so small that the only coefficient with $[h\,\lt\, h_{\rm max}]$ is the coefficient $[F({\bf 0})]$ . This case corresponds essentially to equation (2), but instead of constraining $[F({\bf 0})]$ to zero, it is left unchanged by the projector. This form was used in the original article on the CFA (Oszlányi & Sütő, 2004)

$[F_j^{\rm new} = \cases{ {|F_j^{o}|\over |F_j^{\rm old}|}F_j^{\rm old}\,\,\,\, \, {\rm if }\, {\bf h}_j\in M \cr F_j^{\rm old}\,\,\,\qquad {\rm if }\, {\bf h}_j = {\bf 0} \cr 0 \,\,\,\quad\qquad {\rm otherwise }}.\eqno(6)]$

Among direct space constraints the most studied constraint in phase retrieval is the support constraint. This constraint can be applied if some part of $[\rho]$ is known or assumed to be zero. This is a relevant constraint in single-particle imaging. However, in crystallography the distribution of scattering density in the unit cell is usually unknown and no support constraint can be defined. Instead, the positivity of the electron density can be exploited, and the positivity constraint can be conveniently defined. The corresponding projector is very simple

$[\rho_i^{\rm new} = \cases {\rho_i^{\rm old}\,\, \, {\rm if }\, \rho_i\ge 0 \cr 0 \,\,\,\quad{\rm if }\, \rho_i\,\,\,\,\,\lt\,\, 0}.\eqno(7)]$

Such an operation has been frequently used in macromolecular crystallography as part of phase extension and refinement procedures (solvent flattening; Wang, 1985 ). For ab initio crystal-structure determination, however, it was found that a more aggressive density modification technique is needed

$[\rho_i^{\rm new} = \cases{ \rho_i^{\rm old}\,\, \,{\rm if }\, \rho_i\geq \delta \cr 0 \,\,\,\quad {\rm if }\, \rho_i\,\,\lt\,\,\delta },\, \delta\,\gt\, 0 . \eqno(8)]$

Introduction of the free parameter $[\delta]$ gives the algorithms more freedom to find a balance between the perturbing and stabilizing effect of the operation. Such an operation is the basis of some of the EDM (electron-density modification) techniques used in direct methods (e.g. Giacovazzo & Siliqi, 1997 ). In the context of ab-initio structure solution by dual-space methods, it was first proposed by Shiono & Woolfson (1992 ) and it is in the background of the charge-flipping operation. As noted e.g. in Oszlányi & Sütő (2008 ), this operation is not distance-minimizing, i.e. the distance between $[\rho^{\rm new}]$ and $[\rho^{\rm old}]$ is not the shortest possible distance between $[\rho^{\rm old}]$ and the constraint set. Such operators that have the properties of a projection (i.e. repeated application of the operator has the same effect as a single application), but are not distance minimizing, are sometimes called pseudoprojections. For the sake of simplicity, we will not make a distinction between true distance-minimizing projections and pseudoprojections in this text.

Operation (8) lends itself to a modification, which is not possible with (7), namely

$[\rho_i^{\rm new} = \cases{ \rho_i^{\rm old}\,\, \,{\rm if }\, |\rho_i|\geq \delta \cr 0 \,\quad\,\,{\rm if }\, |\rho_i|\,\,\lt\,\,\delta } .\eqno(9)]$

This constraint does not impose positivity on $[\rho]$ , but only eliminates low-density regions. It can be understood as a `dynamical support' constraint, where, unlike in the standard support constraint, the support is newly identified at every iteration cycle as the region with high density. This operation is at the basis of the band-flipping approach (Oszlányi & Sütő, 2007 ).

Another direct-space constraint used in crystallography is the atomicity constraint. This constraint is less easily expressed by a simple recipe, but, in rough terms, the corresponding projector consists of selecting a prescribed number of peaks in $[\rho]$ , and setting to zero all pixels outside these peaks (Elser, 2003b; Feng, 2012 ).

Whatever the exact constraint and the recipe for the projector, it can be symbolically denoted as P, and the transformation of the image then as $[\rho^{\rm new} = P\rho^{\rm old}]$ . Such operators can be combined to yield more complicated transformations of $[\rho]$ . A particularly important combination of projections is a so-called overprojection

$[R^\gamma = (1+\gamma)P-\gamma I, \eqno(10)]$

where I is the identity operator. Geometrically, such overprojection means that the shift from $[\rho]$ to $[P\rho]$ is continued in the same direction by a fraction $[\gamma]$ of the original distance from $[\rho]$ to $[P\rho]$ . The special case of $[\gamma = 1]$ is called reflector, and will be denoted R without an explicit superscript

$[R:= R^1 = 2P-I. \eqno(11)]$

We are now equipped to review the different algorithms suggested in the literature for phase retrieval, and specifically for crystal structure solution. In some works, the iterative phase retrieval algorithms are described as explicit schemes for pixelwise obtaining $[\rho]$ of cycle n+1 from $[\rho]$ of cycle n. Such recipes do not explicitly separate the combination of projectors acting on $[\rho]$ from the exact definition of the projector, and sometimes cannot even be expressed in the form of a combination of projectors acting on $[\rho]$ . Another approach to describe the algorithms is to define the iteration scheme in terms of operators acting on $[\rho^{(n)}]$ to obtain $[\rho^{(n+1)}]$ , and define the exact form of the operators separately. Where possible we will adopt this second approach, and we will point out cases where this approach leads to difficulties. Explicit flowcharts of the most important algorithms are then summarized in Fig. 1.

Figure 1
Explicit schemes of the most important dual-space algorithms. Projections (6)

and (8)

were used for P_M and P_D, respectively. $[\tau]$ , $[\omega]$ , $[\varphi]$ and $[\psi]$ are intermediate images, $[\hat{\tau}]$ , $[\hat{\omega}]$ , $[\hat{\varphi}]$ and $[\hat{\psi}]$ their Fourier transforms, respectively. The schemes correspond to equations (13)

(CFA), 17

(HIO), 22

(AAR) and 19

(DM).

The basic algorithm is the alternating application of the magnitude and direct-space projections. Expressed as an iteration scheme, this algorithm can be written as

$[\rho^{(n+1)} = P_{\rm M}P_{\rm D}\rho^{(n)}.\eqno(12)]$

Here P_M denotes the magnitude projector and P_D the direct space projector. As for all algorithms that will be presented in this section, the iteration typically starts from a random starting image, but it is not strictly necessary, and starting from non-random starting point changes these algorithms from phase retrieval to phase refinement or phase extension algorithms. This simple algorithm is known in the phase-retrieval community as the Gerchberg–Saxton (Gerchberg & Saxton, 1972 ) or error-reduction algorithm (Fienup, 1982 ), and as the POCS (projections onto convex sets) for the convex feasibility problems (Censor & Zenios, 1997 ). In crystallography this algorithm was used in conjunction with projection (8) under the name low-density elimination (LDE; Shiono & Woolfson, 1992). This method was developed as a phase-extension method for macromolecular crystallography, but the authors added a short comment stating that one of the test structures could be solved ab initio from random phases. This seems to be the first published record of a crystal structure solved ab initio by dual-space methods, although this possibility was considered much earlier, for example in the ground-breaking paper by Fienup (1982). A detailed account on the performance of LDE in ab initio solution is given in Matsugaki & Shiono (2001 ).

The Gerchberg–Saxton/error reduction/LDE algorithm is known to be prone to stagnation at false solutions. One way of reducing the risk of stagnation is to replace the projectors by reflectors. Replacing the direct-space projector P_D by the corresponding reflector yields this algorithm

$[\rho^{(n+1)} = P_{\rm M}R_{\rm D}\rho^{(n)}. \eqno(13)]$

This is the iteration scheme of the basic CFA (Oszlányi & Sütő, 2004), with R_D being the reflector of (8), and P_M the magnitude projection (6). As noted by Wu, Weierstall et al. (2004), this algorithm is a special case of Fienup's output–output algorithm [Fienup (1982), equation (43) with $[\beta = 2]$ and with $[\gamma]$ being the set of all pixels, where $[\rho_i\,\lt\,\delta]$ ].

A symmetric counterpart of this algorithm is the following scheme

$[\rho^{(n+1)} = P_{\rm D}R_{\rm M}\rho^{(n)}. \eqno(14)]$

Here the reflector is applied in reciprocal space. The phase-retrieval algorithm of Feng (2012) resembles very much this type of algorithm, although the operator in Fourier space uses a special version of the Fourier coefficients, yielding this operator

$[F_j^{\rm new} = \cases{(2|F_j^{o}|^2-|F_j^{\rm old}|^2)F_j^{\rm old}\,\,\, \,{\rm if }\, {\bf h}_j\in M \cr 0\qquad\qquad\qquad\qquad\,\,\,{\rm if }\, {\bf h}_j\,\,\notin \,\,M }.\eqno(15)]$

The structure of this operator resembles a reflector, but it is not a reflector in a strict sense.

Another logical extension of the iteration scheme is to replace both projectors by reflectors

$[\rho^{(n+1)} = R_{\rm M}R_{\rm D}\rho^{(n)}.\eqno(16)]$

It turns out that this scheme is difficult to use because of its instability. The perturbation induced by the alternating reflectors is too strong, and the solutions are not stable. This scheme has been made to work only by replacing the magnitude reflector by a special `partial reflector'. This scheme, denoted ` $[F+\Delta F]$ ' will be described in §3 [equation (28)].

In the phase-retrieval community it was quickly noticed that the simple Gerchberg–Saxton iteration is not satisfactory, and tends to stagnate. In pioneering work Fienup (1982) proposed a set of more complicated iterations schemes, of which the hybrid input–output (HIO) algorithm proved to be the most successful. The hybrid input–output algorithm was defined as an explicit recipe for pixelwise obtaining $[\rho^{\rm new}]$ from $[\rho^{\rm old}]$ . Adapted to our notation, this scheme reads

$[\rho_i^{(n+1)} = \cases{ (P_{\rm M}\rho^{(n)})_i\,\,\, \,\qquad\quad {\rm if }\, (P_{\rm D}P_{\rm M}\rho^{(n)})_i = P_{\rm M}\rho^{(n)}_i \cr \rho^{(n)}_i-\beta(P_{\rm M}\rho^{(n)})_i\,\,\, {\rm otherwise}},\eqno(17)]$

where $[\beta]$ is a free parameter of the algorithm, and $[(P_{\rm D}\rho^{(n)})_i]$ means the ith pixel of the image $[P_{\rm D}\rho^{(n)}]$ . This algorithm cannot be expressed in the form of an operator acting on $[\rho^{(n)}]$ (Bauschke et al., 2003 ). Only if the direct-space constraint is the support constraint (or another constraint for which the projector is a linear operator) can the HIO algorithm be expressed as a fixed-point operator (Bauschke et al., 2002 , 2003)

$[\eqalignno{ \rho^{(n+1)} = \, & \{P_{\rm D}[(1+\beta)P_{\rm M}-I])+I-\beta P_{\rm M}\}\rho^{(n)}\cr =\, & {{1} \over {2}}\{R_{\rm D}[R_{\rm M}+(\beta-1)P_{\rm M}]+I+(1-\beta)P_{\rm M}\}\rho^{(n)}.\cr & &(18)}]$

If the second form of the iteration scheme (18) is combined with positivity constraint (and not support constraint), yet another algorithm called hybrid-projection reflection (HPR) is obtained (Bauschke et al., 2003). The HIO algorithm, or elements thereof, has been used in crystallographic phase retrieval schemes (Wu et al., 2006 ; Lei, 2007 ).

Another algorithm that bears a strong relationship to the HIO algorithm was proposed by Elser (2003b) and named the difference map (DM). It is a three-parameter algorithm defined by the following scheme

$[\rho^{(n+1)} = \left[I+\beta\left(P_{\rm D} R_{\rm M}^{\gamma_{\rm M}}-P_{\rm M}R_{\rm D}^{\gamma_{\rm D}}\right)\right]\rho^{(n)}. \eqno(19)]$

In the original work (Elser, 2003b) the optimal values of parameters $[\gamma_{\rm M}]$ and $[\gamma_{\rm D}]$ were estimated to be equal to $[\beta^{-1}]$ and $[-\beta^{-1}]$ , respectively. In subsequent work (Elser, 2003c ) a slightly different choice of $[\gamma_{\rm D}]$ was suggested. It can be easily shown (Elser, 2003b) that, for the case of the support constraint only, the HIO algorithm is a special case of DM with $[\gamma_{\rm M} = \beta^{-1}]$ and $[\gamma_{\rm D} = -1]$ . This equivalence, however, does not hold for the positivity or atomicity constraint. The difference map was demonstrated to work for structure solution (Elser, 2003a ). The specific form of the magnitude constraint was that of equation (3), and the direct-space constraint was the atomicity. Strangely, it appears that this concept was never used to determine an unknown crystal structure, and the test case published by Elser (2003a) so far remains the only explicit application of this algorithm in crystallography. The algorithm has found more applications in the phase retrieval of non-periodic objects.

When the special value of $[\beta = 1]$ is used in the second equality of equation (18), we obtain the particularly simple expression

$[\rho^{(n+1)} = {{1} \over {2}}(R_{\rm D}R_{\rm M}+I)\rho^{(n)}. \eqno(20)]$

This algorithm was first proposed and analyzed by Douglas & Rachford (1956 ) for the solution of differential equations, and adapted for convex sets by Lions & Mercier (1979 ). In the phase-retrieval context it was suggested and analyzed by Bauschke et al. (2004 ) under the name averaged alternating reflections (AAR). The AAR algorithm has the interesting property that, under certain circumstances, it is an important special case of both the HIO algorithm and the difference map. More specifically, assuming P_D is a linear operator, the AAR algorithm is the HIO algorithm with $[\beta = 1]$ , and the difference map algorithm with $[\beta = 1]$ , $[\gamma_{\rm D} = -1]$ and $[\gamma_{\rm M} = 1]$ . Moreover, if, in addition to P_D P_M is also assumed to be linear (keep in mind that this is not the case for the magnitude projection), Elser's difference map with the recommended parameters $[\gamma_{\rm M} = \beta^{-1}]$ and $[\gamma_{\rm D} = -\beta^{-1}]$ becomes a weighted average of two symmetric versions of AAR

$[\eqalignno{\rho^{(n+1)} =\, & {{1+\beta} \over {2}}\left[{{1} \over {2}}(R_{\rm D}R_{\rm M}+I)\right]\rho^{(n)}\cr &+{{1-\beta} \over {2}}\left[{{1} \over {2}}(R_{\rm M}R_{\rm D}+I)\right]\rho^{(n)}. &(21)}]$

These relationships cannot be carried over directly to phase retrieval, where the magnitude constraint and often the direct-space constraints are not linear. Nevertheless, they indicate that all these algorithms have a closely related structure.

Equation (20) has a symmetric counterpart, also obtained from (21) with $[\beta = -1]$

$[\rho^{(n+1)} = {{1} \over {2}}(R_{\rm M}R_{\rm D}+I)\rho^{(n)}. \eqno(22)]$

The two schemes are very similar, but they are not the same because the magnitude and direct-space constraints have a very different structure. The latter scheme was used by Oszlányi & Sütő (2011 ) and shown to be superior to the original CFA, especially when dealing with low-resolution data.

So far, we have not considered the consistency of the phase-retrieval problem and we have assumed the solution exists. However, crystallographic phase retrieval is most often inconsistent. This is caused by the limited resolution of the diffraction data and by the presence of noise in the data. Moreover, if constraint (8) is used the problem is inconsistent, because we are approximating the true $[\rho]$ by a function which does not assume values between 0 and $[\delta]$ . For inconsistent problems, the AAR, HIO, DM and related algorithms have a tendency to diverge from the solution (Marchesini, 2007 ; Fig. 2). This leads to a frequently observed problem of wandering of the iterates away from the solution. The error-reduction algorithm and CFA do not diverge and stay close to the optimal point (i.e. at the place with the shortest distance between the constraint sets), but they suffer from stagnation at the local distance minima (Fig. 2c). An interesting algorithm that does not diverge for inconsistent problems, but inherits most of the ability of the AAR-related algorithms to escape from the local minima, is the relaxed alternating averaged reflection (RAAR) algorithm (Luke, 2005 ). This algorithm is a one-parameter relaxation of the AAR algorithm

$[\rho^{(n+1)} = {{1} \over {2}}\beta(R_{\rm D}R_{\rm M}+I)+(1-\beta)P_{\rm M}\rho^{(n)}. \eqno(23)]$

This algorithm has a fixed point, even if the corresponding problem is inconsistent. So far, this algorithm has not been tested in crystallographic context, but it is certainly an interesting alternative to the established schemes.

Figure 2
Convergence of selected dual-space algorithms on a two-dimensional example. (a) Two convex constraint sets with intersection. (b) Two non-convex constraint sets with several intersections. (c) Two non-convex constraint sets without intersection (infeasible problem). All iterations start from the same point in the right part of the plots. Symbols represent the actual iterates, the dotted lines are connecting consecutive iterates. ER = error–reduction algorithm (12)

, CFA = charge-flipping algorithm (13)

, AAR = averaged alternating reflections (20)

, RAAR = relaxed averaged alternating reflections (23)

, DM = difference map [(19)

, with $[\gamma_{\rm M} = \beta^{-1}]$ , $[\gamma_{\rm D} = -\beta^{-1}]$ ].

Realistic phase retrieval problems operate in spaces of very large dimensions. It is, however, very enlightening to observe the behavior of the algorithms for a simple, two-pixel problem, which can be represented in a plane. Several of the presented algorithms (ER, CFA, AAR, RAAR, DM) were used to solve a simple problem in two dimensions, where the two constraint sets are represented by two curves. Fig. 2 shows the results for a convex consistent problem, a non-convex consistent problem with multiple solutions and a non-convex inconsistent problem. Each symbol in the plots shows an iterate of the algorithms. Successive iterates are connected with a line, forming a path. For the convex consistent problem (Fig. 2a) all algorithms converge to the correct solution. For the non-convex consistent problem (Fig. 2b), ER and CFA stagnate at local minima. However, the CFA is able to avoid some of the local minima, and approaches the solution more than ER. All other algorithms find one of the solutions. The non-convex inconsistent problem is the most challenging. ER and CFA approach the solution, but stagnate at local minima. Again, CFA avoids some of the minima that are trapping the ER algorithm. AAR, HIO and DM algorithms all diverge from the solution. The RAAR algorithm converges close to the solution, and a point very close to the solution would be found by a single application of one of the projections. Readers interested in more details on the behavior of various algorithms for general phase retrieval problems should refer to an excellent, comprehensive and thorough overview by Marchesini (2007).

Most of the algorithms presented so far can be regarded as special cases of a general, six-parameter iteration scheme of the following form

$[\eqalignno{\rho^{(n+1)} =\, &\big[\left(1-\beta_1-\beta_2\right)I+\beta_1\left(R_{\rm D}^{\gamma_{\rm D,1}} R_{\rm M}^{\gamma_{\rm M,1}}\right)\cr & +\beta_2\left(R_{\rm M}^{\gamma_{\rm M,2}} R_{\rm D}^{\gamma_{\rm D,2}}\right)\big]\rho^{(n)}. &(24)}]$

Table 1 gives the parameters of this general algorithm that correspond to the algorithms presented in this section. The only algorithm that cannot be represented as a special case of the above scheme is the general form of the HIO algorithm [equation (17)] and the HPR algorithm [equation (18) with positivity constraint].

Table 1
Dual-space iterative algorithms expressed as instances of the general iteration scheme (24)

β is the free parameter of the algorithms.

	β₁	γ_M,1	γ_D,1	β₂	γ_M,2	γ_D,2
Gerchberg–Saxton/error reduction	1	0	0	0	–	–
Original CFA	1	0	1	0	–	–
HIO†	β	β⁻¹	0	−β	0	1
DM‡	β	β⁻¹	0	−β	0	−β⁻¹
AAR,§ equation (20)	½	1	1	0	–	–
AAR, equation (22)	0	–	–	½	1	1
RAAR	β/2	1	1	1 − β	0	−1

†Strictly valid only for support constraint.
‡With optimal parameters derived from the assumption of locally orthogonal constraint sets.
§Also HPR with β = 1.

This overview of algorithms should serve two main purposes. It should give the reader an idea of the complexity of the field, and point out the similarities, but also the differences between the algorithms. For this purpose, detailed explicit flowcharts of the most important algorithms are also summarized in Fig. 1. The overview should also make clear that the potential and performance of various algorithms in crystallographic context is far from being entirely understood and explored. Finally, it should provide an interested reader a starting point for experiments with various flavors of the phase-retrieval algorithms.

3. Variants of the charge-flipping algorithm

In the previous section, various phase retrieval algorithms were reviewed. Although several algorithms were applied to crystallographic problems, the charge-flipping based algorithms remain the most studied and the most applied. This section therefore provides a detailed overview of variants and flavors of the CFA.

The first and obvious improvement of the efficiency of the algorithm is not related to the algorithm itself, but to the data employed. The original paper on the CFA used the magnitudes of the standard, non-normalized Fourier coefficients as input. Using normalized Fourier coefficients (the E values) yields sharper maps and thus a much better performance of the algorithm. This general knowledge was quantitatively probed by Oszlányi & Sütő (2008), who showed, on a selected example, a reduction of the number of iteration steps by about two orders of magnitude on introducing normalized Fourier coefficients. Other dual-space algorithms (Lei, 2007; Feng, 2012) directly employ the normalized coefficients.

As described in the previous section, the original version of the CFA employed the iteration scheme (13) with the magnitude projection (6), and direct-space projection (8). Due to its crucial role in the CFA, we give here the corresponding reflector of (8) explicitly

$[\rho_i^{\rm new} = \cases{ \rho_i^{\rm old},\,\,\,\,{\rm if }\, \rho_i\geq \delta \cr -\rho_i^{\rm old}\,\, {\rm if } \, \rho_i\,\,\lt\,\,\delta }. \eqno(25)]$

This is the so-called charge-flipping operation, which gave the algorithm its name. The zero Fourier coefficient $[F({\bf 0})]$ deserves special attention. This coefficient is never known experimentally. Nevertheless, in the original formulation of the CFA [equation (6)] it was left unconstrained. The variant with constraining $[F({\bf 0})]$ to zero [i.e. using projector (4)] was also sometimes used (Palatinus, 2004 ; Coelho, 2007a ; Zhou & Harris, 2008 ). However, leaving the $[F({\bf 0})]$ coefficient unconstrained seems to be the most efficient approach. The exact form of the magnitude constraint (6) is important. For example, replacing the constraint by the closely related form (2) has a devastating effect on the efficiency of the algorithm.

The parameter $[\delta]$ is the single free parameter of the algorithm. Its value on absolute scale differs from one problem to another. However, it was shown (Oszlányi & Sütő, 2008) that $[\delta]$ can be conveniently expressed in terms of the standard deviation of the reconstructed density

$[\delta = k_{\rm ed}\sigma(\rho), \eqno(26)]$

where $[\sigma(\rho)]$ is the standard deviation of the distribution of the density values. The optimal k_ed was shown to be most often between 0.9 and 1.3.

Soon after the publication of the algorithm, first applications and improvements of the algorithm appeared. Wu, Spence et al. (2004 ), along with the first application to experimental data, proposed to replace the $[\delta]$ constant in the charge-flipping operation by a dynamical $[\delta]$ determined newly in every cycle so that a constant number of pixels is flipped. While this modification does not seem to have an important effect for realistic structure solution problems, it appears to have a stabilizing effect for problems where the solution is less stable. A short series of experiments with an applet named Charge flipping (Schoeni & Chapuis, 2007 ) shows that in two-dimensional problems the dynamical $[\delta]$ often yields faster and more stable convergence than static $[\delta]$ .

Naturally, most efforts concentrated on the improvement of the phasing power of the algorithm. These attempts focused either on the modification of the constraints or of the iteration scheme. The first class involves the so-called π-half variant (Oszlányi & Sütő, 2005 ), where the magnitude constraint is modified to [cf. equation (6)]

$[F_j^{\rm new} = \cases{ {|F_j^{o}|\over |F_j^{\rm old}|}F_j^{\rm old}\,\,\, \,\,\quad {\rm if }\, {\bf h}_i\in M \, {\rm and \, strong}\cr F_j^{\rm old}\exp({{\pi} \over {2}}i)\,\, {\rm if }\, {\bf h}_j\in M \, {\rm and\, weak}\cr 0 \,\qquad\qquad\,\, {\rm otherwise}}.\eqno(27)]$

The threshold between weak and strong reflections is selected so that a certain fraction of reflections – typically 20–30% – are treated as weak. This modification dramatically improves the performance of the algorithm.

Another improvement of the operation on the Fourier magnitudes was the replacement of the simple magnitude projection by this operation (Oszlányi & Sütő, 2008)

$[F_j^{\rm new} = \cases{ (2|F_j^{o}|-|F_j^{\rm old}|)\exp(2\pi i \varphi_j^{\rm old})\,\,\, \,{\rm if }\, {\bf h}_j\in M \cr 0 \qquad\qquad\qquad\qquad\qquad\quad\,\, {\rm otherwise}}.\eqno(28)]$

Here $[\varphi_j^{\rm old}]$ is the phase of the coefficient F_i^old. It can be regarded as a standard $[F+\Delta F]$ Fourier synthesis used commonly in macromolecular crystallography. This operator resembles a reflector, but a true reflector would have to change the sign of all unobserved Fourier coefficients ( $[{\bf h}_j\,\notin\, M]$ ). The authors recommend that a limit is imposed on the change of [|F_j|] so that $[|F_j^{o}|-W\,\lt\,|F_j^{\rm new}|\,\lt\,|F_j^{o}|+W]$ , where W is a new free parameter of the algorithm. This modification provided similar or somewhat better results than the π-half variant on a test organic structure (Oszlányi & Sütő, 2008).

Oszlányi & Sütő (2008) also proposed an improvement of the direct-space operator. This variant, dubbed flip-mem, defines a new direct-space modification which uses the density of the last two cycles to produce the density of the current cycle

$[\rho_i^{(n+1)} = \cases{ \rho_i^{(n)}+\beta(\rho_i^{(n)}-\rho_i^{(n-1)})\,\,\,\,{\rm if }\,\rho_i^{(n)} \geq \delta \cr -\rho_i^{(n)}\,\qquad\qquad\qquad\quad{\rm if }\, \rho_i^{(n)}\,\lt\,\,\delta }\eqno(29)]$

with $[\beta]$ a positive real number between 0.5 and 1. This modification cannot be expressed using an operator acting on $[\rho^{(n)}]$ , because it uses both $[\rho_i^{(n)}]$ and $[\rho_i^{(n-1)}]$ . It is interesting conceptually because, unlike most other modifications, it acts in direct space and not in Fourier space. However, its efficiency is lower than that of the previous modifications, and it requires additional memory for storing $[\rho^{(n-1)}]$ .

The modifications described so far are aimed at improving the efficiency of the algorithm. A variant called band flipping (Oszlányi & Sütő, 2007) instead aims at lifting the requirement of the positivity of the direct-space constraint. It employs the `dynamical support' constraint (9) instead of the standard constraint (8). The dynamical support constraint does not enforce the positivity of $[\rho]$ . The action of the corresponding reflector (the band-flipping operator) is to change the sign of all pixels with $[-\delta\lt\rho_i\lt\delta]$ . This variant has a weaker phasing power than the standard variant, but is applicable to neutron scattering densities with negative scatterers (Oszlányi & Sütő, 2007), or to the reconstruction of difference electron densities, and hence to the solution of superstructures (Palatinus et al., 2011 ).

An interesting `variant' of the CFA was presented by Zhou & Harris (2008) and named residue-based charge flipping (RBCF). The authors propose a modification of the Fourier space step of CF in a way that uses only a difference Fourier transform

$[\rho^{(n+1)} = R_{\rm D}\rho^{(n)}+\Delta\rho, \eqno(30)]$

where $[R_{\rm D}\rho^{(n)}]$ is the density after the flipping operation, and $[\Delta\rho]$ is obtained as an inverse Fourier transform of residual coefficients R_i

$[R_j = (|F^{o}_j|-|G_j|){{G_j} \over {|G_j|}},\eqno(31)]$

with G_j the Fourier coefficients of $[R_{\rm D}\rho]$ . Furthermore, both $[\delta]$ and $[F({\bf 0})]$ are set to zero throughout the iteration. However, by comparing equations (30) and (31) with the definition of magnitude constraints (2) or (4), it becomes clear that $[\Delta\rho = P_{\rm M}R_{\rm D}\rho^{(n)}-R_{\rm D}\rho^{(n)}]$ and thus this `variant' is (up to numerical differences) exactly equivalent to the standard CFA (13) with $[\delta = 0]$ . The authors do not specify how R_j is calculated, if F^o_j is not known. If in such cases R_j = -G_j (i.e. F^o_i is assumed to be zero), then it corresponds to the standard CFA with magnitude constraint (4). If R_j = 0 for unknown F^o_j, then the magnitude constraint is of the form (2), but with $[F({\bf 0}) = 0]$ . Since the authors do not compare the performance of RBCF with the standard CFA, it is difficult to say if the differences they observe in the behavior of RBCF from standard CFA originate solely from using $[\delta = 0]$ and $[F({\bf 0}) = 0]$ or if they arise due to another difference in implementation. As has been mentioned several times, subtle differences in implementation may sometimes lead to important differences in the results.

In their last publication on the CFA (Oszlányi & Sütő, 2011) the authors combined the charge-flipping operation with the AAR iteration scheme (22). It was shown that the AAR iteration scheme clearly outperforms the standard charge-flipping scheme. The improvement is especially striking for low-resolution data.

The tests used in Oszlányi & Sütő (2008) and Oszlányi & Sütő (2011) used a particular form of intensity normalization

$[E^{o}({\bf h}) = F^{o}({\bf h})/f_{\rm heavy}({\bf h}), \eqno(32)]$

where $[f_{\rm heavy}({\bf h})]$ is the scattering factor of the heaviest atom in the structure for the diffraction vector $[{\bf h}]$ . This scheme under-normalizes the high-frequency Fourier coefficients, because $[f_{\rm heavy}({\bf h})]$ is larger than the average f of all atoms, and it does not correct for the fall-off of the Fourier magnitudes with scattering angle due to the Debye–Waller factor. It is most notable that this normalization scheme seems to perform better than the `proper' intensity normalization using the Wilson plot (Palatinus & Houdková, unpublished results). The reason for this difference is still not understood.

The simplicity of the CFA makes it easy to combine it with other iteration schemes or completely different solution strategies. For example, in the single-particle imaging community, CFA was combined with the HIO algorithm (§7.5). A special case is the combination of the CFA with histogram matching in powder diffraction (§7.3). Coelho (2007a) combined the CFA with the tangent formula (i.e. classical direct methods) to obtain an algorithm that merges the two worlds. The algorithm proposed by Coelho contains a number of modifications with respect to the original algorithm (see Table 1 in Coelho, 2007a), but the principal one is the introduction of the tangent formula in the Fourier-space modification step. Instead of keeping the phases of the Fourier coefficients intact [cf. equation (2)], they are shifted towards phases obtained by application of the tangent formula. With this approach, a substantial improvement of performance was obtained. This algorithm was implemented in the crystallographic suite TOPAS (Coelho, 2007b ) and has become popular especially in combination with histogram matching for structure solution from powder diffraction data.

The outcome of the CFA (as well as of most other iterative algorithms) is not the best possible density, but a density that is close enough to the optimal solution. The raw result of the iteration can be improved by applying one or more cycles of the LDE algorithm (Palatinus & Chapuis, 2007 ; Oszlányi & Sütő, 2008; Fleischer et al., 2010 ), which brings the iterate directly to the intersection of the two constraint sets, if the problem is consistent, or to the local distance minimum for inconsistent problems. A further improvement of the solution can be obtained by using the maximum entropy method (MEM) to optimize the iteration result. This method was applied to powder diffraction data by Samy et al. (2010 ) to obtain entirely model-free reconstructions of electron densities which revealed all the important details of the structure including positional disorder.

4. Charge flipping and symmetry

The potential use of the symmetry information in the CFA has been subject to a recurring debate over the years. All three major publications on dual-space structure solution methods (Matsugaki & Shiono, 2001; Elser, 2003b; Oszlányi & Sütő, 2004) note that symmetry has not been used in their tests, and the latter two express the hope that the proper use of symmetry will improve the power of the algorithms. However, this was never accomplished, and application of the algorithms without any symmetry constraints remains the most efficient approach. Intuitively this fact is not difficult to understand, although, to the knowledge of the author, no mathematically rigorous analysis of the problem has yet been published. If symmetry is imposed on the density, then all features must develop from a random density exactly at the positions determined by symmetry. Without symmetry restriction (i.e. in `P1'), the structure can develop anywhere in the unit cell, giving the algorithm much more freedom to randomly develop a `seed' of the correct structure, and to converge to a complete solution from that seed. Moreover, the $[\delta]$ parameter of the flipping operation must be set to find the balance between the perturbing effect of the operation and the stability at the solution. If the symmetry is fixed – for simplicity, let us consider just the presence of the inversion center at the origin – all Fourier-coefficient phases are fixed to either 0 or π. Switching the phases of important reflections from 0 to π requires an extremely strong perturbation of the density in real space. If δ is set so high as to permit such changes, it will be too high to stabilize the iteration at the solution. If δ is smaller, the phases of the most important reflections will be fixed and the iteration will stagnate. Interestingly, a similar observation has also been made in the framework of direct methods (Sheldrick & Gould, 1995 ; Burla et al., 2000 ) and a procedure called RELAX, which relaxes the symmetry constraints on the structure (Burla et al., 2002 ), has become a standard part of the structure solution process in the program SIR2011 (Burla, Caliandro et al., 2012 ).

An apparent contradiction to the arguments just stated is the method of Eggeman et al. (2009 ), which used symmetry-enhanced charge flipping to solve a two-dimensional structure from zonal electron-diffraction data. The approach is as follows: first run the CFA in P1 for a couple of cycles and then symmetrize the density regularly every few cycles. This approach stabilized and improved the solution. However, the contradiction is only apparent. In the particular case of two-dimensional electron-diffraction data, the problem is not to reach convergence. The structure is very simple to solve, but it is difficult to stabilize the solution due to the limited accuracy and limited amount of data. In such cases, applying the symmetry may indeed help to find the best solution and stabilize it by adding more constraints to the problem. A similar effect can be expected for structures solved from powder diffraction data. Indeed, a possibility to partially or completely impose the symmetry on the current iterate has been implemented in the charge-flipping routine of the program TOPAS-Academic (Coelho, 2007b), and is reported to have a stabilizing effect on the structure solution from low-resolution or powder diffraction data (Coelho, 2012 ).

The fact that the algorithm performs best without any symmetry restrictions can be turned into an advantage. If the solution is found without symmetry restrictions, then it can be analyzed for the presence of symmetry elements, and the most probable space group of the structure can be deduced after the solution (Palatinus & van der Lee, 2008 ). This approach is fundamentally different from the standard space-group determination using the symmetry and systematic absences in diffraction data, because it uses the phased Fourier coefficients and not just their magnitudes. It thus does not suffer from the ambiguities present in the standard approach and allows, for example, an unambiguous discrimination between space groups differing only by the presence/absence of an inversion center. This approach, on the other hand, is less sensitive to small deviations from higher symmetry which can often be reliably revealed in Fourier space. Ideally, the best estimate of the space-group symmetry should be obtained by combining both methods. This algorithm can be especially useful for structure solution from powder diffraction data, where the space-group ambiguity can be much more severe than in single-crystal diffraction (Palatinus & Damay, 2009 ).

5. The problem of missing data

Incomplete diffraction data are a severe problem for the structure solution process regardless of the solution method. Several methods were devised to overcome the problem. The missing coefficients can be extrapolated by imposing the positivity on the Patterson map (Karle & Hauptman, 1964 ; Langs, 1998 ) or probabilistic formulae relating the unknown magnitudes either to the experimental observations (David, 1987 ; Cascarano et al., 1991 ; Xu & Hauptman, 2000 ) or to the Fourier magnitudes of a model density (Caliandro et al., 2005a ,b , 2009 ).

The dual-space algorithms are a Fourier-based technique and thus the problem of an incomplete data set is probably even more critical here than in other methods. In the original formulation of the CFA the magnitude constraint had the form (6), i.e. all unmeasured Fourier magnitudes except for $[F({\bf 0})]$ were reset to zero. This severely hampers the algorithm's performance, even if only a few important low-order Fourier magnitudes are missing. A partial remedy to the problem is to replace projection (6) by projection (5), possibly with infinite c. This modification solves the problem of missing low-order data to a large extent. For cases of an extreme amount of missing data, Palatinus et al. (2007 ) proposed a method based on the optimization of the Patterson function by MEM. The optimization of the Patterson map by MEM leads to an estimation of the missing Fourier magnitudes, which can then be used as experimental data in the charge-flipping iteration. Using this technique test structures could be solved with more than 50% reflections missing inside the resolution sphere. The method is, however, relatively tedious, time consuming and not very efficient in extrapolating the data to higher resolution.

Compared with the standard algorithm with the constraint (5), significant improvement of performance with missing data was reported with the AAR variant (Oszlányi & Sütő, 2011). The published tests show that in some cases the AAR algorithm can solve purely organic, non-centrosymmetric structures from low-resolution data (d_min = 1.5 Å), while the standard algorithm fails already slightly above d_min = 1.2 Å. For centrosymmetric structures, solution from data with d_min = 1.6 Å was easily possible with AAR, while it was very difficult or impossible with standard CFA.

Despite all these improvements, the problem of missing data remains important. In daily practice, severely incomplete data sets are probably a more frequent reason for the failure of the algorithm than an intrinsic complexity of the crystal structure.

6. Software

No modern computing method can hope for widespread usage without publicly available software implementing the method. It is likely one of the key reasons for the success of the CFA that a rich collection of such software is available. Quickly after publication, the CFA has become available for users as a module in the crystallographic software package PLATON (Spek, 2003 ), and in the computer program BayMEM (van Smaalen et al., 2003 ). The latter program is adapted for work in superspace, and it was thus quickly possible to apply the CFA to the solution of incommensurate structures. The CFA was also implemented in the program TOPAS (Coelho, 2007b). This program contains an implementation of CF with several special features (see §§3 and 4). It is focused on structure solution from powder diffraction data and includes the powder CFA with histogram matching (§7.3), but can be also used with single-crystal data. A basic, but functional charge-flipping routine is included in the set of tools smtbx (small molecule toolbox; Bourhis et al., 2009 ), which is distributed with the crystallographic package Olex² (Dolomanov et al., 2009 ).

In 2006 a dedicated program named Superflip was developed and was published the following year (Palatinus & Chapuis, 2007). This program allows the application of the CFA in arbitrary dimensions, allowing the solution of ordinary periodic structures as well as modulated structures and quasicrystals (see §7.2). The program also contains most of the modifications of the charge-flipping algorithm described in §3 (except for the flip-mem variant and the combination of CFA with a tangent formula), and the symmetry-determination algorithm due to Palatinus & van der Lee (2008). It also contains the general, six-parameter iteration scheme [equation (24)], allowing the application of a wide variety of iterative algorithms (Table 1). Superflip is interfaced from a number of crystallographic packages including JANA2006 (Petříček et al., 2006 ), WinGX (Farrugia, 2012 ), Crystals (Betteridge et al., 2003 ) or FullProf (Rodríguez-Carvajal, 2012 ). The script flipsmall.py, written by A. van der Lee, can be used to interface the program with Olex² (Dolomanov et al., 2009). The web page https://www.cbs.cnrs.fr/SP/crystal/SUPERFLIP/ contains a set of tools to facilitate the applications of Superflip in macromolecular crystallography.

7. Applications

7.1. General structure solution

When the CFA was published, the authors themselves were quite skeptical about its competitiveness with state-of-the-art software and methods. Even today it probably remains true that the CFA cannot compete with the best available methods when it comes to the solution of very large, non-centrosymmetric, light-atom structures. However, these structures represent only a small fraction of structures encountered in daily crystallographic practice. When it comes to other problems, charge flipping does offer a number of features that make it attractive, be it the speed, the quality and clarity of solutions, or the fact that it does not require knowledge of the space group and composition. In daily practice, users' preferences tend to be very subjective and unpredictable, and the preference of one method over another is often determined not only by the general power of the method, but also by the type of problems to be solved, by tradition, habits, aesthetic reasons, the ease of use, and by the details of implementation of the method in a computer program.

For all these reasons it is essentially impossible to say which structure solution method is the best. Ideally, the practicing crystallographer should be familiar with a whole set of methods, and combine them to obtain the best results. van der Lee (2009 ) tested automated structure solution work flow on a large set of standard crystal structures using various methods and programs, and found that statistically the ability to find a solution is comparable for direct methods and the CFA, but the best results can be obtained by combining the results from both approaches. Regardless of the comparison, it is clear by now that the CFA has found its users. The first application of the algorithm to experimental data was presented by Wu, Spence et al. (2004), followed by the solution of an interesting, albeit already known, structure with strong pseudosymmetry (Oszlányi et al., 2006 ). The method gained broader acceptance after it became available in user-friendly crystallographic software (§6). The first published periodic structure solved by the CFA and not known previously appears to be acetone 2-nitrophenylhydrazone, published in February 2007 (Wardell et al., 2007 ), although unknown aperiodic structures had already been solved and published in 2006 (§6). The number of solved structures has grown steadily since 2007. It is impossible to say exactly how many published structures were solved by charge flipping, because many references to charge flipping are hidden as references to the software packages, but their number reaches certainly hundreds per year.

7.2. Incommensurately modulated structures and quasicrystals

For periodic structures, dual-space methods are one of several possibilities. For aperiodic structures, the situation is different. Aperiodic structures – incommensurately modulated structures or quasicrystals (Janssen et al., 2007 ; van Smaalen, 2007 ) – are usually described in higher-dimensional superspace, where the atoms are not point-like objects, but are extended along the perpendicular dimensions, forming so-called atomic domains. Although extensions of direct methods to modulated structures have been proposed (Hao et al., 1987 ; Xiang et al., 1990 ; Fan et al., 1993 ), they have not reached wide use in practice and modulated structures used to be solved in a two-step procedure. First, the average structure was solved from main reflections only, and then the modulation was determined essentially by trial and error. In quasicrystal research the situation was similar, and insight into the structures of quasicrystals was often gained through the solution of approximant structures. The advent of dual-space methods changed the situation a lot. They do not impose any restriction on the form of the reconstructed scattering density, and can thus be thus directly generalized to superspace. The generalization is very straightforward. Nothing at all must be changed in the iteration scheme or in the form of the magnitude or positivity constraints [equations (6) and (8)]. The only difference is that $[\rho]$ is sampled not on a three-dimensional grid, but on a (3+d)-dimensional grid, where d depends on the rank of the modulation.

The first successful attempts to solve quasicrystal structures with dual-space algorithms predate the publication of the CFA, and employ the LDE algorithm (Takakura et al., 2001 ). The success rate of the solution was relatively low and a multisolution strategy had to be employed. The success rate was low mainly because the phases of the Fourier coefficients were fixed to 0 or π during the iteration.

The possibility of applying the CFA to incommensurately modulated structures was demonstrated very soon after its publication (Palatinus, 2004). It was demonstrated that the algorithm can solve many modulated structures directly in superspace without the need to first determine the average structure. Soon, the method was successfully applied to the first unknown modulated structures (Zuniga et al., 2006 ; Palatinus et al., 2006 ). The method was also quickly applied to decagonal quasicrystals (Fleischer & Steurer, 2007 ; Strutz & Steurer, 2007 ; Katrych et al., 2007 ). In the latter work it was demonstrated how using only an approximant to gain insight into the true quasicrystal structure may sometimes lead to incorrect conclusions.

Thanks to the implementation of the CFA in the program Superflip, which permits the direct solution of structures in superspace, charge flipping has evolved to a method of first choice for ab-initio solution of complex incommensurately modulated structures and quasicrystals.

7.3. Powder diffraction data

Structure from powder diffraction data is a difficult problem for all but very simple structures. Most of the new structures are nowadays solved by direct-space methods, which employ global minimization techniques to optimize the structure model against a powder diffraction diagram (for an overview see e.g. Cerny & Favre-Nicolin, 2007 ). The complexity of these approaches, however, tends to grow exponentially with the number of degrees of freedom in the model. Therefore, they are very well suited for structures with large known molecular fragments or other motifs. Cases where the complexity of the structure makes it inaccessible for these techniques are still not rare.

The application of truly ab initio methods to the structure solution from powder data is hindered by the fact that the one-dimensional powder diffraction pattern contains overlapping peaks, and hence the intensities of individual reflections are not known. This problem of reflection overlap is central to the solution from powder diffraction data. The first method addressing the overlap problem in combination with charge flipping was proposed by Wu et al. (2006). The key difference of their method from the basic algorithm was the addition of an intensity-repartitioning step during the Fourier-space part of the iteration cycle. In this step, instead of the standard operation (6) the following modification is used¹

$[F_j^{\rm new} = \cases{ {|F_j^{o}|\over|F_j^{\rm old}|}F_j^{\rm old}\,\,\,\,\,\qquad\,\,\,\, {\rm if }\, {\bf h}_j\in M \,{\rm and\, not\, overlapped} \cr \sqrt{{{\sum\limits_{\rm overlap}|F_j^{o}|^2} \over {\sum\limits_{\rm overlap} |F_j^{\rm old}|^2}}}F_j^{\rm old} \,\,\,\, {\rm if }\, {\bf h}_j\in M\, {\rm and\, overlapped} \cr 0\qquad\qquad\qquad \,\,{\rm otherwise} }.\eqno(33)]$

The second possibility is employed if certain reflections belong to a group of overlapping reflections, and thus only the sum of their intensities is known. Then the magnitude of F_j^old is not replaced by the experimental magnitude F_j^o (which is not known), but it is only scaled so that the sum of all $[|F_j^{\rm new}|^2]$ within one overlap group is constant and equal to the sum of [|F_j^o|^2] known from the experiment. The method was shown to work on a series of simple test cases and on two unknown structures of tetragonal tungsten bronzes. Unfortunately, the performance of the modified algorithm is not compared with the standard algorithm without the treatment of the overlapping reflections. The unmodified algorithm was shown to work well several times for powder diffraction data if the structures are not too complex and if the degree of overlap does not exceed the critical limit (Baerlocher, Gramm et al., 2007 ; Le Bail et al., 2009 ). It is thus difficult to judge how important the repartitioning scheme employed in this algorithm was for the solution of the examples presented.

Another approach to the repartitioning problem was adopted by Baerlocher, McCusker & Palatinus (2007). In order to obtain a more reliable partitioning of the overlapped reflections, the charge-flipping iteration was combined with additional external information, namely with the known histogram of the density. The histogram matching procedure was first adopted in macromolecular crystallography as part of the phase-refinement process (Zhang & Main, 1990 ), but here it was employed to update both the phases and intensities of the overlapping reflections. The powder charge-flipping scheme is shown in Fig. 3. The histogram-matching procedure is applied after every n cycles of the basic charge-flipping iteration, n being typically 10–50. The current density values are modified by a piece-wise linear transformation to match the expected density histogram. Such modified density is Fourier-transformed to yield a new set of Fourier coefficients F_j^HM. Then an operation analogous to equation (33) is performed, but using F_j^HM instead of F_j^old for the repartitioning

$[F_j^{\rm new} = \cases {{|F_j^{o}| \over {|F_j^{HM}|}}F_j^{HM}\,\,\,\,\, \,\,\qquad\qquad{\rm if }\, {\bf h}_j\in M \, {\rm and\, not\, overlapped} \cr \sqrt{{{\sum_{\rm overlap}|F_j^{o}|^2} \over {\sum_{\rm overlap}|F_j^{HM}|^2}}}F_j^{HM}\,\,\,\,\,\,\,\,\,{\rm if }\, {\bf h}_j\in M \,{\rm and\, overlapped} \cr 0 \qquad\qquad\qquad\qquad\,\, {\rm otherwise} }.\eqno(34)]$

Thus the overlapped reflections are repartitioned so that the sum of their squared magnitudes equals the experimentally determined sum, but their ratios correspond to the ratios of F_j^HM obtained after the histogram matching step. As the histogram matching procedure is expected to improve the current $[\rho]$ , also the ratios of the Fourier magnitudes of the overlapped reflections should be improved, and the whole procedure should lead to a better repartitioning of the overlapped intensities. After the histogram matching step, the standard charge-flipping iteration continues with the updated magnitudes of the Fourier coefficients.

Figure 3
The flow chart of the powder CFA with histogram matching. For the detailed description of the histogram matching step, see Baerlocher, McCusker & Palatinus (2007)

, equations (1), (2) and (3).

This method was shown to be a very powerful extension of the standard CFA. Baerlocher, McCusker & Palatinus (2007) have demonstrated the solution of several structures, ranging from relatively simple ones to quite complex structures like the zeolite ZSM-5 with 38 atoms in the asymmetric unit (288 in the unit cell). This method was then successfully used to solve a number of structures, mainly of zeolites and other framework materials (Massueger et al., 2007 ; Koyama et al., 2008 ; Xie et al., 2009 ; McCusker et al., 2009 ; Liu et al., 2009 ; Park et al., 2011 ; Gandara et al., 2012 ).

Despite the substantial improvement, the powder CFA was not sufficiently strong to solve some of the true challenges of contemporary powder diffraction, especially among zeolite structures. Means were therefore sought to further improve the algorithm. A solution was found in incorporating the additional knowledge about the structures from high-resolution transmission electron microscopy (HRTEM). Properly acquired HRTEM images on sufficiently thin samples at special projections allow estimating the phases of corresponding Fourier coefficients (Zou et al., 2011 ). Combining the estimated phases with the magnitudes of a few low-resolution reflections yields a low-resolution electron density map – a structure envelope (Brenner et al., 2002 ). Both the phases and the envelope can be used as additional information in the charge-flipping iteration. The complete flow chart of the method is complicated, and details can be found in the original works (Baerlocher et al., 2007a; Baerlocher et al., 2008 ; McCusker & Baerlocher, 2009 ). In general terms, the envelope is used to eliminate the density outside the envelope. The known phases are used to generate a non-random starting model. In practice, the known phases are fixed for a certain number of iteration cycles, and then released to give the model more freedom to develop, and to correct possible errors in the supposedly known phases. Using this combination of charge flipping, histogram matching, structure envelope and known phases, some of the most complex zeolite structures could be elucidated (Baerlocher, Gramm et al., 2007; Baerlocher et al., 2008; Koyama et al., 2008; Sun et al., 2009 ).

A curious but surprisingly effective method for the determination of a subset of Fourier phases directly from the powder diagram was developed by Xie, McCusker & Baerlocher (2011). They noticed that quite reliable Fourier phases can be obtained by running the CFA in two dimensions using only reflections from a planar section passing through the origin of reciprocal space. The result of such a reconstruction is the structure projection on the selected plane. In the tests on centrosymmetric zeolite structures, this technique yielded ∼ 60% of correctly determined phases, corresponding to ∼ 75% of the scattering power. These numbers are comparable with the accuracy obtained from HRTEM images. Intuitively, this technique should work best for special structure projections with many empty spaces between projected atomic positions. Such projections yield the strongest reflection intensities. This intuition must be correct to a certain extent but, surprisingly, the published tests do not show this effect. Comparable results were obtained for different projections with different contrast. The method has been used to solve an unknown zeolite SSZ-82 (Xie, Baerlocher & McCusker, 2011 ). Its full potential and limitations still remain to be explored.

It is worth noting that most of the variants and improvements of the basic CFA described in §3 are not useful for powder diffraction data. Even the most complex structures solved from powder data would be very easy to solve from single-crystal data. What is needed is more external information that allows us to augment the degraded intensity information in the powder diagram. Histogram matching, structure envelope and known phases are efforts going in this direction, as well as the application of symmetry constraints during the iteration (see §4).

7.4. Macromolecular crystallography

The ab-initio structure solution of macromolecular crystals is very challenging due to the large number of mainly light atoms in the unit cell, and generally low-resolution diffraction data. With low-resolution data the atomicity of the corresponding density map is not guaranteed, and the amount of nearly zero electron density is insufficient for the use of positivity projection in dual-space algorithms. If high-resolution data are available, methods for ab initio phasing of macromolecular crystals exist (Weeks & Miller, 1999 ; Foadi et al., 2000 ; Burla et al., 2004, 2006; Sheldrick, 2008 ). The CFA was shown to also be applicable in these cases, if at least a couple of heavy atoms (calcium or heavier) are present (Dumas & van der Lee, 2008 ). The best results were obtained with the π-half variant [equation (27)], with normalized diffraction data, and with relatively high $[k_{\rm ed}\simeq 1.2]$ .²

Another commonly appearing task in macromolecular crystallography is the solution of heavy-atom substructures from anomalous or isomorphous difference data. Such data can be understood as being very noisy corresponding only to the heavy-atom substructure. The CFA was applied to a selection of 5 such data sets comprising between 8 and 120 heavy atoms in the asymmetric unit (Dumas & van der Lee, 2008), and a complete solution was found in all of them. It appears that the CFA can compete with established methods of substructure phasing for complex substructures. Interestingly, the procedure fails to solve some simple test cases, indicating that a certain complexity of the structure is necessary, and too few heavy atoms in the unit cell do not provide sufficient support to stabilize the solution.

7.5. Single-particle imaging

Imaging of non-periodic objects is not a crystallographic problem in the strict sense, but the two fields share a lot of their experimental and computational aspects. Charge flipping has also found some applications in this field and it therefore deserves a short notice. The first applications of the CFA to the solution of the phase problem of non-periodic images are due to Wu and coworkers (Wu, Weierstall et al., 2004; Wu & Spence, 2005b ). Traditionally, the phase retrieval algorithms required some sort of object support to be known or estimated, and the phase retrieval then used the support constraint. The attractive feature of the CFA is that the support can be found dynamically during the iteration. Because the basic CFA is prone to stagnation, it was combined with the HIO algorithm. The charge-flipping part was used to determine the support of the particle, and the HIO algorithm then allowed the determination of the fine structure inside the support. Later various modifications of this basic principle were proposed for phasing single-particle diffraction data (Wu & Spence, 2005a ; Fung et al., 2009 ). Saldin and coworkers used the basic CFA in combination with sophisticated data-treatment methods to reconstruct single-particle images from various types of diffraction patterns of many particles (Saldin, Poon et al., 2010 ; Saldin, Shneerson, Howells et al., 2010 ; Saldin, Shneerson, Starodub et al., 2010 ; Saldin et al., 2011 ). Recently, Dumas et al. (2013 ) demonstrated on simulated noisy data that the CFA alone, especially in its $[F+\Delta F]$ or AAR variant, is capable of reconstructing three-dimensional images of non-periodic objects from their three-dimensional X-ray diffraction patterns. Examples range from small polypeptides up to a vault or mimivirus. No information on the support is needed and the algorithm is robust against the omission of the central part of the diffraction pattern.

In the single particle imaging field, the Fienup's HIO algorithm and related algorithms are state-of-the-art. Charge flipping contributed to the field mainly by drawing attention to the fact that the positivity projector/reflector is strong enough to allow phase retrieval without the need to explicitly determine the support.

8. Conclusions and outlook

In the eight years since its publication, the CFA has marked the field of crystallography with dozens of reacting methodological publications and hundreds of solved crystal structures. In retrospect, it may be tempting to claim that the algorithm did not bring anything new. It was not the first suggested dual-space algorithm for crystal structure solution, the potential of the positivity projection with threshold $[\delta]$ has already been demonstrated through the LDE method, and the role of reflectors in improving the power of dual-space algorithms was known from other fields. While all this is true, the indisputable contribution of the CFA is that it combined all these elements in a single, extremely simple, yet elegant and powerful method. Probably due to its simplicity, elegance and clarity of the presentation it was the first algorithm of its kind that attracted the attention of the wide crystallographic community and soon resulted in successful applications to real problems. The authors of the algorithm also spent considerable effort to provide thorough tests of the algorithm and its variants. That simplified greatly the implementation of the algorithm. Therefore, dedicated user-friendly software appeared quickly, and the method became available to a broad audience. Thanks to the combination of all these aspects, charge flipping meant a breakthrough for dual-space methods in crystallography.

The main problem in the development of phase-retrieval algorithms is that no solid mathematical theory is available that would allow the determination of the perfect algorithm. Much insight can be gained from analogies with convex optimization theory, but the results are not directly applicable. Moreover, an algorithm is not just an iteration scheme, but a combination of the iteration scheme and the exact definition of the constraints and projections. A successful algorithm is a fine balance between all components, and a small, seemingly unimportant change can result in a change of efficiency by several orders of magnitude. Therefore, it can be hoped that even more powerful algorithms will be discovered in the future, and iterative dual-space phasing algorithms will become, together with other structure solution methods, a standard tool among the methods used by crystallographers for crystal structure solution.

Footnotes

¹In the original publication (Wu et al., 2006), the factor in the second of the three options in equation (33) is incorrectly defined as $[\textstyle{{\sum_{\rm overlap}|F_j^{o}|} / {\sum_{\rm overlap} |F_j^{\rm old}|}}]$ . This is a typo in the publication, and the form presented here in equation (33) is the correct form used in the algorithm (Wu, 2012 ).

²In the paper, the reported optimal k_ed is 1.3. This value is found if $[\sigma(\rho)]$ is calculated only once at the begining of the iteration and is assumed to be constant during the iteration. This method was used in the version of Superflip used in the tests, and is valid for the standard CFA and for the magnitude projector (6). If, however, the Fourier magnitudes change during the iteration [as with equation (5) or with the AAR scheme], $[\sigma(\rho)]$ should be updated every cycle. With this approach it was found that optimal k_ed is actually 1.2 instead of 1.3 (Dumas, 2011 ).

Acknowledgements

The author is indebted to Russel Luke (University of Göttingen) for helpful discussions and useful informations about dual-space algorithms. The author would also like to express his thanks to Gabor Oszlányi (Wigner Research Centre for Physics, Hungarian Academy of Sciences) for his readiness to help and openness to share ideas in many discussions over the past years.

References

Baerlocher, C., Gramm, F., Massueger, L., McCusker, L. B., He, Z., Hovmoeller, S. & Zou, X. (2007). Science, 315, 1113–1116. Web of Science CrossRef PubMed CAS Google Scholar
Baerlocher, C., McCusker, L. D. & Palatinus, L. (2007). Z. Kristallogr. 222, 47–53. Web of Science CrossRef CAS Google Scholar
Baerlocher, C., Xie, D., McCusker, L. B., Hwang, S.-J., Chan, I. Y., Ong, K., Burton, A. W. & Zones, S. I. (2008). Nature Mater. 7, 631–635. Web of Science CrossRef CAS Google Scholar
Bauschke, H. H., Combettes, P. L. & Luke, D. R. (2002). J. Opt. Soc. Am. A, 19, 1334–1345. Web of Science CrossRef Google Scholar
Bauschke, H. H., Combettes, P. L. & Luke, D. R. (2003). J. Opt. Soc. Am. A, 20, 1025–1034. Web of Science CrossRef Google Scholar
Bauschke, H. H., Combettes, P. L. & Luke, D. R. (2004). J. Approx. Theory, 127, 178–192. Web of Science CrossRef Google Scholar
Betteridge, P. W., Carruthers, J. R., Cooper, R. I., Prout, K. & Watkin, D. J. (2003). J. Appl. Cryst. 36, 1487. Web of Science CrossRef IUCr Journals Google Scholar
Bourhis, L. J., Gildea, R. J., Dolomanov, O. V., Howard, J. A. K. & Puschmann, H. (2009). IUCr Commission on Crystallographic Computing No. 10, pp. 19–32. Google Scholar
Brenner, S., McCusker, L. B. & Baerlocher, C. (2002). J. Appl. Cryst. 35, 243–252. Web of Science CSD CrossRef CAS IUCr Journals Google Scholar
Buerger, M. J. (1959). Vector Space and its Application in Crystal-Structure Investigation. New York: John Wiley. Google Scholar
Burla, M. C., Caliandro, R., Camalli, M., Carrozzini, B., Cascarano, G. L., Giacovazzo, C., Mallamo, M., Mazzone, A., Polidori, G. & Spagna, R. (2012). J. Appl. Cryst. 45, 357–361. Web of Science CrossRef CAS IUCr Journals Google Scholar
Burla, M. C., Caliandro, R., Carrozzini, B., Cascarano, G. L., De Caro, L., Giacovazzo, C. & Polidori, G. (2004). J. Appl. Cryst. 37, 258–264. Web of Science CrossRef CAS IUCr Journals Google Scholar
Burla, M. C., Caliandro, R., Carrozzini, B., Cascarano, G. L., De Caro, L., Giacovazzo, C., Polidori, G. & Siliqi, D. (2006). J. Appl. Cryst. 39, 527–535. Web of Science CrossRef CAS IUCr Journals Google Scholar
Burla, M. C., Caliandro, R., Giacovazzo, C. & Polidori, G. (2010). Acta Cryst. A66, 347–361. Web of Science CrossRef CAS IUCr Journals Google Scholar
Burla, M. C., Carrozzini, B., Cascarano, G. L., Giacovazzo, C. & Polidori, G. (2000). J. Appl. Cryst. 33, 307–311. Web of Science CrossRef CAS IUCr Journals Google Scholar
Burla, M. C., Carrozzini, B., Cascarano, G. L., Giacovazzo, C. & Polidori, G. (2002). Z. Kristallogr. 217, 629–635. Web of Science CrossRef CAS Google Scholar
Burla, M. C., Carrozzini, B., Cascarano, G. L., Giacovazzo, C. & Polidori, G. (2011). J. Appl. Cryst. 44, 1143–1151. Web of Science CrossRef CAS IUCr Journals Google Scholar
Burla, M. C., Carrozzini, B., Cascarano, G. L., Giacovazzo, C. & Polidori, G. (2012). J. Appl. Cryst. 45, 1287–1294. Web of Science CrossRef CAS IUCr Journals Google Scholar
Burla, M. C., Giacovazzo, C. & Polidori, G. (2010). J. Appl. Cryst. 43, 825–836. Web of Science CrossRef CAS IUCr Journals Google Scholar
Burla, M. C., Giacovazzo, C. & Polidori, G. (2011). J. Appl. Cryst. 44, 193–199. Web of Science CrossRef CAS IUCr Journals Google Scholar
Caliandro, R., Carrozzini, B., Cascarano, G. L., De Caro, L., Giacovazzo, C. & Siliqi, D. (2005a). Acta Cryst. D61, 1080–1087. Web of Science CrossRef CAS IUCr Journals Google Scholar
Caliandro, R., Carrozzini, B., Cascarano, G. L., De Caro, L., Giacovazzo, C. & Siliqi, D. (2005b). Acta Cryst. D61, 556–565. Web of Science CrossRef CAS IUCr Journals Google Scholar
Caliandro, R., Carrozzini, B., Cascarano, G. L., Giacovazzo, C., Mazzone, A. & Siliqi, D. (2009). J. Appl. Cryst. 42, 302–307. Web of Science CrossRef CAS IUCr Journals Google Scholar
Cascarano, G., Giacovazzo, C., Guagliardi, A. & Steadman, N. (1991). Acta Cryst. A47, 480–484. CrossRef CAS Web of Science IUCr Journals Google Scholar
Censor, Y. & Zenios, S. A. (1997). Parallel Optimization: Theory, Algorithms and Applications. Oxford University Press. Google Scholar
Cerny, R. & Favre-Nicolin, V. (2007). Z. Kristallogr. 222, 105–113. CAS Google Scholar
Coelho, A. A. (2007a). Acta Cryst. A63, 400–406. Web of Science CrossRef CAS IUCr Journals Google Scholar
Coelho, A. (2007b). TOPAS Academic, Version 4.1. Coelho Software, Brisbane. Google Scholar
Coelho, A. (2012). TOPAS Academic Technical Reference. Coelho Software, Brisbane. Google Scholar
David, W. I. F. (1987). J. Appl. Cryst. 20, 316–319. CrossRef CAS Web of Science IUCr Journals Google Scholar
Dolomanov, O. V., Bourhis, L. J., Gildea, R. J., Howard, J. A. K. & Puschmann, H. (2009). J. Appl. Cryst. 42, 339–341. Web of Science CrossRef CAS IUCr Journals Google Scholar
Douglas, J. & Rachford, H. H. (1956). Trans. Am. Math. Soc. 82, 421–439. CrossRef Google Scholar
Dumas, C. (2011). Personal communication. Google Scholar
Dumas, C. & van der Lee, A. (2008). Acta Cryst. D64, 864–873. Web of Science CrossRef CAS IUCr Journals Google Scholar
Dumas, C., van der Lee, A. & Palatinus, L. (2013). Submitted. Google Scholar
Eggeman, A., White, T. & Midgley, P. (2009). Acta Cryst. A65, 120–127. Web of Science CrossRef CAS IUCr Journals Google Scholar
Elser, V. (2003a). Acta Cryst. A59, 201–209. Web of Science CrossRef CAS IUCr Journals Google Scholar
Elser, V. (2003b). J. Opt. Soc. Am. A, 20, 40–55. Web of Science CrossRef Google Scholar
Elser, V. (2003c). J. Phys. A, 36, 2995–3007. Web of Science CrossRef Google Scholar
Fan, H. F., van Smaalen, S., Lam, E. J. W. & Beurskens, P. T. (1993). Acta Cryst. A49, 704–708. CrossRef Web of Science IUCr Journals Google Scholar
Farrugia, L. J. (2012). J. Appl. Cryst. 45, 849–854. Web of Science CrossRef CAS IUCr Journals Google Scholar
Feng, J. (2012). Acta Cryst. A68, 298–300. Web of Science CrossRef CAS IUCr Journals Google Scholar
Fienup, J. R. (1982). Appl. Opt. 21, 2758–2769. CrossRef CAS PubMed Web of Science Google Scholar
Fleischer, F. & Steurer, W. (2007). Philos. Mag. 87, 2753–2758. Web of Science CrossRef CAS Google Scholar
Fleischer, F., Weber, T., Deloudi, S., Palatinus, L. & Steurer, W. (2010). J. Appl. Cryst. 43, 89–100. Web of Science CrossRef CAS IUCr Journals Google Scholar
Foadi, J., Woolfson, M. M., Dodson, E. J., Wilson, K. S., Jia-xing, Y. & Chao-de, Z. (2000). Acta Cryst. D56, 1137–1147. Web of Science CrossRef CAS IUCr Journals Google Scholar
Fung, R., Shneerson, V., Saldin, D. K. & Ourmazd, A. (2009). Nature Phys. 5, 64–67. Web of Science CrossRef CAS Google Scholar
Gandara, F., Uribe-Romo, F. J., Britt, D. K., Furukawa, H., Lei, L., Cheng, R., Duan, X., O'Keeffe, M. & Yaghi, O. M. (2012). Chem. Eur. J. 18, 10595–10601. Web of Science CAS PubMed Google Scholar
Gerchberg, R. W. & Saxton, W. O. (1972). Optik, 35, 237–246. Google Scholar
Giacovazzo, C. (1998). Direct Phasing in Crystallography: Fundamentals and Applications. Oxford University Press. Google Scholar
Giacovazzo, C. & Siliqi, D. (1997). Acta Cryst. A53, 789–798. CrossRef CAS Web of Science IUCr Journals Google Scholar
Hao, Q., Liu, Y. & Fan, H. (1987). Acta Cryst. A43, 820–824. CrossRef CAS Web of Science IUCr Journals Google Scholar
Janssen, T., Chapuis, G. & de Boissieu, M. (2007). Aperiodic Crystals: From Modulated Phases to Quasicrystals. IUCr Monographs on Crystallography, No. 20. IUCr/Oxford Science Publishers. Google Scholar
Karle, J. & Hauptman, H. (1964). Acta Cryst. 17, 392–396. CrossRef CAS IUCr Journals Google Scholar
Katrych, S., Weber, T., Kobas, A., Massueger, L., Palatinus, L., Chapuis, G. & Steurer, W. (2007). J. Alloys Compd. 428, 164–172. Web of Science CrossRef CAS Google Scholar
Koyama, Y., Ikeda, T., Tatsumi, T. & Kubota, Y. (2008). Angew. Chem. Int. Ed. 47, 1042–1046. Web of Science CSD CrossRef CAS Google Scholar
Langs, D. A. (1998). Acta Cryst. A54, 44–48. CrossRef CAS IUCr Journals Google Scholar
Le Bail, A., Cranswick, L. M. D., Adil, K., Altomare, A., Avdeev, M., Cerny, R., Cuocci, C., Giacovazzo, C., Halasz, I., Lapidus, S. H., Louwen, J. N., Moliterni, A., Palatinus, L., Rizzi, R., Schilder, E. C., Stephens, P. W., Stone, K. H. & van Mechelen, J. (2009). Powder Diffr. 24, 254–262. Web of Science CrossRef CAS Google Scholar
Lee, A. van der (2009). Acta Cryst. A65, s108–s109. Google Scholar
Lei, N. (2007). Acta Cryst. A63, 66–76. Web of Science CrossRef CAS IUCr Journals Google Scholar
Lions, P.-L. & Mercier, B. (1979). SIAM J. Numer. Anal. 16, 964–979. CrossRef Web of Science Google Scholar
Liu, L., Li, J., Dong, J., Sisak, D., Baerlocher, C. & McCusker, L. B. (2009). Inorg. Chem. 48, 8947–8954. Web of Science CrossRef PubMed CAS Google Scholar
Luke, D. R. (2005). Inverse Probl. 21, 37–50. Web of Science CrossRef Google Scholar
Marchesini, S. (2007). Rev. Sci. Instrum. 78, 011301. Web of Science CrossRef PubMed Google Scholar
Massueger, L., Baerlocher, C., McCusker, L. B. & Zwijnenburg, M. A. (2007). Microporous Mesoporous Mater. 105, 75–81. CAS Google Scholar
Matsugaki, N. & Shiono, M. (2001). Acta Cryst. D57, 95–100. Web of Science CrossRef CAS IUCr Journals Google Scholar
McCusker, L. B. & Baerlocher, C. (2009). Chem. Commun. pp. 1439–1451. Web of Science CrossRef Google Scholar
McCusker, L. B., Baerlocher, C., Wilson, S. T. & Broach, R. W. (2009). J. Phys. Chem. C, 113, 9838–9844. Web of Science CrossRef CAS Google Scholar
Oszlányi, G. & Sütő, A. (2004). Acta Cryst. A60, 134–141. Web of Science CrossRef IUCr Journals Google Scholar
Oszlányi, G. & Sütő, A. (2005). Acta Cryst. A61, 147–152. Web of Science CrossRef IUCr Journals Google Scholar
Oszlányi, G. & Sütő, A. (2007). Acta Cryst. A63, 156–163. Web of Science CrossRef IUCr Journals Google Scholar
Oszlányi, G. & Sütő, A. (2008). Acta Cryst. A64, 123–134. Web of Science CrossRef IUCr Journals Google Scholar
Oszlányi, G. & Sütő, A. (2011). Acta Cryst. A67, 284–291. Web of Science CrossRef IUCr Journals Google Scholar
Oszlányi, G., Sütő, A., Czugler, M. & Párkányi, L. (2006). J. Am. Chem. Soc. 128, 8392–8393. Web of Science CrossRef PubMed CAS Google Scholar
Palatinus, L. (2004). Acta Cryst. A60, 604–610. Web of Science CrossRef CAS IUCr Journals Google Scholar
Palatinus, L. & Chapuis, G. (2007). J. Appl. Cryst. 40, 786–790. Web of Science CrossRef CAS IUCr Journals Google Scholar
Palatinus, L. & Damay, F. (2009). Acta Cryst. B65, 784–786. Web of Science CSD CrossRef CAS IUCr Journals Google Scholar
Palatinus, L., Dušek, M., Glaum, R. & El Bali, B. (2006). Acta Cryst. B62, 556–566. Web of Science CrossRef CAS IUCr Journals Google Scholar
Palatinus, L., Fleischer, F., Pattison, P., Weber, T. & Steurer, W. (2011). Acta Cryst. A67, 9–20. Web of Science CrossRef CAS IUCr Journals Google Scholar
Palatinus, L. & van der Lee, A. (2008). J. Appl. Cryst. 41, 975–984. Web of Science CrossRef CAS IUCr Journals Google Scholar
Palatinus, L., Steurer, W. & Chapuis, G. (2007). J. Appl. Cryst. 40, 456–462. Web of Science CrossRef CAS IUCr Journals Google Scholar
Park, M. B., Cho, S. J. & Hong, S. B. (2011). J. Am. Chem. Soc. 133, 1917–1934. Web of Science CrossRef CAS PubMed Google Scholar
Petříček, V., Dušek, M. & Palatinus, L. (2006). JANA2006. Institute of Physics, Praha, Czech Republic. Google Scholar
Rius, J. (1993). Acta Cryst. A49, 406–409. CrossRef CAS Web of Science IUCr Journals Google Scholar
Rius, J. (2012). Acta Cryst. A68, 77–81. Web of Science CrossRef CAS IUCr Journals Google Scholar
Rius, J., Crespi, A. & Torrelles, X. (2007). Acta Cryst. A63, 131–134. Web of Science CrossRef CAS IUCr Journals Google Scholar
Rius, J. & Frontera, C. (2008). Acta Cryst. A64, 670–674. Web of Science CrossRef CAS IUCr Journals Google Scholar
Rodríguez-Carvajal, J. (2012). FullProf. https://www.ill.eu/sites/fullprof/php/reference.html . Google Scholar
Saldin, D. K., Poon, H. C., Bogan, M. J., Marchesini, S., Shapiro, D. A., Kirian, R. A., Weierstall, U. & Spence, J. C. H. (2011). Phys. Rev. B, 106, 115501. Google Scholar
Saldin, D. K., Poon, H. C., Shneerson, V. L., Howells, M., Chapman, H. N., Kirian, R. A., Schmidt, K. E. & Spence, J. C. H. (2010). Phys. Rev. B, 81, 174105. Web of Science CrossRef Google Scholar
Saldin, D. K., Shneerson, V. L., Howells, M. R., Marchesini, S., Chapman, H. N., Bogan, M., Shapiro, D., Kirian, R. A., Weierstall, U., Schmidt, K. E. & Spence, J. C. H. (2010). New J. Phys. 12, 035014. Web of Science CrossRef Google Scholar
Saldin, D. K., Shneerson, V. L., Starodub, D. & Spence, J. C. H. (2010). Acta Cryst. A66, 32–37. Web of Science CrossRef CAS IUCr Journals Google Scholar
Samy, A., Dinnebier, R. E., van Smaalen, S. & Jansen, M. (2010). Acta Cryst. B66, 184–195. Web of Science CrossRef CAS IUCr Journals Google Scholar
Schoeni, N. & Chapuis, G. (2007). Charge Flipping. Ecole Polytechnique Fédérale de Lausanne, Switzerland: https://escher.epfl.ch/flip/ . Google Scholar
Sheldrick, G. M. (2008). Acta Cryst. A64, 112–122. Web of Science CrossRef CAS IUCr Journals Google Scholar
Sheldrick, G. M. & Gould, R. O. (1995). Acta Cryst. B51, 423–431. CrossRef CAS Web of Science IUCr Journals Google Scholar
Shiono, M. & Woolfson, M. M. (1992). Acta Cryst. A48, 451–456. CrossRef CAS Web of Science IUCr Journals Google Scholar
Spek, A. L. (2003). J. Appl. Cryst. 36, 7–13. Web of Science CrossRef CAS IUCr Journals Google Scholar
Strutz, A. & Steurer, W. (2007). Philos. Mag. 87, 2747–2752. Web of Science CrossRef CAS Google Scholar
Sun, J., Bonneau, C., Cantin, A., Corma, A., Diaz-Cabanas, M. J., Moliner, M., Zhang, D., Li, M. & Zou, X. (2009). Nature, 458, 1154–1157. Web of Science CrossRef PubMed CAS Google Scholar
Takakura, H., Shiono, M., Sato, T. J., Yamamoto, A. & Tsai, A. P. (2001). Phys. Rev. Lett. 86, 236–239. Web of Science CrossRef PubMed CAS Google Scholar
van Smaalen, S. (2007). Incommensurate Crystallography. New York: Oxford University Press. Google Scholar
van Smaalen, S., Palatinus, L. & Schneider, M. (2003). Acta Cryst. A59, 459–469. Web of Science CrossRef CAS IUCr Journals Google Scholar
Wang, B. C. (1985). Methods Enzymol. 115, 90–112. CrossRef CAS PubMed Google Scholar
Wardell, S. M. S. V., Wardell, J. L., Low, J. N. & Glidewell, C. (2007). Acta Cryst. E63, o970–o971. Web of Science CSD CrossRef CAS IUCr Journals Google Scholar
Weeks, C. M., DeTitta, G. T., Miller, R. & Hauptman, H. A. (1993). Acta Cryst. D49, 179–181. CrossRef CAS Web of Science IUCr Journals Google Scholar
Weeks, C. M. & Miller, R. (1999). Acta Cryst. D55, 492–500. Web of Science CrossRef CAS IUCr Journals Google Scholar
Wu, J. S. (2012). Personal communication. Google Scholar
Wu, J. S., Leinenweber, K., Spence, J. C. H. & O'Keeffe, M. (2006). Nature Mater. 5, 647–652. Web of Science CrossRef CAS Google Scholar
Wu, J. & Spence, J. (2005a). J. Opt. Soc. Am. A, 22, 1453–1459. Web of Science CrossRef Google Scholar
Wu, J. S. & Spence, J. C. H. (2005b). Acta Cryst. A61, 194–200. Web of Science CrossRef CAS IUCr Journals Google Scholar
Wu, J. S., Spence, J. C. H., O'Keeffe, M. & Groy, T. L. (2004). Acta Cryst. A60, 326–330. Web of Science CrossRef CAS IUCr Journals Google Scholar
Wu, J. S., Weierstall, U., Spence, J. C. H. & Koch, C. T. (2004). Opt. Lett. 29, 2737–2739. Web of Science CrossRef PubMed CAS Google Scholar
Xiang, S.-B., Fan, H.-F., Wu, X.-J., Li, F.-H. & Pan, Q. (1990). Acta Cryst. A46, 929–934. CrossRef CAS Web of Science IUCr Journals Google Scholar
Xie, D., Baerlocher, Ch. & McCusker, L. B. (2011). J. Appl. Cryst. 44, 1023–1032. Web of Science CrossRef CAS IUCr Journals Google Scholar
Xie, D., McCusker, L. B. & Baerlocher, C. (2011). J. Am. Chem. Soc. 133, 20604–20610. Web of Science CrossRef CAS PubMed Google Scholar
Xie, D., McCusker, L. B., Baerlocher, C., Gibson, L., Burton, A. W. & Hwang, S.-J. (2009). J. Phys. Chem. C, 113, 9845–9850. Web of Science CrossRef CAS Google Scholar
Xu, H. & Hauptman, H. A. (2000). Acta Cryst. A56, 284–287. Web of Science CrossRef CAS IUCr Journals Google Scholar
Zhang, K. Y. J. & Main, P. (1990). Acta Cryst. A46, 41–46. CrossRef CAS IUCr Journals Google Scholar
Zhou, Z. & Harris, K. D. M. (2008). J. Phys. Chem. A, 112, 4863–4868. Web of Science CrossRef PubMed CAS Google Scholar
Zou, X., Hovmöller, S. & Oleynikov, P. (2011). Electron Crystallography. Oxford University Press. Google Scholar
Zuniga, F. J., Palatinus, L., Cabildo, P., Claramunt, R. M. & Elguero, J. (2006). Z. Kristallogr. 221, 281–287. CAS Google Scholar

© International Union of Crystallography. Prior permission is not required to reproduce short quotations, tables and figures from this article, provided the original authors and source are cited. For more information, click here.

STRUCTURAL SCIENCE
CRYSTAL ENGINEERING
MATERIALS

ISSN: 2052-5206

Volume 69| Part 1| February 2013| Pages 1-16

doi:10.1107/S2052519212051366

Free