Speeding up HMM algorithms for genetic linkage analysis

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

GMW_Bioinformatics2009.pdf
PDF file

In  Bioinformatics

Publisher  Oxford University Press
Copyright © 2009 The Authors.

Details

TypeArticle
> Publications > Speeding up HMM algorithms for genetic linkage analysis