From: Alejandro Schaffer [schaffer@ncbi.nlm.nih.gov]
Sent: Friday, January 21, 2005 4:47 PM
To: ncbi-seminar@ncbi.nlm.nih.gov
Subject: CBB seminar on 25 January


Radiation Hybrid Mapping Case Studies
    Alejandro A. Schaffer

Date: Tuesday 25 January 2005, weather permitting
Time: 11AM
Location: Building 38A, B2 level library

Radiation hybrid mapping is a combination of laboratory and
computational techniques to build physical maps of STS markers. In
2000, we publised new software for radiation hybrid mapping called 
rh_tsp_map, and a new human map computed using that
software[1]. rh_tsp_map has been subsequently used by other groups,
most notably the dog mapping group[2].  One innovation in rh_tsp_map
was automation of the known reduction between RH mapping and the
well-studied traveling salesman probelm (TSP)[3]; this enables us to use
superb software called CONCORDE[4] for TSP to solve all RH-derived
instances to global optimality.  The dog group showed that the global
optimum approach rh_tsp_map produces more robust maps than the
incremental approach of previous software such as MultiMap[5]

Despite the encouraging results of the dog group, most published RH
maps are built with other software. Therefore, we set out to
collaborate with some RH mapping groups to figure out how we might
improve rh_tsp_map.  I will describe our usage of rh_tsp_map to
construct dense maps for the cat (Felis catus), a coarse map of rhesus
macaque (Macacca mulatta), and dense maps of 7 horse (Equus caballus)
chromosomes. We implemented some new functionality to address various
practical problems that arose in these studies. 

All the rh_tsp_map work is joint with Richa Agarwala (IEB, NCBI).
Cat maps were constructed in collaboration with Bill Murphy (Texas A&M,
formerly NCI) and Marilyn Menotti-Raymond (NCI)
The macaque map was constructed in collaboration with Bill Murphy
The horse maps are being constructed in collaboration with Bhanu Chowdhary,
Terje Raudsepp, Candice Brinkmeyer, and Glenda Goh (all at Texas A&M)

The cat and dog maps were processed for viewing in MapViewer by Wonhee Jang
(IEB, NCBI).

References:
1. Agarwala R, Applegate DL, Maglott D, Schuler GD, Sch\"affer AA.
A fast and scalable radiation hybrid map construction and integration 
strategy. Genome Res. 2000;10(3):350-64.

2. Guyon R, Lorentzen TD, Hitte C, Kim L, Cadieu E, Parker HG, Quignon P,
Lowe JK, Renier C, Gelfenbeyn B, Vignaux F, DeFrance HB, Gloux S,
Mahairas GG, Andr\'e C, Galibert F, Ostrander EA.
A 1-Mb resolution radiation hybrid map of the canine genome.
Proc Natl Acad Sci USA. 2003; 100(9):5296-301.

3. Applegate, D., R. Bixby, V. Chv\'atal, and W. Cook. 1998.
On the solution of traveling salesman problems.
Documenta mathematica, extra volume International
Congress of Mathematics  1998; III:645-56.


4. Ben-Dor A, Chor B.  On constructing radiation hybrid maps.  J
Comput Biol. 1997;4(4):517-33.


5.Hitte C, Lorentzen TD, Guyon R, Kim L, Cadieu E, Parker HG, Quignon P,
Lowe JK, Gelfenbeyn B, Andr\'e C, Ostrander EA, Galibert F.
Comparison of MultiMap and TSP/CONCORDE for constructing radiation
hybrid maps.  J Hered. 2003; 94(1):9-13.