Faster dynamic programming using the convolution tree.

<p>(<b>a</b>) An alternate transformation for efficiently computing posteriors for all proteins. Instead of unrolling the commutative and associative operator one protein at a time as performed by the quadratic dynamic programming algorithm, variables are paired successively, resulting in a tree with depth (when is a power of ). (<b>b</b>) Inference on this tree can be performed by solving a minimal ternary node structure and then proceeding inductively: all nodes (except for the proteins themselves) have two parent subtrees, and , and one child. The parent subtrees connect the node of interest to all data reachable through the parents above (partitioned into and , respectively), and the child subtree connects to all data reachable below, (denoted ). The joint probability with all data above can be passed as messages from parents to children, and the likelihoods given data below (that is, all data reachable through a downward edge out of a given node) can be passed upward from child to parents. Each of these three messages turns out to be a convolutions (shown in inset). For example, all ways that can be computed by a shifted and reflected dot product, which finds all and with a sum of . Thus the prior probability for can be seen as a vector equal to the convolution of the prior probabilities of prior probabilities for and . These convolutions can be performed with fast Fourier transform (FFT) in time (where is the size of the possible state space of ). If the vectors are very sparse, then a standard discrete Fourier transform-based (DFT) convolution may be faster.