Efficient unbound docking of rigid molecules

EfficientUnboundDockingofRigidMoleculesDinaDuhovny,RuthNussinov,andHaimJ.WolfsonSchoolofComputerScience,TelAvivUniversity,TelAviv69978,Israel,duhovka,[e-mail],SacklerFacultyofMedicine,TelAvivUniversity.IRSP-SAIC,Lab.ofExperimentalandComputationalBiology,NCI-FCRDC,Bldg469,Rm151,Frederick,MD21702,[e-mail]runbound(reallife)dockingofmolecules,whetherprotein–proteinorprotein–drug.Thealgorithmcarriesoutrigiddock-ing,withsurfacevariability/flexibilityimplicitlyaddressedthroughliberalinter-molecularpenetration.Thehighefficiencyofthealgorithmistheoutcomeofseveralfactors:()focusinginitialmolecularsurfacefittingonlocalized,curva-turebasedsurfacepatches;()useofGeometricHashingandPoseClusteringforinitialtransformationdetection;()accuratecomputationofshapecomplemen-tarityutilizingtheDistanceTransform;()efficientstericclashdetectionandgeometricfitscoringbasedonamulti-resolutionshaperepresentation;and()utilizationofbiologicalinformationbyfocusingonhotspotrichsurfacepatches.Thealgorithmhasbeenimplementedandappliedtoalargenumberofcases.1IntroductionReceptor-ligandinteractionsplayamajorroleinallbiologicalprocesses.Knowledgeofthemolecularassociationsaidsinunderstandingavarietyofpathwaystakingplaceinthelivingcell.Dockingisalsoanimportanttoolincomputerassisteddrugdesign.Anewdrugshouldfittheactivesiteofaspecificreceptor.Althoughelectrostatic,hydrophobicandvanderWaalsinteractionsaffectgreatlythebindingaffinityofthemolecules,shapecomplementarityisanecessarycondition.Thedockingproblemisconsidereddifficultandinterestingforanumberofreasons.Thecombinatorialcom-plexityofthepossiblewaystofitthesurfacesisextremelyhigh.Thestructuresofthemoleculesarenotexact,containingexperimentalerrors.Inaddition,moleculesusuallyundergoconformationalchangesuponassociation,knownasinducedfit.Dockingal-gorithmsmustbetoleranttothosedifficulties,makingthedockingtaskoneofthemostchallengingproblemsinstructuralbioinformatics.Therearetwoinstancesinthedockingtask-’bound’and’unbound’.Inthe’bound’casewearegiventheco-crystallizedcomplexoftwomolecules.Weseparatethemarti-ficiallyandthegoalistoreconstructtheoriginalcomplex.NoconformationalchangesTowhomcorrespondenceshouldbeaddressedThepublisherorrecipientacknowledgesrightoftheU.S.Governmenttoretainanonexclusive,royalty-freelicenseinandtoanycopyrightcoveringthearticle.2areinvolved.Successfulapplicationofanalgorithmto’bound’dockingcasesisneces-sarytotestitsvalidity,yetitdoesnotensuresuccessinthereal-life’unbound’dockingprediction,wherewearegiventwomoleculesintheirnativeconformations.Inthiscasethedockingalgorithmshouldconsiderpossibleconformationalchangesuponassocia-tion.Mostofthedockingalgorithmsencounterdifficultieswiththiscase,sinceshapecomplementarityisaffected[14].Thegoalofdockingalgorithmsistodetectatransformationofoneofthemoleculeswhichbringsittooptimalfitwiththeothermoleculewithoutcausingstericclash.Nat-urally,optimalityheredependsnotonlyongeometricfit,butalsoonbiologicalcriteriarepresentingtheresultingcomplexstability.Moleculardockingalgorithmsmaybeclas-sifiedintotwobroadcategories:()bruteforceenumerationofthetransformationspace;()localshapefeaturematching.Bruteforcealgorithmssearchtheentire6-dimensionaltransformationspaceoftheligand.Mostofthesemethods[33,30,31,32,11,2,3]usebruteforcesearchforthe3rotationalparametersandtheFFT(FastFourierTransform,[19])forfastenumerationofthetranslations.TherunningtimesofthosealgorithmsmayreachdaysofCPUtime.Anotherbruteforcealgorithmisthe’softdocking’method[17]thatmatchessurfacecubes.Therearealsonon-deterministicmethodsthatusegeneticalgorithms[18,12].LocalshapefeaturematchingalgorithmshavebeenpioneeredbyKuntz[20].In1986Connolly[6]describedamethodtomatchlocalcurvaturemaximaandminimapoints.Thistechniquewasimprovedfurtherin[23,24]andwasalsoappliedtounbounddocking[25].Additionalalgorithmsthatemployshapecomplementarityconstraints,whensearchingforthecorrectassociationofmoleculeswerealsodeveloped[21,13,10].Somealgorithmsaredesignedtohandleflexiblemolecules[28,27,9].Ourmethodisbasedonlocalshapefeaturematching.Toreducecomplexitywe,first,trytodetectthosemolecularsurfaceareaswhichhaveahighprobabilitytobelongtothebindingsite.Thisreducesthenumberofpotentialdockingsolutions,whilestillretainingthecorrectconformation.Thealgorithmcantreatreceptorsandligandsofvariablesizes.Itsucceedsindockingoflargeproteins(antibodywithantigen)andsmalldrugmolecules.Therunningtimesofthealgorithmareoftheorderofsecondsforsmalldrugmoleculesandseveralminutesforlargeproteins.Inaddition,weimprovetheshapecomplementaritymeasure,makingthefunctionmorepreciseandreducingthecomplexityofitscomputation.2MethodsOurdockingalgorithmisinspiredbyobjectrecognitionandimagesegmentationtech-niquesusedincomputervision.Wecancomparedockingtoassemblingajigsawpuz-zle.Whensolvingthepuzzlewetrytomatchtwopiecesbypickingonepieceandsearchingforthecomplementaryone.Weconcentrateonthepatternsthatareuniqueforthepuzzleelementandlookforthematchi