WIXLIB

Docking ProblemGiven 2 input molecules in theirnative conformation, the goal is tofind their correct association as itappears in nature.T H.J. Wolfson - StructuralBioinformatics?

Docking Problem: H.J. Wolfson - StructuralBioinformatics ?

Detection of a Lead Drug Compound: The Key-in-Lock PrincipleH.J. Wolfson - StructuralBioinformatics

Docking - Motivation Computer aided drug design – a new drugshould fit the active site of a specific receptor. Understanding of the biochemical pathways many reactions in the cell occur throughinteractions between the molecules. Crystallizing large complexes and findingtheir structure is difficult.H.J. Wolfson - StructuralBioinformatics

The Docking Problem Input: A pair of molecules representedby their 3D structures. Tasks :– Decide whether the molecules will form acomplex (interact / bind).– Determine the binding affinity.– Predict the 3D structure of the complex.– Deduce function.H.J. Wolfson - StructuralBioinformatics64

Forces Governing BiomolecularRecognitionDepend on the molecules and the solvent. Van der Waals. Electrostatics. Hydrophobic contacts. Hydrogen bonds Salt bridges . etc.All interactions act at short ranges.Implies that a necessary condition for tightbinding is surface complementarity.H.J. Wolfson - StructuralBioinformatics65

Shape ComplementarityH.J. Wolfson - StructuralBioinformatics66

Necessary Condition for Docking Given two molecules find significantsurface complementarity.T H.J. Wolfson - StructuralBioinformatics67

Geometric Docking Algorithms Based on the assumption of shapecomplementarity between the participatingmolecules. Molecular surface complementarity –protein-protein, protein-drug.Remark : usually “protein” here can bereplaced by “DNA” or “RNA” as well.H.J. Wolfson - StructuralBioinformatics68

Issues to be examined whenevaluating docking methods Rigid docking vs. Flexible docking :– If the method allows flexibility: Is flexibility allowed for ligand only, receptor only or both ? Number of flexible bonds allowed and the cost of addingadditional flexibility. Does the method require prior knowledge of theactive site? Speed - ability to explore large libraries. Performance in “unbound” dockingexperiments.H.J. Wolfson - StructuralBioinformatics69

Bound Docking In the bound docking we are given a complex of 2molecules. After artificial separation the goal is to reconstruct thenative complex. No conformational changes are involved. Used as a first test of the validity of an algorithm.DockingAlgorithmH.J. Wolfson - StructuralBioinformatics70

Unbound Docking In the unbound docking we are given 2molecules in their native conformation. The goal is to find the correct association. Problems: conformational changes (side-chainand backbone movements), experimentalerrors in the structures.H.J. Wolfson - StructuralBioinformatics71

Bound vs. UnboundReceptor surface10 highly penetrating residuesLigandUnbound ligand and receptorsuperimposed on the complexH.J. Wolfson - StructuralKallikrein A/trypsin inhibitorBioinformaticscomplex (PDB codes 2KAI,6PTI)72

The PatchDock Algorithm Based on local shape feature matching. Focuses on local surface patches dividedinto three shape types: concave, convex andflat. The geometric surface complementarityscoring employs advanced data structures formolecular representation: DistanceTransform Grid and Multi-ResolutionSurface.H.J. Wolfson - StructuralBioinformatics73

Docking Algorithm Scheme Part 1: Molecular surface representation Part 2: Feature selection Part 3: Matching of critical features Part 4: Filtering and scoring of candidatetransformationsH.J. Wolfson - StructuralBioinformatics74

1. Surface Representation Dense MS surface Sparse surface(Connolly)(Lin et al.)H.J. Wolfson - StructuralBioinformatics75

1. Surface Representation Dense MS surface Sparse surface(Connolly)(Lin et al.)82,500 points4,100 pointsH.J. Wolfson - StructuralBioinformatics76

Sparse Surface Graph - Gtop Caps (yellow), pits(green), belts (red): Gtop – Surface topology graph:V surface pointsE {(u,v) u,v belong to the same atom}H.J. Wolfson - StructuralBioinformatics77

Docking Algorithm Scheme Part 1: Molecular surface representation Part 2: Feature selection Part 3: Matching of criticalfeatures2.1 Coarse curvaturecalculation2.2 Division to surfacepatches of similarcurvature Part 4: Filtering and scoring of candidatetransformationsH.J. Wolfson - StructuralBioinformatics78

