Reference: Chen, C. C.; Singh, J. P.; Poland, W. B.; & Altman, R. B. Parallel Protein Structure Determination from Uncertain Data. Knowledge Systems Laboratory, Medical Computer Science, September, 1995.
Abstract: Molecular structure determination is an important task in biology because of the intimate relation between form and function of biological molecules. Individual sources of information about molecular structure are subject to uncertainty and are not sufficiently abundant to define the structure to high accuracy by themselves. We have examined a probabilistic algorithm, PROTEAN, which can incorporate multiple sources of uncertain data to estimate the three-dimensional structure of molecules and also predict a measure of the uncertainty in the estimated structure. We have applied this algorithm successfully to several biological structure problems. Like most structure prediction methods, this algorithm is computationally expensive for realistic biological macromolecules. In this paper, we experiment with speeding up the algorithm through the application of parallelism. We present a parallel version of the algorithm, and demonstrate good speedups on a 32-processor Stanford DASH, a cache-coherent shared-address-space multiprocessor. The results were obtained by exploiting data locality only in the per-processor coherent caches, without attempt to distribute data intelligently in the physically distributed main memory of the machine. We also obtained very good speedups on a state-of-the-art commercial multiprocessor, the Silicon Graphics Challenge. Finally, we propose an extension to the serial algorithm which enables it to handle a wider class of data, and discuss the potential for parallelization of the extended algorithm.
Full paper available as ps.