Algorithms for a Simple Point Placement Problem

Joshua Redstone and Walter L. Ruzzo

Algorithms and Complexity, 4th Italian Conference, CIAC 2000, Rome, Italy, March 2000, pp. 32-43.

Abstract:  We consider algorithms for a simple one-dimensional point placement problem: given N points on a line, and noisy measurements of the distances between many pairs of them, estimate the relative positions of the points. Problems of this flavor arise in a variety of contexts. The particular motivating example that inspired this work comes from molecular biology; the points are markers on a chromosome and the goal is to map their positions. The problem is NP-hard under reasonable assumptions. We present two algorithms for computing least squares estimates of the ordering and positions of the markers: a branch and bound algorithm and a highly effective heuristic search algorithm. The branch and bound algorithm is able to solve to optimality problems of 18 markers in about an hour, visiting about 10^6 nodes out of a search space of 10^16 nodes. The local search algorithm usually was able to find the global minimum of problems of similar size in about one second, and should comfortably handle much larger problem instances.

Download:  PostScript   PDF   Conference Proceedings

E-mail: ruzzo /at/ cs /dot/ washington /dot/ edu