Fold Envelopes

From Biowiki
Jump to: navigation, search

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)