Ab initio phasing by Charge Flipping


    The importance of Fourier transforms is also illustrated by a relative simple phasing method named Charge Flipping, allowing to determine an object even if one knows only the moduli (i.e. not the phases) of its Fourier coefficients.
Indeed, some experimental techniques lead to the measurement of the moduli of the Fourier coefficients of a function describing the observed object, but not the associated phases. Then, according to what one saw about the relative importance of phases compared to moduli it should be impossible to know the object from such techniques.
For example, in conventional X-ray diffraction, the intensity of the X-ray beams diffracted by the sample are proportional to the squares of the moduli of the Fourier coefficients of the electronic density of this sample (under given hypothesis and after various corrections linked to absorption, anomalous scattering etc. effects that are unimportant for our purpose here). Then, the measurement of the intensity of these diffracted beams with an appropriate dectector allows the determination of the moduli of the Fourier coefficients but unfortunately not their phases (it could be noted that more specialized techniques allow the measurement of phase differences between some Fourier coefficients). Then, in order to reconstruct the electronic density function (and from here deduce atomic positions within the sample and their interactions) one have to be able to create these lost phases. Several methods more or less complex and effective were developed, ranging from a simple trial-and-error method (i.e. one supposes a given atomic structure and one compares the moduli of the Fourier coefficients calculated from this model to those extracted from the experimental data) to the more complex but more powerfull Direct Methods using positivity and atomicity constraints to the electron density.
    The "Charge Flipping" method (Oszlanyi, G. & Süto, A. (2003) Acta Cryst. A60, 134-141) is a rather simple to understand phasing technique, consisting of recurrent Fourier transformations between Fourier coefficients and the electron density, and by imposing to the latter to be positive (since it represents the number of electrons per volume):

         
'Charge Flipping' principle scheme

Starting with the observed Fourier moduli |F|obs one constructs complex Fourier coefficients using random phases Φaléa. However, these phases have to follow Friedel law (phase antisymmetry) in order to obtain a real value density ρ at the next step.

Then one computes the inverse Fourier transform of these coefficients: the obtained function ρ is of course consistent with the experiment (since it is based on the observed moduli) but due to the use of random phases this function can have areas of negative values, a situation that is not a physical solution for the problem.
To overcome this unphysical state, one modifies simply the density function ρ by converting each negative value in its opposite (one flips the density). In practive, for convergence reasons one uses a small positive threshold : the density above this level is kept unchanged, all value below it is reversed.
Then one computes the Fourier coefficients G of this modified density function g, from which one extract phases ΦG that are used  in comination with observed moduli |F|obsin order to recompute a new density function ρ. The process is then cyclic, and one can expect a convergence toward a physcial solution in a limited number of iterations.

To illustrate this technique one uses as object a digital image that can represent four benzene molecules C6H6.
The phasing technique consists then to use only the moduli of the Fourier coefficients of this image in order to reconstruct the object (i.e. find back the lost phases).

   
Original image and moduli of its Fourier coefficients

On simple applies the procedure described above using 100 cycles, recording the reconstruct density at the end of each cycle (see the movie benzene.avi 318Ko). One can observe that at the end of these 100 cycles the recosntructed image is very similar to the original object, a similarity that is absolutely not present in the first cycles. In this particular example ~60 cycles are required before one can recognize the expected object:

           
Reconstructed image after: 1, 40, 70 & 100 cycles

One can see also that the reconstructed image is shifted compared to the original object: this comes from the fact that the moduli of the Fourier transform of a function and those of the same but shifted function are equal, the only difference being in the phases. If the original image is not symmetric by inversion one will able to observe that the reconstructed image will be in the same or reverse hand (inversion symmetry) than the original one.

The evolution of the reconstruction process can be followed with an agreement factor R, displaying the similarity between the moduli of the original image |F|obs and those of the reconstructed one |G|:

and also as a function of the Fourier coefficient |G(0,0)| which is nothing else than the total intensity of the recontructed image (rmk: initially |G(0,0)| was set to 0 because in X-ray diffraction this Fourier coefficient of the electron density corresponds to the beam diffracted with an angle of 0° relative to the incident beam direction and then cannot be measured).
    

 
Agreement factor between |F|obs & |G| as a function of cycle number(R=0.168 for cycle #100)

 
|G(0,0)| as a function of cycle number (|G(0,0)|=680412 for cycle #100, to be compared to 704712 for the original image, i.e. an error <4%)

The convergence is clearly visible on the plot of R and is achieved between cycle numbers 40 & 70, and one can observe that this R factor does not tend to zero but toward a significative positive value. This is linked to the fact that one choose a flipping threshold slightly positive (not zero): the low value densities cannot therefore be correctly reconstructed since the charge flipping process flip them from a cycle to another; one solution to improve this is to use a high threshold at the beginning in order to converge rapidly toward a physical meaningful solution, then to diminish this threshold in order to deal with low density areas (four 'light atoms' were added in the original image: compare benzenebisstatic.avi 7720Ko & benzenebisdyn.avi 6201Ko obtained with a constant or dynamic flipping threshold).

All these examples are easily done with scripts in DigitalMicrograph.