Letter to the Editor

On a Misconception About Irreducibility of the Single-Site Gibbs Sampler in a Pedigree Application

Corresponding author: N. A. Sheehan, University of Leicester, 22–28 Princess Rd. W., Leicester LE1 6TP, UK., nas11{at}le.ac.uk (E-mail)

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).

The first application of MCMC methods in pedigree analysis (SHEEHAN 1990 ) exploited the single-site Gibbs sampler (GEMAN and GEMAN 1984 ) for a simple single-locus trait on a large complex human pedigree of Greenland Eskimos where the statespace of the underlying Markov chain was the set of genotypic configurations on the pedigree. Reasonable estimates of marginal posterior distributions of founder genotypes were obtained in this way (SHEEHAN 1992 ). By noting that the genetic model is Markovian, a neighborhood system can be defined on a pedigree such that, conditional on the neighbors, genotypes of individuals are independent and the set of genotypic configurations on the pedigree is thus a locally dependent Markov random field. The Gibbs sampler moves between genotypic configurations by selecting a single individual and updating the existing estimate of genotype with one drawn at random from the full conditional distribution of genotype, given the current estimates elsewhere on the graph and any phenotypic data. Because of the local dependencies induced by the neighborhood system, the Gibbs sampler is very easy to implement in these genetic applications. However, it was also noted at this time (SHEEHAN 1990 ; SHEEHAN and THOMAS 1993 ) that although the sampler defines an irreducible Markov chain for most traits determined by a diallelic locus, the irreducibility condition necessary to ensure convergence of the sampler to the correct equilibrium distribution is no longer guaranteed for a genetic system with three or more alleles.

The pedigree Gibbs sampler, as defined above, will converge to the true posterior distribution of genotypes on the pedigree given available phenotypes if it defines an irreducible chain whereby all states communicate and if each individual genotype is updated infinitely often. This follows from the ergodic theorem for finite, aperiodic, irreducible, Markov chains (COX and MILLER 1965 ). In many other areas of application, such as Bayesian image analysis, for example, there is considerable flexibility in the specification of the underlying Markov random field, which is usually constructed to satisfy the positivity condition (see BESAG 1986 ), and this, in turn, trivially guarantees irreducibility of the single-site Gibbs sampler. For a pedigree with n individuals, let S_i = {s_i} be the set of possible genotypes that can be assigned to the ith pedigree member, ignoring all others. Positivity, in our applications, would mean that any assignment (s₁, ... , s_n) of genotypes on the pedigree would have an associated positive probability. This is clearly not the case for discrete genetic models, which pose a complicated excluded adjacency problem. In particular, we cannot start the Gibbs sampler from a random configuration as is usually the case with other applications.

The issue, therefore, is whether the legal configurations of genotypes on a pedigree (i.e., those states that agree both with the data and the genetic model) communicate if genotypes are updated one at a time. It can be shown that the single-site Gibbs sampler is generally irreducible over the legal states of a diallelic genetic system. The only exception (SHEEHAN 1990 ) occurs within the following scenario. Suppose we have a dichotomous trait (e.g., affected and normal) where both homozygotes are affected with positive probability but the heterozygote is affected with probability zero. As illustrated in Fig 1, depending on the observed individuals, this can cause the single-site Gibbs sampler to be reducible. However, as all that is required for irreducibility is a minor relaxation of the penetrance probabilities, allowing the heterozygote to have some small positive probability of having the same phenotype as either homozygote, this does not cause a problem in practice. In many cases, of course, the phenotypic observations are actually the genotypes themselves and information on individuals is either complete in that they are fully typed or missing altogether. This is the setting that we focus on heretoforth. Note that the Gibbs sampler is always irreducible for diallelic loci in this case.

View larger version (6K): In this window In a new window Download PPT slide   Figure 1. An example adapted from SHEEHAN 2000 where observed data on a dichotomous trait [affected and normal determined by a diallelic genetic system (with alleles A and B)] cause the single-site Gibbs sampler to be reducible. Note that both mother and daughter must be homozygous for the same allele, which means that once one pairing has been assigned, the other can never be visited by updating one individual genotype at a time if heterozygotes are affected with zero probability.

