A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure.
A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure.
复制标题
一种记忆有效的动力编程算法，用于最佳对RNA二级结构的序列对齐。
DOI：
10.1186/1471-2105-3-18
复制
发表时间：
2002-07-02
影响因子：
3
通讯作者：
Eddy, SR
中科院分区：
文献类型：
--
作者：
Eddy, SR
协方差模型 (CM) 是 RNA 二级结构的概率模型，类似于线性序列的隐马尔可夫模型。将 CM 与长度为 N 的 RNA 序列比对的动态编程算法在内存中的复杂度为 O(N3)。这仅适用于小 RNA。我描述了比对算法的分而治之的变体，它类似于用于线性序列比对的内存高效的 Myers/Miller 动态编程算法。新算法的内存复杂度为 O(N2 log N)，但代价是时间上的一个小的常数因子。以前需要高达 150 GB 内存的最佳核糖体 RNA 结构比对现在只需要不到 270 MB。
Covariance 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(N3) in memory. This is only practical for small RNAs. I describe a divide and conquer variant of the alignment algorithm that is analogous to memory-efficient Myers/Miller dynamic programming algorithms for linear sequence alignment. The new algorithm has an O(N2 log N) memory complexity, at the expense of a small constant factor in time. Optimal ribosomal RNA structural alignments that previously required up to 150 GB of memory now require less than 270 MB.
登录
查看更多内容
DOI：
10.1073/pnas.89.22.10915
发表时间：
1992-11-15
影响因子：
11.1
作者：
HENIKOFF, S;HENIKOFF, JG
通讯作者：
HENIKOFF, JG
影响因子：
5.6
作者：
KROGH, A;BROWN, M;HAUSSLER, D
通讯作者：
HAUSSLER, D
影响因子：
5.8
作者：
Knudsen, B;Hein, J
通讯作者：
Hein, J
影响因子：
14.9
作者：
Gorodkin, J;Stricklin, SL;Stormo, GD
通讯作者：
Stormo, GD
影响因子：
14.9
作者：
EDDY, SR;DURBIN, R
通讯作者：
DURBIN, R