Constructing large-scale genetic maps using an evolutionary strategy algorithm

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 approximately 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.     

An updated ‘Essex’ by ‘Forrest’ linkage map and first composite interval map of QTL underlying six soybean traits

DNA marker maps based on single populations are the basis for gene, loci and genomic analyses. Individual maps can be integrated to produce composite maps with higher marker densities if shared marker orders are consistent. However, estimates of marker order in composite maps must include sets of markers that were not polymorphic in multiple populations. Often some of the pooled markers were not codominant, or were not correctly scored. The soybean composite map was composed of data from five separate populations based on northern US germplasm but does not yet include ‘Essex’ by ‘Forrest’ recombinant inbred line (RIL) population (E × F) or any southern US soybean cultivars. The objectives were, to update the E × F map with codominant markers, to compare marker orders among this map, the Forrest physical map and the composite soybean map and to compare QTL identified by composite interval maps to the earlier interval maps. Two hundred and thirty seven markers were used to construct the core of the E × F map. The majority of marker orders were consistent between the maps. However, 19 putative marker inversions were detected on 12 of 20 linkage groups (LG). Eleven marker distance compressions were also found. The number of inverted markers ranged from 1 to 2 per LG. Thus, marker order inversions may be common in southern compared to northern US germplasm. A total of 61 QTL among 37 measures of six traits were detected by composite interval maps, interval maps and single point analysis. Seventeen of the QTL found in composite intervals had previously been detected among the 29 QTL found in simple interval maps. The genomic locations of the known QTL were more closely delimited. A genome sequencing project to compare Southern and Northern US soybean cultivars would catalog and delimit inverted regions and the associated QTL. Gene introgression in cultivar development programs would be accelerated.Electronic supplementary material Supplementary material is available in the online version of this article at and is accessible for authorized users.     

A new strategy for estimating recombination fractions between dominant markers from an F2 population

Although most high-density linkage maps have been constructed from codominant markers such as single-nucleotide polymorphisms (SNPs) and microsatellites due to their high linkage information, dominant markers can be expected to be even more significant as proteomic technique becomes widely applicable to generate protein polymorphism data from large samples. However, for dominant markers, two possible linkage phases between a pair of markers complicate the estimation of recombination fractions between markers and consequently the construction of linkage maps. The low linkage information of the repulsion phase and high linkage information of coupling phase have led geneticists to construct two separate but related linkage maps. To circumvent this problem, we proposed a new method for estimating the recombination fraction between markers, which greatly improves the accuracy of estimation through distinction between the coupling phase and the repulsion phase of the linked loci. The results obtained from both real and simulated F2 dominant marker data indicate that the recombination fractions estimated by the new method contain a large amount of linkage information for constructing a complete linkage map. In addition, the new method is also applicable to data with mixed types of markers (dominant and codominant) with unknown linkage phase.     

Multilocus Analysis for Gene-Centromere Mapping Using First Polar Bodies and Secondary Oocytes

Polar body and oocyte typing is a new technique for gene-centromere mapping and for generating female linkage maps. A maximum likelihood approach is presented for ordering multiple markers relative to the centromere and for estimating recombination frequencies between markers and between the centromere and marker loci. Three marker-centromere orders are possible for each pair of markers: two orders when the centromere flanks the two markers and one order when the centromere is flanked by the two markers. For each possible order, the likelihood was expressed as a function of recombination frequencies for two adjacent intervals. LOD score for recombination frequency between markers or between the centromere and a marker locus was derived based on the likelihood for each gene-centromere order. The methods developed herein provide a general solution to the problem of multilocus genecentromere mapping that involves all theoretical crossover possibilities, including four-strand double crossovers.     

Fast and Accurate Construction of Ultra-Dense Consensus Genetic Maps Using Evolution Strategy Optimization

Our aim was to develop a fast and accurate algorithm for constructing consensus genetic maps for chip-based SNP genotyping data with a high proportion of shared markers between mapping populations. Chip-based genotyping of SNP markers allows producing high-density genetic maps with a relatively standardized set of marker loci for different mapping populations. The availability of a standard high-throughput mapping platform simplifies consensus analysis by ignoring unique markers at the stage of consensus mapping thereby reducing mathematical complicity of the problem and in turn analyzing bigger size mapping data using global optimization criteria instead of local ones. Our three-phase analytical scheme includes automatic selection of ~100-300 of the most informative (resolvable by recombination) markers per linkage group, building a stable skeletal marker order for each data set and its verification using jackknife re-sampling, and consensus mapping analysis based on global optimization criterion. A novel Evolution Strategy optimization algorithm with a global optimization criterion presented in this paper is able to generate high quality, ultra-dense consensus maps, with many thousands of markers per genome. This algorithm utilizes "potentially good orders" in the initial solution and in the new mutation procedures that generate trial solutions, enabling to obtain a consensus order in reasonable time. The developed algorithm, tested on a wide range of simulated data and real world data (Arabidopsis), outperformed two tested state-of-the-art algorithms by mapping accuracy and computation time.     

