Multilocus ordering strategies based on sperm typing

Sperm typing is a promising new approach for fine-structure human gene mapping. We examine three-locus sperm typing and its implications for the estimation of recombination fractions and for locus ordering. In particular, we compare some sequential stopping rules for three-locus assignment and develop methods for approximating their mean stopping times and error probabilities. A stopping rule recently described by Thompson and Boehnke et al. appears to be nearly optimal. Under this rule, one stops sampling as soon as the number of sperm of the least frequent recombinant type is s fewer than the number of sperm of the next least frequent type. We develop a random-walk algorithm and some heuristic formulas for assessing the performance of this rule. Since the broader goal of linkage analysis is to order many more than three loci, we propose a trisection strategy for ordering a new locus relative to an existing ordered set of loci. The crux of the trisection strategy is to restrict attention to the smallest block of ordered loci among which the new locus can fall and to divide this block into thirds for the next comparison. This trisection strategy is optimal in the sense that it has the best worse-case performance of any strategy. When it is applied sequentially to order a collection of loci, it is only nearly optimal, as we demonstrate by specific counter-example. However, it does become asymptotically optimal as the size of the collection increases.