A graph theoretical approach for analysis of protein flexibility change at protein complex formation.

Hitherto analyses of protein complexes are frequently confined to the changes in the interface of the protein subunits undergoing interaction, while the holistic picture of the protein monomers' structure transformation, or the pervasive rigidity adopted by the newly formed complex are most often than not improperly evaluated in spite of the multiple and deep insights that they can yield about the interaction process itself at the molecular level, or at the higher level of genomic functional analyses for which relevant systems biological information can be obtained. To address this aspect of protein-protein interaction we propose in this work a newly developed algorithm that is based on graph theoretical instances and makes possible the evaluation of the changes in the flexibility of the interacting molecules and the rigidity adopted at complex formation. Since one can also figure out the opposite process, i.e. that in which the complex decomposes into its constituent subunits, each of which may accomplish another vital role in the organism, the methodology proposed here is also able to address such problem. The algorithm we propose performs a rigidity and/or flexibility evaluation of every node (atom) on the network constituted by the entire set of intra and inter-molecular inter-atomic interactions. Comparison of flexible or rigid molecular regions or domains within the complex with those in the respective isolated monomers leads to quantification of the loss (or gain) in the number of degrees of freedom at complex formation and their effects on protein complex formation mechanisms. This index is also valuable in the identification of collective motions within the protein that may play a critical role in the process of complex formation, and the influences they may have in the behavior and function of the complex (as well as the subunits constituting it) within the organism. Furthermore, the methodology, embedded in protein docking algorithms allows the development of a framework for categorizing and ranking decoys output by broadly used grid scoring type algorithms, one of which is the system for protein-protein interaction system MIAX that has been under continuous development in recent years.