Probabilistic Algorithms for Modeling Protein Structure and Dynamics

Specifically, this thesis addresses three main problems that permeate protein modeling research. The first problem, known as "from-structure-to-function,'' asks how to infer the function of a protein from knowledge of its active structure. The second problem, known as "from-sequence-to-structure,'' relates to the open question of how to predict the biologically-active structure of a protein when provided information on the identities and order of constitutive building blocks. The third problem advances the current computational treatment of proteins to alleviate assumptions of their rigidity and instead model them as dynamic macromolecules switching between structures to tune their biological activity. The objective here is to model protein dynamics efficiently by computing the molecular motions employed in structural transitions among diverse functionally-relevant states of a protein.;The algorithmic techniques employed in this thesis span machine learning, computational geometry, and stochastic optimization. In particular, we combine computational geometry and machine learning in a novel framework to infer the function of a protein from knowledge of its structure. In our treatment of the de-novo structure prediction problem, we employ and investigate in detail an adaptive stochastic optimization framework capable of balancing between search breadth and depth in the exploration of a high-dimensional and nonlinear search space. We pursue such frameworks further and propose novel robotics-inspired probabilistic algorithms to model protein dynamics. In particular, in our treatment of structure and dynamics, we exploit analogies between protein modeling and the motion planning problem in robotics, which allow us to employ relevant concepts from motion planning algorithms and propose powerful algorithms capable of handling highly-constrained articulated systems with hundreds or thousands of continuous and discrete variables.;This thesis advances protein modeling research by extending the size and complexity of systems that can be modeled, as well as the detail and accuracy with which relevant biological questions can be answered. For instance, algorithms proposed here to model structural transitions are now able to explain the impact of sequence mutations on protein function. Just as important, the algorithmic techniques proposed in this thesis are of general utility to other domains in computer science focusing on extending optimization algorithms for vast and nonlinear search spaces of complex systems.