A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure.
BACKGROUND
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.


RESULTS
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.


CONCLUSIONS
Optimal ribosomal RNA structural alignments that previously required up to 150 GB of memory now require less than 270 MB.
Eddy
Sean R
SR
Howard Hughes Medical Institute & Department of Genetics, Washington University School of Medicine, Saint Louis, Missouri 63110 USA. eddy@genetics.wustl.edu
D000465:Algorithms; D019295:Computational Biology / Q000706:statistics & numerical data; D016384:Consensus Sequence; D036262:Empirical Research; D008390:Markov Chains; D015233:Models, Statistical; D009690:Nucleic Acid Conformation; D011382:Programming, Linear / Q000706:statistics & numerical data*; D012313:RNA / Q000737:chemistry*; D012335:RNA, Ribosomal / Q000737:chemistry; D020733:RNA, Small Cytoplasmic / Q000737:chemistry; D012343:RNA, Transfer / Q000737:chemistry; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data*; D018271:Signal Recognition Particle / Q000737:chemistry; D012984:Software; D012985:Software Design; D013997:Time Factors
C115990:7SL RNA; D012335:RNA, Ribosomal; D020733:RNA, Small Cytoplasmic; D018271:Signal Recognition Particle; D012313:RNA; D012343:RNA, Transfer