Once the genetic system has three or more alleles, it is easy to see how the Gibbs sampler can define a reducible Markov chain. The classic example for a three-allele system, with alleles A, B, and C, say (see SHEEHAN and THOMAS 1993 , for example), is shown in Fig 2, where unobserved parents have two typed offspring, one of whom is heterozygous AB and the other homozygous for the third allele, CC. Clearly, each parent carries the C allele and one carries an A while the other carries a B. From the symmetry of genetic inheritance, it is equally plausible that either parent can have one or the other of the genotypes AB and AC. However, once one has been assigned in a starting configuration for a single-site Gibbs sampler, the other must take the complementary type and neither will change for the duration of the run.

View larger version (9K): In this window In a new window Download PPT slide   Figure 2. A genetic system with three alleles, A, B, and C, adapted from SHEEHAN 2000 , where observations on two siblings force noncommunicating alternatives on their unobserved parents.

Reducibility depends on the data. If it were possible to enumerate the noncommunicating classes of the Markov chain described by the Gibbs sampler, a scheme that would move between the different classes using the reversible-jump method of GREEN 1995 or the Metropolis jumping-kernel method of LIN 1996, for example, could be devised. A deterministic algorithm to find the noncommunicating classes was proposed by LIN et al. 1994 , which depended on the assumption that such classes can be caused only by observations on offspring forcing noncommunicating alternatives for unobserved parents, as in the classic scenario of Fig 2. However, this assumption does not suffice: There are many other ways in which data can be assigned on a pedigree to cause the Gibbs sampler to be reducible and the algorithm does not work on several simple examples (JENSEN and SHEEHAN 1998 ). In particular, partial information can filter down a pedigree from an ancestor, which, when combined with other information coming up from descendants, can create noncommunicating classes on individuals in intermediate generations. To date, there is no algorithm that will find all these classes. Moreover, it would seem that a completely general algorithm would require storage of so much partial information as to make it akin to peeling (JENSEN and SHEEHAN 1998 ).

The practical implication of this is that it may not be possible to sample correctly from the true posterior distribution of genotype, given phenotype, using a single-site Gibbs sampler once there are three or more alleles in the genetic system, and any estimates of probabilities and likelihoods obtained in this way are hence unreliable.

In animal breeding circles, especially those concerned with animals where artificial insemination is practiced, it is not uncommon to have a small number of males with large numbers of mates and offspring. In particular, full DNA information would usually be available on these males. The pedigrees resulting from such a breeding program are extremely complex and defy exact calculation of probabilities and likelihoods for any genetic system, however simple. Often, the pedigree structure is sacrificed and estimates are obtained on a simple subpedigree such as a half-sib design, using methods like least squares (HALEY et al. 1994 ), which permit fast analysis using permutation tests (CHURCHILL and DOERGE 1994 ), for example, or maximum likelihood. However, it is more appealing to preserve the pedigree information and apply MCMC methods.

It has been claimed in the animal genetics literature (see HOESCHELE et al. 1997 ; BINK and ARENDONK 1999 , for example) that the single-site Gibbs sampler is irreducible if at least one in every parent pair is observed and many analyses have been performed on animal pedigrees with fully typed males in the belief that this is true. A counter-example to this claim involving a simple unlooped pedigree with three generations is presented in Fig 3.

View larger version (9K): In this window In a new window Download PPT slide   Figure 3. A simple pedigree where one member of each marriage is fully typed. The mother-daughter pair, labeled A?, are either both AB or both AC. Once one configuration has been assigned, the other can never be reached by a single-site Gibbs sampler.

For a half-sib design that includes only individuals over two generations and assumes that the dams are unrelated and distinct, the single-site Gibbs sampler is irreducible when the sires are fully typed, regardless of any observations on mates or offspring. However, it is not the case in general and misleading results can be obtained.

