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.     

Monte Carlo simulations on marker grouping and ordering

Four global algorithms, maximum likelihood (ML), sum of adjacent LOD score (SALOD), sum of adjacent recombinant fractions (SARF) and product of adjacent recombinant fraction (PARF), and one approximation algorithm, seriation (SER), were used to compare the marker ordering efficiencies for correctly given linkage groups based on doubled haploid (DH) populations. The Monte Carlo simulation results indicated the marker ordering powers for the five methods were almost identical. High correlation coefficients were greater than 0.99 between grouping power and ordering power, indicating that all these methods for marker ordering were reliable. Therefore, the main problem for linkage analysis was how to improve the grouping power. Since the SER approach provided the advantage of speed without losing ordering power, this approach was used for detailed simulations. For more generality, multiple linkage groups were employed, and population size, linkage cutoff criterion, marker spacing pattern (even or uneven), and marker spacing distance (close or loose) were considered for obtaining acceptable grouping powers. Simulation results indicated that the grouping power was related to population size, marker spacing distance, and cutoff criterion. Generally, a large population size provided higher grouping power than small population size, and closely linked markers provided higher grouping power than loosely linked markers. The cutoff criterion range for achieving acceptable grouping power and ordering power differed for varying cases; however, combining all situations in this study, a cutoff criterion ranging from 50 cM to 60 cM was recommended for achieving acceptable grouping power and ordering power for different cases.     

A computerised algorithm for selecting a subset of multiplex molecular markers and optimising linkage map construction

A computer algorithm is presented which allows selection of a subset of multiplex markers based on the minimisation of an optimality criterion for a genetic linkage map. It could be applied for choosing a subset of primers (e.g. RAPD, IMA or AFLP), each of which provides several unevenly spaced genetic markers. The goal is to achieve a saturated map of evenly spaced markers, using as few primers as possible to minimise cost and labour. Minimising the average map distance between markers is trivial, but simply leads to selection of those primers which provide the greatest number of markers. However, minimising the standard deviation of interval length ensures that weight is given both to the number of markers and to the evenness of their distribution on the linkage map. This criterion was found empirically to give a result fairly close to the optimum. A stepwise-like selection procedure is therefore implemented, which stops when the optimality criterion does not decrease any more. An example is given of a molecular map of perennial ryegrass with 463 markers obtained from 17 AFLP primers. It is demonstrated that this can be safely reduced to a 175 marker map with only 6 primers. Genetic diversity studies may also benefit from using such a subset of less-redundant markers in genetic distance estimation. Received: 17 March 1999 / Accepted: 23 August 1999     

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.     

Effects of genotyping errors,missing values and segregation distortion in molecular marker data on the construction of linkage maps

A simulation study was performed to investigate the effects of missing values, typing errors and distorted segregation ratios in molecular marker data on the construction of genetic linkage maps, and to compare the performance of three locus-ordering criteria (weighted least squares, maximum likelihood and minimum sum of adjacent recombination fractions criteria) in the presence of such effects. The study was based upon three linkage groups of 10 loci at 2, 6, and 10 cM spacings simulated from a doubled-haploid population of size 150. Criteria performance were assessed using the number of replicates with correctly estimated orders, the mean rank correlation between the estimated and the true order and the mean total map length. Bootstrap samples from replicates in the maximum likelihood analysis produced a measure of confidence in the estimated locus order. The effects of missing values and/or typing errors in the data are to reduce the proportion of correctly ordered maps, and this problem worsens as the distances between loci decreases. The maximum likelihood criterion is most successful at ordering loci correctly, but gives estimated map lengths, which are substantially inflated when typing errors are present. The presence of missing values in the data produces shorter map lengths for more widely spaced markers, especially under the weighted least-squares criterion. Overall, the presence of segregation distortion has little effect on this population.     

TetraploidMap: construction of a linkage map in autotetraploid species

TetraploidMap is a suite of Fortran 90 routines run from Microsoft Windows with a text-based input and output. TetraploidMap enables the user to assemble a linkage map from dominant and codominant (multiallelic) marker loci scored for the parents and full-sib progeny of a cross in an autotetraploid species. It includes routines for the inference of the parental genotypes, identification of linkage groups, two-point analysis to estimate the recombination frequency and LOD score between all pairs of marker in a linkage group, and locus ordering by simulated annealing.     

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.     

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.     

Efficient multipoint mapping: making use of dominant repulsion-phase markers

