Faster sequential genetic linkage computations
Cottingham RW Jr, Idury RM, Schaffer AA
American Journal of Human Genetics 1993 Jul;53(1):252-63
Abstract
Linkage analysis using maximum-likelihood estimation is a powerful
tool for locating genes. As available data sets have grown, the
computation required for analysis has grown exponentially and become
a significant impediment. Others have previously shown that parallel
computation is applicable to linkage analysis and can yield
order-of-magnitude improvements in speed. In this paper, we
demonstrate that algorithmic modifications can also yield
order-of-magnitude improvements, and sometimes much more. Using the
software package LINKAGE, we describe a variety of algorithmic
improvements that we have implemented, demonstrating both how these
techniques are applied and their power. Experiments show that these
improvements speed up the programs by an order of magnitude, on
problems of moderate and large size. All improvements were made only
in the combinatorial part of the code, without restoring to parallel
computers. These improvements synthesize biological principles with
computer science techniques, to effectively restructure the
time-consuming computations in genetic linkage analysis.
back to link-compute