The belief that the single-site Gibbs sampler defines an irreducible Markov chain on the space of genotypic configurations over a general pedigree provided one member of each spouse pairing is observed would seem to derive from the erroneous statement in LIN et al. 1994 that noncommunicating classes can arise only on unobserved parents from offspring data. JENSEN and SHEEHAN 1998 presented several counter-examples to this algorithm, involving two-, three-, and four-generational pedigrees with and without loops. The important point is that information forcing noncommunicating alternatives on a set of individuals can come from above via the ancestors as well as from below via the descendants. In particular, as noted by THOMPSON 1986 , the terms "above" and "below" do not necessarily define disjoint sets in a complex pedigree and the routes by which information filters through a pedigree may be interconnected and hence highly complicated. In this article, we have presented a counter-example to the animal genetics community and have attempted to clarify the reducibility issue.

However, while it is true that any analysis based on a reducible sampling scheme is potentially dubious, reducibility itself is not really a problem. There are several methods for getting around reducibility (see THOMPSON 2001 for an overview). Most of these involve some sort of relaxation of the genetic model, which enables the sampler to move between illegal configurations. These include importance sampling with weights of zero and one (SHEEHAN and THOMAS 1993 ), the Metropolis-coupled samplers of GEYER 1991 , the heated companion chains of LIN et al. 1993 , and the annealing-type samplers of GEYER and THOMPSON 1995 , to name but a few. The corresponding statespace of the Markov chain could be vastly augmented from that defined by the single-site Gibbs sampler and good mixing of the chain becomes the important issue (GILKS et al. 1993 ).

Using meiosis indicators or descent graphs (SOBEL and LANGE 1996 ) rather than genotypes greatly improves mixing of MCMC samplers on pedigrees (THOMPSON 1994 , THOMPSON 2000B ). In addition, there are all kinds of joint or block updating schemes such as the blocking Gibbs method of JENSEN et al. 1995 , which updates large blocks of the pedigree conditional on the values at the remaining variables, the locus-by-locus samplers of HEATH 1997 and SILLANPAA and ARJAS 1999 , the meiosis-by-meiosis sampler of THOMPSON and HEATH 2000 , or the combination samplers that alternate between chromosome peeling and pedigree peeling (HURME et al. 2000 ; THOMAS et al. 2000 ; THOMPSON 2000A ), all of which require that the pedigree can be peeled for at least one locus. For large complex animal pedigrees, however, it may not be possible to peel even for a single locus and a relaxed sampler may be required in addition to blocking. The ESIP sampler of FERNANDEZ et al. 2001 samples genotypes over the entire pedigree at a single locus by using a sample obtained from a modified pedigree obtained by iterative peeling as the proposal in a Metropolis-Hastings updating step. However, the main problem in animal genetics applications is that the pedigrees are often enormous and these alternative MCMC methods have not been tested sufficiently on big problems (HOESCHELE et al. 1997 ). Nonetheless, they at least have the potential to yield estimates from the correct distribution and provide a wealth of attractive alternatives to the single-site Gibbs sampler.

ACKNOWLEDGMENTS

We acknowledge Rohan Fernando for bringing this problem to our attention. In addition, Nuala Sheehan acknowledges support from the Wellcome Trust Biomedical Research Collaboration Grant 056266/Z/98/Z and the TVW Telethon Institute for Child Health Research, Perth, Western Australia.

Manuscript received May 3, 2002; Accepted for publication August 13, 2002.

LITERATURE CITED

BESAG, J., 1986  On the statistical analysis of dirty pictures. J. R. Stat. Soc. Ser. B 48:259-302.

BINK, M. C. A. M. and J. A. M. V. ARENDONK, 1999  Detection of quantitative trait loci in outbred populations with incomplete marker data. Genetics 151:409-420.[Abstract/Free Full Text]

