Faulon J.L., Bender A. Handbook of Chemoinformatics Algorithms

Подождите немного. Документ загружается.

158 Handbook of Chemoinformatics Algorithms

false positives) [85,86], or that interact with hERG channel [87]. Structure-based

screening has been combined successfully with 3D pharmacophore searching and

3D similarity searches, to add complementary information to the searching process.

Structure-based virtual screening remains a useful tool in the arsenal for lead-drug

development.

5.2.2 DOCKING ALGORITHMS

5.2.2.1 Orientational Search: The Clique Detection Algorithm

Many docking algorithms separate between the orientational search and the confor-

mational search. The clique detection algorithm for orientational search that finds

interconnected sets between ligand sphere–sphere distances with receptor sphere–

sphere distances (Figure 5.1) is still one of the most commonly used docking

algorithms. Later versions of the algorithm use ligand atoms themselves rather than

ligand spheres for docking small molecules. Although to find the largest clique in a

graph is considered an NP complete problem, the search for all cliques of a limited

size is tractable. The original algorithm used a bipartite graph, where ligand nodes

and receptor nodes were assigned to separate graphs. However, in DOCK 4.0 [51,88]

the algorithm was changed to a single “docking” graph where each node represented a

ligand/receptor–sphere pairing. This docking graph and the exhaustive search method

were first discussed by Bron and Kerbosch [89].

The algorithm begins (see Figure 5.2 and Algorithm 5.1) with a set of T total

nodes, each representing a ligand/atom pair, where T equals the number of ligand

atoms times the number receptor spheres. It then precalculates all “edges” between

the nodes. An edge exists between two nodes if the distance between ligand atoms in

the two nodes is within a residual (distanceTol) of the distance between the receptor

spheres in the two nodes. All edges are stored in an EdgeMatrix of size T × T.Ifno

edge exists, null is put in that spot.

Two arrays then store the growing clique search, each of size N, the length of

the current clique. The first is Clique [N], containing all nodes of the current grow-

ing clique. The second is NodeSearchGraph [N][T], containing the set of all new

nodes consistent with the current clique of length M, meaning that edges exist from

clique nodes 1, ..., N to these nodes. (Up to T nodes can be stored at each N Index,

representing all nodes being allowed.)

The search begins by adding a new branch node j Node from the NodeSearchGraph

[N] list of allowable nodes, onto the current clique at Clique [N +1].The NodeSearch

Graph [N +1] is then calculated as the intersection of all remaining nodes kNode

from NodeSearchGraph [N] and all nodes with an edge to j Node, by testing all k

Nodes for an edge to j Node in the precalculated EdgeMatrix. If an edge exists, k Node

is added to NodeSearchGraph [N +1]. When a clique is complete, either because no

more nodes can be found or it reaches NODESMAX size, pop_node() removes the

Nth node in the clique and the next node is tried in that position. If none is found,

pop_node() removes the N−1 node. Backtracking can continue back to position 0,

until all nodes have exhaustively been searched. In practice MAXCLIQUES is used

to limit the total number of cliques found.

Ligand- and Structure-Based Virtual Screening 159

(a)

(b)

FIGURE 5.2 Clique detection algorithm. (a) Set of nodes (receptor/ligand pairs) and edges

connecting nodes. (b) Exhaustive search for cliques. Initial growing clique (C

) is NULL

and node search graph (G

) is the set of all nodes. The next node N

from G

is added to

n+1

. G

n+1

is recalculated as all nodes in G

with an edge to N

The procedure is repeated

until ≥ MAXNODES or no further expansion is possible. Additional cliques are searched by

backtracking and testing next node N

in G

ALGORITHM 5.1 PSEUDOCODE FOR EXHAUSTIVE SEARCH FOR

CLIQUES OF GIVEN SIZE RANGE (NONRECURSIVE)

C=Clique

N=number of nodes in current clique C ==

size(clique)

NODESMIN,NODESMAX: minimum/maximum allowed

nodes in a clique

S=NodeSearchGraph[NODESMAX][T]: list of

allowed nodes

