Many Needles in a Haystack: Finding the Global Optimum and Best Populations in Biomolecular Systems
Rayan, A., Glick, M., Gorelik, B., Noy, E., Brinker, G., and Goldblum, A.
Department of Medicinal Chemistry and Natural Products,
School of Pharmacy, Hebrew University of Jerusalem
A new search algorithm that finds global minima and best populations in complex combinatorial problems has been successfully applied to a few problems in biomolecular structure, such as large loop predictions and homology modeling, side chain positioning, predicting proton positions from crystallographic results and cyclic peptide conformations. It is currently applied to flexible protein-ligand docking, flexible protein-protein interactions, molecular conformations, and to various aspects of structure based drug design.
The above have been achieved by applying a general approach to searching complex surfaces of cost functions. An initial stochastic construction of a system’s configuration is followed by eliminating values that consistently contribute to maximal cost function values. Further iterations reduce the overall number of values to a point from which a full exhaustive search is performed and "best populations" may be constructed. Such populations are relevant to structure and function analysis. Comparison between stochastic and exhaustive searches prove that this new search reproduces the real populations in the problems studied. The efficiency of the algorithm encourages parallel processing for substantial increase in problem size.
We will use the "traveling salesman problem" to demonstrate how this algorithm may be applied to a well known difficult issue which has an exact cost function. Energy functions in structural biology are huge approximations and still lack the ability to "lead" to the best answers. This algorithm may however be employed also for finding improved cost functions to problems of structural biology.
References: