Parallel Algorithms and Methods for Solving Macromolecular Structures

Principal Investigators: Robert E. Lynch, Dan C. Marinescu, John R. Rice, M. G. Rossmann

Research Associate: Z. Zhang

Research Assistants: M. Cornea-Hasegan, C. Costian

Sponsor: NSF

The goal of this research is to study parallel algorithms and methods for the computation related to the determination and analysis of biological structures, and to make possible the determination of structures larger than is possible with the best supercomputers of the 1980's. Specifically, we are concerned with viruses and their complexes with neutralizing antibodies, receptors, and other ligands.

The principal tool for structure determination of biological molecules is X-ray Crystallography. After useful crystalline material has been obtained, X-ray diffraction data are collected and processed extensively by computers.

The three spatial coordinates of each atom are to be determined, and the number of parameters that need to be determined for even a small virus is about 2x10 to the sixth power. That also means it is necessary to collect and analyze at least that amount of data. To account for experimental error a small virus structure requires about 20 million primary observations. Many more are needed for the study of numerous mutants and ligand complexes that give functional understanding to a structure.

The largest amount of computing is in the analysis of these data--specifically in the solution of the phase problem. This is the central problem of X-ray crystallography and the analysis breaks down into the following principal components:

1. Data acquisition and processing
The objective is to guide the diffraction instruments for the collection of quality diffraction information and then to reduce these data to structure amplitudes, F, the amplitudes of the diffracted rays which are the moduli of the Fourier coefficients of the electron density.
2. Solution of the phase problem
To determine the phases of the Fourier coefficients of the electron density, the principle methods and tools are (a) multiple isomorphous replacement, (b) molecular replacement, and (c) multiple wavelengths anomalous dispersion.
3. Model building and analysis using computer graphics systems
4. Refinement of structures
5. Analyses, sequence and structure comparisons

This leads to further experiments using biochemical, genetic, crystallographic, NMR, and other techniques. The objective here is to understand the function in terms of the mechanical and electronic structures of biological molecules. In a wider sense the objectives are to understand biological processes in terms of the constitutive molecules and molecular assemblies that are in living organisms.

The structure determination uses a methodology for phase refinement and extension pioneered by the Structural Studies Group at Purdue. The computation is based upon an iterative process summarized in Figure 1 on page 83.

The goal of the project is to reduce the processing time needed for phase refinement and extension by two orders of magnitude by developing parallel algorithms for each of the tasks shown in Figure 1 on page 83, and by implementing efficiently such algorithms for different architectures. Figure 2 on page 84 presents the execution time functions of the number of PEs for the electron density averaging, one of the most compute-intensive tasks in the structure determination.