# Presentation: 090109

## Evolutionary Hybrids for Flexible Ligand Docking(Electronic Notes)

- William E. Hart
- Optimization/Uncertainty Estimation Dept
- Sandia National Laboratories
- wehart@sandia.gov
- www.cs.sandia.gov/~wehart
- In Collaboration with
- Chris Rosin (TSRI), Richard K. Belew (UCSD)
- Garrett Morris (TSRI)

## Overview

- 1. Evolutionary algorithms (EAs)
- 2. EA Hybrids
- Design
- Motivation
- Dynamics
- Applications
- 3. Drug Docking with AutoDock
- Problem formulation
- Empirical evaluation of EA hybrids

- Electronic Notes: Flexible Ligand Docking

## Evolutionary Algorithms			          Overview

- Idea: a multi-point search strategy inspired from natural evolutionary processes
- Motivation:
- Selection of better individuals			(Darwin)
- Generation of variants from selected individuals	(Mendel)
- Analogous Search Mechanisms:
- Stochastic competitive selection
- Selective recombination (a.k.a. crossover)
- Evolutionary Algorithms: genetic algorithms, genetic programming, evolutionary programming, evolutionary strategies

- Electronic Notes: Flexible Ligand Docking

## Evolutionary Algorithms				  Search

- Methods for generating variants
- Mutation 	- generate a simple change
- Recombination	- combine two or more search points (a.k.a. parents)
- Example: searching
-                 _Mutation__	__	__	_  _Recombination_

- Electronic Notes: Flexible Ligand Docking

## 

(1)  Stochastic competition
(2)  Generate new variants
(3)  Replacement competition

- (1)  Stochastic competition
- (2)  Generate new variants
- (3)  Replacement competition

**Evolutionary Algorithms****	****	****	****        Main Loop**

- Electronic Notes: Flexible Ligand Docking

## Local Search

- Idea: iterative examine solutions in a local neighborhood and select one that has a lower value.
- Examples of local neighborhoods:
- An ε-close ball (in      )
- Adjacent nodes in a graph

- Electronic Notes: Flexible Ligand Docking

## EA Hybrids with Local Search		        Motivation

- Idea: utilize local search to refine solutions in each iteration of the EA.
- Biological Motivation
- Organisms utilize phenotypic adaptations (e.g. learning) to adapt to their environment
- Evolution modifies an individual’s genotype across generations
- Phenotypic adaptations smooth the evolutionary landscape
- Mathematical Motivation
- Local search quickly refines solutions
- Global search ensures that all areas of the search domain are adequately explored
- Most effective global search methods combine global and local search

- Electronic Notes: Flexible Ligand Docking

## EA Hybrids						   Model

- Local search can distinguish between a genotypic and phenotypic search space through a developmental map                    .

- Electronic Notes: Flexible Ligand Docking

## EA Hybrids					 Model (cont’d)

- Lamarckian Local Search
- modifies the fitness value and solution parameters
- is typical used for optimization
- NonLamarckian Local Search
- modifies only the fitness value
- can be useful when the EA’s selection pressure is “too strong”
- can be viewed as a “repair mechanism for constrained problems

- Electronic Notes: Flexible Ligand Docking

## EA Hybrids						   Design

- Perform local search?
- Repeat
- 	Perform competitive selection to select
- 	Apply evolutionary operators (mutation, recombination)
- 	Apply local search (A)
- 	Replace previous population of points
- 	Apply local search (B)
- Until stopping rule satisfied

**EA Hybrids****	****	****	****	****	****	****   Design**

- Pseudo Code

- Electronic Notes: Flexible Ligand Docking

## EA Hybrids					Design (cont’d)

- Design Issues
- Duration of local search
- Type of local search (robustness!)
- How local search is initialized
- What points are refined with local search
- Lamarckian or nonLamarckian local search
- Hybrid designs:memetic algorithms			genetic local searchparallel genetic algorithms		genetic hillclimbingLamarckian genetic algorithms		EA-LS hybrids

- Electronic Notes: Flexible Ligand Docking

## Hybrid Dynamics		           Fitness Transformation

- Local search can play a variety of roles in EAs (Hart et al, 94)
- I. Fitness transformation: nonLamarckian EA hybrids
- f(x) Func
- g(x) Transformed func

- Electronic Notes: Flexible Ligand Docking

## Hybrid Dynamics		 	  Refinement Operator

- II. Refinement operator: Lamarckian EA hybrids
- Extreme Case
- all solutions are mapped to their respective local minima
- recombination and mutation define transition between local minima
- Example: genetic local search

- Electronic Notes: Flexible Ligand Docking

## Hybrid Dynamics			          Repair Operator

- III. Repair operator: nonLamarckian EAs with a genotype-phenotype distinction
- Example: evolving grammars (Kammeyer and Belew, 97)

- Electronic Notes: Flexible Ligand Docking

## Applications of EA Hybrids

- Thin Film Metrology (Land et al, 97)
- Flowshop Scheduling (Ishibuchi et al, 97)
- Drug Docking (Rosin et al, 97; Morris et al, 98; Hart et al, 99)
- Reliable Communication Networks (Dengiz et al, 97)
- QAP (Mühlenbein, 91)
- Neural Network (Belew et al, 91; Keesing and Stork, 91; Gruau and Whitley, 93)
- [ See also www.ing.unlp.edu.ar/cetad/mos/memetic_home.html ]

- Electronic Notes: Flexible Ligand Docking