2.1 Curvature Calculationknob Shape function is a measure of localcurvature.hole ‘knobs’ and ‘holes’ are local minima andmaxima ( 1/3 or 2/3), ‘flats’ – the rest ofthe points.flat Problems: sensitivity to molecularmovements, 3 sets of points withdifferent sizes.knobsflatsholes Solution: divide the values of theshape function to 3 equal sizedsets: ‘knobs’, ‘flats’ and ‘holes’.H.J. Wolfson - StructuralBioinformatics79

2.2 Patch DetectionGoal: Divide the surface into connected, nonintersecting, equal sized patches of criticalpoints with similar curvature. connected – the points of the patchcorrespond to a connected sub-graph of Gtop. similar curvature – all the points of the patchcorrespond to only one type: knobs, flats orholes. equal sized – to assure better matching wewant shape features of almost the same size.H.J. Wolfson - StructuralBioinformatics80

Patch Detection bySegmentation Technique Construct a sub-graph for each type ofpoints: knobs, holes, flats.Example: Gknob will include all surface pointsthat are knobs and an edge between two‘knobs’ if they belong to the same atom. Compute connected components of everysub-graph. Problem: the sizes of the connectedcomponents can vary. Solution: apply ‘split’ and ‘merge’ routines.H.J. Wolfson - StructuralBioinformatics81

Split and Merge Geodesic distance between two nodes is aweight of the shortest path between them insurface topology graph. The weight of eachedge is equal to the Euclidean distancebetween the corresponding surface points. Diameter of the component – is thelargest geodesic distance between the nodesof the component. Nodes s and t that givethe diameter are called diameter nodes.sH.J. Wolfson - StructuralBioinformaticst82

Split and Merge (cont.) The diameter of every connected componentis computed using the APSP (All pairsshortest paths) algorithm (O(n3)).1. low patch thr diam high patch thr validpatch split3. diam low patch thr merge2. diam high patch thrlow patch thr 10Åhigh patch thr 20ÅH.J. Wolfson - StructuralBioinformatics83

Split and Merge (cont.) Split routine: compute Voronoi cells of the diameternodes s,t. Points closer to s belong to newcomponent S, points closer to t belong to newcomponent T. The split is applied until the newcomponent has a valid diameter.Merge routine: compute the geodesic distance ofevery component point to all the patches. Merge withthe patch with closest distance.Note: the merge routine maymerge point with patch ofdifferent curvature type.H.J. Wolfson - StructuralBioinformaticsst84

Examples of Patches for trypsinand trypsin inhibitorYellow – knob patches, cyan – hole patches, green – flat patches, theproteins are in blue.H.J. Wolfson - StructuralBioinformatics85

Complementarity of the Patches:Interface holepatches of thereceptorInterface knobpatches of theligandH.J. Wolfson - StructuralBioinformatics86

Cox-2 cavity represented by asingle hole patch:Indomethacininside the COX2 hole patchIndomethacininside its knobpatchesH.J. Wolfson - StructuralBioinformatics87

Shape Representation PartH.J. Wolfson - StructuralBioinformatics88

Focusing on Active SiteThere are major differences in the interactions of different types ofmolecules (enzyme-inhibitor, antibody-antigen, protein drug).Studies have shown the presence of energetic hot spots in theactive sites of the molecules.Enzyme/inhibitor –Select patches with high enrichment of hot spot residues(Ser, Gly, Asp and His for the enzyme;Arg, Lys, Leu, Cys and Pro for the inhibitor).Antibody/antigen –1. Detect CDRs of the antibody.2. Select hot spot patches(Tyr, Asp, Asn, Glu, Ser and Trp for antibody;and Arg, Lys, Asn and Asp for antigen)Protein/drug – Select large protein cavitiesH.J. Wolfson - StructuralBioinformaticsStructural Bioinformatics 200889

Docking Algorithm Scheme Part 1: Molecular surfacerepresentation Part 2: Feature selection Part 3: Matching ofcritical features Part 4: Filtering and scoringof candidate transformationsH.J. Wolfson - StructuralBioinformatics90

3. Matching of patchesThe aim is to align knob patches with holepatches, and flat patches with any patch. Weuse two types of matching: Single Patch Matching – one patch from thereceptor is matched with one patch from theligand. Used in protein-drug cases. Patch-Pair Matching – two patches from thereceptor are matched with two patches from theligand. Used in protein-protein cases.H.J. Wolfson - StructuralBioinformaticsStructural Bioinformatics 200891

Creating Transformations in 3D Space A correspondence between a pair of 3 points isnecessary to compute a 3D transformationAb3D transformationaBCc A correspondence between a pair of 2 points isenough in case their normals are given3D TransformationH.J. Wolfson - StructuralBioinformaticsnaanbb92

