An Incremental Algorithm for Effecient
Multipoint Linkage Analysis
Robert W. Kramer, Daniel E. Weeks, Donald M. Chiarulli
Human Heredity 45, 323--336 (1995)
Abstract
While much effort has gone into developing effecient
algorithms for calculating multipoint likelihood, 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 effecient 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. Thuis, computing the likelihood for one position
of an unmapped maker locus requires only the reevalutation
of the rational function. Timing data suggest that when
pedigrees are fully or nearly fully typed, our program
runs about 3-fold faster tham CMAP to compute the likelihood
for one position of a marker locus. Additional positions
do not add any appreciable time to our program; thus
sppedups become more pronouced as more marker locus
positions are considered.
back to link-compute