Global Search Algorithms

Virtual screening applications based on superposition or docking usually contain difficult-to-solve optimization problems with a mixed combinatorial and numerical flavor. The combinatorial aspect results from discrete models of conformational flexibility and molecular interactions. The numerical aspect results from describing the relative orientation of two objects, either two superimposed molecules or a ligand with respect to a protein in docking calculations. Problems of this kind are in most cases hard to solve optimally with reasonable compute resources. Sometimes, the combinatorial and the numerical part of such a problem can be separated and independently solved. For example, several virtual screening tools enumerate the conformational space of a molecule in order to address a major combinatorial part of the problem independently (see for example [199]). Alternatively, heuristic search techniques are used to tackle the problem as a whole. Some of them will be covered in this section. 

A very small molecule is significantly simpler to align or to dock because of its limited conformational space. The molecule is either rigid or has a low number of conformations, which can be enumerated. This is not the case anymore for molecules with more than, say, five rotatable bonds. Here, the number oflow-energy conformations is typically too high to justify an enumeration. Since several algorithmic engines for 

The remaining open issue is then how to combine or extend placements for fragments to placements for the whole molecule. 

Combinatorial chemistry, developed in the mid-90s [227-229], allows the efficient synthesis of large sets of compounds with diverse features. It is therefore a widely used technology for creating screening libraries. For experimental screening, the most 

Owing to the much longer per-molecule computing time, exploiting the structure of combinatorial libraries becomes much more important for molecular docking algorithms. 

---

G. M. Crippen and H. A. Scheraga, Arch. Biochem. Biophys., 144, 453 (1971). Minimization of Polypeptide Energy. X. A Global Search Algorithm. 

Another alternative to standard iterative linearized localization methods is the probabilistic inversion approach of Tarantola and Valette [1982]. In recent years, software packages have become available that combine efficient, nonlinear, global search algorithms (e.g. NonLinLoc, Lomax et al. 2000). This method gained in importance for the precise localization of... 

D. R. Smith. The structure and design of global search algorithms. TR KES.U.87. 12, Kestrel Inst., Palo Alto, 1988. To appear in Acta Informatica. 

Marchal, R., CarbonniSre, R, 8c Rouchan, C. (2009). A global search algorithm of minima exploration for the investigation of low lying isomers of clusters from density functional theory-based potential energy surfaces the example of Si (n = 3,15) as a test case. Journal of Chemical Physics, 232(11), 114105/1-114105/9. 

In spite of the wealth of information they provide, global search algorithms ordinarily fail to identify aU the minima of a given cluster. The best explored potential surface for clusters belong to possibly the simplest empirical potential, namely, the Lennard-Jones potential. The Lennard-Jones potential is a simple model that captures the long- and short-range behavior of atoms and molecules. It was proposed in 1931 by J. E. Lennard-Jones (1931) and has been used in innumerable studies ever since. It has the following simple form... 

Outside of the domain of simple empirical potentials, identifying the global minima of cluster PESs becomes a prohibitively demanding task. Therefore, most studies on the theoretical determination of cluster minima employ methods that either focus on local minima obtained through an adequate initial guess or a mixture of global search algorithms with simple potentials to reduce the number of minima followed by local minimization techniques that are more accurate. 

---