Single Patch MatchingReceptor hole patchLigand knob patchTransformation Base: a pair of critical points with their normals fromone patch.Match every base from a receptor patch with all thebases from complementary ligand patches.Compute the transformation for each pair of matchedbases.H.J. Wolfson - StructuralBioinformatics93

Base CompatibilityThe signature of the baseis defined as follows:dE, dG, α, β, ω1. Euclidean and geodesic distancesbetween the points: dE, dG2. The angles α, β between the [a,b]segment and the normals3. The torsion angle ω between theplanesTwo bases are compatible if their signatures match.H.J. Wolfson - StructuralBioinformatics94

Patch Matching Preprocessing: the bases are built for allligand patches (single or pairs) and storedin hash table according to base signature. Recognition: for each receptor baseaccess the hash-table with base signature.The transformations set is computed for allcompatible bases.H.J. Wolfson - StructuralBioinformatics95

Docking Algorithm Scheme Part 1: Molecular surfacerepresentation Part 2: Feature selection Part 3: Matching of criticalfeatures Part 4: Filtering and scoringof candidate transformationsH.J. Wolfson - StructuralBioinformatics96

Distance Transform GridDense MS surface(Connolly)-10 1H.J. Wolfson - StructuralBioinformatics97

Filtering Transformations withSteric Clashes Since the transformations were computed by local shape featuresmatching they may include unacceptable steric clashes. Candidate complexes with slight penetrations are retained due tomolecular flexibility.Steric clash test:For each candidate ligand transformationtransform ligand surface pointsFor each transformed pointaccess Distance Transform Grid and check distance valueIf it is more than max penetrationDisqualify transformationH.J. Wolfson - StructuralBioinformatics98

Scoring Shape Complementarity The scoring is necessary to rank the remaining solutions. The surface of the receptor is divided into five shells according to thedistance function: S1-S5[-5.0,-3.6), [-3.6,-2.2), [-2.2, -1.0), [-1.0,1.0), [1.0 ). The number of ligand surface points inevery shell is counted. Each shell is given a weight: W1-W5-10, -6, -2, 1, 0. The geometric score is a weighted sum ofthe number of ligand surface points Ninside every shell:score N Si Wii99

Docking Algorithm Scheme Part 1: Molecularsurface Representation Part 2: FeaturesselectionThe correct solution isfound in 90% of thecases with RMSD under5A.The rank of the correctsolution can be in therange of 1 – 1000. Part 3: Matching ofcritical features Part 4: Filtering andscoring of candidateH.J. Wolfson - StructuraltransformationsBioinformaticsRefinement andRescoring minimizingan Energy Function !100

Example 1: Enzyme-inhibitor docking(unbound case)trypsininhibitor from complexdocking solutionΑ-chymotrypsin (5CHA) withEglin C (1CSE(I)). RMSD 1.46Å,rank 10H.J. Wolfson - StructuralBioinformatics101

Example 2: Antibody-antigen docking(unbound case)antibodytissue factor fromcomplexdocking solutionAntibody Fab 5G9 (1FGN)with tissue factor (1BOY).RMSD 2.27Å, rank 8H.J. Wolfson - StructuralBioinformatics102

Example 3: Protein-DNA docking(semi-unbound case)DNA strandendonucleasedocking solutionEndonuclease I-PpoI (1EVX)with DNA (1A73).RMSD 0.87Å, rank 2H.J. Wolfson - StructuralBioinformatics103

Example 4: Protein-drug docking(bound case)Estrogen receptorEstradiol fromcomplexdocking solutionEstrogen receptor withestradiol (1A52). RMSD0.9Å, rank 1, running time: 11secondsH.J. Wolfson - StructuralBioinformatics104

References (PatchDock): D. Duhovny, R. Nussinov, H.J. Wolfson, EfficientUnbound Docking of Rigid Molecules, 2’nd Workshop onAlgorithms in Bioinformatics (WABI’02 as part ofALGO’02), 2002, Lecture Notes in Computer Science2452, pp. 185-200, Springer Verlag. D. Schneidman-Duhovny, Y. Inbar, R. Nussinov and H.J. Wolfson, PatchDock and SymmDock: servers for rigidand symmetric docking, Nuc. Acids Res., 33, W363—W367, (2005). SERVER URL : http://bioinfo3d.cs.tau.ac.il/PatchDock/H.J. Wolfson - StructuralBioinformaticsStructural Bioinformatics 2008105

Bioinformatics "It has not escaped our notice that the specific pairing we . R[i,j,l] – valid pos. of c(j) given that c(i) is aligned to s(l). . programming, the rest can be solved by branch-and-bound with only several branch nodes 2. Re