GENETIC ALGORITHMS AND MACROMOLECULAR PHASING M. Fujinaga & M. N. G. James MRC of Canada, Group in Protein Structure and Function Department of Biochemistry, University of Alberta Edmonton Alberta, Canada T6G 2H7

A program has been developed for exploring the use of genetic algorithms for macromolecular phasing. Genetic algorithms are powerful optimization techniques that borrow ideas from natural evolution. Unlike normal optimization techniques, it deals with a set (population) of possible solutions and these are improved by combining (mating) pairs of solutions from the population. The choice of the pair of solutions to mate is governed by the function value that one is trying to optimize (fitness function). The implementation of a genetic algorithm for the crystallographic problem has been done by representing a set of carbon atoms on a three-dimensional grid. The fitness function includes contributions from the agreement between observed and calculated structure factors as well as conformity to the expected distribution of atoms in a protein. One of the advantages of genetic algorithm is that it does not rely on gradients so that functions without derivatives can be included in the fitness function. The mating is done by a continuous crossover method that involves complete mixing and random separation of two sets of atoms. The number of atoms in common is monitored and the offspring are penalized according to the degree of inbreeding. The entire process is rather computationally expensive and the program has been parallelized to run on 20 IBM RS6000 workstations linked together using PVM (parallel virtual machine). The method is being tested on the complex of TEM-1 beta-lactamase and beta-lactamase inhibitory protein (BLIP). The enzyme part of the structure (62%) had been solved by molecular replacement but it was not possible the locate the inhibitor. Density modification techniques have failed to improve the phases sufficiently to solve the remaining 38% of the structure. The structure was eventually resolved by molecular replacement and refined so that a set of 'correct' phases exists to monitor the progress of the genetic algorithm.

This work is supported by the Medical Research Council of Canada.