RADtyping: An Integrated Package for Accurate De Novo Codominant and Dominant RAD Genotyping in Mapping Populations

Genetic linkage maps are indispensable tools in genetic, genomic and breeding studies. As one of genotyping-by-sequencing methods, RAD-Seq (restriction-site associated DNA sequencing) has gained particular popularity for construction of high-density linkage maps. Current RAD analytical tools are being predominantly used for typing codominant markers. However, no genotyping algorithm has been developed for dominant markers (resulting from recognition site disruption). Given their abundance in eukaryotic genomes, utilization of dominant markers would greatly diminish the extensive sequencing effort required for large-scale marker development. In this study, we established, for the first time, a novel statistical framework for de novo dominant genotyping in mapping populations. An integrated package called RADtyping was developed by incorporating both de novo codominant and dominant genotyping algorithms. We demonstrated the superb performance of RADtyping in achieving remarkably high genotyping accuracy based on simulated and real mapping datasets. The RADtyping package is freely available at http://www2.ouc.edu.cn/mollusk/ detailen.asp?id=727.     

High density SNP and SSR-based genetic maps of two independent oil palm hybrids

Background

Oil palm is an important perennial oil crop with an extremely long selection cycle of 10 to 12 years. As such, any tool that speeds up its genetic improvement process, such as marker-assisted breeding is invaluable. Previously, genetic linkage maps based on AFLP, RFLP and SSR markers were developed and QTLs for fatty acid composition and yield components identified. High density genetic maps of crosses of different genetic backgrounds are indispensable tools for investigating oil palm genetics. They are also useful for comparative mapping analyses to identify markers closely linked to traits of interest.

Results

A 4.5 K customized oil palm SNP array was developed using the Illumina Infinium platform. The SNPs and 252 SSRs were genotyped on two mapping populations, an intraspecific cross with 87 palms and an interspecific cross with 108 palms. Parental maps with 16 linkage groups (LGs), were constructed for the three fruit forms of E. guineensis (dura, pisifera and tenera). Map resolution was further increased by integrating the dura and pisifera maps into an intraspecific integrated map with 1,331 markers spanning 1,867 cM. We also report the first map of a Colombian E. oleifera, comprising 10 LGs with 65 markers spanning 471 cM. Although not very dense due to the high level of homozygosity in E. oleifera, the LGs were successfully integrated with the LGs of the tenera map. Direct comparison between the parental maps identified 603 transferable markers polymorphic in at least two of the parents. Further analysis revealed a high degree of marker transferability covering 1,075 cM, between the intra- and interspecific integrated maps. The interspecific cross displayed higher segregation distortion than the intraspecific cross. However, inclusion of distorted markers in the genetic maps did not disrupt the marker order and no map expansion was observed.

Conclusions

The high density SNP and SSR-based genetic maps reported in this paper have greatly improved marker density and genome coverage in comparison with the first reference map based on AFLP and SSR markers. Therefore, it is foreseen that they will be more useful for fine mapping of QTLs and whole genome association mapping studies in oil palm.

Electronic supplementary material

The online version of this article (doi:10.1186/1471-2164-15-309) contains supplementary material, which is available to authorized users.     

RECORD: a novel method for ordering loci on a genetic linkage map

A new method, REcombination Counting and ORDering (RECORD) is presented for the ordering of loci on genetic linkage maps. The method minimizes the total number of recombination events. The search algorithm is a heuristic procedure, combining elements of branch-and-bound with local reshuffling. Since the criterion we propose does not require intensive calculations, the algorithm rapidly produces an optimal ordering as well as a series of near-optimal ones. The latter provides insight into the local certainty of ordering along the map. A simulation study was performed to compare the performance of RECORD and JoinMap. RECORD is much faster and less sensitive to missing observations and scoring errors, since the optimisation criterion is less dependent on the position of the erroneous markers. In particular, RECORD performs better in regions of the map with high marker density. The implications of high marker densities on linkage map construction are discussed.     

Combination of multipoint maximum likelihood (MML) and regression mapping algorithms to construct a high-density genetic linkage map for loblolly pine (Pinus taeda L.)

