= Felsenstein pruning algorithm
{c}
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_bK(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>.
Back to article page
