Search Algorithms

 

Search Algorithms

In the conformational search, structural parameters of the ligands, such as torsional (dihedral), translational and rotational degrees of freedom, are incrementally modified. Conformational search algorithms perform this task by applying different methods. The identification of molecular features and modifications in compounds, in order to improve the potency are the difficult issues to understand. The docking process may be regarded as a multi-step process in which each step introduces one or more additional degrees of complication. Accurate structural modeling and correct prediction of activity are the aspirants of docking studies. The search algorithms used to predict plausible conformations of the complex are defined by a set of rules and parameters.

In terms of the flexibility of the ligand and/or the receptor, docking algorithms can be categorized in two large sets: rigid-body and flexible docking which are based on different types of algorithms.

Rigid-body docking simulation has been capable of identifying ligand binding sites for proteins which are close enough to the crystallographic structures. Root mean square deviation (RMSD) between the atomic coordinates obtained from docking simulation and crystallographic structure is used for the comparison of the structures. In docking simulations, the best results generate RMSD values below 1.5 Å.

There are also steps in algorithm which checks the steric clashes between the ligand and receptor. In the case of unacceptable orientation the ligand is reoriented within the least square fit limit until acceptable orientation is obtained. The acceptable orientation is then scored on the basis of interaction energy computation. Subsequently, new orientations are generated by matching sphere centers and ligand atoms and scored using scoring functions. Orientations are arranged on the basis of these scores for the subsequent analysis.

After initial screening of ligands through rigid-body docking, the flexible docking is utilized for a more specific refinement and lead optimization. In Flexible docking, several possible conformations of ligand or receptor, or both of the molecules is considered at the same time. Rigid-body docking considers only six degrees of freedom (translational and rotational) while flexible docking method considers conformational degrees of freedom of ligands and receptor too. Most of the methods only consider the conformational space for the ligands while the receptor is considered to be rigid.

Docking algorithms contain several common methods for searching conformational space. To treat ligand flexibility and, to some extent, protein flexibility different search algorithms are used. Ligand flexibility search methods can be divided into three basic classes: Systematic search methods, Random or Stochastic methods and Simulation methods.

 

1.    Systematic search algorithms

Systematic search algorithms approve slight variations in the structural parameters, progressively changing the conformation of the ligands. Systemic search algorithms try to explore all the degrees of freedom in a molecule which is dictated by the rotations of the bonds and angles and size of increments. Although the method is effective in exploring the conformational space, it can converge to a local minimum rather than the global minimum. This drawback can be overcome by performing simultaneous searches starting from different points of the energy landscape.

Incremental Construction, Conformational search, Database, Fast Shape Mappings, Distance Geometry are the examples of the Systematic search algorithms.

Systematic search methods can be categorized into exhaustive search algorithms and fragmentation based algorithms.

a)   Exhaustive search algorithms

Exhaustive searches explain ligand conformations by systematically rotating all possible rotatable bonds at a given interval. Large conformational space often prohibits an exhaustive systematic search. Algorithms such as GLIDE8 use heuristics to focus on regions of conformational space that are likely to contain good scoring ligand poses.

b)   Fragment based algorithms

Different Fragment based algorithms used are  Incremental Construction,  Distance Geometry  and  Fast Shape Matching algorithms.

In Incremental Construction, ligand conformations are obtained from fragments by dividing the ligand of interest. Ligand conformations are obtained by docking fragments. In Distance Geometry systematic algorithm, intra and inter molecular distances are used. FLOG utilizes distance geometry systematic algorithm. Fast Shape matching algorithms are based upon the geometrical overlap between the two molecules derived from molecular surfaces. ZDOCK  utilizes fast shape matching algorithms.

2.    Stochastic or Random search methods

Stochastic or Random search methods are based on making random changes to either a single ligand or a population of ligands which are evaluated with a predefined probability function. For this, the algorithm generates groups of molecular conformations and populates a wide range of the energy landscape. As the algorithm promotes a broad coverage of the energy landscape, the computational cost associated with this procedure is an important limitation. Genetic algorithm, Monte carlo simulation, Tabu search etc. methods are the examples of stochastic or random search methods which uses different probability criteria of acceptance.

3.    Simulation approach

The most popular simulation approach for molecular docking is the Molecular dynamics simulation which calculates the trajectory of the system by the application of Newtonian mechanics. Molecular dynamics simulation can locate ligands within local minima. The complement of other methods followed (like Simulated annealing) by molecular dynamics simulation may provide better results.