PreCompute EdgeMatrix[T x T} for all Nodes, such that

EdgeMatrix[iNode][jNode]=edge if jedge exists within

distanceTol,

or 0 if it does not exist;

getNextClique(clique){

#remove last node to start new clique

IF (size(clique)>0)THEN

pop_node(clique)

END IF

160 Handbook of Chemoinformatics Algorithms

Boolean validClique=false;

WHILE (not ValidClique) THEN

#Expand clique until no further expansion

possible

#(i.e.clique size is >= NODESMAX or no more

expansion nodes

Expand (clique)

IF (expand(clique) == TRUE) THEN

CONTINUE;

END IF

IF (size (clique) >= NODESMIN)

validClique=TRUE;

ELSE

#remove last node and try again

pop_node(clique)

END ELSE

END WHILE

RETURN clique.

}

Expand (clique){

N=size(clique)

#termination 1: test if clique already fully

expanded

IF (N>NODESMAX) THEN

return FALSE;

ENDIF

#termination 2: test if have explored all possible

nodes at #position N+1

IF ((jNode=next node in NodeSearchGraph[N] array )

==0) THEN

return FALSE;

END IF

#jNode=new node to add to clique at position N+1

#kNode=remaining node consistent with current

clique

#jEdge=edge between jNode and kNode

Add jNode to clique

#Calculate set of edges consistent with jNode and

rest of clique.

FOREACH kNode (loop through NodeSearchGraph[N]) DO

jEdge=EdgeMatrix[jNode][kNode];

IF (jEdge != 0) THEN

Add kNode to NodeSearchGraphIndex[N+1] array

END IF

Ligand- and Structure-Based Virtual Screening 161

END DO

RETURN TRUE

}

This algorithm was first implemented in UCSF DOCK4 [51], and is

included in the latest version of UCSF DOCK6 [70,90]. UCSF DOCK at

http://dock.compbio.ucsf.edu/DOCK_6/index.htm is freely available to academics,

but a license fee is charged for commercial users.A similar algorithm is implemented

in FLOG [55], using a minimal-residual heuristic to limit the search, where only

the node with the minimal residual is expanded at each branch point, rather than

all remaining exceed the number of nodes. FLOG is an in-house software package

at Merck, in current use. The primary advantage of this clique detection approach

is a more efficient sampling of relevant orientational space compared to random

rotation/translation. In fact, despite the overhead of identifying cliques and then trans-

forming the ligand coordinates, it has been shown to have a speed-up between 10-

and 100-fold compared to uniform random translation [91]. The memory cost for the

docking-graph algorithm is not large and limited to the precomputed EdgeMatrix,

which grows as the square of (ligand atoms × receptor spheres). The search time for

this algorithm grows as a function of the number of distance-constrained solutions

rather than all possible unconstrained solutions, because the search does not explore

invalid branches.

5.2.2.2 Conformational Search: Incremental Buildup

Programs that use a rigid orientational search algorithm can then either start with a

database of precomputed conformations of ligands, using a program such as Omega

[92], or perform orientational search on a rigid unit of a small molecule, and fol-

low it with a buildup procedure. Algorithm 5.2 outlined below is a common buildup

procedure, used in UCSF DOCK [51]. A similar procedure is used in FlexX [52],

commercially available at http://www.biosolveit.de/flexx/. As the scoring and opti-

mization steps are the primary time-consumingsteps in the algorithm, thetime demand

for this algorithm can be approximated by the number of function evaluations, which

becomes [51]

Time = C

×N

where C

and C

are constants, N

is the number of anchor orientations searched, N

is the average number of pruned configurations saved each round, N

is the number

of rotatable bonds, and N

is the average number of torsions per bond.

ALGORITHM 5.2 PSEUDOCODE FOR CONFORMATIONAL SEARCH

USING INCREMENTAL BUILDUP

Identify flexible units in ligand

Start with largest rigid unit

Order flexible groups in layers starting from rigid unit

Orient rigid unit using orientational search

162 Handbook of Chemoinformatics Algorithms

Loop over flexible layers

Add next layer