Genetic maps have been successfully applied to assist in the dissection of complex traits, provide insight on genome structure, and estimate recombination in conjunction with physical maps. Despite an extensive list of genetic maps developed for loblolly pine (Pinus taeda L.) over the past two decades, a high-density consensus map has not yet been constructed. In this study, we used two reference three-generation outbred pedigrees, base and qtl, obtained from the North Carolina State University Cooperative Tree Improvement Program, to obtain a high-density genetic consensus map. Both populations were genotyped with ≈ 7,000 different markers (restriction fragment length polymorphisms, expressed sequence tag polymorphisms, simple sequence repeats, SNPs). The grouping, ordering, and spacing of the markers on each linkage group were performed with JoinMap® 4.1, which implements the multipoint maximum likelihood algorithm for outbred populations. The final consensus map contains 2,466 markers, with a total length of 1,476 centimorgans (cM). The average marker density across the 12 linkage groups was 0.62 cM/marker. This high-density map provides an important resource for breeders and geneticists and will enable comparative studies across species, as well as improve the loblolly pine genome sequence assembly.     

A novel Markov chain monte carlo approach for constructing accurate meiotic maps

Mapping markers from linkage data continues to be a task performed in many genetic epidemiological studies. Data collected in a study may be used to refine published map estimates and a study may use markers that do not appear in any published map. Furthermore, inaccuracies in meiotic maps can seriously bias linkage findings. To make best use of the available marker information, multilocus linkage analyses are performed. However, two computational issues greatly limit the number of markers currently mapped jointly; the number of candidate marker orders increases exponentially with marker number and computing exact multilocus likelihoods on general pedigrees is computationally demanding. In this article, a new Markov chain Monte Carlo (MCMC) approach that solves both these computational problems is presented. The MCMC approach allows many markers to be mapped jointly, using data observed on general pedigrees with unobserved individuals. The performance of the new mapping procedure is demonstrated through the analysis of simulated and real data. The MCMC procedure performs extremely well, even when there are millions of candidate orders, and gives results superior to those of CRI-MAP.     

SMOOTH: a statistical method for successful removal of genotyping errors from high-density genetic linkage data

High-density genetic linkage maps can be used for purposes such as fine-scale targeted gene cloning and anchoring of physical maps. However, their construction is significantly complicated by even relatively small amounts of scoring errors. Currently available software is not able to solve the ordering ambiguities in marker clusters, which inhibits the application of high-density maps. A statistical method named SMOOTH was developed to remove genotyping errors from genetic linkage data during the mapping process. The program SMOOTH calculates the difference between the observed and predicted values of data points based on data points of neighbouring loci in a given marker order. Highly improbable data points are removed by the program in an iterative process with a mapping algorithm that recalculates the map after cleaning. SMOOTH has been tested with simulated data and experimental mapping data from potato. The simulations prove that this method is able to detect a high amount of scoring errors and demonstrates that the program enables mapping software to successfully construct a very accurate high-density map. In potato the application of the program resulted in a reliable placement of nearly 1,000 markers in one linkage group.     

An integrated genetic linkage map of pepper (Capsicum spp.)

