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

by: SR Eddy

BMC Bioinformatics, Vol. 3, No. 1. (2 July 2002)

View FullText article

DOI, Pubmed, Hubmed

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

evaf, marcius, mtagaya, vwchan, beta (group), BioinfoCIPF (group), SGU-CIPF (group)

Find related articles with these CiteULike tags

algorithm, alignment, bioinformatics, covariance, 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.

@article{Eddy2002, 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.}, address = {Howard Hughes Medical Institute \& Department of Genetics, Washington University School of Medicine, Saint Louis, Missouri 63110 USA. eddy@genetics.wustl.edu}, author = {Eddy, S. R. }, citeulike-article-id = {118691}, doi = {http://dx.doi.org/10.1186/1471-2105-3-18}, issn = {1471-2105}, journal = {BMC Bioinformatics}, keywords = {covariance, rna}, month = {July}, number = {1}, posted-at = {2007-05-29 22:58:37}, priority = {2}, title = {A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure.}, url = {http://dx.doi.org/10.1186/1471-2105-3-18}, volume = {3}, year = {2002} }

RIS record

TY - JOUR ID - Eddy2002 L3 - citeulike-article-id:118691 TI - A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure. JF - BMC Bioinformatics VL - 3 IS - 1 AD - Howard Hughes Medical Institute & Department of Genetics, Washington University School of Medicine, Saint Louis, Missouri 63110 USA. eddy@genetics.wustl.edu SN - 1471-2105 N2 - 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. KW - covariance KW - rna AU - Eddy, SR PY - 2002/07/02/ UR - http://dx.doi.org/10.1186/1471-2105-3-18 ER -

RIS BibTeX