The phase problem is the major problem in the field of X-ray crystallography. In the context of direct methods, that use mathematical techniques to compute an electron density map from the diffraction data without any further experiments, binary integer programming models for solving the phase problem have been de- veloped. Based on descriptions of topological properties of 2-dimensional binary pictures known from the field of discrete tomography, these models have been extended for the 3-dimensional case. As the formulations are in general not sufficient to describe the more complex properties of the shape of proteins, binary integer pro- grams have been derived for describing different additional topological properties. In general, the binary integer program for solving the phase problem, leads to a set of different optimal solutions. The additional constraints increase the quality of the solution set. The main property considered is one restricting the number of components in the resulting solution. Using graph theoretical methods and a separation algorithm, a model to describe this property has been found and implemented. Computational results have been presented and evaluated. It has been shown, that the added topological constraints increase significantly the quality of the solution set. In the last chapter, a method to find the solutions all at once based on singu- lar value decomposition and methods to find integer points in ellipsoids has been developed. In further work, the efficiency of this method for the phase problem should be evaluated and the method could be implemented and tested. In order to further increase the solutions’ quality, more additional constraints could be formulated and added. If the running time of the solving algorithm could be decreased, a refinement of the model would be possible. Bigger grids could be considered showing more de- tails of the reconstructed protein. More phase values than just four ones could be introduced. A restriction of the electron density distribution to a finite number of states instead of regarding just the two binary ones would be a possible extension. So, based on the promising results presented here, lots of further work extending and refining the developed approaches is possible.

Academic Advisor

Prof. Dr. Alexander Bockmayr

Degree

PhD

Date

Dec 14, 2010