Speeding up HMM algorithms for genetic linkage analysis via chain reductions of the state space

Abstract

We develop an hidden Markov model (HMM)-based algorithm for computing exact parametric and non-parametric linkage scores in larger pedigrees than was possible before. The algorithm is applicable whenever there are chains of persons in the pedigree with no genetic measurements and with unknown affection status. The algorithm is based on shrinking the state space of the HMM considerably using such chains. In a two g-degree cousins pedigree the reduction drops the state space from being exponential in g to being linear in g. For a Finnish family in which two affected children suffer from a rare cold-inducing sweating syndrome, we were able to reduce the state space by more than five orders of magnitude from 2(50) to 2(32). In another pedigree of state-space size of 2(27), used for a study of pituitary adenoma, the state space reduced by a factor of 8.5 and consequently exact linkage scores can now be computed, rather than approximated.

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

A normalized pedigree with two founders (A and B) and three typed distant cousins (D_t, E_u and F_z, with genotypes g₁, g₂ and g₃ respectively). The chains D, E and F can be reduced from a collection of selectors to one cluster each with number of states linear in the chain's length. In Pedigree II, the collection of the selectors in the two chains, can be reduced to a single cluster with number of states linear in the sum of lengths of the two chains.

Fig. 2.

A normalized pedigree used by Vierimaa et al. (2006) for the study of pituitary adenoma. There are six typed individuals in the pedigree that are marked in black stripes. We use chains 1, 2 and 3 to reduce the state space by a factor of 8.5 and speedup computations.

Fig. 3.

Runtime comparison for computations using the original model and the reduced state-space model for the pedigree in Figure 2, as a function of the length m of Chain 1.

Fig. 4.

Runtime comparison for computations using the original model and the reduced state-space model for the pedigree in Figure 2 across 6000 markers, where Chain 1 is of length 0.

Fig. 5.

The Finnish family studied by Knappskog et al. (2003), which includes two affected individuals that suffer from cold-inducing sweating syndrome (marked in black).