Protein flexibility predictions using graph theory

Techniques from graph theory are applied to analyze the bond networks in pr oteins and identify the flexible and rigid regions. The bond network consis ts of distance constraints defined by the covalent and hydrogen bonds and s alt bridges in the protein, identified by geometric and energetic criteria. We use an algorithm that counts the degrees of freedom within this constra int network and that identifies all the rigid and flexible substructures in the protein, including overconstrained regions (with more crosslinking bon ds than are needed to rigidify the region) and underconstrained or flexible regions, in which dihedral bond rotations can occur. The number of extra c onstraints or remaining degrees of bond-rotational freedom within a substru cture quantifies its relative rigidity/flexibility and provides a flexibili ty index for each bond in the structure. This novel computational procedure , first used in the analysis of glassy materials, is approximately a millio n times faster than molecular dynamics simulations and captures the essenti al conformational flexibility of the protein main and side-chains from anal ysis of a single, static three-dimensional structure. This approach is demo nstrated by comparison with experimental measures of flexibility for three proteins in which hinge and loop motion are essential for biological functi on: HIV protease, adenylate kinase, and dihydrofolate reductase. (C) 2001 W iley-Liss, Inc.