Researchers at the National Institute of Health have used Concorde's TSP solver to construct radiation hybrid maps as part of their ongoing work in genome sequencing.   The TSP provides a way to integrate local maps into a single radiation hybrid map for a genome; the cities are the local maps and the cost of travel is a measure of the likelihood that one local map immediately follows another.   A report on the work is given in the paper "A Fast and Scalable Radiation Hybrid Map Construction and Integration Strategy", by R. Agarwala, D.L. Applegate, D. Maglott, G.D. Schuler, and A.A. Schaffler.

This application of the TSP has been adopted by a group in France developing a map of the mouse genone. The mouse work is decribed in "A Radiation Hybrid Transcript May of the Mouse Genome", Nature Genetics 29 (2001), pages 194--200.

Next Application