Mapping 1000000 markers with Flipper

Authors: Crane, Charles

Submitted to: Plant and Animal Genome Conference Proceedings
Publication Type: Abstract Only
Publication Acceptance Date: 11/1/2017
Publication Date: 1/17/2018
Citation: Crane, C.F. 2018. Mapping 1000000 markers with Flipper. Plant and Animal Genome Conference XXVI Proceedings. January, 13-17, 2018, San Diego, CA.

Interpretive Summary:

Technical Abstract: Flipper is a fast linkage and deletion mapper that implements Kruskal’s algorithm to produce a minimum spanning tree of genetic markers. Additional heuristics allow Flipper to recognize and repair many instances of misplaced markers and misjoined subsets of markers. Flipper requires memory in proportion to the square of the number of markers. With 16 Gb of system memory, it cannot run more than about 43000 markers at once without paging to disk. Flipper allows efficient deduplication of marker sets to mutually recombining exemplar markers, and this can be used to reduce 1000000 perfectly genotyped markers to a sufficiently small number of exemplars. Since Flipper keeps track of the nonrecombining markers that accompany each exemplar, those can be inserted into the map based on exemplars. However, this method fails with even 0.1% genotyping error, since the errors introduce spurious recombination and greatly increase the number of apparent exemplars. A better, more general method is to map a subset of enough markers to place ca. 100 per linkage group, and then use this map as a set of mathematical attractors to cluster the entire marker set into linkage groups that might fit within the 43000-marker limit. Since each recombination fraction is calculated only once, this grouping of markers requires very little memory. The same idea can be applied to abutting subsets of markers within a single linkage group. The markers that fall into each non-overlapping cluster can then be mapped and the clusters can be sutured together with local permutation of 8-10 markers at each junction. An example of each of these three methods is given for a simulated genotyping-by-sequencing experiment with 1000000 markers.