Coarse-grained parallelization of distance-bound smoothing for the molecular conformation problem

    Authors

    N. Deo;P. Micikevicius

    Keywords

    COMPUTATIONAL EXPERIENCE; ALGORITHM; GEOMETRY; Computer Science, Theory & Methods

    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.

    Journal Title

    Distributed Computing, Proceedings: Mobile and Wireless Computing

    Volume

    2571

    Publication Date

    1-1-2002

    Document Type

    Article

    Language

    English

    First Page

    55

    Last Page

    66

    WOS Identifier

    WOS:000181655000006

    ISSN

    0302-9743; 3-540-00355-X

    Share

    COinS