# Special projects between Bavaria and Florida

Lehrstuhl Biopolymere

Universität Bayreuth

School of EECS

University of Central Florida

## **Determining Shapes of Protein Molecules Fast: with Parallel Computers**

In order to fully understand the role of a specific protein, it is important to determine the exact shape of the protein molecule. At present, the most popular experimental means of determining the 3-D shape of a molecule is X-ray crystallography, but it has severe limitations. Some protein crystals take months to grow large enough to be used for X-ray crystallography. Many proteins do not form crystals at all. An alternative tool is Nuclear Magnetic Resonance (NMR) spectroscopy. NMR spectroscopy does not directly give the structure of a molecule. What it gives is the upper and lower limits on distances between some (not all) of the pairs of atoms in the molecule being studied. Calculating the shape of the molecule from their interatomic distances is computationally a challenging task. Efficient parallel processing is thought to drastically reduce the time required for structure determination.

Prof. Deo and his doctoral students have discovered new computational approaches which have the potential of drastically reducing the computation time needed (from months to hours). The reduction will come from two sources: (1) novel application of distance geometry, combinatorial mathematics and graph-theory may reduce the total number of calculations performed (by a factor of perhaps as much as 100), and (2) recasting the algorithms (and data structures) to exploit concurrency and execute them on a large cluster of processors which communicate and continuously divide the work among themselves to solve the problem much faster than with a single processor.

The goal of this project is to develop fast and efficient software that would employ these new and sophisticated algorithms-- based on novel use of distance geometry, graph theory and combinatorial mathematics--for determining the 3-D structure of proteins and other large biomolecules. At the completion of the project, we expect to have designed, written, and tested such a software which would take the NMR data of a protein molecule as its input and produce as its output the 3-D structure of the molecule. The software would be designed to run on a cluster of computers and efficiently exploit parallel processing.

Below are two sample publications by Prof. Deo on this topic:

- P. Micikevicius and N. Deo, ”Exploring Topological Properties of NMRGraphs,”
*Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering*, 2007, BIBE 2007, pp. 1304-1307 - K. Rajan and N. Deo, “Computational Experience with a Parallel Algorithm for Tetrangle Inequality Bound Smoothing,”
*Bulletin of Mathematical Biology*, Vol. 61, No. 5, pp. 987-1008, 1999.

The project will be conducted in collaboration with the group of PD Dr. Schwarzinger from the Department of Biopolymers at the Universität Bayreuth, who have long standing interest in structure elucidation using NMR spectroscopy.