Bioinformatics Advance Access originally published online on December 14, 2004
Bioinformatics 2005 21(8):1703-1704; doi:10.1093/bioinformatics/bti222
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
CARHTA GENE: multipopulation integrated genetic and radiation hybrid mapping
INRA, Biométrie et Intelligence Artificielle/Génétique Cellulaire BP 27, 31326 Castanet-Tolosan Cedex, France
*To whom correspondence should be addressed.
 |
Abstract |
|---|
 TOP Abstract INTRODUCTIONMETHODSIMPLEMENTATIONREFERENCES |
|---|
Summary: CARHTA GENE: is an integrated genetic and radiation hybrid (RH) mapping tool which can deal with multiple populations, including mixtures of genetic and RH data. CARHTA GENE: performs multipoint maximum likelihood estimations with accelerated expectation–maximization algorithms for some pedigrees and has sophisticated algorithms for marker ordering. Dedicated heuristics for framework mapping are also included. CARHTA GENE: can be used as a C++ library, through a shell command and a graphical interface. The XML output for companion tools is integrated.
Availability: The program is available free of charge from www.inra.fr/bia/T/CarthaGene for Linux, Windows and Solaris machines (with Open Source).
Contact: tschiex{at}toulouse.inra.fr
|
INTRODUCTION |
|---|
|
TOPAbstractINTRODUCTIONMETHODSIMPLEMENTATIONREFERENCES |
|---|
The genetic mapping technique is used to locate polymorphic markers on chromosomes by making use of a probabilistic model of crossing-over. Many genetic mapping tools are available to analyze data in experimental crosses. Most of them are designed to analyze line crosses, one family at a time; few can integrate data from several crosses to build consensus maps (see http://linkage.rockfeller.edu/soft).
Radiation hybrid (RH) mapping is a somatic cell technique that complements the genetic mapping technique, allowing for finer resolution. Most existing RH mapping packages are listed at compgen.rutgers.edu/rhmap
Although capable of handling line crosses, CARHTA GENE has been designed to create consensus maps from multiple populations. Instead of directly integrating existing maps, CARHTA GENE computes maximum multipoint likelihood maps, taking into account all the available information, offering additional reliability. It can integrate RH and genetic data together.
|
METHODS |
|---|
|
TOPAbstractINTRODUCTIONMETHODSIMPLEMENTATIONREFERENCES |
|---|
Parametric probabilistic HMM based models for crossover during meiosis (Lander et al., 1987) and for chromosome breakage and retention during RH panel construction (Lange et al., 1995) include parameters such as recombination and breakage probabilities between adjacent markers as well as retention probability. Given experimental data, and assuming some marker ordering, the values of these parameters can be estimated by maximizing the probability that the data observed has been generated by the model. This likelihood therefore allows simultaneous evaluation of the assumed marker ordering and estimation of the corresponding parameters (distances). This is done by a so-called expectation–maximization (EM) algorithm. Models for backcross, f2 intercross, recombinant inbred lines (self and sibs) and phase-known outbreds are available. For RH estimation, the equal retention model both in its haploid and diploid forms is used. The EM forward–backward algorithm used in CARHTA GENE has been accelerated by taking into account specific properties of backcross and haploid RH data (see Schiex et al., 2001). Compared with usual EM implementations, the accelerated algorithm can run one or two orders of magnitude faster with no loss of precision.
CARHTA GENE provides two ways to merge data files:
- If one assumes that the data merged represents a single map (same order and distances, either genetic or RH), a so-called genetic merging is done. Untyped markers in a population/panel are considered as missing data and one consensus map is produced. RH and genetic data cannot be merged under this model because they use different distances.
- Otherwise, it is assumed that the data files are representative of maps with a common marker ordering but specific distances per dataset. Here, a single consensus ordering is produced but a specific set of distances is estimated for each model merged. Any type of data, genetic or RH, can be merged here. This is called order merging. These two methods can be combined freely.
For genetic merging, the EM implementation deals with combined datasets by performing an E computation on each dataset and then using an M step that takes into account the merging performed. For datasets merged by order, independent log-likelihoods are obtained per dataset and summed up.
The main problem in genetic or RH mapping arises from the number of possible marker orders. For n markers, there exists n!/2 different possible orders. Since the connection between mapping and the traveling salesman problem (TSP) is well known for genetic mapping (Schiex and Gaspin, 1997 www.inra.fr/bia/T/CartaGene) and for RH mapping, (Ben-Dor et al., 2000) CARHTA GENE relies on this connection and provides extensions of TSP solving algorithms:
- Fast heuristics (e.g. nearest neighbor) using 2-point information for guidance and multipoint estimations for final evaluation.
- More powerful meta-heuristics (e.g. simulated annealing and taboo search) directly using multipoint maximum likelihood as the optimization criterion.
- Even more efficient pure TSP heuristics such as the Lin-Kernighan heuristic (LKH) (Lin and Kernighan, 1973), using the LKH implementation (Helsgaun, 2000, http://www.dat.ruc.dk/keld/research/LKH). These algorithms can use either multiple 2-point maximum likelihood or obligate chromosome breaks (Ben-Dor et al., 2000; Agarwala et al., 2000) to define optimal maps. All the maps identified in this way are then evaluated using a multipoint EM based estimation.
- Finally, dedicated heuristics for framework mapping, duplicated marker detection and map validation.
A unique feature of CARHTA GENE is that, instead of producing a single supposedly optimal map, it produces an ordered set of alternative maps which allows an estimation of the reliability of ordering of each marker. The set of all these maps can be explored manually and compared graphically (with a Postscript output; Fig. 1). Dedicated automatic tools facilitate the identification of unreliable markers for further analysis.
|
Final maps can be produced under MapMaker (Lander et al., 1987) and XML formats for data exchange with MCQTL (Jourjon et al., 2004) (a multiple population QTL mapping software) and BioMercator (Arcade et al., 2004) (a software for integrating genetic maps and QTL detected in independent experiments).
|
IMPLEMENTATION |
|---|
|
TOPAbstractINTRODUCTIONMETHODSIMPLEMENTATIONREFERENCES |
|---|
CARHTA GENE is implemented as a C++ library. A Tcl programable shell command for automated mapping is available and a graphical Tcl/Tk interface for interactive mapping. Binaries for Windows, Solaris and Linux are provided with an open source distribution (using the G-Forge site mulcyber.toulouse.inra.fr).
|
Acknowledgments |
|---|
This work was supported by GENOPLANTE project ‘Integrative Tools for Genetic Mapping’.
Received on September 14, 2004; revised on November 3, 2004; accepted on November 3, 2004
|
REFERENCES |
|---|
|
TOPAbstractINTRODUCTIONMETHODSIMPLEMENTATIONREFERENCES |
|---|
Agarwala, R., Applegate, D.L., Maglott, D., Schuler, G.D., Schaffer, A.A. (2000) A fast and scalable radiation hybrid map construction and integration strategy. Genome Res., 10, 350–364
Arcade, A., Labourdette, A., Falque, M., Mangin, B., Chardon, F., Charcosset, A., Joets, J. (2004) Biomercator: integrating genetic maps and QTL towards discovery of candidate genes. Bioinformatics, 20, 2324–2326
Ben-Dor, A., Chor, B., Pelleg, D. (2000) RHO—radiation hybrid ordering. Genome Res., 10, 365–378
Helsgaun, K. (2000) An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res., 126, 106–130[CrossRef].
Jourjon, M.-F., Jasson, S., Marcel, J., Ngom, B., Mangin, B. (2004) MCQTL: Multi-allelic QTL mapping in multi-cross design. Bioinformatics, 21, 128–130.
Lander, E.S., Green, P., Abrahamson, J., Barlow, A., Daly, M.J., Lincoln, S.E., Newburg, L. (1987) MAPMAKER: an interactive computer package for constructing primary genetic linkage maps of experimental and natural populations. Genomics, 1, 174–181[CrossRef][Medline].
Lange, K., Boehnke, M., Cox, D.R., Lunetta, K.L. (1995) Statistical methods for polyploid radiation hybrid mapping. Genome Res., 5, 136–150
Lin, S. and Kernighan, B.W. (1973) An effective heuristic algorithm for the traveling salesman problem. Oper. Res., 21, 498–516[CrossRef].
Schiex, T. and Gaspin, C. (1997) Cartagene: constructing and joining maximum likelihood genetic maps. Proceedings of ISMB'97, , Halkidiki, Greece Porto Carras, pp. 258–267.
Schiex, T., Chabrier, P., Bouchez, M., Milan, D. (2001) Boosting EM for radiation hybrid and genetic mapping. Proceedings of WABI'01, , pp. 41–51 vol. 2149 LNCS.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  D. P. Reid, C.-A. Smith, M. Rommens, B. Blanchard, D. Martin-Robichaud, and M. Reith A Genetic Linkage Map of Atlantic Halibut (Hippoglossus hippoglossus L.) Genetics, October 1, 2007; 177(2): 1193 - 1205. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. A. Cartwright, M. Troggio, R. Velasco, and A. Gutin Genetic Mapping in the Presence of Genotyping Errors Genetics, August 1, 2007; 176(4): 2521 - 2527. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Z. Granevitze, S. Blum, H. Cheng, A. Vignal, M. Morisson, G. Ben-Ari, L. David, M. W. Feldman, S. Weigend, and J. Hillel Female-Specific DNA Sequences in the Chicken Genome J. Hered., May 1, 2007; 98(3): 238 - 242. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 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]
|
|
|
|
|
|
K. Gharbi, A. Gautier, R. G. Danzmann, S. Gharbi, T. Sakamoto, B. Hoyheim, J. B. Taggart, M. Cairney, R. Powell, F. Krieg, et al. A Linkage Map for Brown Trout (Salmo trutta): Chromosome Homeologies and Comparative Genome Organization With Other Salmonid Fish Genetics, April 1, 2006; 172(4): 2405 - 2419. [Abstract] [Full Text] [PDF]
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||