Research from EPSRC project GR/S03546/01. Project research papers.

• What is Genetic Programming?
• Applications of Genetic Programming
• Using GP within GSK for drug discovery
  • Predicting Drug Enzyme interaction
  • Data mining DNA chip gene expression data
• Future, Bioinformatic data fusion
• Conclusions. More info. in handout

• In genetic programming (GP) we use the ideas of Darwinian natural selection inside the computer.
• We start with a population containing a primordial soup of randomly created programs.
• Selection is applied. So that the "fitter" programs survive and have more children.
• Over a series of generations the population evolves and fitness improved.
• After, say, 50 generations a suitable solution, or approximate solution, may be found.

1. Initial random populations of trial solutions
2. Test individual programs
3. Good enough? Stop
4. Select better
5. Breed new generation of programs with crossover and mutation
6. Goto 2

• Model represented as tree. Eg eval=(a+b)*c
  • a,b,c inputs to model, leaves of tree
  • + * functions, internal nodes of tree
  • result from root node of tree

• Fitness function guides evolution.
• Need some way of preferring better programs
• Classic fitness functions use training examples where desired output from inputs is given.
  • RMS error
  • number correct predictions (but beware class imbalance. Use ROC based fitness).

• Prediction and Classification
• Image and Signal Processing
  • Target detection, Blood capillaries
• Optimisation
  • Engineering, BAe wing, GE turbofan. Scheduling, vehicle routing
• Financial Trading
  • Currency trading, Stock market prediction (Horse race betting)
• Robots and Autonomous Agents, Artificial Life
  • Economic simulations, Robot walking, flying, hand-eye co-ordination
• Artistic
  • Flocking, Craig Reynolds' Film Oscar. Architecture.

• Drug Discovery
  • Predicting Human oral bioavailability
  • Predicting drug-enzyme interaction
• DNA chip gene expression data. GSK data (and childhood leukemia, childhood cancer)

• Quick introduction to drug discovery
• What is P450?
• How computer based (known as in silico) prediction of P450 v. Chemical interaction can aid drug discovery.
• GSK "blind trial" competition. 12 groups entered (all but one in GSK). GP winner.
• Training, test and extrapolation data sets.
• GP set up. Results.

• Medical research on a disease may discover the disease's life cycle.
• There may be a critical point in the life cycle that might be disrupted by a drug. E.g. a point where a chemical might bind and prevent the diseases action.
• Search space of potential drugs is huge. Estimated 10⁴⁰ drug like chemicals.
• Using high throughput robot based screening in the region of 10⁶ can be measured.
• Computer models are used at many stages of the discovery "funnel" to predict chemical properties.

1. Which existing chemicals to test next
2. Models can make predictions for "virtual" chemicals, i.e. chemicals that do not exist. If model suggests virtual chemical looks promising it could be made

• As drug proceeds down discovery funnel costs escalate
• Later a potential drug is abandoned the more expensive
• A major cause of late failure is adverse interaction with other parts of the body.
• P450 is responsible for degrading most drugs on the market.
• Early prediction of P450 activity is sought by the pharmaceutical industry.
• Most companies are looking at computer based approaches.

• GSK formed by merger of Glaxo Wellcome and SmithKline Beecham in 2000.
• Both GW and SB had large libraries of chemicals which might be used as drugs.
• Large program to measure biochemical properties, especially P450.
• Workshop to assess feasibility of automatic computer prediction in drug discovery
• Blind trial. 12 techniques.
  • Train on former SB training data.
  • Test on former SB.
  • Extrapolate to former GW.

• Measured chemical affinity as concentration
• Split into 3 classes
  inhibitor (<=3uM), substrate (>3 to <30uM) and inactive (>=30uM)
• Training Set
  3000 compounds from the SB Collection
  (random selection but 1000 compounds in each class)
• Test set
  (4570 compounds from the SB collection)
• Extrapolation set
  (1932 compounds from the GW collection)

1000	1000	1000	3000	training SB	Value given
4570	91	1562	2916	test SB	no value
1932	114	446	1372	Extrapolate GW	no value

• For each chemical GSK calculated 121 "features" from the chemical's formula.
• Features can be Boolean, categorical or continuous.
• Features represent chemical properties. E.g. charge imbalance, acid or base, heavy metal.

• Measurements high quality but still noisy data.
• Training data was deliberately set up to have equal numbers in each of the three classes.
• The test (or interpolation) data set and the extrapolation set very unequal split.

• Functions: Arithmetic + * - / IF min max
• Leaves: 121 features, 100 constants
• Fitness: 3000 training cases
  • Output of tree compared to measurement
  • fitness = 20,000 * #hits - error2
• a hit is a correctly classified example
• Population size: 5000, 50 generations (~2 hours)

%r14S.p500.2.50 fitness  3.36243e+07 hits 1838 len 51 %Tue Feb 25 17:57:33 2003
(ADD	(IFLTE f1
	             f2
	             (Max
		(ADD
		         (DIV
		               (SUB f3 20.33) 
		              0.8546)
		        (Min f4 25.58))
		f2)
	             (SUB
		(ADD
		     (DIV 493.1 f5)
		     (SUB f3 23.83))
		20.33))
	(Max
	             (Max
	                    (Max
	                          (Min
	                                (MaxA f4 -21.38)
	                               25.58)
	                          (IFLTE 0.6186 f6 2 55.27))
	                    (Min f7 f8))
	             (SUB
	                    (MUL 10.02 f2)
	                    14.04)))