The paper is devoted to the problem of multipoint gene ordering with a particular focus on "dominance" complication that acts differently in conditions of coupling-phase and repulsion-phase markers. To solve the problem we split the dataset into two complementary subsets each containing shared codominant markers and dominant markers in the coupling-phase only. Multilocus ordering in the proposed algorithm is based on pairwise recombination frequencies and using the well-known travelling salesman problem (TSP) formalization. To obtain accurate results, we developed a multiphase algorithm that includes synchronized-marker ordering of two subsets assisted by re-sampling-based map verification, combining the resulting maps into an integrated map followed by verification of the integrated map. A new synchronized Evolution-Strategy discrete optimization algorithm was developed here for the proposed multilocus ordering approach in which common codominant markers facilitate stabilization of the marker order of the two complementary maps. High performance of the employed algorithm allows systematic treatment for the problem of verification of the obtained multilocus orders, based on computing-intensive bootstrap and jackknife technologies for detection and removing unreliable marker scores. The efficiency of the proposed algorithm was demonstrated on simulated and real data.Communicated by J.W. Snape     

A high density barley microsatellite consensus map with 775 SSR loci

A microsatellite or simple sequence repeat (SSR) consensus map of barley was constructed by joining six independent genetic maps based on the mapping populations 'Igri x Franka', 'Steptoe x Morex', 'OWB(Rec) x OWB(Dom)', 'Lina x Canada Park', 'L94 x Vada' and 'SusPtrit x Vada'. Segregation data for microsatellite markers from different research groups including SCRI (Bmac, Bmag, EBmac, EBmag, HVGeneName, scsssr), IPK (GBM, GBMS), WUR (GBM), Virginia Polytechnic Institute (HVM), and MPI for Plant Breeding (HVGeneName), generated in above mapping populations, were used in the computer program RECORD to order the markers of the individual linkage data sets. Subsequently, a framework map was constructed for each chromosome by integrating the 496 "bridge markers" common to two or more individual maps with the help of the computer programme JoinMap 3.0. The final map was calculated by following a "neighbours" map approach. The integrated map contained 775 unique microsatellite loci, from 688 primer pairs, ranging from 93 (6H) to 132 (2H) and with an average of 111 markers per linkage group. The genomic DNA-derived SSR marker loci had a higher polymorphism information content value (average 0.61) as compared to the EST/gene-derived SSR loci (average 0.48). The consensus map spans 1,068 cM providing an average density of one SSR marker every 1.38 cM. Such a high-density consensus SSR map provides barley molecular breeding programmes with a better choice regarding the quality of markers and a higher probability of polymorphic markers in an important chromosomal interval. This map also offers the possibilities of thorough alignment for the (future) physical map and implementation in haplotype diversity studies of barley.     

Three-point appraisal of genetic linkage maps

This paper develops a simple diagnostic for the investigation of uncertainty within genetic linkage maps using a Bayesian procedure. The method requires only the genotyping data and the proposed genetic map, and calculates the posterior probability for the possible orders of any set of three markers, accounting for the presence of genotyping error (mistyping) and for missing genotype data. The method uses a Bayesian approach to give insight into conflicts between the order in the proposed map and the genotype scores. The method can also be used to assess the accuracy of a genetic map at different genomic scales and to assess alternative potential marker orders. Simulation and two case studies were used to illustrate the method. In the first case study, the diagnostic revealed conflicts in map ordering for short inter-marker distances that were resolved at a distance of 8–12?cM, except for a set of markers at the end of the linkage group. In the second case study, the ordering did not resolve as distances increase, which could be attributed to regions of the map where many individuals were untyped.     

Constructing linkage maps in autotetraploid species using simulated annealing

In this paper we demonstrate how molecular markers segregating in a full-sib autotetraploid mapping population can be ordered to form a linkage map using simulated annealing. This approach facilitates the examination of orders close to the optimum to see which marker placings are fixed and identify the markers whose position is less certain. A simulation study investigates the effects of population size, marker spacing, ratio of dominant to codominant markers, typing errors and missing values. The method is applied to map 30 amplified fragment length polymorphism and microsatellite markers on linkage group IV of potato.     

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.     

Detection of closely linked multiple quantitative trait loci using a genetic algorithm

The existence of a quantitative trait locus (QTL) is usually tested using the likelihood of the quantitative trait on the basis of phenotypic character data plus the recombination fraction between QTL and flanking markers. When doing this, the likelihood is calculated for all possible locations on the linkage map. When multiple QTL are suspected close by, it is impractical to calculate the likelihood for all possible combinations of numbers and locations of QTL. Here, we propose a genetic algorithm (GA) for the heuristic solution of this problem. GA can globally search the optimum by improving the "genotype" with alterations called "recombination" and "mutation." The "genotype" of our GA is the number and location of QTL. The "fitness" is a function based on the likelihood plus Akaike's information criterion (AIC), which helps avoid false-positive QTL. A simulation study comparing the new method with existing QTL mapping packages shows the advantage of the new GA. The GA reliably distinguishes multiple QTL located in a single marker interval.     

ODS2: a multiplatform software application for creating integrated physical and genetic maps

