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. ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT(k), that generalizes them. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = ∞ and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < ∞. We prove that ADOPT(k) is a correct and complete algorithm and experimentally show that ADOPT(k) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics. Recently there has been a surge of interest to use branch-and-bound (bnb) optimisation for 3D point cloud registration. While bnb guarantees globally optimal solutions, it is usually too slow to be practical. A fundamental source of difficulty is the search for the rotation parameters in the 3D rigid transform. In this work, assuming that the translation parameters are known, we focus on constructing a fast rotation search algorithm. With respect to an inherently robust geometric matching criterion, we propose a novel bounding function for bnb that allows rapid evaluation. Underpinning our bounding function is the usage of stereographic projections to precompute and spatially index all possible point matches. This yields a robust and global algorithm that is significantly faster than previous methods. To conduct full 3D registration, the translation can be supplied by 3D feature matching, or by another optimisation framework that provides the translation. On various challenging point clouds, including those taken out of lab settings, our approach demonstrates superior efficiency. In a large and complex distributed sensor network, the individual sensor directly communicates only with its neighboring sensors. Despite being restricted to such local communications, the network itself should be self-organizing to maintain certain desirable properties, such as network connectivity and lifetime maximization. Topology control is a technique to determine the optimal transmit parameters for each sensor, such that the network topology has the best possible network performance. In this paper, we investigate a dynamic topology control scheme to improve the network lifetime for wireless sensor networks in the presence of selfish sensors. A non-cooperative game aided topology control approach is developed for designing energy-efficient and energy balanced network topologies dynamically. Each sensor in the topology control game tries to minimize its unwillingness for constructing a connected network according to its residual energy and transmit power. We prove the existence of Nash equilibrium (NE) and demonstrate that the NE is Pareto optimal as well. Specifically, a fully distributed algorithm-topology control with lifetime extension (TCLE)-is proposed to construct dynamic network topologies. The topologies derived by TCLE algorithm can improve the network lifetime significantly as compared with existing algorithms. Simulations demonstrate the efficiency of our TCLE algorithm.