An integrated genetic map of pepper including 6 distinct progenies and consisting of 2262 markers covering 1832 cM was constructed using pooled data from six individual maps by the Keygene proprietary software package INTMAP. The map included: 1528 AFLP, 440 RFLP, 288 RAPD and several known gene sequences, isozymes and morphological markers. In total, 320 anchor markers (common markers in at least two individual maps) were used for map integration. Most anchor markers (265) were common to two maps, while 27, 26 and 5 markers were common to three, four and five maps, respectively. Map integration improved the average marker density in the genome to 1 marker per 0.8 cM compared to 1 marker per 2.1 cM in the most dense individual map. In addition, the number of gaps of at least 10 cM between adjacent markers was reduced in the integrated map. Although marker density and genome coverage were improved in the integrated map, several small linkage groups remained, indicating that further marker saturation will be needed in order to obtain a full coverage of the pepper genome. The integrated map can be used as a reference for future mapping studies in Capsicum and to improve the utilization of molecular markers for pepper breeding.These authors contributed equally to the work described in this paper(e-mail:     

A novel method for estimating linkage maps

The goal of linkage mapping is to find the true order of loci from a chromosome. Since the number of possible orders is large even for a modest number of loci, the problem of finding the optimal solution is known as a NP-hard problem or traveling salesman problem (TSP). Although a number of algorithms are available, many either are low in the accuracy of recovering the true order of loci or require tremendous amounts of computational resources, thus making them difficult to use for reconstructing a large-scale map. We developed in this article a novel method called unidirectional growth (UG) to help solve this problem. The UG algorithm sequentially constructs the linkage map on the basis of novel results about additive distance. It not only is fast but also has a very high accuracy in recovering the true order of loci according to our simulation studies. Since the UG method requires n-1 cycles to estimate the ordering of n loci, it is particularly useful for estimating linkage maps consisting of hundreds or even thousands of linked codominant loci on a chromosome.     

A Composite Linkage Map from Three Crosses Between Commercial Clones of Cacao, Theobroma cacao L.

In this paper, we report the construction of the first composite map of cacao from linkage data of one F₂ and two F₁ mapping populations with a high number of codominant markers in common. The combination of linkage information from all three maps results in the currently most precise estimates of marker locations and distances between markers, especially in densely marked areas. JoinMap®V4 software was used for all marker quality assessment and mapping. Individual (sub-composite) maps and the composite map contained 10 major linkage groups, corresponding to the number of cacao chromosomes. Homogeneity of marker placement was very high among sub-composite maps, the composite map, and the designated “reference” map. Care was exercised in the re-creation of sub-composite maps and the composite map to include only markers with acceptable mapping quality parameters. The composite map places more markers with higher precision than any individual map. This research clearly demonstrates for the first time a very high level of marker homogeneity among commercial cacao clones compared to other species. The observed homogeneity between different maps, including the composite one, is probably due to a narrow genetic base of commercial cacao clones. Markers linked to identified quantitative trait loci (QTLs) are more likely to retain linkage in other commercial clones, rendering the QTLs in cacao potentially more stable than in other species.     

A nearest-neighboring-end algorithm for genetic mapping

MOTIVATION: High-throughput methods are beginning to make possible the genotyping of thousands of loci in thousands of individuals, which could be useful for tightly associating phenotypes to candidate loci. Current mapping algorithms cannot handle so many data without building hierarchies of framework maps. RESULTS: A version of Kruskal's minimum spanning tree algorithm can solve any genetic mapping problem that can be stated as marker deletion from a set of linkage groups. These include backcross, recombinant inbred, haploid and double-cross recombinational populations, in addition to conventional deletion and radiation hybrid populations. The algorithm progressively joins linkage groups at increasing recombination fractions between terminal markers, and attempts to recognize and correct erroneous joins at peaks in recombination fraction. The algorithm is O (mn3) for m individuals and n markers, but the mean run time scales close to mn2. It is amenable to parallel processing and has recovered true map order in simulations of large backcross, recombinant inbred and deletion populations with up to 37,005 markers. Simulations were used to investigate map accuracy in response to population size, allelic dominance, segregation distortion, missing data and random typing errors. It produced accurate maps when marker distribution was sufficiently uniform, although segregation distortion could induce translocated marker orders. The algorithm was also used to map 1003 loci in the F7 ITMI population of bread wheat, Triticum aestivum L. emend Thell., where it shortened an existing standard map by 16%, but it failed to associate blocks of markers properly across gaps within linkage groups. This was because it depends upon the rankings of recombination fractions at individual markers, and is susceptible to sampling error, typing error and joint selection involving the terminal markers of nearly finished linkage groups. Therefore, the current form of the algorithm is useful mainly to improve local marker ordering in linkage groups obtained in other ways. AVAILABILITY: The source code and supplemental data are http://www.iubio.bio.indiana.edu/soft/molbio/qtl/flipper/ CONTACT: ccrane@purdue.edu.     

An international reference consensus genetic map with 897 marker loci based on 11 mapping populations for tetraploid groundnut (Arachis hypogaea L.)

Only a few genetic maps based on recombinant inbred line (RIL) and backcross (BC) populations have been developed for tetraploid groundnut. The marker density, however, is not very satisfactory especially in the context of large genome size (2800 Mb/1C) and 20 linkage groups (LGs). Therefore, using marker segregation data for 10 RILs and one BC population from the international groundnut community, with the help of common markers across different populations, a reference consensus genetic map has been developed. This map is comprised of 897 marker loci including 895 simple sequence repeat (SSR) and 2 cleaved amplified polymorphic sequence (CAPS) loci distributed on 20 LGs (a01-a10 and b01-b10) spanning a map distance of 3, 863.6 cM with an average map density of 4.4 cM. The highest numbers of markers (70) were integrated on a01 and the least number of markers (21) on b09. The marker density, however, was lowest (6.4 cM) on a08 and highest (2.5 cM) on a01. The reference consensus map has been divided into 20 cM long 203 BINs. These BINs carry 1 (a10_02, a10_08 and a10_09) to 20 (a10_04) loci with an average of 4 marker loci per BIN. Although the polymorphism information content (PIC) value was available for 526 markers in 190 BINs, 36 and 111 BINs have at least one marker with >0.70 and >0.50 PIC values, respectively. This information will be useful for selecting highly informative and uniformly distributed markers for developing new genetic maps, background selection and diversity analysis. Most importantly, this reference consensus map will serve as a reliable reference for aligning new genetic and physical maps, performing QTL analysis in a multi-populations design, evaluating the genetic background effect on QTL expression, and serving other genetic and molecular breeding activities in groundnut.     

Towards a unified genetic map for diploid roses

We have constructed the first integrated consensus map (ICM) for rose, based on the information of four diploid populations and more than 1,000 initial markers. The single population maps are linked via 59 bridge markers, on average 8.4 per linkage group (LG). The integrated map comprises 597 markers, 206 of which are sequence-based, distributed over a length of 530?cM on seven LGs. By using a larger effective population size and therefore higher marker density, the marker order in the ICM is more reliable than in the single population maps. This is supported by a more even marker distribution and a decrease in gap sizes in the consensus map as compared to the single population maps. This unified map establishes a standard nomenclature for rose LGs, and presents the location of important ornamental traits, such as self-incompatibility, black spot resistance (Rdr1), scent production and recurrent blooming. In total, the consensus map includes locations for 10 phenotypic single loci, QTLs for 7 different traits and 51 ESTs or gene-based molecular markers. This consensus map combines for the first time the information for traits with high relevance for rose variety development. It will serve as a tool for selective breeding and marker assisted selection. It will benefit future efforts of the rose community to sequence the whole rose genome and will be useful for synteny studies in the Rosaceae family and especially in the section Rosoideae.     

Comparing EST-based genetic maps between <Emphasis Type="BoldItalic">Pinus sylvestris</Emphasis> and <Emphasis Type="BoldItalic">Pinus taeda</Emphasis>

A genetic map of Pinus sylvestris was constructed using ESTP (expressed sequence tag polymorphism) markers and other gene-based markers, AFLP markers and microsatellites. Part of the ESTP markers (40) were developed and mapped earlier in Pinus taeda, and additional markers were generated based on P. sylvestris sequences or sequences from other pine species. The mapping in P. sylvestris was based on 94 F₁ progeny from a cross between plus-tree parents E635C and E1101. AFLP framework maps for the parent trees were first constructed. The ESTP and other gene sequence-based markers were added to the framework maps, as well as five published microsatellite loci. The separate maps were then integrated with the aid of AFLPs segregating in both trees (dominant segregation ratios 3:1) as well as gene markers and microsatellites segregating in both parent trees (segregation ratios 1:1:1:1 or 1:2:1). The integrated map consisted of 12 groups corresponding to the P. taeda linkage groups, and additionally three and six smaller groups for E1101 and E635C, respectively. The number of framework AFLP markers in the integrated map is altogether 194 and the number of gene markers 61. The total length of the integrated map was 1,314 cM. The set of markers developed for P. sylvestris was also added to existing maps of two P. taeda pedigrees. Starting with a mapped marker from one pedigree in the source species resulted in a mapped marker in a pedigree of the other species in more than 40% of the cases, with about equal success in both directions. The maps of the two species are largely colinear, even if the species have diverged more than 70 MYA. Most cases of different locations were probably due to problems in identifying the orthologous members of gene families. These data provide a first ESTP-containing map of P. sylvestris, which can also be used for comparing this species to additional species mapped with the same markers.Communicated by C. Möllers     

Construction of a genetic linkage map in tetraploid species using molecular markers

This article presents methodology for the construction of a linkage map in an autotetraploid species, using either codominant or dominant molecular markers scored on two parents and their full-sib progeny. The steps of the analysis are as follows: identification of parental genotypes from the parental and offspring phenotypes; testing for independent segregation of markers; partition of markers into linkage groups using cluster analysis; maximum-likelihood estimation of the phase, recombination frequency, and LOD score for all pairs of markers in the same linkage group using the EM algorithm; ordering the markers and estimating distances between them; and reconstructing their linkage phases. The information from different marker configurations about the recombination frequency is examined and found to vary considerably, depending on the number of different alleles, the number of alleles shared by the parents, and the phase of the markers. The methods are applied to a simulated data set and to a small set of SSR and AFLP markers scored in a full-sib population of tetraploid potato.