| Protein complexes play vital roles in the fundamental processes of life. In particular, homo-oligomers are involved in cell signaling, regulation, and transport. To make detailed studies of these symmetric proteins, they need to be discovered, and their structures need to be solved. For nuclear magnetic resonance (NMR) structure determination, a protein of interest must be first selected, then NMR data must be assigned and then applied to a structure determination method. In this thesis we present several algorithms for each of these steps (selection, assignment, and structure determination). Our particular area of focus is on the NMR structure determination of symmetric homo-oligomers because they form a large fraction of all known protein structures. We present algorithms to compute the structure of an entire symmetric homo-oligomer, given the structure of the sub-unit, and a sparse number of additional restraints, such as restraints from the nuclear Overhauser effect (NOE), along with the possible addition of residual dipolar couplings (RDCs).;Traditional methods for structure determination are typically incomplete in that they do not consider all possibilities in the configuration-space. As a result, they often have no provable guarantees for returning all valid solutions. For example, stochastic approaches (such as simulated annealing and Monte-Carlo methods) only consider those configurations which they have explicitly sampled. Because their sampling set is discrete and finite, they can fail to discover important solutions that are not in their sample set. Gridsearch approaches suffer from the same disadvantage. Local differential approaches (such as gradient-descent, molecular dynamics (MD)), may become trapped in local-minima and not consider valid solutions in other regions of the configuration space. In contrast, we present structure determination algorithms which are provably complete. By complete we mean that the algorithm returns a super-set of all possible solutions, and therefore is guaranteed never to miss any valid solutions. Our algorithm achieves completeness by using geometric bounds to consider all possibilities in the configuration space, and to provably eliminate large sections of the configuration space which cannot contain a solution. In addition, our geometric bound also allows us to remain complete, even when restraints are ambiguous with many possible interpretations. |
