Systematic Conformational Search with Constraint Satisfaction

Throughout biological, chemical, and pharmaceutical research,conformational searches are used to explore the possiblethree-dimensional configurations of molecules. This thesis describesa new systematic method for conformational search, including anapplication of the method to determining the structure of a peptidevia solid-state NMR spectroscopy. A separate portion of the thesis isabout protein-DNA binding, with a three-dimensional macromolecularstructure determined by x-ray crystallography.The search method in this thesis enumerates all conformations of amolecule (at a given level of torsion angle resolution) that satisfy aset of local geometric constraints, such as constraints derived fromNMR experiments. Systematic searches, historically used for smallmolecules, generally now use some form of divide-and-conquer forapplication to larger molecules. Our method can achieve a significantimprovement in runtime by making some major and counter-intuitivemodifications to traditional divide-and-conquer:(1) OmniMerge divides a polymer into many alternative pairs ofsubchains and searches all the pairs, instead of simply cutting inhalf and searching two subchains. Although the extra searches mayappear wasteful, the bottleneck stage of the overall search, which isto re-connect the conformations of the largest subchains, can be greatlyaccelerated by the availability of alternative pairs of sidechains.(2) Propagation of disqualified conformations acrossoverlapping subchains can disqualify infeasible conformations veryrapidly, which further offsets the cost of searching the extrasubchains of OmniMerge.(3) The search may be run in two stages, once at low-resolutionusing a side-effect of OmniMerge to determine an optimalpartitioning of the molecule into efficient subchains; then again athigh-resolution while making use of the precomputed subchains.(4) An A* function prioritizes each subchain based onestimated future search costs. Subchains with sufficiently lowpriority can be omitted from the search, which improves efficiency.A common theme of these four ideas is to make good choices about howto break the large search problem into lower-dimensional subproblems.In addition, the search method uses heuristic local searches withinthe overall systematic framework, to maintain the systematic guaranteewhile providing the empirical efficiency of stochastic search.These novel algorithms were implemented and the effectiveness of eachinnovation is demonstrated on a highly constrained peptide with 40degrees of freedom