Specific alignment of structured RNA: stochastic grammars and sequence annealing.
BACKGROUND
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.


BACKGROUND
Stemloc-AMA is available from http://biowiki.org/StemLocAMA as part of the dart software package for sequence analysis.
Bradley
Robert K
RK
Biophysics Graduate Group, Department of Mathematics and Department of Bioengineering, University of California, Berkeley, CA 94720, USA.
Pachter
Lior
L
Holmes
Ian
I
D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D016678:Genome; D023281:Genomics; D022661:RNA, Untranslated / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012984:Software
D022661:RNA, Untranslated
BMC Bioinformatics. 2006 Sep 04;7:400
16952317
Bioinformatics. 2007 Apr 15;23(8):926-32
17324941
BMC Bioinformatics. 2008 Jan 23;9:33
18215258
Nucleic Acids Res. 2005 Apr 28;33(8):2433-9
15860779
Bioinformatics. 2007 Dec 15;23(24):3304-11
18006551
J Mol Biol. 2002 Mar 22;317(2):191-203
11902836
Nucleic Acids Res. 1997 Sep 15;25(18):3724-32
9278497
Genome Res. 2008 Feb;18(2):242-51
18096747
BMC Bioinformatics. 2006 Oct 03;7:428
17018148
J Mol Biol. 1999 May 21;288(5):911-40
10329189
Bioinformatics. 2005 May 1;21(9):1815-24
15657094
Bioinformatics. 2007 Aug 1;23(15):1883-91
17537756
Genome Res. 2007 Dec;17(12):1850-64
17989254
PLoS Comput Biol. 2007 Apr 13;3(4):e65
17432929
J Mol Evol. 1987;25(4):351-60
3118049
BMC Genomics. 2007 Nov 08;8:406
17996037
Biopolymers. 1990 May-Jun;29(6-7):1105-19
1695107
BMC Bioinformatics. 2005 Mar 24;6:73
15790387
Bioinformatics. 2004 Sep 22;20(14):2222-7
15073017
Bioinformatics. 2007 Nov 1;23(21):2947-8
17846036
Bioinformatics. 2007 Jan 15;23(2):e24-9
17237099
J Mol Biol. 1996 Dec 13;264(4):823-38
8980688
Bioinformatics. 2007 Jul 1;23(13):1588-98
17459961
Algorithms Mol Biol. 2006 Oct 24;1:19
17062125
BMC Bioinformatics. 2004 Jun 04;5:71
15180907
Cold Spring Harb Symp Quant Biol. 1987;52:123-33
2456874
Bioinformatics. 2006 Jul 15;22(14):e90-8
16873527
PLoS Comput Biol. 2007 Oct;3(10):1896-908
17937495
J Mol Biol. 2002 Jun 21;319(5):1059-66
12079347
Nucleic Acids Res. 2003 Jul 1;31(13):3423-8
12824339