Transcript Selection Pressure

Research of Inhibitor-enzyme interaction using Autodock
Interactions between biomolecules are stereospecific
• (google docking movie autodock or go autodock
page directly)
Final Docked Energy
Energy evaluation in Autodock
ΔGsolvation
Grid Maps
Search for optimal conformations of ligands
• Translation, Torsion, Orientation
• 103x3611x363
Computational procedure of GA
1.
2.
3.
4.
Start from, say, 100 random conformations.
Calculate energies of ligand-protein complexes for 100 structures.
To generate new conformations, the ligand conformations of lower
energy are weighted more to generate new conformations.
Repeat 2-3 until the calculation converges.
(look at ‘movie’ at the autodock website!)
Subroutine of random number
generation
•
REAL FUNCTION RANF ( DUMMY )
•
•
•
•
•
•
•
•
•
•
C
C
C
C
C
C
C
C
C
C
*******************************************************************
** RETURNS A UNIFORM RANDOM VARIATE IN THE RANGE 0 TO 1.
**
**
**
***************
**
**
** WARNING **
**
**
***************
**
**
**
** GOOD RANDOM NUMBER GENERATORS ARE MACHINE SPECIFIC.
** PLEASE USE THE ONE RECOMMENDED FOR YOUR MACHINE.
*******************************************************************
•
•
INTEGER L, C, M
PARAMETER ( L = 1029, C = 221591, M = 1048576 )
•
•
•
•
INTEGER SEED
REAL
DUMMY
SAVE
SEED
DATA
SEED / 0 /
•
C
*******************************************************************
•
•
SEED = MOD ( SEED * L + C, M )
RANF = REAL ( SEED ) / M
•
•
RETURN
END
**
**
**
Lamarckian Genetic Algorithm
(LGA)
BIM3-PDK1
Testing Docking Methods
• Automated Docking Using a Lamarckian
GeneticAlgorithm and an Empirical
Binding Free Energy Function
• GARRETT M. MORRIS, DAVID S. GOODSELL,ROBERT S.
HALLIDAY, RUTH HUEY, WILLIAM E. HART,RICHARD K. BELEW,
ARTHUR J. OLSON
• Journal of Computational Chemistry,Vol. 19, No. 14, 1693-1662
(1998)
Introduction- GOLD software
• GOLD- Genetic Optimisation for Ligand Docking
• Scoring Function- Goldscore：
Fitness＝S(hb_ext)＋1.375×S(vdw_ext)＋S(hb_int)＋S(int)＋S(bar)
• van der Waals‘ forces → Lennard-Jones potential
• Hydrogen bond →
Introduction- Genetic Algorithm
START
Encoding
New
Population
Initial population
Generation
Crossover
Biased
toward better
‘fitters’!
Selection
N
Termination
?
Y
STOP
Mutation
Evaluation
Decoding
Solutions
Fitness
Computation
GA - coding
GA- introduction to operations
Introduction- GOLD
Default 1
2 times
speed-up
3 times
speed-up
7-8 times
speed-up
100
100
100
100
1.1
1.1
1.1
1.1
100000
50000
30000
10000
No. of Islands
5
5
3
1
Niche Size
2
2
2
2
Migrate
10
10
10
0
95
95
95
100
95
95
95
100
Population Size
Selection Pressure
100
populations
each!
No. of Operations
operations Mutate
Crossover
Sset as
0 if # of
island is
1
because
no
migratio
n
between
‘islands’.
A random pick: keep the frequency this ratio!
Selection Pressure
•
•
•
•
•
•
•
•
•
Each of the genetic operations (crossover, migration, mutation) (see Operator Weights: Migrate, Mutate,
Crossover) takes information from parent chromosomes and assembles this information in child chromosomes.
The child chromosomes then replace the worst members of the population.
•
The selection of parent chromosomes is biased towards those of high fitness, i.e. a fit chromosome is more likely
to be a parent than an unfit one.
•
The selection pressure is defined as the ratio between the probability that the most fit member of the population is
selected as a parent to the probability that an average member is selected as a parent. Too high a selection
pressure will result in the population converging too early.
•
For the GOLD docking algorithm, a selection pressure of 1.1 seems appropriate, although 1.125 may be better for
library screening where the aim is faster convergence.
•
Changes to genetic algorithm parameters should be made with care (see Controlling Accuracy and Speed with
Genetic Algorithm Parameter Settings)
Note
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Why some fitness function is higher than final score during docking ?
Information on the Progress of Docking Runs
…
During a docking run, the fitness score may appear to get worse as the
docking proceeds. This is due to the fact that the effects of poor H-bond
geometry and close nonbonded contacts are artificially down-weighted at
early stages of the docking (annealing). Only the final fitness score (i.e.
from the completed docking) has any meaning.
…
Van der Waals and Hydrogen Bonding Annealing Parameters
When GoldScore is being used, the annealing parameters, Van der
Waals and Hydrogen Bonding, allow poor hydrogen bonds to occur at the
beginning of a genetic algorithm run, in the expectation that they will
evolve to better solutions.
(this is in more details now! Can read later!)
The selection pressure is defined as the ratio between the probability that
the most fit member of the population is selected as a parent to the
probability that an average member is selected as a parent. Too high a
selection pressure will result in the population converging too early.
(Yes, higher this value, more biased to fitter chromosomes!)
Niche size:
變化形 niches;
1.
壁龕
2.
合適的職務(或地位等)[(+in)]
You can then find your own niche in public life. 那時候你就可以在社
會上找到適
合自己的工作了。
3.
利基
vt. 及物動詞
變化形 niches;
1.
把(雕像等)放入壁龕[H]
(for keep diversity of conformations in a population!):
Niching is a common technique used in genetic algorithms to
preserve diversity within the population.
In GOLD, two individuals share the same niche if the rmsd between
the coordinates of their donor and acceptor atoms is less than 1.0
Å.
When adding a new individual to the population, a count is made of
the number of individuals in the population that inhabit the same
niche as
the new chromosome. If there are more than NicheSize individuals
in the
niche, then the new individual replaces the worst member of the
niche rather
than the worst member of the total population
(don’t know when the replacement of individuals happens, but,
knowing its
meaning first! … typical value is 2)
In Autodock:
• ga_elitism <integer> (usually is 1)
• [1]This is used in the selection mechanism of the GA. This is the
number of top individuals that are guaranteed to survive into the
next generation.
• Crossover and mutation are performed on random members of the
population according to user-defined rates of crossover and
mutation. First, crossover is performed. Two-point crossover is used,
with breaks occurring only between genes, never within a gene—
this prevents erratic changes in the real values of the genes. Thus,
both parents’ chromosomes would be broken into three pieces at the
same gene positions, each piece containing one or more genes; for
instance, ABC and abc. The chromosomes of the resulting offspring
after two point crossover would be AbC and aBc. These offspring
replace the parents in the population, keeping the population size
constant.
Molecular Dynamics simulation
•解牛頓方程式：
需要初始位置與速度
•分子力場：