Abstract
Determining the three-dimensional structure of proteins is crucial to efficient drug design and understanding biological processes. One successful method for computing the molecule’s shape relies on the inter-atomic distance bounds provided by the Nucleo-Magnetic Resonance (NMR) spectroscopy. The accuracy of computed structures as well as the time required to obtain them are greatly improved if the gaps between the upper and lower distance-bounds are reduced. These gaps are reduced most effectively by applying the tetrangle inequality, derived from the Cayley-Menger determinant, to all atom-quadruples. However, tetrangle-inequality bound-smoothing is an extremely computation intensive task, requiring O(n 4) time for an n-atom molecule. To reduce the computation time, we propose a novel coarse-grained parallel algorithm intended for a Beowulf-type cluster of PCs. The algorithm employs p n/6 processors and requires O(n 4/p) time and O(p 2) communications. The number of communications is at least an order of magnitude lower than in the earlier parallelizations. Our implementation utilized the processors with at least 59% efficiency (including the communication overhead) — an impressive figure for a nonembarrassingly parallel problem on a cluster of workstations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. B. Anfinsen. Principles that govern the protein folding chains. Science, vol. 181, pp. 233–230, 1973.
A. Aszödi, M. J. Gradwell, W. R. Taylor. Global fold determination from a small number of distance restraints. Journal of Molecular Biology, vol. 251, pp. 308–326, 1995.
D. J. Becker, T. Sterling, D. Savarese, E. Dorband, U. A. Ranawake, C. V. Packer. BEOWULF: A parallel workstation for scientific computation. Proceedings of the 1995 International Conference on Parallel Processing (ICPP), pp. 11–14, 1995.
H. M. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. N. Bhat, H. Weissig, I. In. Shindyalov, P. E. Bourne. The Protein Data Bank, Nucleic Acids Research, vol. 28, pp. 235–242, 2000.
L. M. Blumenthal. Theory and Applications of Distance Geometry. Chelsea Publishing Company, Bronx, New York, 1970.
A. E. Brouwer. Optimal packings of K4’s into a Kn. Journal of Combinatorial Theory, vol. 26, pp. 278–297, 1979.
F. E. Cohen, I. D. Kuntz. Tertiary structure prediction. In G. D. Fasman, editor, Prediction of Protein Structure and the Principles of Protein Conformation, pp. 647–705, Plenum Press, New York, 1989.
G. M. Crippen. A novel approach to the calculation of conformation: Distance geometry. Journal of Computational Physiology, vol. 24, pp. 96–107, 1977.
G. M. Crippen, T. F. Havel. Distance Geometry and Molecular Conformation. Research Studies Press Ltd., Taunton, Somerset, England, 1988.
N. Deo, P. Micikevicius. Coarse-grained parallelization of distance-bound smoothing. Computer Science Technical Report CS-TR-02-06, University of Central Florida, 2002.
N. Deo, P. Micikevicius. On cyclic one-factorization of complete 3-uniform hypergraphs. Congressus Numerantium, to appear, 2003.
P. L. Easthope and T. F. Havel. Computational experience with an algorithm for tetrangleinequality bound-smoothing. Bulletin of Mathematical Biology, vol. 51, pp. 173–194, 1989.
P. Güntert. Structure calculation of biological macromolecules from NMR data. Quarterly reviews of biophysics, vol. 31, pp. 145–237, 1998.
T. F. Havel. The sampling properties of some distance geometry algorithms applied to unconstrained polypeptide chains: a study of 1830 independently computed conformations. Biopolymers, vol. 29, pp. 1565–1585, 1990.
T. F. Havel. An evaluation of computational strategies for use in the determination of protein structure from distance constraints obtained by nuclear magnetic resonance. Prog. Biophys. Mol. Biol., vol. 56, pp. 43–78, 1991.
B. A. Hendrickson. The molecule problem: Exploiting structure in global optimizations. SIAM Journal on Optimization, vol. 5, pp. 835–857, 1995.
N. Kumar, N. Deo, R. Addanki. Empirical study of a tetrangle-inequality boundsmoothing algorithm. Congressus Numerantium, vol. 117, pp. 15–31, 1996.
K. Menger. New foundation of Euclidean geometry. Amer. J. Math., vol. 53, pp. 721–45, 1931.
P. Micikevicius. Parallel Graph Algorithms for Molecular Conformation and Tree Codes. Ph.D. thesis, University of Central Florida, Orlando, Florida, 2002.
K. Rajan. Parallel Algorithms for the Molecular Conformation Problem. Ph.D. thesis, University of Central Florida, Orlando, Florida, 1999.
K. Rajan, N. Deo. A parallel algorithm for bound-smoothing. Proceedings of the 13 th International Parallel Processing Symposium, April 12-16, San Juan, Puerto Rico, 1999, pp. 645–652.
K. Rajan, N. Deo. Computational experience with a parallel algorithm for tetrangle inequality bound smoothing. Bulletin of Mathematical Biology, vol. 61(5), pp. 987–1008, 1999.
K. Rajan, N. Deo, N. Kumar. Generating disjoint t-(v, k, 1) packings in parallel. Congressus Numerantium, vol. 131, pp. 5–18, 1998.
D. K. Searls. Grand challenges in computational biology. In Computational Models in Molecular Biology, S. L. Salzberg, D. K. Searls, S. Kasif, editors. Elsevier, 1998.
M. Snir, S. Otto, S. Huss-Lederman, D. Walker, J. Dongarra. MPI: The Complete Reference. MIT Press, Cambridge, Massachusetts, 1996.
T. Sterling, D. Savarese. A coming of age for Beowulf-class computing. Lecture Notes in Computer Science, vol. 1685, pp. 78–88, 1999.
W. D. Wallis. Combinatorial Designs. Marcel Dekker, Inc., New York, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Deo, N., Micikevicius, P. (2002). Coarse-Grained Parallelization of Distance-Bound Smoothing for the Molecular Conformation Problem. In: Das, S.K., Bhattacharya, S. (eds) Distributed Computing. IWDC 2002. Lecture Notes in Computer Science, vol 2571. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36385-8_6
Download citation
DOI: https://doi.org/10.1007/3-540-36385-8_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00355-7
Online ISBN: 978-3-540-36385-9
eBook Packages: Springer Book Archive