= Solution
For node $v$ with children $l,r$, the <phylogenetic pruning algorithm> combines the two conditionally independent descendant subtrees:
$$
L_v(a)=\left[\sum_b P_{ab}(t_l)L_l(b)\right]
\left[\sum_c P_{ac}(t_r)L_r(c)\right].
$$
The <likelihood function> is $\mathcal L(\mu)=\frac14\sum_a L_{\mathrm{root}}(a)$ under a uniform ancestral prior. In the supplied numbering, children have smaller indices than their parents, so increasing node order is a valid bottom-up traversal:
``
def felsenstein(prob, mu, L, left, right, left_time, right_time):
# All four entries are overwritten at every internal node.
for node in range(L, 2*L-1):
Tl = np.array([[jukes(a,b,left_time[node],mu)
for b in range(4)] for a in range(4)])
Tr = np.array([[jukes(a,b,right_time[node],mu)
for b in range(4)] for a in range(4)])
prob[node] = (Tl @ prob[left[node]]) * (Tr @ prob[right[node]])
return float(np.log(prob[-1].mean()))
print(felsenstein(prob, .5, len(leaves), left, right, left_time, right_time))
``
\b[At $\mu=0.5$, the log-likelihood is $-10.5052883$.] Internal rows must remain unnormalized in this implementation, because their magnitudes contribute to the tree <likelihood function>; normalization without retaining the removed factors would lose that information. The final root normalization required for a <posterior probability> is a separate step in part (e).
Back to article page
