An Algorithmic Approach to the Identification of Rigid Domains in Proteins

Many proteins undergo conformational changes to perform their functions. A simple mechanism of conformational change in proteins is a rigid domain motion, in which two parts of a structure move rigidly with respect to each other. The identification of rigid domains is therefore useful in understanding the structure-function relationship of proteins. Many algorithms, including those in 16], 22], 13], 10], and 19], have been developed to identify rigid domains. In this paper we complement these works by proposing a mathematical definition of a rigid domain. We argue that our definition more accurately captures the intuitive notion of rigid domain in the previous work, than the quantitative definition of a rigid domain introduced by Nichols et al. 19]. Furthermore, our definition admits a practical approximation algorithm. We can prove theoretical guarantee on the quality of the output of our algorithm. We implement a randomized version of our algorithm, and demonstrate its effectiveness on several known protein complexes.