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 higher.
|Original language||English (US)|
|Title of host publication||SIAM International Conference on Data Mining 2014, SDM 2014|
|Editors||Mohammed Zaki, Zoran Obradovic, Pang Ning-Tan, Arindam Banerjee, Chandrika Kamath, Srinivasan Parthasarathy|
|Publisher||Society for Industrial and Applied Mathematics Publications|
|Number of pages||9|
|State||Published - 2014|
|Event||14th SIAM International Conference on Data Mining, SDM 2014 - Philadelphia, United States|
Duration: Apr 24 2014 → Apr 26 2014
|Name||SIAM International Conference on Data Mining 2014, SDM 2014|
|Other||14th SIAM International Conference on Data Mining, SDM 2014|
|Period||4/24/14 → 4/26/14|
Bibliographical notePublisher Copyright:
Copyright © SIAM.