A Fast Algorithm and Software for Building Ultra-Dense Genetic Maps in the Presence of Genotyping Errors and Missing Data

With very large number of markers available for a mapping population, most of the markers will remain inseparable by recombination. In such cases, only one representative per group could be placed on the (skeleton) map; the remaining markers can then be attached to the skeleton. Real situations are also complicated by genotyping errors, which “diversify” a certain part of markers that would be identical in error-free situations. The higher the error rate the more difficult is the problem of building a reliable map. The situation is further complicated by missing data, a usual factor in genotyping-by-sequencing. Our approach to address these problems is based on a simple probabilistic estimation of the proportion of identical markers as a function of the error level when the errors are rare, and of “radius of diversified markers” when the error level is increased. For sample size N and probability p of genotyping errors per marker, the probability that in all individuals both alleles of a marker will be unmistakably identified, is e^-pN. Assuming 1% errors within a group of absolutely linked markers, about 1/3 of markers will still remain error-free. For a chromosome of 100 cM, in a population with N=100, the minimum non-zero interval length between markers will be 1 cM, thus the map density cannot exceed 100 markers. With 10,000 markers on the chromosome, only 100 ( skeletal) markers can be ordered, whereas the rest will remain linked to the skeletal markers. In our algorithm, we assume that error-free markers can be selected based on the presence of “twins”. There is also a probability of an opposite effect, when non-identical markers become “twins” because of genotyping errors. Therefore, a certain threshold is introduced for selection of markers with a sufficient number of absolutely linked copies. The developed algorithm (implemented in MultiPoint software) enables mapping big sets of markers (~10⁵).