A Note on Discretization Orders for Distance Geometry Problems

When a weighted graph is an instance of the Distance Geometry Problem, certain types of vertex orders (called discretization orders) make it amenable to be solved by means of a discrete search type algorithm, rather than a continuous one. We show that finding a discretization order is difficult if we require each vertex to be adjacent to immediate predecessors (which happens to be the case for the important application to finding the 3D structure of proteins). This justifies the use of heuristics in finding such orders.

By: Andrea Cassioli, Leo Liberti

Published in: Optimization Letters, volume 6, (no 4), pages 783-96 in 2012

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .