Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 39 / 3 / f

The nine maximal cliques of this triangulation areEvery other nonempty clique is a subset of one of these. One junction tree, listing its separators after the edges, isEach variable appears in a connected subtree, verifying the running intersection property. For example, the cliques containing $M$ are $K_1,K_2,K_4,K_5,K_6$, and their connecting paths contain $M$ throughout.

The junction tree algorithm assigns every founder factor and every child-with-parents factor to one containing clique, and multiplies any observation or penetrance factors there. The junction-tree sum-product message from clique $i$ to clique $j$ sums out $C_i\setminus (C_i\cap C_j)$ after multiplying the local potential and all incoming messages except $j$'s. An inward pass sums the joint probability or pedigree likelihood; a subsequent outward pass gives each person's posterior genotype probabilities. This is the same variable-elimination principle as the Elston-Stewart algorithm, organized to handle the pedigree loop. Its largest clique has four genotype variables, much smaller than summing naively over fourteen at once.