# Algorithms for Ordering DNA Probes on Chromosomes

## Joshua Redstone and Walter L. Ruzzo

### Technical Report UW-CSE-98-12-04, December, 1998.

**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
*