CANNINGS, C., E. A. THOMPSON, and M. H. SKOLNICK, 1978  Probability functions on complex pedigrees. Adv. Appl. Probab. 10:26-61.

CHURCHILL, G. A. and R. W. DOERGE, 1994  Empirical threshold values for quantitative trait mapping. Genetics 138:963-971.[Abstract]

COX, D. R., and H. D. MILLER, 1965 Stochastic Processes. Methuen & Co., London.

ELSTON, R. C. and J. STEWART, 1971  A general model for the genetic analysis of pedigree data. Hum. Hered. 21:523-542.[Medline]

FERNÁNDEZ, S. A., R. L. FERNANDO, B. GULDBRANDTSEN, L. R. TOTIR, and A. L. CARRIQUIRY, 2001  Sampling genotypes in large pedigrees with loops. Genet. Sel. Evol. 33:337-367.[Medline]

GEMAN, S. and D. GEMAN, 1984  Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Patt. Anal. Mach. Intell. 45:721-741.

GEYER, C. J., 1991 Markov chain Monte Carlo maximum likelihood, pp. 156–163 in Computer Science and Statistics: Proceedings of the 23rd Symposium on the Interface, edited by E. M. KERAMIDAS and S. M. KAUFMAN. Interface Foundation of North America, Fairfax Station, VA.

GEYER, C. J. and E. A. THOMPSON, 1995  Annealing Markov chain Monte Carlo with applications to ancestral inference. J. Am. Stat. Assoc. 90(431):909-920.

GILKS, W. R., D. CLAYTON, D. J. SPIEGELHALTER, N. G. BEST, and A. J. MCNEIL et al., 1993  Modelling complexity: applications of gibbs sampling to medicine. J. R. Stat. Soc. Ser. B 55:39-52.

GREEN, P. J., 1995  Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika 82:711-732.[Abstract/Free Full Text]

HALEY, C. S., S. A. KNOTT, and J. M. ELSEN, 1994  Mapping quantitative trait loci in crosses between outbred lines using least squares. Genetics 136:1195-1207.[Abstract]

HEATH, S. C., 1997  Markov chain Monte Carlo segregation and linkage analysis for oliogenic models. Am. J. Hum. Genet. 61:748-760.[Medline]

HOESCHELE, I., P. UIMARI, F. GRIGNOLA, Q. ZHANG, and K. GAGE, 1997  Advances in statistical methods to map quantitative trait loci in outbred populations. Genetics 147:1445-1457.[Abstract]

HURME, P., M. J. SILLANPÄÄ, E. ARJAS, T. REPO, and O. SAVOLAINEN, 2000  Genetic basis of climatic adaptation in Scots Pine by Bayesian quantitative trait locus analysis. Genetics 156:1309-1322.[Abstract/Free Full Text]

JENSEN, C. S. and N. SHEEHAN, 1998  Problems with determination of noncommunicating classes for Monte Carlo Markov chain applications in pedigree analysis. Biometrics 54:416-425.[Medline]

JENSEN, C. S., U. KJAERULFF, and A. KONG, 1995  Blocking Gibbs sampling in very large probabilistic expert systems. Int. J. Hum. Comput. Stud. 42:647-666.

JENSEN, F. V., 1996 An Introduction to Bayesian Networks. University College Press, London.

LAURITZEN, S. L. and D. J. SPIEGELHALTER, 1988  Local computations with probabilities on graphical structures and their applications to expert systems. J. R. Stat. Soc. Ser. B 50:157-224.

LIN, S., 1996  Multipoint linkage analysis via Metropolis jumping kernels. Biometrics 52:1417-1427.[Medline]

LIN, S., E. THOMPSON, and E. WIJSMAN, 1993  Achieving irreducibility of the Markov chain Monte Carlo method applied to pedigree data. IMA J. Math. Appl. Med. Biol. 10:1-17.[Abstract/Free Full Text]

