{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T16:32:17Z","timestamp":1721925137162},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"23","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>\n               <jats:p>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.<\/jats:p>\n               <jats:p>Availability: \u00a0Stemloc-AMA is available from http:\/\/biowiki.org\/StemLocAMA as part of the dart software package for sequence analysis.<\/jats:p>\n               <jats:p>Contact: \u00a0lpachter@math.berkeley.edu; ihh@berkeley.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn495","type":"journal-article","created":{"date-parts":[[2008,9,17]],"date-time":"2008-09-17T03:08:35Z","timestamp":1221620915000},"page":"2677-2683","source":"Crossref","is-referenced-by-count":30,"title":["Specific alignment of structured RNA: stochastic grammars and sequence annealing"],"prefix":"10.1093","volume":"24","author":[{"given":"Robert K.","family":"Bradley","sequence":"first","affiliation":[{"name":"1 Biophysics Graduate Group, 2Department of Mathematics and 3Department of Bioengineering, University of California, Berkeley, CA 94720, USA"}]},{"given":"Lior","family":"Pachter","sequence":"additional","affiliation":[{"name":"1 Biophysics Graduate Group, 2Department of Mathematics and 3Department of Bioengineering, University of California, Berkeley, CA 94720, USA"}]},{"given":"Ian","family":"Holmes","sequence":"additional","affiliation":[{"name":"1 Biophysics Graduate Group, 2Department of Mathematics and 3Department of Bioengineering, University of California, Berkeley, CA 94720, USA"},{"name":"1 Biophysics Graduate Group, 2Department of Mathematics and 3Department of Bioengineering, University of California, Berkeley, CA 94720, USA"}]}],"member":"286","published-online":{"date-parts":[[2008,9,16]]},"reference":[{"key":"2023020212240617500_B1","doi-asserted-by":"crossref","first-page":"e90","DOI":"10.1093\/bioinformatics\/btl246","article-title":"CONTRAfold: RNA secondary structure prediction without physics-based models","volume":"22","author":"Do","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020212240617500_B2","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1186\/1471-2105-5-71","article-title":"Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction","volume":"5","author":"Dowell","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023020212240617500_B3","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1186\/1471-2105-7-400","article-title":"Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints","volume":"7","author":"Dowell","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023020212240617500_B4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin","year":"1998"},{"key":"2023020212240617500_B5","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","article-title":"Progressive sequence alignment as a prerequisite to correct phylogenetic trees","volume":"25","author":"Feng","year":"1987","journal-title":"J. Mol. Evol."},{"key":"2023020212240617500_B6","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1093\/nar\/gki541","article-title":"A benchmark of multiple sequence alignment programs upon structural RNAs","volume":"33","author":"Gardner","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023020212240617500_B7","doi-asserted-by":"crossref","first-page":"3724","DOI":"10.1093\/nar\/25.18.3724","article-title":"Finding the most significant common sequence and structure motifs in a set of RNA sequences","volume":"25","author":"Gorodkin","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023020212240617500_B8","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1006\/jmbi.1996.0679","article-title":"Significant improvement in accuracy of multiple protein alignments by iterative refinement as assessed by reference to structural alignments","volume":"264","author":"Gotoh","year":"1996","journal-title":"J. Mol. Biol."},{"key":"2023020212240617500_B9","doi-asserted-by":"crossref","first-page":"1815","DOI":"10.1093\/bioinformatics\/bti279","article-title":"Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%","volume":"21","author":"Havgaard","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020212240617500_B10","doi-asserted-by":"crossref","first-page":"1896","DOI":"10.1371\/journal.pcbi.0030193","article-title":"Fast pairwise structural RNA alignments by pruning of the dynamical programming matrix","volume":"3","author":"Havgaard","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023020212240617500_B11","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1016\/S0022-2836(02)00308-X","article-title":"Secondary structure prediction for aligned RNA sequences","volume":"319","author":"Hofacker","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023020212240617500_B12","doi-asserted-by":"crossref","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","article-title":"Alignment of RNA base pairing probability matrices","volume":"20","author":"Hofacker","year":"2004","journal-title":"Bioinformatics"},{"key":"2023020212240617500_B13","article-title":"Studies in probabilistic sequence alignment and evolution","volume-title":"PhD Thesis","author":"Holmes","year":"1998"},{"key":"2023020212240617500_B14","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1186\/1471-2105-6-73","article-title":"Accelerated probabilistic inference of RNA structure evolution","volume":"6","author":"Holmes","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023020212240617500_B15","doi-asserted-by":"crossref","first-page":"1588","DOI":"10.1093\/bioinformatics\/btm146","article-title":"Murlet: a practical multiple alignment tool for structural RNA sequences","volume":"23","author":"Kiryu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020212240617500_B16","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1186\/1471-2105-7-428","article-title":"XRate: a fast prototyping, training and annotation tool for phylo-grammars","volume":"7","author":"Klosterman","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023020212240617500_B17","doi-asserted-by":"crossref","first-page":"3423","DOI":"10.1093\/nar\/gkg614","article-title":"Pfold: RNA secondary structure prediction using stochastic context-free grammars","volume":"31","author":"Knudsen","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023020212240617500_B18","doi-asserted-by":"crossref","first-page":"2947","DOI":"10.1093\/bioinformatics\/btm404","article-title":"Clustal W and Clustal X version 2.0","volume":"23","author":"Larkin","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020212240617500_B19","doi-asserted-by":"crossref","first-page":"3304","DOI":"10.1093\/bioinformatics\/btm525","article-title":"MASTR: multiple alignment and structure prediction of non-coding RNAs using simulated annealing","volume":"23","author":"Lindgreen","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020212240617500_B20","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1006\/jmbi.2001.5351","article-title":"Dynalign: an algorithm for finding the secondary structure common to two RNA sequences","volume":"317","author":"Mathews","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023020212240617500_B21","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","article-title":"Expanded sequence dependence of thermodynamic parameters provides robust prediction of RNA secondary structure","volume":"288","author":"Mathews","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023020212240617500_B22","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1002\/bip.360290621","article-title":"The equilibrium partition function and base pair binding probabilities for RNA secondary structure","volume":"29","author":"McCaskill","year":"1990","journal-title":"Biopolymers"},{"key":"2023020212240617500_B23","first-page":"1","article-title":"A dynamic topological sort algorithm for directed acyclic graphs","volume":"11","author":"Pearce","year":"2006","journal-title":"J. Exp. Algorithmics"},{"key":"2023020212240617500_B24","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1186\/1471-2164-8-406","article-title":"Computational RNomics of drosophilids","volume":"8","author":"Rose","year":"2007","journal-title":"BMC Genomics"},{"key":"2023020212240617500_B25","doi-asserted-by":"crossref","first-page":"1850","DOI":"10.1101\/gr.6597907","article-title":"Evolution, biogenesis, expression, and target predictions of a substantially expanded set of Drosophila microRNAs","volume":"17","author":"Ruby","year":"2007","journal-title":"Genome Res."},{"key":"2023020212240617500_B26","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding, alignment, and protosequence problems","volume":"45","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math."},{"key":"2023020212240617500_B27","doi-asserted-by":"crossref","first-page":"e24","DOI":"10.1093\/bioinformatics\/btl311","article-title":"Multiple alignment by sequence annealing","volume":"23","author":"Schwartz","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020212240617500_B28","volume-title":"Alignment metric accuracy","author":"Schwartz","year":"2006"},{"key":"2023020212240617500_B29","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1186\/1471-2105-9-33","article-title":"A fast structural multiple alignment method for long RNA sequences","volume":"9","author":"Tabei","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023020212240617500_B30","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1093\/bioinformatics\/btm049","article-title":"Multiple structural alignment and clustering of RNA sequences","volume":"23","author":"Torarinsson","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020212240617500_B31","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1101\/gr.6887408","article-title":"Comparative genomics beyond sequence-based alignments: RNA structures in the ENCODE regions","volume":"18","author":"Torarinsson","year":"2008","journal-title":"Genome Res."},{"key":"2023020212240617500_B32","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1101\/SQB.1987.052.01.017","article-title":"Improved parameters for prediction of RNA structure","volume":"52","author":"Turner","year":"1987","journal-title":"Cold Spring Har. Symp. Quant. Biol."},{"key":"2023020212240617500_B33","doi-asserted-by":"crossref","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","article-title":"Inferring noncoding RNA families and classes by means of genome-scale structure-based clustering","volume":"3","author":"Will","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023020212240617500_B34","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1186\/1748-7188-1-19","article-title":"An enhanced RNA alignment benchmark for sequence alignment programs","volume":"1","author":"Wilm","year":"2006","journal-title":"Algorithms Mol. Biol."},{"key":"2023020212240617500_B35","doi-asserted-by":"crossref","first-page":"1883","DOI":"10.1093\/bioinformatics\/btm272","article-title":"RNA Sampler: a new sampling based algorithm for common RNA secondary structure prediction and structural alignment","volume":"23","author":"Xu","year":"2007","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/23\/2677\/49055850\/bioinformatics_24_23_2677.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/23\/2677\/49055850\/bioinformatics_24_23_2677.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T14:58:27Z","timestamp":1675349907000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/23\/2677\/179719"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9,16]]},"references-count":35,"journal-issue":{"issue":"23","published-print":{"date-parts":[[2008,12,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn495","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,12,1]]},"published":{"date-parts":[[2008,9,16]]}}}