The computation of the global minimum energy conformation (GMEC) is an important and challenging topic in structure-based computational protein design. In this paper, we propose a new protein design algorithm based on the AND OR branch-and-bound (AOBB) search, which is a variant of the traditional branch-and-bound search algorithm, to solve this combinatorial optimization problem. By integrating with a powerful heuristic function, AOBB is able to fully exploit the graph structure of the underlying residue interaction network of a backbone template to significantly accelerate the design process. Tests on real protein data show that our new protein design algorithm is able to solve many prob- lems that were previously unsolvable by the traditional exact search algorithms, and for the problems that can be solved with traditional provable algorithms, our new method can provide a large speedup by several orders of magnitude while still guaranteeing to find the global minimum energy conformation (GMEC) solution.
The traditional BnB search algorithm @cite_0 usually ignores the underlying topological information of the residue interaction network constructed based on the backbone template, while AOBB is designed to exploit this property.
@cite_0
2134002980
Elastic network models have been successful in elucidating the largest scale collective motions of proteins. These models are based on a set of highly coupled springs, where only the close neighboring amino acids interact, without any residue specificity. Our objective here is to determine whether the equivalent cooperative motions can be obtained upon further coarse-graining of the protein structure along the backbone. The influenza virus hemagglutinin A (HA), composed of N = 1509 residues, is utilized for this analysis. Elastic network model calculations are performed for coarse-grained HA structures containing only N 2, N 10, N 20, and N 40 residues along the backbone. High correlations (>0.95) between residue fluctuations are obtained for the first dominant (slowest) mode of motion between the original model and the coarse-grained models. In the case of coarse-graining by a factor of 1 40, the slowest mode shape for HA is reconstructed for all residues by successively selecting different subsets of residues, shifting one residue at a time. The correlation for this reconstructed first mode shape with the original all-residue case is 0.73, while the computational time is reduced by about three orders of magnitude. The reduction in computational time will be much more significant for larger targeted structures. Thus, the dominant motions of protein structures are robust enough to be captured at extremely high levels of coarse-graining. And more importantly, the dynamics of extremely large complexes are now accessible with this new methodology.