Constructing Large-Scale Genetic Maps Using an Evolutionary Strategy Algorithm

Corresponding author: A. Korol, University of Haifa, Haifa 31905, Israel., korol{at}esti.haifa.ac.il (E-mail)

Communicating editor: G. CHURCHILL

This article is devoted to the problem of ordering in linkage groups with many dozens or even hundreds of markers. The ordering problem belongs to the field of discrete optimization on a set of all possible orders, amounting to n!/2 for n loci; hence it is considered an NP-hard problem. Several authors attempted to employ the methods developed in the well-known traveling salesman problem (TSP) for multilocus ordering, using the assumption that for a set of linked loci the true order will be the one that minimizes the total length of the linkage group. A novel, fast, and reliable algorithm developed for the TSP and based on evolution-strategy discrete optimization was applied in this study for multilocus ordering on the basis of pairwise recombination frequencies. The quality of derived maps under various complications (dominant vs. codominant markers, marker misclassification, negative and positive interference, and missing data) was analyzed using simulated data with 50–400 markers. High performance of the employed algorithm allows systematic treatment of the problem of verification of the obtained multilocus orders on the basis of computing-intensive bootstrap and/or jackknife approaches for detecting and removing questionable marker scores, thereby stabilizing the resulting maps. Parallel calculation technology can easily be adopted for further acceleration of the proposed algorithm. Real data analysis (on maize chromosome 1 with 230 markers) is provided to illustrate the proposed methodology.

This article has been cited by other articles:

				O. Niehuis, A. K. Judson, and J. Gadau Cytonuclear Genic Incompatibilities Cause Increased Mortality in Male F2 Hybrids of Nasonia giraulti and N. vitripennis Genetics, January 1, 2008; 178(1): 413 - 426. [Abstract] [Full Text] [PDF]

				Y.-D. Tan and Y.-X. Fu A New Strategy for Estimating Recombination Fractions Between Dominant Markers From an F2 Population Genetics, February 1, 2007; 175(2): 923 - 931. [Abstract] [Full Text] [PDF]

				T. Faraut, S. de Givry, P. Chabrier, T. Derrien, F. Galibert, C. Hitte, and T. Schiex A comparative genome approach to marker ordering Bioinformatics, January 15, 2007; 23(2): e50 - e56. [Abstract] [Full Text] [PDF]

				Y. Fu, T.-J. Wen, Y. I. Ronin, H. D. Chen, L. Guo, D. I. Mester, Y. Yang, M. Lee, A. B. Korol, D. A. Ashlock, et al. Genetic Dissection of Intermated Recombinant Inbred Lines Using a New Genetic Map of Maize Genetics, November 1, 2006; 174(3): 1671 - 1683. [Abstract] [Full Text] [PDF]

				Y.-D. Tan and Y.-X. Fu A Novel Method for Estimating Linkage Maps Genetics, August 1, 2006; 173(4): 2383 - 2390. [Abstract] [Full Text] [PDF]

				J. Jansen Construction of Linkage Maps in Full-Sib Families of Diploid Outbreeding Species by Minimizing the Number of Recombinations in Hidden Inheritance Vectors Genetics, August 1, 2005; 170(4): 2013 - 2025. [Abstract] [Full Text] [PDF]

				R. Wu and C.-X. Ma A General Framework for Statistical Linkage Analysis in Multivalent Tetraploids Genetics, June 1, 2005; 170(2): 899 - 907. [Abstract] [Full Text] [PDF]

				C. F. Crane and Y. M. Crane A nearest-neighboring-end algorithm for genetic mapping Bioinformatics, April 15, 2005; 21(8): 1579 - 1591. [Abstract] [Full Text] [PDF]