Format

Send to:

Choose Destination
See comment in PubMed Commons below
BMC Bioinformatics. 2002 Jul 2;3:18.

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

Author information

  • 1Howard Hughes Medical Institute & Department of Genetics, Washington University School of Medicine, Saint Louis, Missouri 63110 USA. eddy@genetics.wustl.edu

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.

PMID:
12095421
[PubMed - indexed for MEDLINE]
PMCID:
PMC119854
Free PMC Article
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for BioMed Central Icon for PubMed Central
    Loading ...
    Write to the Help Desk