One can adapt the Lander-Green-Kruglyak algorithm to perform haplotyping. In the notation of Section 9.11, define i(yi | j) to be the likelihood of the

One can adapt the Lander-Green-Kruglyak algorithm to perform haplotyping. In the notation of Section 9.11, define γi(yi | j) to be the likelihood of the most likely descent state consistent with the descent graph j and the marker phenotypes yi at locus i. Section 9.9 describes how to compute γi(yi | j). At locus 1 set β1(j) = γ1(y1 | j)

and p1(j) = j for each descent graph j of the pedigree. Given these initial values, recursively set

βi+1(k) = maxj βi(j)ti(k | j)γi+1(yi+1 | k).

If the maximum over j occurs for descent graph j∗, let pi+1(k)=(pi(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 pn(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(n22m), where m is the effective number of meioses.