Dynafold: A Dynamic Programming Approach to Protein Structure Calculation From Residual Dipolar Couplings

Nearly any biomolecular process of medical or biological significance involves the interactions of one or more proteins. As a result, methods for determining the three dimensional structure of proteins are of tremendous interest to researchers in a variety of fields. Presently, methods of protein structure determination are dominated by X-ray crystallography and nuclear magnetic resonance (NMR) spectroscopy. Most NMR-based methods are based on the collection of nuclear overhauser effect (NOE) data. However, the set of proteins amenable to analysis by NOE-based methods and X-ray methods does not span the entire set of protein structures found in nature. In particular, transmembrane proteins, a large and important class of proteins that mediate the flow of molecules into and out of a cell, tend not to be amenable to analysis by either NOE-based NMR techniques or X-ray crystallography. A new type of NMR restraint, residual dipolar couplings (RDCs), has shown promise as a source of data for large classes of proteins including transmembrane proteins. To date, most methods of utilizing residual dipolar couplings as structural re- straints have centered around either non-linear least squares optimization with simulated annealing or by treating the problem as a combinatorial optimization problem. The former methods are reliable as methods of refining structures that are already quite near their global optimum, but are not reliable in the general case of constructing a protein structure from RDC data alone. The combinatorial optimization techniques need to examine a search tree that is exponentially large in the length of the protein. Since searching all possible solutions in such a large search space explic- itly is impractical, these techniques generally employ heuristics to prune the search tree and find a solution in a practical (polynomial) amount of time. However, to date, none of the proposed methods have any mathematical guarantees of the optimality of the result. In this dissertation, a new approach to the problem of protein backbone structure determination from residual dipolar couplings is presented. In particular, a novel parameterization of protein backbone geometry is presented. This parameterization has mathematical properties that enable the optimization problem to be expressed recursively so that dynamic programming techniques can be used to find the optimal protein structure in a practical amount of computational time which grows linearly in the length of the protein and polynomially in the resolution of the search space