Journal of Heredity 2003:94(1)
© 2003 The American Genetic Association 94:9-13
Comparison of MultiMap and TSP/CONCORDE for Constructing Radiation Hybrid Maps
From UMR6061, CNRS, Université de Rennes1, 2 av. Pr. Léon Bernard 35043 Rennes Cedex, France (Hitte, Guyon, Cadieu, Quignon, Andre, and Galibert) and the Divisions of Clinical Research and Human Biology, Fred Hutchinson Cancer Research Center, 1100 Fairview Ave. N, D4-100, Seattle WA 98109-1024 (Lorentzen, Kim, Parker, Lowe, Gelfenbeyn, and Ostrander).
Address correspondence to Francis Galibert at the address above, or e-mail: francis.galibert{at}univ-rennes1.fr.
 |
Abstract |
|---|
 Top Abstract ConclusionReferences |
|---|
Radiation hybrid (RH) map construction allows investigators to locate both type I and type II markers on a given genome map. The process is composed of two steps. The first consists of determining the pattern distribution of a set of markers within the different cell lines of an RH panel. This is mainly done by polymerase chain reaction (PCR) amplification and gel electrophoresis, and results in a series of numbers indicating the presence or the absence of each marker in each cell line. The second step consists of a comparison of these numbers, using various algorithms, to group and then order markers. Because different algorithms may provide (slightly) different orders, we have compared the merits of the MultiMap and TSP/CONCORDE packages using a data set of information currently under analysis for construction of the canine genome RH map.
Whole genome map construction is a two-step process: molecular data generation and the resulting data analysis (McCarthy 1996). The latter uses computer programs specifically dedicated to the nature of the map under construction. There are three different types of genome maps: meiotic linkage, radiation hybrid (RH), and physical. They differ, in part, in the type of markers used to make up the map, the method of genotyping, and the presentation of the results. One of the fundamental differences between meiotic linkage and RH map construction versus physical maps is in assembly methodology. For a physical map, the respective position of two markers A and B is not—or should not be—affected by the addition of new markers to the data set. By comparison, in meiotic linkage and RH map construction, the addition of new markers to an existing data set can, and often does, affect the position of previously mapped markers. This is due to the fact that meiotic linkage and RH maps result from a statistical treatment of experimental data, and thus depend on the analysis program used as well the underlying parameters used in evaluating the data set. As happens frequently, distinct analysis may yield statistically valid yet distinctly different maps. Even recomputing the same set of data using an identical setting of parameters and the same computer program can produce different versions of a given map (Figure 1).
|
RH Mapping
RH maps result from comparing marker distributions within collections of hybrid cell lines that were previously obtained by fusion of gamma-irradiated cells with heterologous carrier cells (Goss and Harris 1975; Vignaux et al. 1999; Walter et al. 1994). Since each viable hybrid contains only a subset, ideally 25%–35%, of the irradiated genome, markers sharing identical or similar distributions within the RH panel will be identified as being in close physical proximity on the chromosome of interest, while markers with a distinct distribution pattern are, of necessity, unlinked. During the first step of RH map construction, the presence or absence of each marker to be localized is determined for each cell line of interest by polymerase chain reaction (PCR) amplification using DNA isolated from each cell line in the RH panel. The resulting data set consists of a series of numbers, with 1 indicating the presence of a marker in a specific hybrid cell line, 0 its absence, and 2 an uncertain result. Thus the distribution of each marker in the panel is characterized by a sequence of 1, 0, 2, called "vectors" (Cox et al. 1990), as shown in Figure 2.
|
During the second step of map construction, marker retention patterns within the panel are compared using different algorithms. This comparison is performed in two phases. In the former, a two-point analysis assigns markers to RH groups that ultimately will correspond to individual chromosomes. In a well-developed map there will be only one RH group associated with each chromosome. The second phase involves determining the markers order within each RH group. To perform these computations, several computing program packages, including RHMAP, RHMAPPER, and MultiMap, have been made publicly available (Boehnke et al. 1991; Matise et al. 1994; Slonim et al. 1997).
Interpreting RH Maps
As discussed previously, the end result of RH map construction is a graphical representation of the vector distribution that most closely fits the results of statistical treatment. Unfortunately, for a given set of vectors, there is no unique statistically sound graphical representation. As shown in Figure 1, we analyzed the same set of vectors 10 times with the MultiMap program (Matise et al. 1994), varying only the initial pair of markers that were used. Comparison of the 10 maps shows they are not exactly the same. For instance, the most telomeric marker is marker 8 in six maps, marker 17 in three maps, and marker 13 in the last map. Figure 1 also shows that marker 12 is mapped at four different positions: 2, 3, 11, and 15. Other discrepancies between the 10 maps can be detected in Figure 1.
General Principles of RH Map Construction
Two methods, classified as nonparametric and parametric, are widely used in constructing RH maps. Nonparametric methods utilized by programs such as RHMAP, developed by M. Boehnke (Boehnke et al. 1991), or a program developed by A. Ben-Dor (Ben-Dor and Chor 1997) try to determine the order of markers that minimizes the number of obligate chromosome breaks (OCB). These data are calculated by publicly available software based on the retention pattern of each marker. Parametric methods (MultiMap, RHMAPPER, RHMAP) (Boehnke et al. 1991; Matise et al. 1994; Slonim et al. 1997) are based on the comparison of the likelihood of several locus orders. Starting with a pair or triplet of markers, parametric approaches carry out local extension and perform local permutations of consecutive markers to produce the most likely marker order.
RH Mapping and the TSP Approach
In 2000 Agarwala et al. published an RH computation package using the CONCORDE algorithm, which utilizes the "traveling salesman problem" (TSP) approach for ordering markers within a specific region (Agarwala et al. 2000; Ben-Dor and Chor 1997). In the classic TSP problem, one attempts to determine the shortest route by which a series of cities can be visited without ever visiting the same city twice. In the mathematical adaptation of this problem to genome map construction, the cities correspond to the markers and the cost to the distances. The TSP/CONCORDE algorithm systematically computes five independent RH maps. Three are variants of the maximum likelihood estimate (MLE) approach and two of the OCB approach. Agarwala et al. (2000) described the TSP/CONCORDE package as an improved option to compute maps, resulting in marker orders with higher MLE and lower OCB values. In this particular case, the analysis is mostly insensitive to the initial RH data file and the final map orders are independent of the initial format of the data set (alphabetical order or reverse, etc.), as marker order is determined using large neighborhood rearrangements rather than local permutations. Thus the work represents a major step forward in RH mapping software.
Constructing Canine RH Maps
We are presently using the TSP/CONCORDE package to order the 3,270 markers that make up the most recent version of the whole-genome canine RH map (Guyon et al., in preparation). Figure 3 shows an example of the type of results we have obtained thus far. In contrast to the example presented in Figure 1, the five TSP maps are derived using both principles—that is, the MLE approach for the first three maps, which has three independent parameter settings, and the OCB approach, which has two independent settings to compute the two OCB maps. In its original presentation, the TSP/CONCORDE package (Agarwala et al. 2000) presents the results as five independent maps, systematically and automatically generated from the same set of RH data. We developed an additional feature that evaluates the five maps and calculates a consensus map. Our method consists of determining the frequency of the position of a given marker over the five variant maps. When the position of a marker is concordant between the five maps, the placement is considered to have a high confidence level and is assigned a support score of 100%. By comparison, any marker displaying a concordant position in only three maps is assigned a 60% confidence level. We then generate a consensus map containing the markers placed at their best position determined by the position frequency calculated among the five TSP maps, as represented in Figure 3. Markers with a high confidence support are very likely to be mapped at a robust position, whereas markers present less than three times at the same position in the five maps (less than 60% confidence support) are considered questionable.
|
Occasionally a single marker will be placed at two different positions, revealing a major mapping conflict. Since presentation of the results as a consensus map is prone to mask regions where a certain level of uncertainty exists, we include a graphical representation of the best position data for each marker. This will allow map users to immediately spot regions with high statistical support, as well as those for which less confidence can be obtained. Of interest is that quite often, even if the scrambled region is made of several markers, it can be subdivided in smaller subregions of two to four markers (Figure 4a). At this stage it is not necessary to account for this slight scrambling; all markers have been typed twice and demonstrate results above a predefined quality threshold. As shown in Figure 4b, by exclusively recomputing the vectors of the 12 markers present between positions 13 and 25 with the TSP/CONCORDE package, more marker placements are now concordant between the five maps.
|
One final strategy we propose to use for solving construction problems in difficult regions is to repeat the two-point analysis using MultiMap, but with a higher LOD score than used previously (i.e., 9, 10, or even higher), if the first one was done at LOD 8. When this is done, more than one RH group often results, dividing the chromosome into two to three RH groups. These individual RH groups can often be ordered in a more satisfactory way with TSP/CONCORDE. Alternatively, or in addition, a two-point analysis performed with a higher LOD score threshold might eject markers with dubious vectors, thus facilitating subsequent correct ordering of the novel RH groups.
|
Conclusion |
|---|
|
TopAbstractConclusionReferences |
|---|
It is still too early to judge the merits of the TSP/CONCORDE package in RH mapping relative to other programs such as MultiMap and RHMAPPER, which have been extensively used for previous map construction. (Avner et al. 2001; Breen et al. 2001; Deloukas et al. 1998; Mellersh et al. 2000; Murphy et al. 2000; Priat et al. 1998; Stewart et al. 1997). However, the advantages we presently perceive manifest themselves at both map construction and map utilization levels. During map construction, this program acts as an automatic alert, highlighting construction problems. Such problems can then be solved by regional recomputing and identifying problematic vectors. Obviously, as shown in Figure 1, several computations of the same vectors can, in principle, be done with another program, resulting in delineation of problematic regions. But then this is done using a unique approach and each time with the same parameter setting. In addition, such multiple computations are not made automatically and necessitate a program adaptation. At the level of map utilization, graphical representation of the five maps and display of the name of the markers immediately tell users what confidence they may have in the map and where problems may still exist.
|
Acknowledgments |
|---|
We thank Richa Agarwala and Alejandro Schaffer for their help with the TSP/CONCORDE package and for meaningful discussions. We thank Tara Matise for her help with MultiMap. We gratefully acknowledge the support of the American Kennel Club Canine Health Foundation, the U.S. Army (grant no. DAAD19-01-1-0658; to E.A.O. and F.G.), the National Institutes of Health (grant no. 1R01CA092167; to E.A.O. and F.G.), and PHS National Research Grant T32 GM07270 (to H.G.P.). R. Guyon is supported by a fellowship from La Region de Bretagne and L. Kim is supported by a fellowship from Nestlé Purina. The TSP/CONCORDE package is available at ftp://ftp.ncbi.nih.gov/pub/agarwala/rhmapping/rh_tsp_map.tar.gz. This paper was delivered at the Advances in Canine and Feline Genomics symposium, St. Louis, MO, May 16–19, 2002.
|
Footnotes |
|---|
Corresponding Editor: William Murphy
Received July 18, 2002
Accepted October 9, 2002
|
References |
|---|
|
TopAbstractConclusionReferences |
|---|
-
Agarwala R, Applegate DL, Maglott D, Schuler GD, Schaffer AA, 2000. A fast and scalable radiation hybrid map construction and integration strategy. Genome Res. 3:350-364.
Avner P, Bruls T, Poras I, Eley L, Gas S, Ruiz P, Wiles MV, Sousa-Nunes R, Kettleborough R, Rana A, Morissette J, Bentley L, Goldsworthy M, Haynes A, Herbert E, Southam L, Lehrach H, Weissenbach J, Manenti G, Rodriguez-Tome P, Beddington R, Dunwoodie S, Cox RD, 2001. A radiation hybrid transcript map of the mouse genome. Nat Genet. 29:194-200.[CrossRef][ISI][Medline]
Ben-Dor A, Chor B, 1997. On constructing radiation hybrid maps. J Comput Biol. 4:517-533.[ISI][Medline]
Boehnke M, Lange K, Cox DR, 1991. Statistical methods for multipoint radiation hybrid mapping. Am J Hum Genet. 49:1174-1188.[ISI][Medline]
Breen M, Jouquand S, Renier C, Mellersh CS, Hitte C, Holmes NG, Chéron A, Suter N, Vignaux F, Bristow AE, Priat C, McCann E, Andre C, Boundy S, Gitsham P, Thomas R, Bridge W, Spriggs HF, Ryder EJ, Curson A, Sampson J, Ostrander EA, Binns M, Galibert F, 2001. Chromosome-specific single-locus fish probes allow anchorage of an 1800-marker integrated radiation-hybrid/linkage map of the domestic dog genome to all chromosomes. Genome Res. 11:1784-1795.
Cox DR, Burmeister M, Price ER, Kim S, Myers RM, 1990. Radiation hybrid mapping: a somatic cell genetic method for constructing high-resolution maps of mammalian chromosomes. Science. 250:245-250.
Deloukas P, Schuler GD, Gyapay G, Beasley EM, Soderlund C, Rodriguez-Tome P, Hui L, Matise TC, McKusick KB, Beckmann JS, Bentolila S, Bihoreau M, Birren BB, Browne J, Butler A, Castle AB, Chiannilkulchai N, Clee C, Day PJ, Dehejia A, Dibling T, Drouot N, Duprat S, Fizames C, Bentley DR, et al., 1998. A physical map of 30,000 human genes. Science. 282:744-746.
Goss SJ, Harris H, 1975. New method for mapping genes in human chromosomes. Nature. 255:680-684.[CrossRef][Medline]
Matise TC, Perlin M, Chakravarti A, 1994. Automated construction of genetic linkage maps using an expert system (MultiMap): a human genome linkage map. Nat Genet. 4:384-90.
McCarthy LC, 1996. Whole genome radiation hybrid mapping. Trends Genet. 12:491-493.[CrossRef][ISI][Medline]
Mellersh CS, Hitte C, Richman M, Vignaux F, Priat C, Jouquand S, Werner P, Andre C, DeRose S, Patterson DF, Ostrander EA, Galibert F, 2000. An integrated linkage-radiation hybrid map of the canine genome. Mamm Genome. 11:120-130.[CrossRef][ISI][Medline]
Murphy WJ, Sun S, Chen Z, Yuhki N, Hirschmann D, Menotti-Raymond M, O'Brien SJ, 2000. A radiation hybrid map of the cat genome: implications for comparative mapping. Genome Res. 5:691-702.
Priat C, Hitte C, Vignaux F, Renier C, Jiang Z, Jouquand S, Cheron A, Andre C, Galibert F, 1998. A whole-genome radiation hybrid map of the dog genome. Genomics. 54:361-378.[CrossRef][ISI][Medline]
Slonim D, Kruglyak L, Stein L, Lander E, 1997. Building human genome maps with radiation hybrids. J Comput Biol. 4:487-504.[ISI][Medline]
Stewart EA, McKusick KB, Aggarwal A, Bajorek E, Brady S, Chu A, Fang N, Hadley D, Harris M, Hussain S, Lee R, Maratukulam A, O'Connor K, Perkins S, Piercy M, Qin F, Reif Y, Sanders C, She X, Sun W-L, Tabar P, Voyticky S, Cowles S, Fan J-B, Mader C, Quackenbush J, Myers RM, and Cox DR, 1997. An STS-based radiation hybrid map of the human genome. Genome Res. 7:422-433.
Vignaux F, Hitte C, Priat C, Chuat JC, André C, Galibert F, 1999. Construction and optimization of a dog whole-genome radiation hybrid panel. Mamm Genome. 10:888-894.[CrossRef][ISI][Medline]
Walter MA, Spillett DJ, Thomas P, Weissenbach J, Goodfellow PN, 1994. A method for constructing radiation hybrid maps of whole genomes. Nat Genet. 7:22-28.[CrossRef][ISI][Medline]
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. A. Schaffer, E. S. Rice, W. Cook, and R. Agarwala rh_tsp_map 3.0: end-to-end radiation hybrid mapping with improved speed and quality control Bioinformatics, May 1, 2007; 23(9): 1156 - 1158. [Abstract] [Full Text] [PDF]
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||