 | Xplor-NIH home Documentation |
Next: Embedding Up: Implementation of Distance Geometry Previous: Pseudoatoms
Bound Smoothing
Input distances usually define only a small fraction of the
interatomic distances in the system. However, they do imply upper and
lower bounds on the other atoms to which they are connected by means of
the triangle inequalities
(Crippen and Havel, 1988). Determining these
implied bounds is equivalent to a well-studied computational problem,
finding the shortest path between two points in a directed graph. The
shortest-path algorithm used in this implementation is that of
Dijkstra (see Tarjan (1983) for a review). It
proceeds by calculating
the shortest paths from one atom (the root) to all other atoms.
The shortest-path routine calculates both upper and lower bounds by
keeping track of two halves of the graph, one that holds the upper
bounds and one that holds the lower. By solving the shortest-path
problem for the upper bounds first, the program can then calculate the
lower bounds by continuing the shortest-path routine with the second
half of the graph. This process is repeated, with each atom taking its
turn as root.
Xplor-NIH 2024-09-13