A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure

摘要

BackgroundCovariance models (CMs) are probabilistic models of RNA secondary structure, analogous to profile hidden Markov models of linear sequence. The dynamic programming algorithm for aligning a CM to an RNA sequence of length N is O(N³) in memory. This is only practical for small RNAs.