Title

Coarse-Grained Parallelization Of Distance-Bound Smoothing For The Molecular Conformation Problem

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(n4) 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(n4/p) time and O(p2) 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.

Publication Date

1-1-2002

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

2571

Number of Pages

55-66

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/3-540-36385-8_6

Socpus ID

47649115278 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/47649115278

This document is currently not available here.

Share

COinS