Prediction of Protein Rigid Domains and Hinge Residues Based on Graph Theory and Elastic Network Model

Many proteins undergo large-scale motions where relatively rigid domains move against each other. The prediction of rigid domains, as well as the hinge residues important for their relative movements, is important for various applications. We developed a novel method for protein rigid domain identification, DAGR (Domain Analysis base on GRaph theory), based on an exhaustive enumeration of maximal rigid domains, the rigid domains not fully contained within other domains. The computation is performed by mapping the problem to that of finding maximal cliques in a graph. A minimal set of rigid domains are then selected, which cover most of the protein with minimal overlap. Combining DAGR with elastic network model, we construct a method for predicting the rigid domains and the hinge regions of a protein.