Graphical models for genetic analyses. (English) Zbl 1055.62126

Summary: This paper introduces graphical models as a natural environment in which to formulate and solve problems in genetics and related areas. Particular emphasis is given to the relationships among various local computation algorithms which have been developed within the hitherto mostly separate areas of graphical models and genetics. The potential of graphical models is explored and illustrated through a number of example applications where the genetic element is substantial or dominating.


62P10 Applications of statistics to biology and medical sciences; meta analysis
92D10 Genetics and epigenetics
05C90 Applications of graph theory


HUGIN; SimWalk2
Full Text: DOI


[1] Adalsteinsson, S., Hersteinsson, P. and Gunnarsson, E. (1987). Fox colors in relation to colors in mice and sheep. J. Heredity 78 235–237.
[2] Amestoy, P. R., Davis, T. A. and Duff, I. S. (1996). An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17 886–905. · Zbl 0861.65021
[3] Andersen, S. K., Olesen, K. G., Jensen, F. V. and Jensen, F. (1989). HUGIN—a shell for building belief universes for expert systems. In Proc. 11th International Joint Conference on Artificial Intelligence 1080–1085. Morgan Kaufmann, San Mateo, CA. · Zbl 0713.68051
[4] Baum, L. E. (1972). An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes. In Inequalities. III (O. Shisha, ed.) 1–8. Academic Press, New York.
[5] Berry, A., Bordat, J.-P. and Cogis, O. (2000). Generating all the minimal separators of a graph. Internat. J. Found. Comput. Sci. 11 397–403. · Zbl 1320.05120
[6] Bouchitté, V. and Todinca, I. (2001). Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31 212–232. · Zbl 0987.05085
[7] Cannings, C., Thompson, E. A. and Skolnick, M. H. (1978). Probability functions on complex pedigrees. Adv. in Appl. Probab. 10 26–61. JSTOR: · Zbl 0431.92019
[8] Cottingham, R. W., Idury, R. M. and Schäffer, A. A. (1993). Faster sequential genetic linkage computations. Amer. J. Human Genetics 53 252–263.
[9] Cowell, R. G., Dawid, A. P., Lauritzen, S. L. and Spiegelhalter, D. J. (1999). Probabilistic Networks and Expert Systems . Springer, New York. · Zbl 0937.68121
[10] Dawid, A. P. (1992). Applications of a general propagation algorithm for probabilistic expert systems. Statist. Comput. 2 25–36.
[11] Dawid, A. P. and Mortera, J. (1996). Coherent analysis of forensic identification evidence. J. Roy. Statist. Soc. Ser. B 58 425–443. JSTOR: · Zbl 0853.62095
[12] Dawid, A. P. and Mortera, J. (1998). Forensic identification with imperfect evidence. Biometrika 85 835–849. JSTOR: · Zbl 0921.62129
[13] Dawid, A. P., Mortera, J. and Pascali, V. L. (2001). Non-fatherhood or mutation? A probabilistic approach to parental exclusion in paternity testing. Forensic Sci. Int. 124 55–61.
[14] Dawid, A. P., Mortera, J., Pascali, V. L. and van Boxel, D. (2002). Probabilistic expert systems for forensic infererence from genetic markers. Scand. J. Statist. 29 577–595. · Zbl 1035.62111
[15] Egeland, T., Mostad, P. F., Mevåg, B. and Stenersen, M. (2000). Beyond traditional paternity and identification cases: Selecting the most probable pedigree. Forensic Sci. Int. 110 47–59.
[16] Elston, R. C. and Stewart, J. (1971). A general model for the genetic analysis of pedigree data. Human Heredity 21 523–542.
[17] Falconer, D. S. and Mackay, T. F. C. (1996). Introduction to Quantitative Genetics , 4th ed. Addison Wesley Longman Limited, Harlow, UK.
[18] Fernandez, S. A., Fernando, R. L., Gulbrandtsen, B., Totir, L. R. and Carriquiry, A. L. (2001). Sampling genotypes in large pedigrees with loops. Genetics Selection Evolution 33 337–367.
[19] Fishelson, M. and Geiger, D. (2002). Exact genetic linkage computations for general pedigrees. Bioinformatics 18 S189–S198.
[20] George, A. and Liu, J. W. H. (1989). The evolution of the minimum degree ordering algorithm. SIAM Rev. 31 1–19. JSTOR: · Zbl 0671.65024
[21] Gill, P. E., Ivanov, P. L., Kimpton, C., Piercy, R., Benson, N., Tully, G., Evett, I., Hagelberg, E. and Sullivan, K. (1994). Identification of the remains of the Romanov family by DNA analysis. Nature Genetics 6 130–135.
[22] Haldane, J. B. S. (1919). The combination of linkage values and the calculation of distances between the loci of linked factors. J. Genetics 8 299–309.
[23] Hansen, B. and Pedersen, C. B. (1994). Analysing complex pedigrees using Gibbs sampling: A theoretical and empirical investigation. Technical Report R-94-2032, Institute for Electronic Systems, Aalborg Univ., Aalborg, Denmark.
[24] Heath, S. C. (2003). Genetic linkage analysis using Markov chain Monte Carlo techniques. In Highly Structured Stochastic Systems (P. J. Green, N. L. Hjort and S. Richardson, eds.) 363–381. Oxford Univ. Press.
[25] Jensen, C. S. (1997). Blocking Gibbs sampling for inference in large and complex Bayesian networks with applications in genetics. Ph.D. thesis, Aalborg Univ., Aalborg, Denmark.
[26] Jensen, C. S., Kjærulff, U. and Kong, A. (1995). Blocking Gibbs sampling in very large probabilistic expert systems. Int. J. Human-Computer Studies 42 647–666.
[27] Jensen, C. S. and Kong, A. (1999). Blocking Gibbs sampling for linkage analysis in large pedigrees with many loops. Amer. J. Human Genetics 65 885–901.
[28] Jensen, F. V. (1996). An Introduction to Bayesian Networks . Springer, New York.
[29] Jensen, F. V. (2002). HUGIN API Reference Manual Version 5.4 . HUGIN Expert Ltd., Aalborg, Denmark.
[30] Jensen, F. V., Lauritzen, S. L. and Olesen, K. G. (1990). Bayesian updating in causal probabilistic networks by local computation. Computational Statistics Quarterly 4 269–282. · Zbl 0715.68076
[31] Kjærulff, U. (1992). Optimal decomposition of probabilistic networks by simulated annealing. Statist. Comput. 2 7–17.
[32] Kong, A. (1991). Efficient methods for computing linkage likelihoods of recessive diseases in inbred pedigrees. Genetic Epidemiology 8 81–103.
[33] Kruglyak, L., Daly, M. J., Reeve-Daly, M. P. and Lander, E. S. (1996). Parametric and nonparametric linkage analysis: A unified multipoint approach. Amer. J. Human Genetics 58 1347–1363.
[34] Lander, E. S. and Green, P. (1987). Construction of multilocus genetic linkage maps in humans. Proc. Natl. Acad. Sci. U.S.A. 84 2363–2367.
[35] Lander, E. S. and Schork, N. J. (1994). Genetic dissection of complex traits. Science 265 2037–2048.
[36] Lange, K. and Elston, R. C. (1975). Extensions to pedigree analysis. I. Likelihood calculations for simple and complex pedigrees. Human Heredity 25 95–105.
[37] Lauritzen, S. L. (1996). Graphical Models . Clarendon, Oxford. · Zbl 0907.62001
[38] Lauritzen, S. L. (2001). Causal inference from graphical models. In Complex Stochastic Systems (O. E. Barndorff-Nielsen, D. R. Cox and C. Klüppelberg, eds.) 63–107. Chapman and Hall/CRC Press, Boca Raton, FL. · Zbl 1010.62004
[39] Lauritzen, S. L. and Jensen, F. V. (1997). Local computation with valuations from a commutative semigroup. Ann. Math. Artificial Intelligence 21 51–69. · Zbl 0895.68045
[40] Lauritzen, S. L. and Spiegelhalter, D. J. (1988). Local computations with probabilities on graphical structures and their application to expert systems (with discussion). J. Roy. Statist. Soc. Ser. B 50 157–224. JSTOR: · Zbl 0684.68106
[41] Lund, M. S. and Jensen, C. S. (1999). Blocking Gibbs sampling in the mixed inheritance model using graph theory. Genetics Selection Evolution 31 3–24.
[42] Mendel, G. (1866). Experiments in plant hybridisation. (Mendel’s original paper in English translation, with a commentary by R. A. Fisher, J. H. Bennett, ed., was published by Oliver and Boyd, Edinburgh, 1965.)
[43] Monaco, A. P., Bertelson, C. J., Middlesworth, W., Colletti, C. A., Aldridge, J., Fischbeck, K. H., Bartlett, R., Pericak-Vance, M. A., Roses, A. D. and Kunkel, L. M. (1985). Detection of deletions spanning the Duchenne muscular dystrophy locus using a tightly linked DNA segment. Nature 316 842–845.
[44] Mortera, J., Dawid, A. P. and Lauritzen, S. L. (2003). Probabilistic expert systems for DNA mixture profiling. Theor. Population Biology 63 191–205. · Zbl 1105.92017
[45] Morton, N. E. (1955). Sequential tests for the detection of linkage. Amer. J. Human Genetics 7 277–318.
[46] O’Connell, J. R. (2001). Rapid multipoint linkage analysis via inheritance vectors in the Elston–Stewart algorithm. Human Heredity 51 226–240.
[47] Ott, J. (1999). Analysis of Human Genetic Linkage , 3rd ed. Johns Hopkins Univ. Press, Baltimore.
[48] Pearl, J. (1986). Fusion, propagation and structuring in belief networks. Artificial Intelligence 29 241–288. · Zbl 0624.68081
[49] Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems . Morgan Kaufmann, San Mateo, CA. · Zbl 0649.68104
[50] Riordan, J. R., Rommens, J. M., Kerem, B., Alon, N., Rozmahel, R., Grzelczak, Z., Zielenski, J., Lok, S., Plavsic, N., Chou, J. L., Drumm, M. L., Iannuzzi, M. C., Collins, F. S. and Tsui, L. C. (1989). Identification of the cystic fibrosis gene: Cloning and characterization of complimentary DNA. Science 245 1066–1073.
[51] Sham, P. (1997). Statistics in Human Genetics . Arnold, London. · Zbl 0895.62109
[52] Sheehan, N. A. (2000). On the application of Markov chain Monte Carlo methods to genetic analyses on complex pedigrees. Internat. Statist. Rev. 68 83–110. · Zbl 1107.92305
[53] Sheehan, N. A., Gulbrandtsen, B., Lund, M. S. and Sorensen, D. A. (2002). Bayesian MCMC mapping of quantitative trait loci in a half-sib design: A graphical model perspective. Internat. Statist. Rev. 70 241–267. · Zbl 1217.62190
[54] Shenoy, P. P. and Shafer, G. (1990). Axioms for probability and belief–function propagation. In Uncertainty in Artificial Intelligence (R. D. Shachter, T. S. Levitt, L. N. Kanal and J. F. Lemmer, eds.) 4 169–198. North-Holland, Amsterdam.
[55] Shoikhet, K. and Geiger, D. (1997). A practical algorithm for finding optimal triangulations. In Proc. 14th National Conference on Artificial Intelligence 185–190. AAAI Press, Menlo Park, CA.
[56] Silvers, W. K. (1979). The Coat Colors of Mice . Springer, New York.
[57] Skjøth, F., Lohi, O. and Thomas, A. W. (1994). Genetic models for the inheritance of the silver colour mutation of foxes. Genetical Res. 64 11–18.
[58] Sobel, E. and Lange, K. (1996). Descent graphs in pedigree analysis: Applications to haplotyping, location scores, and marker-sharing statistics. Amer. J. Human Genetics 58 1323–1337.
[59] Spiegelhalter, D. J. (1990). Fast algorithms for probabilistic reasoning in influence diagrams, with applications in genetics and expert systems (with discussion). In Influence Diagrams, Belief Nets and Decision Analysis (R. M. Oliver and J. Q. Smith, eds.) 361–384. Wiley, Chichester, U.K.
[60] Spiegelhalter, D. J. (1998). Bayesian graphical modelling: A case-study in monitoring health outcomes. Appl. Statist. 47 115–133.
[61] Thomas, A. (1985). Data structures, methods of approximation and optimal computation for pedigree analysis. Ph.D. thesis, Cambridge Univ.
[62] Thomas, A., Gutin, A., Abkevich, V. and Bansal, A. (2000). Multilocus linkage analysis by blocked Gibbs sampling. Statist. Comput. 10 259–269.
[63] Thompson, E. A. (1981). Pedigree analysis of Hodgkin’s disease in a Newfoundland genealogy. Ann. Human Genetics 45 279–292.
[64] Thompson, E. A. (1986). Pedigree Analysis in Human Genetics . Johns Hopkins Univ. Press, Baltimore.
[65] Thompson, E. A. (1994). Monte Carlo likelihood in genetic mapping. Statist. Sci. 9 355–366.
[66] Thompson, E. A. (2000). Statistical Inference from Genetic Data on Pedigrees . IMS, Beachwood, OH. · Zbl 0972.92022
[67] Thompson, E. A. (2001). Monte Carlo methods on genetic structures. In Complex Stochastic Systems (O. E. Barndorff-Nielsen, D. R. Cox and C. Klüppelberg, eds.) 176–218. Chapman and Hall/CRC Press, Boca Raton, FL. · Zbl 1002.65007
[68] Thompson, E. A. and Heath, S. C. (1999). Estimation of conditional multilocus gene identity among relatives. In Statistics in Molecular Biology and Genetics (F. Seillier-Moiseiwitsch, ed.) 95–113. IMS, Hayward, CA.
[69] Thompson, E. A. and Wijsman, E. M. (1990). The Gibbs sampler on extended pedigrees: Monte Carlo methods for the genetic analysis of complex traits. Technical Report 193, Dept. Statistics, Univ. Washington, Seattle.
[70] Yannakakis, M. (1981). Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2 77–79. · Zbl 0496.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.