Shortest-path problems and molecular conformation

DOI10.1016/0166-218X(88)90009-1MaRDI QIDQ1095924zbMATH OpenFDO

Authors Andreas W. M. Dress, T. F. Havel

Publication date 1988

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(88)90009-1

zbMATH Keywords

algorithmdistance limitsdistancestetrangle inequalitytriangle limits

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Chemistry (92Exx)

Review text

Given a set of experimentally determined lower and upper bounds on the distances between the atoms of a molecule, we study the minimum and maximum values that any one distance can attain when all of the remaining distances are confined between their lower and upper bounds. The triangle inequality may be used to derive a first approximation to these `distance limits', and a complete characterization of these `triangle limits', together with an efficient algorithm for computing them, is presented. A four-point relation known as the `tetrangle inequality' is then discussed as a possible means of obtaining an improved approximation.

Recommendations

• Computational experience with a parallel algorithm for tetrangle inequality bound smoothing
• scientific article; zbMATH DE number 3895768
• Computational experience with an algorithm for tetrangle inequality bound smoothing
• scientific article; zbMATH DE number 2188749
• A Branch‐and‐Prune algorithm for the Molecular Distance Geometry Problem

Cites work

• A distance geometry program for determining the structures of small proteins and other macromolecules from nuclear magnetic resonance measurements of intramolecular \({}^ 1H-^ 1H\) proximities in solution
• An approach to nonlinear programming
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3895768 (Why is no real title available?)
• scientific article; zbMATH DE number 3331438 (Why is no real title available?)
• Tensegrity Frameworks
• The Algebraic Geometry of Stresses in Frameworks
• The art and theory of dynamic programming
• The theory and practice of distance geometry
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

Cited in

(9)

• Computational experience with an algorithm for tetrangle inequality bound smoothing
• The embedding problem for predistance matrices
• Molecular conformation search by distance matrix perturbations
• Searching for spreads and packings
• The cone of distance matrices
• scientific article; zbMATH DE number 3895768 (Why is no real title available?)
• scientific article; zbMATH DE number 1154585 (Why is no real title available?)
• scientific article; zbMATH DE number 1522763 (Why is no real title available?)
• Molecular geometry and conformation: Mathematical relations between intra-molecular distances and conformation in Fréchet-type dendrimers and dendrons

This page was built for publication: Shortest-path problems and molecular conformation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095924)