Search torsions for each flexible group in layer

Prune by score

End loop

Minimize and score final structure

5.2.2.3 Combined Orientational and Conformational Search:

Lamarckian Genetic Algorithm

Simulated annealing, Monte Carlo, and evolutionary algorithms have all been applied

to docking programs to combine orientational and conformational search steps.

Although initially these stochastic approaches were prohibitively slow and were used

primarily to study a known ligand/receptor interaction in detail, owing to increases

in computer power it is now possible to use these approaches for virtual screening

as well. One algorithm in common use is the Lamarckian Genetic Algorithm (LGA)

[42,93,94].

The LGA combines the global search properties of a genetic algorithm (GA) with

a local search. The LGA is structured in the same way as the normal GA algorithm: a

chromosome is created representing the orientation/conformation of the ligand with

respect to the target receptor. The chromosome is shown in Figure 5.3 and consists

of a number of variables for ligand translation/rotation that is the same for all ligands

and a number of variables for ligand flexibility that is specific to each ligand. The sum

of the chromosome represents the genotype of a ligand. The phenotype of a ligand

is its 3D coordinates after applying all the transformations in the genotype. Ligand

fitness can be calculated from its phenotype using any of the standard docking scoring

functions.

The standard GA starts with a random population of size N, and runs through

a set number of generations. Each generation runs through the following steps: (1)

mapping genotype to phenotype for each member of the population; (2) fitness of

each member; (3) selection of members for use in breeding the next population; (4)

breeding: consisting of mutation and crossover; and (5) elitist selection (optional).

The new addition for the LGA (described in Algorithm 5.3) is to add a local search

function, performed at the end of each generation, on a set percentage of the (new)

population. The local search algorithm can be any local optimization technique, such

as Pattern search [95,96], or Solis–Wets [97]. The local search may be performed on

the phenotype and transformed back onto the genotype, or performed directly on the

genotype. As long as the local search results are passed onto the final genotypes it is

...

FIGURE 5.3 Chromosome for docking genetic algorithm. The first three genes (C

–C

)

represent coordinates for ligand translation. The next four genes (Q

–Q

) are the quaternian

for ligand rotation. The last N genes (T

–T

) is the ligand torsional values, the number of

which vary per ligand. Receptor torsions can also be added to this portion.

Ligand- and Structure-Based Virtual Screening 163

considered Lamarckian [42]. In a standard GA, the crossover function provides large

search moves, while mutations generate small, refining genotypic changes. In LGA,

the local search provides the refining moves, while mutations are employed for more

exploratory moves and for its role in replacing alleles that have been lost during the

selection process. The global GA continues until one of several termination steps is

reached, either the number of the current generation exceeds the maximum number

of generations, the number of total fitness evaluations exceeds the maximum allowed

evaluations, the fitness of the worst individual is the same as average fitness in the

population (i.e., population convergence), and so on.

ALGORITHM 5.3 PSEUDOCODE FOR LGA

LGA {

Generate G=population size N of random genotypes

generation=1;

Mapping genotype G to phenotype P of population

Fitness

valuation F

(scoring) on P

#Loop over generations

WHILE (not TERMINATION) do

Process generation {

selection of G’ from G for reproduction using

weighted function based on

of each individual

=child population=crossover & mutation of G’

=Mapping genotype to phenotype of G

=Fitness evaluation on Pc

elitist selection (optional)

=local_search on (G

’=percentage of G

;

calculate F

’)

G2 (next generation)=compose(G, G

)

Generation ++

}

END WHILE

}

local_search(G) {

(optional) mapping genotype G to phenotype P

local optimization (e.g., Pattern-search or Solis-Wets)

on P to calculated

optimized P2 F

164 Handbook of Chemoinformatics Algorithms

(optional) mapping of optimized P2 to G2 return G2,

}

termination conditions:

generation>maximum generations

number of fitness evaluations>maximum number

evaluations

worst fitness is average fitness in population

The Lamarckian GA has been implemented in AutoDock [42] and is avail-

able with a GNU General Public License at http://autodock.scripps.edu/. GOLD