A contig map is a physical map that shows the native order of a library of overlapping genomic clones. One common method for creating such maps involves using hybridization to detect clone overlaps. False- positive and false-negative hybridization errors, the presence of chimeric clones, and gaps in library coverage lead to ambiguity and error in the clone order. Genomes with good genetic maps, such as Neurospora crassa, provide a means for reducing ambiguities and errors when constructing contig maps if clones can be anchored with genetic markers to the genetic map. A software application called ODS2 for creating contig maps based on clone-clone hybridization data is presented. This application is also designed to exploit partial ordering information provided by anchorage of clones to a genetic map. This information, along with clone-clone hybridization data, is used by a clone ordering algorithm and is represented graphically, allowing users to interactively align physical and genetic maps. ODS2 has a graphical user interface and is implemented entirely in Java, so it runs on multiple platforms. Other features include the flexibility of storing data in a local file or relational database and the ability to create full or minimum tiling contig maps.     

Parallel computation of a maximum-likelihood estimator of a physical map

Reconstructing a physical map of a chromosome from a genomic library presents a central computational problem in genetics. Physical map reconstruction in the presence of errors is a problem of high computational complexity that provides the motivation for parallel computing. Parallelization strategies for a maximum-likelihood estimation-based approach to physical map reconstruction are presented. The estimation procedure entails a gradient descent search for determining the optimal spacings between probes for a given probe ordering. The optimal probe ordering is determined using a stochastic optimization algorithm such as simulated annealing or microcanonical annealing. A two-level parallelization strategy is proposed wherein the gradient descent search is parallelized at the lower level and the stochastic optimization algorithm is simultaneously parallelized at the higher level. Implementation and experimental results on a distributed-memory multiprocessor cluster running the parallel virtual machine (PVM) environment are presented using simulated and real hybridization data.     

Simultaneous mining of linkage and linkage disequilibrium to fine map quantitative trait loci in outbred half-sib pedigrees: revisiting the location of a quantitative trait locus with major effect on milk production on bovine chromosome 14

A maximum-likelihood QTL mapping method that simultaneously exploits linkage and linkage disequilibrium and that is applicable in outbred half-sib pedigrees is described. The method is applied to fine map a QTL with major effect on milk fat content in a 3-cM marker interval on proximal BTA14. This proximal location is confirmed by applying a haplotype-based association method referred to as recombinant ancestral haplotype analysis. The origin of the discrepancy between the QTL position derived in this work and that of a previous analysis is examined and shown to be due to the existence of distinct marker haplotypes associated with QTL alleles having large substitution effects.     

Estimating linkage disequilibrium between a polymorphic marker locus and a trait locus in natural populations.

Positional cloning of gene(s) underlying a complex trait requires a high-resolution linkage map between the trait locus and genetic marker loci. Recent research has shown that this may be achieved through appropriately modeling and screening linkage disequilibrium between the candidate marker locus and the major trait locus. A quantitative genetics model was developed in the present study to estimate the coefficient of linkage disequilibrium between a polymorphic genetic marker locus and a locus underlying a quantitative trait as well as the relevant genetic parameters using the sample from randomly mating populations. Asymptotic covariances of the maximum-likelihood estimates of the parameters were formulated. Convergence of the EM-based statistical algorithm for calculating the maximum-likelihood estimates was confirmed and its utility to analyze practical data was exploited by use of extensive Monte-Carlo simulations. Appropriateness of calculating the asymptotic covariance matrix in the present model was investigated for three different approaches. Numerical analyses based on simulation data indicated that accurate estimation of the genetic parameters may be achieved if a sample size of 500 is used and if segregation at the trait locus explains not less than a quarter of phenotypic variation of the trait, but the study reveals difficulties in predicting the asymptotic variances of these maximum-likelihood estimates. A comparison was made between the statistical powers of the maximum-likelihood analysis and the previously proposed regression analysis for detecting the disequilibrium.     

Integrated consensus genetic and physical maps of flax (Linum usitatissimum L.)

Three linkage maps of flax (Linum usitatissimum L.) were constructed from populations CDC Bethune/Macbeth, E1747/Viking and SP2047/UGG5-5 containing between 385 and 469 mapped markers each. The first consensus map of flax was constructed incorporating 770 markers based on 371 shared markers including 114 that were shared by all three populations and 257 shared between any two populations. The 15 linkage group map corresponds to the haploid number of chromosomes of this species. The marker order of the consensus map was largely collinear in all three individual maps but a few local inversions and marker rearrangements spanning short intervals were observed. Segregation distortion was present in all linkage groups which contained 1–52 markers displaying non-Mendelian segregation. The total length of the consensus genetic map is 1,551?cM with a mean marker density of 2.0?cM. A total of 670 markers were anchored to 204 of the 416 fingerprinted contigs of the physical map corresponding to ~274?Mb or 74?% of the estimated flax genome size of 370?Mb. This high resolution consensus map will be a resource for comparative genomics, genome organization, evolution studies and anchoring of the whole genome shotgun sequence.     

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.