An algorithm to improve the computational efficiency of genetic linkage analysis

The computational complexity of genetic linkage analysis can increase exponentially with the square of the number of alleles at a marker locus. Many of the most informative marker loci have a large number of associated alleles. The precise identities of the alleles are irrelevant to the linkage analysis so long as identity-by-descent and linkage-phase information are preserved. This paper introduces an algorithm which, by relabeling, reduces the number of alleles at the marker locus, thereby increasing the speed of the analysis. The relabeling scheme preserves linkage-phase and identity-by-descent information so the results of the analysis are unaffected. Unlike previously published methods, this algorithm can be applied to pedigrees of arbitrary structure with both complete and incomplete phenotypic information.