[45] uses a GA without the local search and is commercially available at

http://www.ccdc.cam.ac.uk/products/life_sciences/gold/. DARWIN [98], an in-house

softwarepackage at theWistarInstitute, employs a similar GA, where every phenotype

is minimized using CHARMM as part of the fitness evaluation procedure.

As the GA is a nondeterministic search strategy, the time required to reach a solu-

tion is dependent on user parameters to stop the calculation. In general, if a set

number of scoring evaluations (the slowest step in the algorithm) is taken as a stop-

ping condition, then the search speed will go roughly as the square of the size of the

ligand, since the intramolecular energy calculation for the ligand scales as O(N

while the intermolecular grid score scales as O(N). The LGA was shown to reliably

provide faster and more accurate solutions than simulated annealing or GA alone

[42] within the context of the AutoDock program and scoring function. In comparing

GAs to incremental construction, in practice the GAs take more time to run than

the incremental-construction algorithms for the range of ligands commonly used in

virtual screening, but as the number of flexible ligand bonds increases the compu-

tational time for incremental construction goes up linearly, while the GA solution

times stay constant. In terms of pose accuracy in real examples, no comprehensive

comparison has been performed between GAs and incremental construction alone,

and studies that compare various programs are confounded by other differences in

the protocols, in particular the scoring functions, making the outcomes difficult to

compare. In practice both approaches reproduce known crystal structures well.

In summary, docking has become a ubiquitous tool in virtual screening. A number

of algorithms have successfully been applied to discover novel small molecule ligands

(Table 5.1). However, there are still many active areas for development in docking

algorithms. In particular, all docking algorithms have the general limitation that they

are highly sensitiveto small changes in the 3D structure of the receptor and ligand. This

is mitigated in algorithms that incorporate a measure of ligand flexibility, and further

reduced with receptor flexibility, but further improvement is needed. In addition,

scoring functions, while useful for enriching databases, are not accurate enough to

predict individual binding affinities reliably. Even so, the current algorithms generate

enough enrichment of screening databases to be an important tool in the drug discovery

process.

Ligand- and Structure-Based Virtual Screening 165

TABLE 5.1

Commonly Used Docking Programs and Their Algorithms

Orientation Conformation Scoring Examples of Novel

Program Algorithm Algorithm Function Leads Identiﬁed

DOCK [39,51,70] Sphere matching Incremental construction, flexible

DB/multiple receptors

Force field, MM-PBSA,

MM-GBSA

20a-hydroxysteroid

dehydrogenase [99]

AutoDock [42,60] LGA Flexible ligand and receptor

sidechains

Semi-empirical force field Cdc25 phosphatase [100]

FlexX [52] Descriptor match Incremental construction/

multiple receptors

Empirical Histamine H4 receptor [101]

FRED [54] Shape matching (Gaussian) Precompute ligand

conformations (OMEGA)

Consensus Cdc25 phosphatase [102]

GLIDE [46,47,62] Descriptor match/

Monte Carlo

Induced fit w/protein

structure prediction

Semiempirical force field Liver X receptor modulators

[103]

GOLD [45] GA Ligand and receptor sidechains Empirical SARS-3CL(pro) [104]

ICM [48,105] Monte Carlo Flexible sidechains and

loops/multiple receptors

Consensus Serotonin N-acetyltransferase

[106]

QXP [49] Monte Carlo/ systematic

Flexible sidechains and loops Empirical and force field β-Catenin [107]

SLIDE [108] Descriptor matching Induced-fit ligand and receptor Empirical Brugia malayi asparaginyl-tRNA

synthetase [109]

166 Handbook of Chemoinformatics Algorithms

REFERENCES

1. Bath, P. A., Morris, C. A., and Willett, P., Effect of standardization on fragment-based

measures of structural similarity. J. Chemometr. 1993, 7, 543–550.

2. Lin, T.-H., Yu, Y.-S., and Chen, H.-J., Classification of some active compounds and

their inactive analogues using two three-dimensional molecular descriptors derived from

computation of three-dimensional convex hulls for structures theoretically generated for

them. J. Chem. Inf. Comput. Sci. 2000, 40, 1210–1211.

3. Jaccard, P., Étude comparative de la distribution florale dans une portion des Alpes et

des Jura. Bull. Soc. Vaud. Sci. Nat. 1901, 37, 547–579.

4. Tversky, A., Features of similarity. Psych. Rev. 1977, 84, 327–352.

5. Shemetulskis, N. E.,Weininger,D., Blankley, C. J.,Yang, J. J., and Humblet, C., Stigmata:

An algorithm to determine structural commonalities in diverse datasets. J. Chem. Inf.

Comput. Sci. 1996, 36, 862–871.

6. Clark, R. D., Fox, P. C., andAbrahamian, E., Using pharmacophore multiplet fingerprints

for virtual HTS. In: J.Alvarezand B. Shoichet (Eds),Virtual Screening in Drug Discovery,

pp. 207–225. CRC Press, Taylor & Francis: Boca Raton, FL, 2005.

7. Nicholls, A., MacCuish, N. E., and MacCuish, J. D., Variable selection and model val-

idation of 2D and 2D molecular descriptors. J. Comput. Aided Mol. Des. 2004, 18,

451–474.

8. Abrahamian, E., Fox, P. C., Nærum, L., Christensen, I. T., Thøgersen, H., and Clark,

R. D., Efficient generation, storage and manipulation of fully flexible pharmacophore

multiplets and their use in 3-D similarity searching. J. Chem. Inf. Comput. Sci. 2003, 43,

458–468.

9. Cheng, C., Maggiora, G., Lajiness, M., and Johnson, M., Four association coeffi-

cients for relating molecular similarity measures. J. Chem. Inf. Comput. Sci. 1996, 36,

909–915.

10. Shemetulskis, N. E., Dunbar, J. B., Jr., Dunbar, B. W., Moreland, D.W., and Humblet,

C., Enhancing the diversity of a corporate database using chemical database clustering

and analysis. J. Comput. Aided Mol. Des. 1995, 9, 407–416.

11. Pearlman, R. S. and Smith, K. M., Metric validation and the receptor-relevant subspace

concept. J. Chem. Inf. Comput. Sci. 1999, 39, 28–35.

12. Lipinski, C. A., Lombardo, F., Dominy, B. W., and Feeney, P. J., Experimental and

computational approaches to estimate solubility and permeability in drug discovery and

development settings. Adv. Drug Deliv. Rev. 2001, 46, 3–26.

13. Ginn, C. M., Turner, D. B., and Willett, P., Similarity searching in files of three-

dimensional chemical structures: Evaluation of the EVA descriptor and combination

of rankings using data fusion. J. Chem. Inf. Comput. Sci. 1997, 37, 23–37.

14. Willett, P. and Winterman, V., A Comparison of some measures of inter-molecular

structural similarity. Quant. Struct. Act. Relat. 1986, 5, 18–25.

15. Nettles, J. H., Jemkins, J. L., Bender,A., Deng, Z., Davies, J. W., and Glick, M., Bridging

chemical and biological space: “Target Fishing” using 2D and 3D molecular descriptors.

J. Med. Chem. 2006, 49, 6802–6810.

16. Hahn, M., Three-dimensional shape-based searching of conformationally flexible

molecules. J. Chem. Inf. Comput. Sci. 1997, 37, 80–86.

17. Putta, S., Eksterowicz, J., Lemmen, C., and Stanton, R., A novel subshape molecular

descriptor. J. Chem. Inf. Comput. Sci. 2003,

43,

1623–1635.

18.

Haigh, J. A., Pickup, B. T., Grant, J. A., and Nicholls, A., Small molecule shape-

fingerprints. J. Chem. Inf. Model 2005, 45, 673–684.

Ligand- and Structure-Based Virtual Screening 167

19. Hull, R. D., Fluder, E. M., Singh, S. B., Nachbar, R. B., Kearsley, S. K., and Sheridan,

R. B., Chemical similarity searches using latent variable semantic structural indexing

(LaSSI) and comparison to TOPOSIM. J. Med. Chem. 2001, 44, 1185–1191.

20. McGaughey, G. B., Sheridan, R. P., Bayly, C. I., Culberson, J. C., Kreatsoulas, C., Linds-

ley, S., Maiorov,V., Truchon, J.-F., and Cornell, W. D., Comparison of topological, shape,

and docking methods in virtual screening. J. Chem. Inf. Model 2007, 47, 1504–1519.

21. Ewing, T., Baber, J. C., and Feher, M., Novel 2D fingerprints for ligand-based virtual

screening. J. Chem. Inf. Model 2006, 46, 2423–2431.

22. Carbó, R., Leyda, L., and Arnau, M., How similar is a molecule to another? An electron

density measure of similarity between two molecular structures. Int. J. Quantum Chem.

1980, 17, 1185–1189.

23. Hodgkin, E. E. and Richards, W. G., Molecular similarity based on electrostatic potential

and electric field. Int. J. Quantum Chem. 1987, 14, 105–110.

24. Good, A. C., Hodgkin, E. E., and Richards, W. G., Utilization of Gaussian functions

for the rapid evaluation of molecular similarity. J. Chem. Inf. Comput. Sci. 1992, 32,

188–191.

25. Grant, J.A., Haigh, J. A., Pickup, B. T., Nicholls, A., and Sayle, R. A., Lingos, finite state

machines, and fast similarity searching. J. Chem. Inf. Model. 2006, 46, 1912–1918.

26. Gower, J. C., Measures of similarity, dissimilarity and distance. In: S. Kotz and N. L.

Johnson (Eds), Encyclopedia of Statistical Sciences, Vol. 5, pp. 397–405. Wiley, New

York, 1985.

27. Willett, P., Barnard, J. M., and Downs, G. M., Chemical similarity searching. J. Chem.

Inf. Comput. Sci. 1998, 38, 983–996.

28. Flower, D. R., On the properties of bit string-based measures of chemical similarity.

J. Chem. Inf. Comput. Sci. 1998, 38, 379–386.

29. Dixon, S. L. and Koehler, R. T., The hidden component of size in two-dimensional

fragment descriptors: Side effects on sampling in bioactive libraries. J. Med. Chem.

1999, 42, 2887–2900.

30. Patterson, D. E., Cramer, R. D., Ferguson, A. M., Clark, R. D., and Weinberger, L.

E., Neighborhood behavior: A useful concept for validation of molecular diversity

descriptors. J. Med. Chem. 1996, 39, 3049–3059.

31. Clark, R. D., Brusati, M., Jilek, R., Heritage, T., and Cramer, R. D., Validat-

ing novel QSAR descriptors for use in diversity analysis. In: K. Gundertofte and

F. S. Jørgensen (Eds), Molecular Modeling and Prediction of Bioactivity, pp. 95–100.

Kluwer Academic/Plenum Publishers, New York, 2000.

32. Salim, N., Holliday, J., and Willett, P., Combination of fingerprint similarity coefficients

using data fusion. J. Chem. Inf. Comput. Sci. 2003, 43, 435–442.

33. Willett, P., Enhancing the effectiveness of ligand-based virtual screening using data

fusion. QSAR Comb. Sci. 2006, 25, 1143–1152.

34. Klon, A. E., Glick, M., and Davies, J. W., Combination of Naïve Bayesian classifier with

consensus scoring improves enrichment of high-throughput docking results. J. Med.

Chem. 2004, 47, 4356–4359.

35. Hert, J., Willett, P., and Wilton, D. J., comparison of fingerprint-based methods for virtual

screening using multiple bioactive reference structures.

J. Chem. Inf. Comput. Sci. 2004,

44,

1177–1185.

36.

Hert, J., Willett, P., Wilton, D. J., Acklin, P., Azzaoui, K., Jacoby, E., and

Schuffenhauer, A., Comparison of topological descriptors for similarity-based virtual

screening using multiple bioactive reference structures. Org. Biomol. Chem. 2004, 2,

3256–3266.