A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure
Top Cited Papers
Open Access
- 2 July 2002
- journal article
- research article
- Published by Springer Nature in BMC Bioinformatics
- Vol. 3 (1) , 18
- https://doi.org/10.1186/1471-2105-3-18
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(N-3) 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(N-2 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.Keywords
This publication has 55 references indexed in Scilit:
- Dynalign: an algorithm for finding the secondary structure common to two RNA sequencesJournal of Molecular Biology, 2002
- Non–coding RNA genes and the modern RNA worldNature Reviews Genetics, 2001
- A Polyhedral Approach to RNA Sequence Structure AlignmentJournal of Computational Biology, 1998
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programsNucleic Acids Research, 1997
- tRNAscan-SE: A Program for Improved Detection of Transfer RNA Genes in Genomic SequenceNucleic Acids Research, 1997
- CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choiceNucleic Acids Research, 1994
- Hidden Markov Models in Computational BiologyJournal of Molecular Biology, 1994
- Automatic Identification of Group I Intron Cores in Genomic DNA SequencesJournal of Molecular Biology, 1994
- Identifying potential tRNA genes in genomic DNA sequencesJournal of Molecular Biology, 1991
- A tutorial on hidden Markov models and selected applications in speech recognitionProceedings of the IEEE, 1989