Constraint-based methods for phasing in crystallography

Abstract

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.

Röntgenkristallographie ist derzeit die Standardmethode zur Ermittlung der drei- dimensionalen Struktur biologischer Makromoleküle, wie z. B. von Proteinen, und liefert damit eine wichtige Basis der Strukturbiologie sowie der modernen Biotechnologie. Aus Röntgenexperimenten erhält man Beugungsmuster, aus welchen dann die Struktur des zu untersuchenden Kristalls berechnet werden soll. Diese wird durch die zugehörige Elektronendichteverteilung beschrieben. Allerdings liefert das Beugungsmuster nur die Beträge der komplexen Fourierkoeffizienten der Elektronendichte, nicht die zugehörigen Phasenwerte. Das Problem, diese Phasenwerte zu ermitteln, ist das Phasenproblem in der Röntgenkristallographie. Die Informationen, welche aus dem Röntgenexperiment gewonnen werden können, sind nicht ausreichend um dieses Phasenproblem zu lösen. Daher erhält man nicht nur eine, sondern eine Menge zulässiger Lösungen. Zusätzliche Informationen über die Elektronendichteverteilung können dann hinzugezogen werden um die Qualität dieser Lösungen zu verbessern. In dieser Arbeit wird ein ganzzahliger linearer Optimierungsansatz zur Lösung des Phasenproblems entwickelt, in dem verschiedene topologische Eigenschaften von Proteinen modelliert und als zusätzliche Informationen verwendet werden. Die wichtigste Eigenschaft, die so modelliert und für die Problemlösung hinzugezogen wird, ist die Zusammenhangseigenschaft von Proteinen. Diese sichert, dass die berechnete Struktur nicht aus mehr als einer gegebenen Anzahl zusammenhängender Komponenten besteht. Bei der Modellierung dieser Zusammenhangseigenschaft werden graphentheoretische Methoden sowie ein Separationsalgorithmus genutzt. Der Modellierungsansatz wurde implementiert und mit Daten von echten Proteinen getestet. Die Testergebnisse zeigen, dass die Qualität der Lösungen des Phasenproblems durch die Hinzunahme der topologischen Eigenschaften deutlich verbessert wird.