Iterative framework radiation hybrid mapping

Building comprehensive radiation hybrid maps for large sets of markers is a computationally expensive process, since the basic mapping problem is equivalent to the traveling salesman problem. The mapping problem is also susceptible to noise, and as a result, it is often beneficial to remove markers that are not trustworthy. The resulting framework maps are typically more reliable but don’t provide information about as many markers. We present an approach to mapping most markers by first creating a framework map and then incrementally adding the remaining markers. We consider chromosomes of the human genome, for which the correct ordering is known, and compare the performance of our two-stage algorithm with the Carthagene radiation hybrid mapping software. We show that our approach is not only much faster than mapping the complete genome in one step, but that the quality of the resulting maps is also much