# Fold Envelopes

**Brief description**

A "fold envelope" is simply an ordered listing of the inside subsequences *(i..j)*
that are visited in a dynamic programming iteration
for calculating likelihoods of sequences under Stochastic Context Free Grammars.

Such DP iterations include the Cocke-Younger-Kasami algorithm, the Inside algorithm and the Outside algorithm.
The ordering of sequences in a fold envelope is inside-before-outside (by definition),
so if *i<j<k<l* where *(i..l)* and *(j..k)* are subsequences in a fold envelope,
then *(j..k)* appears before *(i..l)* .

Fold envelopes can be used to constrain a DP iteration, e.g. to restrict the iteration to a set of pre-specified structures, or to force the DP iteration to be more like an HMM iteration.

Specifically, suppose that the grammar is right-regular (and therefore equivalent to an HMM).
Then, if the fold envelope only includes
subsequences of the form *(i..L)* , where *L* is the sequence length, then the iteration will correctly compute
sequence likelihoods, while having the same time and memory requirements as the Viterbi or Forward algorithms.

**References**

Holmes & Rubin: Pairwise RNA structure comparison with stochastic context-free grammars. *Pac Symp Biocomput* 2002;:163-74.

(PDF of this paper)