A fast and scalable radiation hybrid map construction and integration strategy

This paper describes a fast and scalable strategy for constructing a radiat ion hybrid (RH) map from data on different RH panels. The maps on each pane l are then integrated to produce a single RH map for the genome. Recurring problems in using maps from several sources are that the maps use different markers, the maps do not place the overlapping markers in same order, and the objective functions for map quality are incomparable. We use methods fr om combinatorial optimization to develop a strategy that addresses these is sues. We show that by the standard objective functions of obligate chromoso me breaks and maximum likelihood, software for the traveling salesman probl em produces RH maps with better quality much more quickly than using softwa re specifically tailored for RH mapping. We use known algorithms for the lo ngest common subsequence problem as part of our map integration strategy. W e demonstrate our methods by reconstructing and integrating maps for marker s typed on the Genebridge 4 (GB4) and the Stanford G3 panels publicly avail able from the RH database. We compare map quality of our integrated map wit h published maps for GB4 panel and G3 panel by considering whether markers occur in the same order on a map and in DNA sequence contigs submitted to G enBank. We find that all of the maps are inconsistent with the sequence dat a for at least 50% of the contigs, but our integrated maps are more consist ent. The map integration strategy not only scales to multiple RH maps but a lso to any maps that have comparable criteria for measuring map quality. Ou r software improves on current technology for doing RH mapping in areas of computation time and algorithms for considering a large number of markers f or mapping. The essential impediments to producing dense high-quality RH ma ps are data quality and panel size, not computation.