Skip to main content
U.S. flag

An official website of the United States government

Here’s how you know

Official government website icon

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

icon-https

Secure .gov websites use HTTPS
A lock ( Lock Locked padlock icon )or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

NIH: National Institute of Diabetes and Digestive and Kidney Diseases NIH: National Institute of Diabetes and Digestive and Kidney Diseases

  next up previous contents index  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 2025-03-21
  • Privacy Policy
  • Freedom of Information Act
  • Accessibility
  • Disclaimers
  • Copyright
  • Vulnerability Disclosure Policy
  • U.S. Department of Health and Human Services
  • National Institutes of Health