Faster and More Accurate Estimation of Protein Hinges Based on Information Criteria

Protein hinges are flexible parts connecting several rigid substructures of proteins that are crucial to determine protein function. Various methods have been developed for efficiently and accurately estimating protein hinge positions by comparing two different conformations of the same protein for a growing number of protein structures. However, few studies have focused on accurately estimating the number of hinges, and it is required to accurately estimate both the number and positions of hinges. We propose faster and more accurate algorithms for estimating the number and positions of hinges by utilizing information criteria that run in O(n²)-time, where n is the protein length. Our algorithms utilize Bayesian Information Criterion (BIC) or Akaike's Information Criterion based on a newly proposed k-hinge structure generation model that models the hinge motions between two protein conformations. Our exact algorithm based on BIC outperformed the most accurate previous method in terms of both hinge number and position accuracy on our simulation dataset. Our exact algorithm was approximately as fast as the previous fastest method, DynDom, on our simulation dataset. We evaluated the hinge number and position accuracy of our exact algorithm and previous methods on one hinge-annotated dataset. The hinge number and position accuracy of our exact algorithm were comparable to the most accurate previous method on the hinge-annotated dataset. We further propose even faster O(n)-time heuristic algorithms, where n is the protein length. Our heuristic algorithm achieved almost the same hinge number and position accuracy as our exact algorithm, and was over 18 times faster than our exact algorithm and DynDom.