title: Specific alignment of structured RNA: stochastic grammars and sequence annealing.
abstract: 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.
authors.affiliation: Biophysics Graduate Group, Department of Mathematics and Department of Bioengineering, University of California, Berkeley, CA 94720, USA.
authors.forename: Robert K
authors.initials: RK
authors.lastname: Bradley
authors.forename: Lior
authors.initials: L
authors.lastname: Pachter
authors.forename: Ian
authors.initials: I
authors.lastname: Holmes
mesh_terms: 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
chemical_list: D022661:RNA, Untranslated
references.citation: BMC Bioinformatics. 2006 Sep 04;7:400
references.pmid: 16952317
references.citation: Bioinformatics. 2007 Apr 15;23(8):926-32
references.pmid: 17324941
references.citation: BMC Bioinformatics. 2008 Jan 23;9:33
references.pmid: 18215258
references.citation: Nucleic Acids Res. 2005 Apr 28;33(8):2433-9
references.pmid: 15860779
references.citation: Bioinformatics. 2007 Dec 15;23(24):3304-11
references.pmid: 18006551
references.citation: J Mol Biol. 2002 Mar 22;317(2):191-203
references.pmid: 11902836
references.citation: Nucleic Acids Res. 1997 Sep 15;25(18):3724-32
references.pmid: 9278497
references.citation: Genome Res. 2008 Feb;18(2):242-51
references.pmid: 18096747
references.citation: BMC Bioinformatics. 2006 Oct 03;7:428
references.pmid: 17018148
references.citation: J Mol Biol. 1999 May 21;288(5):911-40
references.pmid: 10329189
references.citation: Bioinformatics. 2005 May 1;21(9):1815-24
references.pmid: 15657094
references.citation: Bioinformatics. 2007 Aug 1;23(15):1883-91
references.pmid: 17537756
references.citation: Genome Res. 2007 Dec;17(12):1850-64
references.pmid: 17989254
references.citation: PLoS Comput Biol. 2007 Apr 13;3(4):e65
references.pmid: 17432929
references.citation: J Mol Evol. 1987;25(4):351-60
references.pmid: 3118049
references.citation: BMC Genomics. 2007 Nov 08;8:406
references.pmid: 17996037
references.citation: Biopolymers. 1990 May-Jun;29(6-7):1105-19
references.pmid: 1695107
references.citation: BMC Bioinformatics. 2005 Mar 24;6:73
references.pmid: 15790387
references.citation: Bioinformatics. 2004 Sep 22;20(14):2222-7
references.pmid: 15073017
references.citation: Bioinformatics. 2007 Nov 1;23(21):2947-8
references.pmid: 17846036
references.citation: Bioinformatics. 2007 Jan 15;23(2):e24-9
references.pmid: 17237099
references.citation: J Mol Biol. 1996 Dec 13;264(4):823-38
references.pmid: 8980688
references.citation: Bioinformatics. 2007 Jul 1;23(13):1588-98
references.pmid: 17459961
references.citation: Algorithms Mol Biol. 2006 Oct 24;1:19
references.pmid: 17062125
references.citation: BMC Bioinformatics. 2004 Jun 04;5:71
references.pmid: 15180907
references.citation: Cold Spring Harb Symp Quant Biol. 1987;52:123-33
references.pmid: 2456874
references.citation: Bioinformatics. 2006 Jul 15;22(14):e90-8
references.pmid: 16873527
references.citation: PLoS Comput Biol. 2007 Oct;3(10):1896-908
references.pmid: 17937495
references.citation: J Mol Biol. 2002 Jun 21;319(5):1059-66
references.pmid: 12079347
references.citation: Nucleic Acids Res. 2003 Jul 1;31(13):3423-8
references.pmid: 12824339