Felsenstein pruning algorithm

The Felsenstein pruning algorithm computes a site likelihood function by sum-product belief propagation from leaves to root. For a finite-state Markov kernel $K$, the subtree likelihood function obeys $L_v(a)={\prod }_{w\text{ child of }v}{\sum }_{b}K(a,b)L_w(b)$, with observed-state indicators at leaves. Summing against the root probability distribution gives the site likelihood function. An outward pass gives edge posterior probabilities and expected transition counts for the expectation-maximization algorithm.