Abstract: Accurate estimates of the ordering and positioning of DNA markers (probes) on a chromosome are valuable tools used, for example, to help researchers isolate genetic factors in diseases. One such mapping technique, called fluorescent in situ hybridization (FISH), obtains approximate pairwise distance measurements between probes on a chromosome. We have developed two algorithms for computing least squares estimates of the ordering and positions of the probes: a branch and bound algorithm and a local search algorithm motivated by gradient descent. Simulations demonstrate the effectiveness of the branch and bound pruning heuristic and show that the local search algorithm is usually fast and accurate. The branch and bound algorithm is able to solve to optimality problems of 18 probes 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 18 probes in about a minute. We also investigate (via simulation) the accuracy with which maps can be constructed from FISH data.
Download: PostScript PDF
E-mail: ruzzo /at/ cs /dot/ washington /dot/ edu