Parallel hierarchical molecular structure estimation

ABSTRACT

Determining the structure of biological macromolecules such as proteins and nucleic acids is an important element of molecular biology because of the intimate relation between form and function of these molecules. Individual sources of data about molecular structure are subject to varying degrees of uncertainty. Previously we have examined the parallelization of a probabilistic algorithm for combining 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. In this paper we extend our work on two major fronts. First we present a hierarchiacal decomposition of the original algorithm which reduces the sequential computational complexity tremendously. The hierarchical decomposition in turn reveals a new axis of parallelism not present in the "flat" organization of the problems, as well as new parallelization problems. We demonstrate good speedups on two cache-coherent shared-memory multiprocessors, the Stanford DASH and the SGI Challenge, with distributed and centralized memory organization, respectively. Our results point to several areas of further study to make both the hierarchiacal and the parallel aspects more flexible for general problems: automatic structure decomposition, processor load balancing across the hierarchy, and data locality management in conjunction with load balancing. Finally we outline the directions we are investigating to incorporate these extensions.

REFERENCES

• 1: Russ B. Altman, A probabilistic approach to determining biological structure: integrating uncertain data sources, International Journal of Human-Computer Studies, v.42 n.6, p.593-616, June 1995 [doi>10.1006/ijhc.1995.1026]
• 2: Altman, R. B., C. C. Chen, W. B. Poland, J. P. Singh, "Probabilistic Constraint Satisfaction with Non-Gaussian Noise", Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence, pp. 15-22, San Francisco, CA, 1994.
• 3: Altman, R. B., B. Weiser, H. F. Noller, "Constraint Satisfaction Techniques for Modeling Large Complexes: Application to Central Domain of the 16S Ribosomal Subunit", Proceedings of Second International Conference on Intelligent Systems for Molecular Biology, pp.10-18, Stanford, August 1994, AAAI Press.
• 4: Capel, M. S., D. M. Engelman, B. R. Freeborn, M. Kjeldgaard, J. A. Langer, V. Ramakrishnan, D. G. Schindler, D. K. Schneider, B. P. Schoenborn, I. Y. Sillers, et. al., "A Complete Mapping of the Proteins in the Small Ribosomal Subunit of Escherichia coli", Science, 238(4832): 1403-6, 1987.
• 5: Capel, M. S., M. Kjeldgaard, D. M. Engelman, P. B. Moore, "Positions of S2, S13, S16, S17, S19 and S21 in the 30S Ribosomal Subunit of Escherichia coli", J. Mol. Bio., 200(1): 65-87, 1988.
• 6: Cheng Che Chen , Jaswinder Pal Singh , William B. Poland , Russ B. Altman, Parallel protein structure determination from uncertain data, Proceedings of the 1994 conference on Supercomputing, p.570-579, December 1994, Washington, D.C., United States
• 7: Chen, R., D. Fink, R. B. Altman, "Computing the Structure of Large Complexes: Applying Constraint Satisfaction Techniques to Modeling the 16S Ribosomal RNA", Biomolecular NMR Spectroscopy (Markley, J. L. and S. J. Opella, eds.), pp.279-299, Oxford University Press, 1995.
• 8: Gelb, A., ed., Applied Optimal Estimation, the MIT Press, Cambridge, MA, 1984.
• 9: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, Proceedings of the 17th annual international symposium on Computer Architecture, p.148-159, May 28-31, 1990, Seattle, Washington, United States
• 10: Stryer, L., Biochemistry, W. H. Freeman, New York, 1991.
• 11: Wuthrich, K., NMR of Proteins and Nucleic Acids, John Wiley and Sons, 1986.
• 12: Crippen, G. M., Distance Geometry and Conformational Calculations, John Wiley and Sons, 1981.
• 13: Havel, T. F., I. D. Kuntz, G. M. Crippen, "The Theory and Practice of Distance Geometry", Bulletin of Mathematical Biology, 45(5), pp.665-720, 1983.
• 14: Levitt, M., R. Sharon, "Accurate Simulation of Protein Dynamics in Solution", Proceedings of the National Academy of Science, 85, pp.7557-7561, 1988.
• 15: Liu, Y., D. Zhao, R. Altman, O. Jardetzky, "A Systematic Comparison of Three Structure Determination Methods from NMR Data: Dependence upon Quality and Quantity of Data", Journal of Biomolecular NMR, 2, pp.373-388, 1992.
• 16: Nemethy, G., H. A. Scheraga, "Theoretical Studies of Protein Conformation by Means of Energy Computations", FASEB Journal, 4, pp.3189-3197, November 1990.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Human Factors, Performance, Theory

Keywords:
molecular structures, hierarchical computation, shared-memory parallel processing, computing with uncertainty