Linkage analysis using maximum-likelihood estimation is a powerful too
l for locating genes. As available data sets have grown, the computati
on required for analysis has grown exponentially and become a signific
ant impediment. Others have previously shown that parallel computation
is applicable to linkage analysis and can yield order-of-magnitude im
provements in speed. In this paper, we demonstrate that algorithmic mo
difications can also yield order-of-magnitude improvements, and someti
mes much more. Using the software package LINKAGE, we describe a varie
ty of algorithmic improvements that we have implemented, demonstrating
both how these techniques are applied and their power. Experiments sh
ow that these improvements speed up the programs by an order of magnit
ude, on problems of moderate and large size. All improvements were mad
e only in the combinatorial part of the code, without resorting to par
allel computers. These improvements synthesize biological principles w
ith computer science techniques, to effectively restructure the time-c
onsuming computations in genetic linkage analysis.