AN INCREMENTAL ALGORITHM FOR EFFICIENT MULTIPOINT LINKAGE ANALYSIS

While much effort has gone into developing efficient algorithms for calculating multipoint likelihoods, these calculations still form a significant bottleneck in the construction of genetic linkage maps. Our approach to this problem is based on incremental processing techniques, which attempt to reduce the time required to perform iterative computations by storing intermediate results during the initial iteration, so that they may be reused with little extra computation in subsequent iterations. We have developed an incremental program which provides a more efficient substitute for the CMAP program of the LINKAGE package. Our incremental approach stores intermediate results of the computations in the form of a rational function. Thus, computing the likelihood for one position of an unmapped marker locus requires only the reevaluation of the rational function. Timing data suggest that when pedigrees are fully or nearly fully typed, our program runs about 3-fold faster than CMAP to compute the likelihood for one position of a marker locus. Additional positions do not add any appreciable time to our program; thus, speedups become more pronounced as more marker locus positions are considered.