Constraint-based methods for phasing in crystallography [Elektronische Ressource] / Corinna Melanie Heldt

Sujets

• Mathematics

Informations

• Publié par: freie_universitat_berlin
• Publié le: 01 janvier 2010
• Nombre de lectures: 26
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Constraint-based methods for phasing in
crystallography
Corinna Melanie Heldt
Dissertation
zur Erlangung des Grades
Doktor der Naturwissenschaften (Dr. rer. nat.)
des Fachbereichs Mathematik und Informatik
der Freien Universit¨at Berlin
Freie Universit¨at Berlin
2010Gutachter:
Prof. Dr. Alexander Bockmayr (Freie Universit¨at Berlin)
Prof. Dr. Alexandre Urzhumtsev (Universit´e de Strasbourg und
Universit´e Henri Poincar´e, Nancy)
Tag der Disputation: 14. Dezember 2010
iiAcknowledgments
It is a pleasure to thank those who made this thesis possible and I express my
regardsandgratitudetothem supportingmeinany respect duringitscompletion.
My deepest gratitude is to my advisor, Prof. Dr. Alexander Bockmayr for his
encouragement, supervision, expert advice and guidance from the preliminary to
the concluding level of this dissertation.
I would like to thank my co-advisor, Prof. Dr. Alexandre Urzhumtsev, for his
support already in the early beginning of my thesis-writing, for helpful comments
and providing me with useful software.
I am indebted to the former and current members of the Mathematics in Life Sci-
ences Group, especially Dr. Heike Siebert, Dr. Gunnar Klau and Katja Geiger,
for providing a stimulating and pleasant working environment, fruitful discussions
and support in many different ways.
Thisthesishasbenefited fromthecommentsandcriticisms ofthosewhohaveread
various drafts of various parts of it, including Heike, Klaus and Daniel.
My deepest thanksgotomy family andfriends, especially my husband Daniel, my
parents KlausandAstrid and my sisters Birgit, Inge andCaroline fortheir contin-
uous encouragement, care and emotional support. This dissertation is dedicated
to them.
iiiivContents
Introduction 1
1 Some Crystallographic and Mathematical Basics 3
1.1 Introduction to X-ray Crystallography . . . . . . . . . . . . . . . . 3
1.1.1 X-ray-scattering . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Unit cell, real and reciprocal space . . . . . . . . . . . . . . 5
1.1.3 Bragg’s law . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.4 Ewald sphere . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Fourier analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Fourier series . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . 12
1.2.3 Multidimensional Fourier analysis . . . . . . . . . . . . . . . 12
1.2.4 Properties of Fourier series and DFT . . . . . . . . . . . . . 14
1.2.5 Protein crystallography . . . . . . . . . . . . . . . . . . . . . 16
1.2.6 The phase problem . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.7 Symmetries . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 A Binary Integer-Programming Approach to the Phase Problem 23
2.1 Solving the phase problem with a binary integer programming ap-
proach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.1 The Sayre equation . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.2 Grid structure factors. . . . . . . . . . . . . . . . . . . . . . 25
2.1.3 Structure factors vs. grid structure factors . . . . . . . . . . 27
2.1.4 Inequalities for the grid electron density values . . . . . . . . 28
v2.2 Recovering the phases . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.1 Symmetries . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.2 Properties of grid structure factors . . . . . . . . . . . . . . 30
2.2.3 Acentric reflections . . . . . . . . . . . . . . . . . . . . . . . 32
2.3 Constraint-based modelling of the phasing problem . . . . . . . . . 37
2.3.1 Constraint system . . . . . . . . . . . . . . . . . . . . . . . . 37
2.4 The objective function . . . . . . . . . . . . . . . . . . . . . . . . . 39
3 3-D Polyominoes 41
3.1 Two-dimensional reconstruction problem . . . . . . . . . . . . . . . 41
3.2 Three-dimensional reconstruction problem . . . . . . . . . . . . . . 45
4 Additional Geometric Constraints 49
4.1 Additional constraints . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.1 Exclusion of Isolated Points . . . . . . . . . . . . . . . . . . 50
4.1.2 Minimum covering . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2.2 Constraint programming . . . . . . . . . . . . . . . . . . . . 53
4.2.3 Graph-theoretical approach . . . . . . . . . . . . . . . . . . 54
4.2.4 Linear programming . . . . . . . . . . . . . . . . . . . . . . 57
4.2.5 Spanning tree polytopes . . . . . . . . . . . . . . . . . . . . 58
4.2.6 Connected components in a graph . . . . . . . . . . . . . . . 63
4.2.7 Cutset formulation . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.8 Cutting plane algorithms . . . . . . . . . . . . . . . . . . . . 74
4.2.9 Separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.10 Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . 77
4.2.11 Graph partitioning problems . . . . . . . . . . . . . . . . . . 78
5 Modelling the Phase Problem 83
5.1 Cutting plane algorithm . . . . . . . . . . . . . . . . . . . . . . . . 93
vi6 Implementation and Computational Results 95
6.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.1.1 Data Extraction . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.1.2 Program structure in SCIP . . . . . . . . . . . . . . . . . . . 97
6.1.3 Constraint handler . . . . . . . . . . . . . . . . . . . . . . . 99
6.1.4 Testing the programs . . . . . . . . . . . . . . . . . . . . . . 102
6.2 Test results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2.1 Evaluation of the results . . . . . . . . . . . . . . . . . . . . 104
7 A Different Approach: Integer Points in Polyhedra 111
7.1 Application in X-ray crystallography . . . . . . . . . . . . . . . . . 111
7.2 Singularvaluedecomposition,normalpseudosolutionandperturbed
systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.3 Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.4 Integer points in an ellipsoid . . . . . . . . . . . . . . . . . . . . . . 118
7.4.1 The LAMBDA-method . . . . . . . . . . . . . . . . . . . . . 120
7.4.2 Flow chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Bibliography 130
viiviiiAbstract
X-raycrystallographyisoneofthemainmethodstoestablishthethree-dimensional
structure of biological macromolecules, which is an essential base of structural bi-
ology and modern biotechnology.
In an X-ray experiment, one can measure only the magnitudes of the complex
Fourier coefficients of the electron density distribution under study, but not their
phases. The problem of recovering the lost phases is called the phase problem. As
the information provided by the X-ray diffraction experiment is not sufficient to
solve this problem, additional information about the electron density distribution
has to be considered.
Inthisworkbinaryintegerprogrammingapproachestomodeldifferenttopological
propertiesofproteinsaredeveloped. Especiallytheconnectivityconstraint,enforc-
ing that the calculated structure consists of at most a given number of connected
components, is considered. Using graph theoretical methods and a separation al-
gorithm,amodelisworkedout. Thedetailsoftheimplementationofthepresented
additional constraints are described and computational results are presented.
ixx