Computing the 3-D Structure of Protein Molecule
by
Narsingh Deo
Department of Computer Science, University of Central Florida, Orlando, Florida, USA

Determining the three-dimensional structure of a protein molecule (or any other large biomolecule) is an extremely important and computationally challenging problem.One approach involves using NMR (nucleo magnetic resonance) spectroscopy, through which a small subset of the n(n-1)/2 inter-atomic distances in an n-atom- molecule are determined. Furthermore, these distance measurements are not exact, but each lies within an upper and a lower bound. Computing the coordinates of the n points (atoms) in the 3-D Euclidean space which conforms to the NMR distance measurements is referred to as the molecular conformation problem. We use an edge-weighted, complete graph of order n, embedded in the 3-D space to model the n-atom molecule. First, the triangle inequality is applied to tighten the distance bounds. Warshall-Floyd all-pairs shortest path algorithm is used to ensure convergence and an optimal order of processing the triangles. The distance-bounds are further tightened by applying the so-called tetrangle inequality (resulting from the Cayley-Menger determinants) to all quadruples of atoms. Parallel algorithms are designed in order to keep execution times within reasonable limits. Only edge-disjoint sets of 4-node subgraphs can be processed concurrently. Finding such edge-disjoint subgraphs is equivalent to constructing a large set of 2-(n, 4, 1) packing designs. A number of other interesting problems involving design theory as well as graph theory arise in this context. After the distance bounds are tightened, a well-known result from distance-geometry is used to determine the coordinates in 3-D space (from the three largest eigenvectors of the metric matrix). [Background Reference: R. Kumar and N. Deo, “Computational Experience with a Parallel Algorithm for Tetrangle Inequality Bound Smoothing,” Bulletin of Mathematical Biology (1999), 61, 987-1008]

Date received: October 28, 2002