LIN, S., E. THOMPSON, and E. WIJSMAN, 1994  Finding noncommunicating sets for Markov chain Monte Carlo estimations on pedigrees. Am. J. Hum. Genet. 54:695-704.[Medline]

SHEEHAN, N., 1992  Sampling genotypes on complex pedigrees with phenotypic constraints: the origin of the B allele among the Polar Eskimos. IMA J. Math. Appl. Med. Biol. 9:1-18.[Abstract/Free Full Text]

SHEEHAN, N. and A. THOMAS, 1993  On the irreducibility of a Markov chain defined on a space of genotype configurations by a sampling scheme. Biometrics 49:163-175.[Medline]

SHEEHAN, N. A., 1990 Genetic restoration on complex pedigrees. Ph.D. Thesis, University of Washington, Seattle.

SHEEHAN, N. A., 2000  On the application of Markov chain Monte Carlo methods to genetic analyses on complex pedigrees. Int. Stat. Rev. 68:83-110.

SHEEHAN, N. A., B. GULDBRANDTSEN, M. S. LUND, and D. A. SORENSEN, 2002  Bayesian MCMC mapping of quantitative trait loci in a half-sib design: a graphical model perspective. Int. Stat. Rev. 70:241-267.

SILLANPÄÄ, M. J. and E. ARJAS, 1999  Bayesian mapping of multiple quantitative trait loci from incomplete outbred offspring data. Genetics 151:1605-1619.[Abstract/Free Full Text]

SOBEL, E. and K. LANGE, 1996  Descent graphs in pedigree analysis: applications to haplotyping, location scores, and marker-sharing statistics. Am. J. Hum. Genet. 58:1323-1337.[Medline]

THOMAS, A., A. GUTIN, V. ABKEVICH, and A. BANSAL, 2000  Multilocus linkage analysis by blocked Gibbs sampling. Stat. Comput. 10:259-269.

THOMPSON, E. A., 1986 Pedigree Analysis in Human Genetics. Johns Hopkins University Press, Baltimore.

THOMPSON, E. A., 1994  Monte Carlo likelihood in genetic mapping. Stat. Sci. 9(3):355-366.

THOMPSON, E. A., 2000a  MCMC estimation of multi-locus genome sharing and multipoint gene location scores. Int. Stat. Rev. 68(1):53-73.

THOMPSON, E. A., 2000b Statistical Inference from Genetic Data on Pedigrees, NSF-CBMS Regional Conference Series in Probability and Statistics, Vol. 6. Institute of Mathematical Statistics and the American Statistical Association, Beachwood, OH.

THOMPSON, E. A., 2001 Monte Carlo methods on genetic structures, pp. 176–218 in Complex Stochastic Systems, edited by O. E. BARNDORFF-NIELSEN, D. R. COX and C. KLUPPELBERG. Chapman & Hall, London.

THOMPSON, E. A., and S. C. HEATH, 2000 Estimation of conditional multilocus gene identity among relatives, pp. 95–113 in Statistics in Molecular Biology and Genetics, IMS Lecture Notes, edited by F. SEILLER-MOISEIWITSCH. Institute of Mathematical Statistics, American Mathematical Society, Providence, RI.

WANG, T., R. L. FERNANDO, C. STRICKER, and R. C. ELSTON, 1996  An approximation to the likelihood for a pedigree with loops. Theor. Appl. Genet. 93:1299-1309.

This article has been cited by other articles:

				S. H. Lee, J. H. J. Van der Werf, and B. Tier Combining the Meiosis Gibbs Sampler With the Random Walk Approach for Linkage and Association Studies With a General Complex Pedigree and Multimarker Loci Genetics, December 1, 2005; 171(4): 2063 - 2072. [Abstract] [Full Text] [PDF]

				S. H. Lee and J. H. J. Van der Werf The Role of Pedigree Information in Combined Linkage Disequilibrium and Linkage Mapping of Quantitative Trait Loci in a General Complex Pedigree Genetics, January 1, 2005; 169(1): 455 - 466. [Abstract] [Full Text] [PDF]