Page 256 - Applied Probability

11. Radiation Hybrid Mapping
243
The necessity of evaluating this sum of products lands us in familiar terrain.
Here, however, there is more symmetry than in pedigree calculations. As
suggested by Baum [2, 11], it is natural to evaluate the sum as an iterated
sum in either the forward or reverse direction.
Suppose Z i is the unobserved number of markers at locus i. The only
restriction on Z i is that Z i ∈ O i . Baum’s forward algorithm is based on
recursively evaluating the joint probabilities
α k (j) = Pr(Z 1 ∈ O 1 ,...,Z k−1 ∈ O k−1 ,Z k = j)
c
j c−j
for j ∈ O k . At the leftmost locus α 1 (j)= r (1 − r) , and the obvious
j
update is

α k+1 (j) = α k (i)t c,k (i, j).
i∈O k

The likelihood (11.14) can be recovered by forming the sum α m (j)
j∈O m
at the rightmost locus.
In Baum’s backward algorithm we recursively evaluate the conditional
probabilities
β k (i)=Pr(Z k+1 ∈ O k+1 ,...,Z m ∈ O m | Z k = i),
for i ∈ O k , starting by convention at β m (j) = 1 for j ∈ O m . The required
update is clearly

β k (i) = t c,k (i, j)β k+1 (j).
j∈O k+1
In this instance the likelihood (11.14) can be recovered at the leftmost locus

by forming the sum α 1 (i)β 1 (i).
i∈O 1
A quick search of the likelihood can be achieved if the partial derivatives
of the likelihood can be computed analytically. Let us now indicate briefly
how to do this based on the intermediate results of Baum’s forward and
backward algorithms. For instance, consider a partial derivative ∂ P of P
∂θ i
with respect to a breakage probability. Inspection of equation (11.14) leads
to the expression
∂
c
P = ··· r (1 − r) c−j 1
j 1
∂θ i j 1
j 1 ∈O 1 j m ∈O m
∂

× t c,i (j i ,j i+1 ) t c,k (j k ,j k+1 ). (11.15)
∂θ i
k =i
Evidently, (11.15) can be evaluated as
∂ ∂
P = α i (j i ) t c,i (j i ,j i+1 ) β i+1 (j i+1 ).(11.16)
∂θ i ∂θ i
j i ∈O i j i+1 ∈O i+1