Cluster computing for determining three-dimensional protein structure

    Authors

    P. Micikevicius;N. Deo

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    J. Supercomput.

    Keywords

    parallel algorithms; Beowulf cluster; molecular conformation; NUCLEAR-MAGNETIC-RESONANCE; DISTANCE GEOMETRY; SHORTEST-PATH; COMPUTATIONAL EXPERIENCE; ALGORITHMS; MACROMOLECULES; CONFORMATION; RESTRAINTS; MATRIX; Computer Science, Hardware & Architecture; Computer Science, Theory &; Methods; Engineering, Electrical & Electronic

    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 inter-atomic distance bounds provided by Nuclear Magnetic Resonance 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 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, where n is the number of atoms in a molecule. The number of communications is at least an order of magnitude lower than in the earlier parallelizations. Our implementation utilized processors with at least 59% efficiency (including the communication overhead)-an impressive figure for a non-embarrassingly parallel problem on a cluster of workstations.

    Journal Title

    Journal of Supercomputing

    Volume

    34

    Issue/Number

    3

    Publication Date

    1-1-2005

    Document Type

    Article

    Language

    English

    First Page

    243

    Last Page

    271

    WOS Identifier

    WOS:000231761000002

    ISSN

    0920-8542

    Share

    COinS