Computational experience with a parallel algorithm for tetrangle inequality bound smoothing

    Authors

    K. Rajan;N. Deo

    Comments

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

    Keywords

    Distance Geometry; Conformation; Packings; Biology; Mathematical & Computational Biology

    Abstract

    Determining molecular structure from interatomic distances is an important and challenging problem. Given a molecule with n atoms, lower and upper bounds on interatomic distances can usually be obtained only for a small subset of the n(n-1)/2 atom pairs, using NMR. Given the bounds so obtained on the distances between some of the atom pairs, it is often useful to compute tighter bounds on all the n(n-1)/2 pairwise distances. This process is referred to as bound smoothing. The initial lower and upper bounds for the pairwise distances not measured are usually assumed to be 0 and infinity. One method for bound smoothing is to use the limits imposed by the triangle inequality. The distance bounds so obtained can often be tightened further by applying the tetrangle inequality-the limits imposed on the six pairwise distances among a set of four atoms (instead of three for the triangle inequalities). The tetrangle inequality is expressed by the Cayley-Menger determinants. For every quadruple of atoms, each pass of the tetrangle inequality hound smoothing procedure finds upper and lower limits on each of the six distances in the quadruple. Applying the tetrangle inequalities to each of the ((n)(4)) quadruples requires O(n(4)) time. Here, we propose a parallel algorithm fbr bound smoothing employing the tetrangle inequality. Each pass of our algorithm requires O(n(3) log n) time on a CREW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) with O(n/log n) processors. An implementation of this parallel algorithm on the Intel Paragon XP/S and its performance are also discussed. (C) 1999 Society for Mathematical Biology.

    Journal Title

    Bulletin of Mathematical Biology

    Volume

    61

    Issue/Number

    5

    Publication Date

    1-1-1999

    Document Type

    Article

    Language

    English

    First Page

    987

    Last Page

    1008

    WOS Identifier

    WOS:000083089400009

    ISSN

    0092-8240

    Share

    COinS