Algorithms in rigidity theory with applications to protein flexibility and mechanical linkages

A natural question was asked by James Clark Maxwell: Can we count vertices and edges in a framework in order to make predictions about its rigidity and flexibility? The first complete combinatorial generalization for (generic) bar and joint frameworks in dimension 2 was confirmed by Laman in 1970. The 6|V| – 6 counting condition for 3-dimensional molecular structures, and a fast 'pebble game' algorithm which tracks this count in the multigraph have led to the development of the program FIRST for rapid predictions of the rigidity and flexibility of proteins.;In this thesis we develop the mathematical models, algorithms and theory using the concepts from combinatorial rigidity theory that have various important applications in protein science and mechanical engineering. Using our extensions of the pebble game algorithm, we have developed a novel protein hinge prediction algorithm. The hinge predictions are tested on numerous hinge bending proteins. We have also introduced several rigidity-based allostery models with corresponding allostery-detection algorithms that can detect transmission of rigidity (change in shape) between distant sites. Various examples and theoretical results on the rigidity-based allosteric communication will be provided. We will apply our algorithm on some allosteric proteins, including the important class of signalling proteins known as G-protein couple receptors. The results obtained show that rigidity-based modelling of allostery and our algorithms are promising tools in studying allostery in proteins. We also present a novel FIRST-ensemble method which extends FIRST to give a prediction of rigidity/flexibility of structural protein ensembles, and when combined with ensemble solvent accessibility data, it gives a good prediction of hydrogen-deuterium exchange. In the area of mechanical linkages, we have developed novel techniques and a pinned version of the pebble game algorithm that can decompose linkages into important d-Assur graphs.