## Flexible Drug Docking			        Motivation

- Goal: develop docking tools for structure-based drug discovery
- AutoDock Method
- Flexible ligand
- Rigid receptor
- Conformational search used to find good docking configurations

- Electronic Notes: Flexible Ligand Docking

## The AutoDock Potential Energy Model

- Energy Potential:
- Long-range electrostatic forces
- Short-range weak van der Waals attractive forces
- Hydrogen bonds (12-10 LJ potential)
- Unfavorable conformational entropy
- Desolvation measure (Stouten et al ‘93)

- Electronic Notes: Flexible Ligand Docking

## Computing Potential Energies

- Ligand-protein pairwise interaction energies are precalculated
- Grid-based method rapidly computes interpolated energies

- Electronic Notes: Flexible Ligand Docking

## Docking Formulation

**Docking Formulation**

- Search Dimensions
- Cartesian Coordinates (3 dimensions)
- Quarternion (unit vector plus rotation angle)
- Torsion angles

- Electronic Notes: Flexible Ligand Docking

## Docking Formulation					 (cont’d)

- Optimization Formulation
- Unconstrained variables
- Quadratic penalty for coordinate bound constraints
- Quarternion vector renormalized
- Note: this objective is nondifferentiable

- Electronic Notes: Flexible Ligand Docking

## Optimization Methods

- Simulated annealing
- Steepest descent that accepts inferior points with probability
-             ,
-    where       is the difference in energy and    is a “temperature” constant
- Good for “walking through” shallow local minima
- Evolutionary algorithms
- Evolutionary programs
- Evolutionary pattern search
- EA hybrids

- Electronic Notes: Flexible Ligand Docking

## Evolutionary Programming			

- Evolutionary operator: mutation
- Idea: add a scaled random variable to each dimension
- Normal:
- Cauchy:
- Self-adaptation
- Mutation scale adapted (co-evolved) with the search parameters
- Idea: multiply scale by a random variable
- Gaussian:
- Lognormal:

- Electronic Notes: Flexible Ligand Docking

## Evolutionary Pattern Search

- An adaptive EA
- Evolutionary operators: coordinate-wise crossover and mutation
- Uses a global mutation step scale parameter
- For all individuals
- For all dimensions
- Uses a fixed pattern of mutation offsets

- Electronic Notes: Flexible Ligand Docking

## EA Hybrids for Docking

- Experimental options
- Cauchy mutation and coordinate-wise crossover
- Infrequent local search
- Local search
- Solis-Wets
- Pattern Search
- Fixed local search duration
- 300 function evaluations
- 3000 function evaluations
- Step-length initialization
- Fixed
- Adaptive

- Electronic Notes: Flexible Ligand Docking

## Solis-Wets Local Search

- Electronic Notes: Flexible Ligand Docking

## Solis-Wets Local Search				 (cont’d)

- Properties
- Cheap local search (especially in high dimensions)
- Can rapidly adjust the step length parameter
- Convergence properties unclear
- Does not have robust stopping rules

- Electronic Notes: Flexible Ligand Docking

## Pattern Search Local Search

- Electronic Notes: Flexible Ligand Docking

## Pattern Search Local Search				 (cont’d)

- Properties:
- More expensive search (especially in high dimensions)
- Slowly adjust the step length parameter
- Can guarantee that                                                 on c.d.f.’s
- Reasonable stopping rules exist

- Electronic Notes: Flexible Ligand Docking

## Experiments

- Six Docking Test Problems

- Electronic Notes: Flexible Ligand Docking

## Relative Performance

- Note:
- All EAs were terminated after 1.5M function evaluations
- The EPSAs were also terminated with a step-size criterion
- Hart, 99; Hart, Rosin, Belew and Morris, 99

- Electronic Notes: Flexible Ligand Docking

## Relative Performance				(cont’d)

- EA hybrids
- Better mean energy than previous methods
- New best energies for 5 of the 6 test problems
- Lower mean rmsd than previous methods (less than one!)
- Local search evaluation
- Pattern search more consistent than Solis-Wets
- Long searches particularly important for pattern search
- Initial step length of local search not a significant factor

- Electronic Notes: Flexible Ligand Docking

## Length of Optimization

- Question: Are 1.5M function evaluations really needed?
- Stall Statistic:  The last iteration where an improvement of more than 0.0001 was found
- Results
- 2cpp,3ptb: 		Terminate within 400,000 function evaluations
- 1hvr,1stp,2mcp,4hmg: 	Require at least 1M function evaluations
- Note: preliminary experiments suggest that a multistart method could be more efficient

- Electronic Notes: Flexible Ligand Docking

## Future Work

- Reconsider problem formulation
- Used constrained optimizers
- Periodic boundary constraints
- Work around singularities in problem representation         (Quarternions)
- Rescale search w.r.t. torsion angles 	        (scalability of method?)
- Exploit local smoothness
- More rapid convergence
- Guarantee convergence to a local optimum

- Electronic Notes: Flexible Ligand Docking

## Acknowledgements

- Evolutionary Programming
- Kumar Chellapilla (UCSD)
- Evolutionary Pattern Search
- Keith Hunter (Sandia)
- AutoDock
- Art Olson (TSRI)
- Garret Morris (TSRI)
- EA Hybrids
- Rik Belew (UCSD)
- Chris Rosin (TSRI)
- Natalio Krasnogor (UW England)

- Electronic Notes: Flexible Ligand Docking