On reducing the statespace of hidden Markov models for the identity by descent process

Abstract

Important methods for calculating likelihoods of genealogical relationships and mapping genes are based on hidden Markov models for the process of identity by descent along chromosomes. The computational time for the algorithms depends critically on the size of the statespace of the hidden Markov model. We describe the maximal grouping together of states of the model to reduce the size of the statespace. This grouping is based on pedigree symmetries. We also present an efficient algorithm for finding the maximal grouping.