Page 213 - Applied Probability

9. Descent Graph Methods
198
11. Formally describe the transition rules T 2a and T 2b on descent graphs
in terms of the transition rules T 0 and T 1 .
t
12. Consider the set G of column vectors j =(j 1 ,... ,j m ) whose entries
are either 0 or 1. If m = 3, a typical vector in G is (0, 1, 1). Altogether
G has 2 m elements. Prove that G forms a commutative group under
the addition operation
t
j + k =[(j 1 + k 1 )mod2,... , (j m + k m )mod 2] .
This entails showing that
(a) If j and k are in G, then j + k is in G.
(b) For all j, k, and l in G, we have j +(k + l)= (j + k)+ l.
(c) For all j and k in G, we have j + k = k + j.
(d) There is an identity element 0 of G such that j +0 = j.
(e) Every element j has an additive inverse −j such that

j − j = j +(−j)= 0.

Note that you may simply cite without proof any relevant facts about
modulo arithmetic.

13. One can adapt the Lander-Green-Kruglyak algorithm to perform hap-
lotyping. In the notation of Section 9.11, define γ i (y i | j) to be the
likelihood of the most likely descent state consistent with the descent
graph j and the marker phenotypes y i at locus i. Section 9.9 de-
scribes how to compute γ i (y i | j). At locus 1 set β 1 (j)= γ 1 (y 1 | j)
and p 1 (j)= j for each descent graph j of the pedigree. Given these
initial values, recursively set

β i+1 (k) = max β i (j)t i (k | j)γ i+1 (y i+1 | k).
j
∗
If the maximum over j occurs for descent graph j ,let
p i+1 (k)=(p i (j ),k).
∗
∗
In the case of a tie, arbitrarily choose j from among the possible
best j. At locus n, the last locus, suppose k provides a maximum
of β n (j). Show that the path p n (k) solves the haplotyping problem
in the sense of providing an optimal descent graph, which can be
completed to an optimal descent state as described in Section 9.9.
Prove that this dynamic programming solution has computational
complexity O(n2 2m ), where m is the effective number of meioses.