On a Misconception About Irreducibility of the Single-Site Gibbs Sampler in a Pedigree Application
C. Cannings, Nuala A. Sheehan · Genetics · 2002
THE analysis of genetic data on groups of related individuals, or pedigrees, frequently necessitates the calculation of probabilities and likelihoods. There are well-known algorithms such as the peeling algorithm (Elston and Stewart 1971), which was extended to include arbitrarily complex pedigrees and genetic models by Cannings et al. (1978), and the expert systems algorithms such as that of Lauritzen and Spiegelhalter (1988) for large Bayesian networks (Jensen 1996), which can perform these calculations in theory. However, in practice, exact methods break down either when the pedigree structure or the genetic model under consideration becomes too complicated. A complex pedigree is one that has too many interconnecting undirected cycles or loops that force large cutsets in any peeling sequence, leading to impossible storage requirements. In a general graph, a sequence of edges for which each edge has a node in common with both preceding and succeeding edges forms an undirected cycle if it begins and ends at the same node. There are many ways of forming loops in a general graph but in pedigrees, loops are typically caused by inbreeding or intermarital relationships. A complex genetic model can pose similar computational challenges, even on a simple pedigree structure, because the underlying graphical model for the computational problem may be highly looped (Sheehan et al. 2002). In these situations, the required probabilities and likelihoods must be estimated. One approach is to approximate the problem by sacrificing a sufficient amount of the complexity to enable exact calculation (e.g., Wang et al. 1996). Alternatively, the complexity of the problem can be preserved and the calculations in question approximated using Markov chain Monte Carlo (MCMC) methods (see Thompson 2001 for an overview).