Journal Article

Specific alignment of structured RNA: stochastic grammars and sequence annealing

Robert K. Bradley, Lior Pachter and Ian Holmes

in Bioinformatics

Volume 24, issue 23, pages 2677-2683
Published in print December 2008 | ISSN: 1367-4803
Published online September 2008 | e-ISSN: 1460-2059 | DOI:
Specific alignment of structured RNA: stochastic grammars and sequence annealing

More Like This

Show all results sharing this subject:

  • Bioinformatics and Computational Biology


Show Summary Details


Motivation: Whole-genome screens suggest that eukaryotic genomes are dense with non-coding RNAs (ncRNAs). We introduce a novel approach to RNA multiple alignment which couples a generative probabilistic model of sequence and structure with an efficient sequence annealing approach for exploring the space of multiple alignments. This leads to a new software program, Stemloc-AMA, that is both accurate and specific in the alignment of multiple related RNA sequences.

Results: When tested on the benchmark datasets BRalibase II and BRalibase 2.1, Stemloc-AMA has comparable sensitivity to and better specificity than the best competing methods. We use a large-scale random sequence experiment to show that while most alignment programs maximize sensitivity at the expense of specificity, even to the point of giving complete alignments of non-homologous sequences, Stemloc-AMA aligns only sequences with detectable homology and leaves unrelated sequences largely unaligned. Such accurate and specific alignments are crucial for comparative-genomics analysis, from inferring phylogeny to estimating substitution rates across different lineages.

Availability: Stemloc-AMA is available from as part of the dart software package for sequence analysis.


Supplementary information: Supplementary data are available at Bioinformatics online.

Journal Article.  4980 words.  Illustrated.

Subjects: Bioinformatics and Computational Biology

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.