Tuesday, November 6, 2007 - 10:35 AM

A Novel Integer Minimal Principle with Atomicity Constraints for Phasing Single-Crystal X-Ray Diffraction Data

Alexander B. Smith and Nick Sahinidis. University of Illinois, Department of Chemical and Biomolecular Engineering, 600 South Mathews Avenue, Urbana, IL 61801

A vast majority of structural solutions are derived using the physics of X-ray diffraction, especially in the case of important biological macromolecules. The computation of a structure from X-ray diffraction data, however, remains a very challenging, nontrivial problem, both experimentally and computationally. A major obstacle, coined, “the phase problem,” represents a dilemma in which phase information, critical to computation of the 3D structure of a crystal, is not directly measurable in a traditional X-ray diffraction experiment.

The phase problem has recently been approached via combinatorial optimization techniques and the resulting sieve method has been demonstrated to be effective for phasing centrosymmetric structures [1]. The purpose of the current work is to (a) develop a more robust enforcement of atomicity constraints in direct space and (b) extend the approach of [1] from the centric to the most challenging non-centric case, thus making the approach directly applicable to proteins and other chiral molecules.

A mixed-integer linear programming model for phasing based on the minimal principle is presented; one which includes the introduction of specific atomicity constraints. Building on the MILP model presented in [1], atomicity is constrained through sampling of electron density on a grid. First, a set of points is selected, at random, to sample the unit cell. Electron density is calculated at these points in terms of the integer variables, which describe the phases. Physical constraints in direct space are then enforced using the grid of electron density. Computational results are presented for many challenging structures, and the extension to non-centrosymmetric space groups is presented.


[1] A. B. Smith, H. Xu, and N. V. Sahinidis. An integer minimal principle and triplet sieve method for phasing centrosymmetric structures. Acta Crystallographica A, 63(2):164–171, 2007.