A parallel algorithm for bound-smoothing

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 tight 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 ∞. 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 bound-smoothing procedure finds upper and lower limits on each of the six distances in the quadruple. Applying the tetrangle inequalities to each of the (₄ⁿ) quadruples requires Θ(n⁴) time. Here, we propose a parallel algorithm for bound-smoothing employing the tetrangle inequality. Each pass of our algorithm requires Θ(n³ log n) time on a CREW PRAM with Θ(n/log n) processors. An implementation of this parallel algorithm on the Intel Paragon XP/S and its performance are also discussed