title: A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure.
abstract: 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.
authors.affiliation: Howard Hughes Medical Institute & Department of Genetics, Washington University School of Medicine, Saint Louis, Missouri 63110 USA. eddy@genetics.wustl.edu
authors.forename: Sean R
authors.initials: SR
authors.lastname: Eddy
mesh_terms: 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
chemical_list: C115990:7SL RNA; D012335:RNA, Ribosomal; D020733:RNA, Small Cytoplasmic; D018271:Signal Recognition Particle; D012313:RNA; D012343:RNA, Transfer