New high throughput DNA technologies resulted in a disproportion between the high number of scored markers for the mapping populations and relatively small sizes of the genotyped populations. Correspondingly, the number of markers may, by orders of magnitude, exceed the threshold of recombination resolution achievable for a given population size. Hence, only a small part of markers can be genuinely ordered in the map. The question is how to choose the most informative markers for building such a reliable “skeleton” map. We believe that our approach provides a solution to this difficult problem due to: a) powerful tools of discrete optimization for multilocus ordering; b) a verification procedure, which is impossible without fast and high-quality optimization, to control the map quality based on re-sampling techniques; c) an interactive algorithm of marker clustering in complicated situations caused by significant deviation of recombination rates between markers of non-homologous chromosomes from the expected 50% (referred to as quasi-linkage or pseudo-linkage); and d) an algorithm for detection and removing excessive markers to increase the stability of multilocus ordering.
Lander, E.S. and Green, P. (1987) Construction of multilocus linkage maps in human. Proceedings of the National Academy of Science, USA, 84(8), 2363-2367.
Stam, P. (1993) Construction of integrated genetic linkage maps by means of a new computer package: JoinMap. Plant Journal, 3(5), 739-744.
Sapre, A.B. and Deshpande, D.S. (1987) Spontaneous emergence of parents from the F1 interspecific hybrids of Coix L. Journal of Heredity, 78(6), 357-360
Korol, A.B., Preygel, I.A. and Preygel, S.I. (1994) Recombination variability and evolution. Chapman & Hall, London.
Peng, J., Korol, A.B., Fahima, T., Roder M.S., Ronin, Y. I., Li, Y.C. and Nevo, E. (2000) Molecular genetic maps in wild emmer wheat, Triticum dicoccoides: genomewide coverage, massive negative interference, and putative quasi-linkage. Genome Research. 10(10), 1509-1531.
Korol, A.B., Shirak, A., Cnaani, A. and Hallerman, E.M. (2007) Detection and analysis of QTLs for economic traits in aquatic species. In: Liu, Z.J., Ed., Aquaculture Genome Technologies. Blackwell, Oxford, 169-197.
Nilsson, N.O., Säll, T. and Bengtsson, B.O. (1993) Chiasma and recombination data in plants: are they compatible? Trends in Genetics, 9(10), 344-348.
Anderson, L.K., Doyle, G. G., Brigham, B., Carter, J., Hooker, K. D., Lai, A., Rice, M. and Stack, S.M. (2003) High-resolution crossover maps for each bivalent of Zea mays using recombination nodules. Genetics, 165(2), 849-865.
Korol, A.B., Mester, D., Frenkel, Z. and Ronin, Y.I. (2009) Methods for genetic analysis in the Triticeae. Chapter 6, In: Feuillet, C. and Muehlbauer, G.J., Eds., Genetics and Genomics of the Triticeae. Springer, Berlin, pp. 163-199.
Esch, E., and Weber, W.E. (2002) Investigation of crossover interference in barley (Hordeum vulgare L.) using the coefficient of coincidence. Theoretical and Applied Genetics, 104(5), 786-796.
Mester, D., Ronin, Y., Minkov, D., Nevo, E. and Korol, A. (2003b) Constructing large scale genetic maps using an evolutionary strategy algorithm. Genetics, 165(4), 22692282.
Efron, B. (1979) Bootstrap method: Another look at the jackknife. The Annals of Statistics, 7(1), 1-26.
Efron, B. and Tibshirani, R.J. (1993) An introduction to the bootstrap. Chapman and Hall, New York.
Mester, D. and Braysy, O. (2005) Active guided evolution strategies for large-scale vehicle routing problems with time windows. Computers & Operation Research 32(6), 1593-1614.
Mester, D.I., Ronin, Y.I., Nevo, E. and Korol, A.B. (2004) Fast and high precision algorithms for optimization in large scale genomic problems. Computational Biology and Chemistry, 28(4), 281-290.
Fu, Y., Wen, T.J., Ronin, Y.I., Chen, H.D., Guo, L., Mester, D.I., Yang, Y.J., Lee, M., Korol, A.B., Ashlock D. A., et al. (2006) Genetic dissection of maize intermated recombinant inbred lines. Genetics, 174(3), 1671-1683.
Liu, B.H. (1998) Statistical genomics: Linkage, mapping, and QTL analysis. CRC Press, New York.
Jansen, J., de Jong, A.G. and Ooijen, J.W. (2001) Constructing dense genetic linkage maps. Theoretical and Applied Genetics, 102(6-7), 1113-1122.
Mester, D.I., Ronin, Y.I., Hu, Y., Peng, J., Nevo, E. and Korol, A.B. (2003a) Efficient multipoint mapping: Making use of dominant repulsion-phase markers. Theoretical and Applied Genetics, 107(6), 1002-1112.
Korol, A.B. (2001) Recombination. In: Encyclopedia of Biodiversity. Vol. 5, Academic Press, San Diego, pp. 53-71.
Sakamoto, T., Danzmann, R.G., Gharbi, K., Howard, P., Ozaki, A., Khoo, S.K., Woram, R.A., Okamoto, N., Ferguson, M.M., Holm, L.E., et al. (2000) A microsatellite linkage map of rainbow trout (Oncorhynchus mykiss) characterized by large sex-specific differences in recombination rates. Genetics, 155(3), 1331-1345.
Sivagnanasundaram, S., Broman, K.W., Liu, M. and Petronis, A. (2004) Quasi-linkage: A confounding factor in linkage analysis of complex diseases? Hum Genet, 114(6), 588-593.
Morrell, P.L., Toleno, D.M., Lundy, K.E., and Clegg, M. T. (2006) Estimating the contribution of mutation, recombination and gene conversion in the generation of haplotypic diversity. Genetics, 173(3), 1705-1723.
Plagnol, V., Padhukasahasram, B., Wall, J.D., Marjoram, P. and Nordborg, M. (2006) Relative influences of crossing over and gene conversion on the pattern of linkage disequilibrium in Arabidopsis thaliana. Genetics, 172(4), 2441-2448.
Dodds, K.G., Ball, R., Djorovic, N. and Carson, S.D. (2004) The effect of an imprecise map on interval mapping QTLs. Genetical Research, 84(1), 47-55.
Mester, D.I., Ronin, Y.I., Korostishevsky, M.A., Pikus, V. L., Glazman, A.E. and Korol, A.B. (2006) Multilocus consensus genetic maps (MCGM): Formulation, algorithms, and results. Computational Biology and Chemistry, 30(1), 12-20.
Hitte, C., Lorentzen, T.D., Guyon, R., Kim, L., Cadieu, E., Parker, H.G., Quignon, P., Lowe, J.K., Gelfenbeyn, B., Andre, C., et al. (2003) Comparison of MultiMap and TSP/CONCORDE for constructing radiation hybrid maps. Journal of Heredity, 94(1), 9-13.
Menotti-Raymond, M., David, V.A., Chen, Z.Q., Menotti, K.A., Sun, S., Schaffer, A.A., Agarwala, R., Tomlin, J.F., O’Brien, S.J. and Murphy, W.J. (2003) Second-generation integrated genetic linkage/radiation hybrid maps of the domestic cat (Felis catus). Journal of Heredity, 94(1), 95-106.
Dantzig, G., Fulkerson, R. and Johnson, S. (1954) Solution of a large-scale traveling salesman problem. Operations Research, 2, 393-410.
Appligate, D., Bixby, R., Chvatal V. and Cook, W. (1998) On the solution of traveling salesman problem. Documenta mathematica, extra volume International Congress of Mathematics III, 645-656.
Cook, W. and Rich, J.L. (1999) A parallel cutting-plane algorithm for vehicle routing problem with time window. Grant working, Princeton University, USA.
Appligate, D., Cook, W., Dash, S. and Rohe, A. (2002) Solution of Min-Max vehicle routing problem. INFORMS Journal on Computing, 14(2), 132-143.
Voudouris, C. (1997) Guided local search for combinatorial problems, Ph.D. thesis, Department of Computer Science, University of Essex, Colchester.
Tsang, E. and Voudouris, C. (1997) Fast local search and guided local search and their application to British telecom’s workforce scheduling problem. Operations Research Letters, 20(3), 119-127.