Automation And Performance Optimisation Of The Direct Space Method For Crystal Structure Determination

The methods for crystal structure determination can be roughly classified into two categories,the reciprocal space methods and the direct space method(DSM).The reciprocal space methods work by extracting the amplitudes of structure factors for individual reflections and then phasing these reflections,after which the Fourier transform is used to obtain the electron density distribution in the unit cell.In contrast,the DSM uses global optimisation(GO)algorithms to minimise the divergence between the computed and measured diffraction patterns,and uses the coordinate combination of atoms in the unit cell as the variables to be optimised.In comparison with the reciprocal space methods,the DSM is more suitable for handling low-resolution diffraction data,and is more tolerant of overlapping reflection peaks in diffraction patterns.When using the DSM,a priori knowledge of the structure to be determined is very helpful,so the DSM is quite suitable for structures like molecular crystals and framework crystals;on the other hand,it is much more difficult to determine structures using the DSM when the bonding relations are largely unknown.To reduce the degree of freedom of the GO problem,the equivalent position combination(EPC)method can often be used for the latter kind of structures: by assigning the atoms to the available Wyckoff positions,we can transform the 3n-dimensional GO problem with regard to all n atoms in the unit cell into multiple mutually independent problems,each of which only using the non-fixed coordinates of the independent atoms from one EPC,and usually having a degree of freedom much smaller than 3n.In structure determination using the DSM,often encountered are chemically unreasonable crystallographic models with the computed diffraction patterns very similar to the measured patterns,and one of the top problems is atom bumping: in many of these crystallographic models,the distance between some atom pairs are unreasonably short.To automatically handle atom bumping,we need to efficiently detect and eliminate crystallographic models with atom bumping in real time during the GO procedure;since the detection of atom bumping is known as collision detection in computational geometry,what we need first is a real-time algorithm for crystallographic collision detection.Based on the axis-aligned bounding box(AABB)model,and noticing the unique geometric structure of the unit cell,the author proposed a generic framework for crystallographic collision detection.Based on this framework,regarding structures with largely unknown bonding relations,the author modified the sweep and prune(SAP)algorithm,enabling it to detect atom bumping in the unit cell in O(n log n)time bound.In addition,considering that the EPC method is often used in determination of these structures,the author proposed a method that employs the equivalent position symmetry to significantly reduce the computational complexity of collision detection.Based on these algorithms,the author designed an evaluation function for atom bumping in crystallographic models,which can be used to eliminate unreasonable models in real time during the GO procedure;additionally,apart from the prevention of atom bumping,the collision detection algorithms mentioned above can also be very helpful in computation of coordination polyhedra,valence,etc.in crystallographic models.To facilitate practical use of above-mentioned mechanisms in determination of unknown structures,the author wrote decryst,a software suite for structure determination from powder diffraction that uses the DSM.decryst is functionally similar to EPCryst:both use indexed data,employ the EPC method and abstract structure determination as4 stages,enumerating EPCs,statistical analyses of EPCs,GO of EPCs and exporting the results;and due to the EPC method,both are particularly suitable when the bonding relations are largely unknown.The most important advantage of decryst over EPCryst is that the former can automatically and efficiently eliminate atom bumping.In addition,inspired by the make utility from Unix,the author employed incremental computation in a generic way,for the first time,in the GO procedure,resulting in a dramatic speedup of the procedure;decryst also employs an incremental algorithm for the generation of EPCs,allowing for real-time filtering during the generation procedure in the future.In order to accommodate for contemporary developments in scientific computing,the author designed decryst with parallel and distributed computing in mind,allowing for further enhancement of the performance by simultaneous use of multiple processors.Noticing that EPCs are mutually independent,and that the number of EPCs is large in most useful cases,it is expected that the parallelisation of statistical analyses and GO of EPCs will offer unprecedented opportunities for determination of structures with largely unknown bonding relations.decryst is free and open source software that runs on Unix-like platforms,and can be obtained from https://gitlab.com/CasperVector/decryst;it is designed to be simple and flexible,in the hope that the underlying techniques could be adopted in more crystallographic applications.In combination with well-established automation utilities,it is easy to implement fairly complicated structure determination procedures: the heavyatom method,filtering of EPCs based on the Bragg R factor after statistical analyses and GO;filtering of EPCs that would definitely produce crystallographic models with atom bumping before actually solving the structure,real-time elimination of models with atom bumping in GO,filtering of EPCs that have atom bumping in the solutions,etc.The final parts of this dissertation discussed the design and implementation of decryst and then demonstrated its basic usage and some useful techniques,using example structures from various crystal families and of varying complexities,that are taken from the American Mineralogist Crystal Structure Database(AMCSD).