Faster Multipoint Linkage Analysis Through State Space Reduction

K.G. Markianos, L. Kruglyak, M.A. Eberle

Molecular Medicine, Fred Hunchinson Cancer Research Center, Seattle, W

Computational constraints currently limit exact multipoint linkage analysis to pedigrees of moderate size. We are developing new algorithms that allow analysis of larger pedigrees by reducing CPU and memory requirements of the computation. The algorithms are being implemented in a new version of the software package GENEHUNTER. One algorithm uses the observed pedigree genotypes to reduce the inheritance vector space. Performing the calculation in the reduced vector space increases the efficiency of multipoint analysis several times both in terms of computational speed and memory requirements. Specifically, we introduce the following improvements:

1. Identification of the COMPLETE set of illegal inheritance vectors.
2. Computation of prior probabilities only for legal inheritance patterns.
3. Efficient computation of the Whittemore & Halpern statistic used for nonparametric (NPL) linkage analysis.
4. Computation and storage of cumulative transition probabilities only for states compatible with the observed genotypes.

We will present performance data for the new version of GENEHUNTER.