Page 203 - Applied Probability

9. Descent Graph Methods
188
9.11 The Lander-Green-Kruglyak Algorithm
Descent graphs also provide a basis for deterministically computing the
likelihood of a small pedigree [18, 19, 20, 21]. Success within this framework
depends on (a) the assumption of genetic equilibrium, (b) the product
rule for calculating penetrances across many loci, and (c) the application
of results from the theory of hidden Markov chains and Fourier analysis.
In explaining how these parts fit together, our first order of business is
to identify an appropriate Markov chain. Instead of viewing the chain as
evolving over time, we think of it as evolving from one locus to the next
along a sequence of ordered loci. At each locus, the state of the chain is the
pedigree’s descent graph at that locus. Likelihood calculation proceeds via
Baum’s forward algorithm as described here and in Chapter 11 [1, 4].
Baum’s algorithm recursively updates the joint probabilities
α i (j)=Pr(Y 1 = y 1 ,...,Y i−1 = y i−1 ,Z i = j),
where in the current context Y i represents the random vector of pheno-
types at locus i, and Z i represents the random descent graph at that lo-
cus. In Section 9.5 we dealt with the problem of computing the likelihood
φ i (y i | j) that Y i = y i given that Z i = j. Each of the m meiotic events
in the pedigree involves a random choice of whether the contributing par-
ent transmits a grandmaternally or a grandpaternally derived allele. These
choices determine 2 m a priori equally likely descent graphs at each locus.
Hence, α 1 (j)= 2 −m at the first locus. Because of the inherent phase un-
certainties within a pedigree founder, it is also possible to force one child of
each founder to inherit the founder’s grandmaternal allele at an autosomal
locus [20]. This action decreases the size of the state space of the Markov
chain and speeds up likelihood evaluation. In the interests of brevity, we
omit further discussion of this subtle effect.
Baum’s forward algorithm updates α i (j)via

α i+1 (k)= α i (j)φ i (y i | j)t i (k | j), (9.13)
j
where t i (k | j) is the conditional probability that descent graph k occurs
at locus i + 1 given descent graph j at locus i. At the last locus, say
locus n, we recover the likelihood of the pedigree by forming the sum

φ n (y n | j)α n (j). At first sight it appears that the update (9.13) takes
j
on the order of O(2 2m ) arithmetic operations. This discouraging estimate
neglects crucial symmetries, however.
To expose these symmetries, we represent the descent graphs j and k by
m-vectors of indicators
j =(j 1 ,...,j m )
k =(k 1 ,...,k m ),