{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:13:47Z","timestamp":1773274427526,"version":"3.50.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":3015,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The need for accurate and efficient tools for computational RNA structure analysis has become increasingly apparent over the last several years: RNA folding algorithms underlie numerous applications in bioinformatics, ranging from microarray probe selection to de novo non-coding RNA gene prediction.<\/jats:p>\n               <jats:p>In this work, we present RAF (RNA Alignment and Folding), an efficient algorithm for simultaneous alignment and consensus folding of unaligned RNA sequences. Algorithmically, RAF exploits sparsity in the set of likely pairing and alignment candidates for each nucleotide (as identified by the CONTRAfold or CONTRAlign programs) to achieve an effectively quadratic running time for simultaneous pairwise alignment and folding. RAF's fast sparse dynamic programming, in turn, serves as the inference engine within a discriminative machine learning algorithm for parameter estimation.<\/jats:p>\n               <jats:p>Results: In cross-validated benchmark tests, RAF achieves accuracies equaling or surpassing the current best approaches for RNA multiple sequence secondary structure prediction. However, RAF requires nearly an order of magnitude less time than other simultaneous folding and alignment methods, thus making it especially appropriate for high-throughput studies.<\/jats:p>\n               <jats:p>Availability: Source code for RAF is available at:http:\/\/contra.stanford.edu\/contrafold\/<\/jats:p>\n               <jats:p>Contact: \u00a0chuongdo@cs.stanford.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn177","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T07:43:13Z","timestamp":1214552593000},"page":"i68-i76","source":"Crossref","is-referenced-by-count":73,"title":["A max-margin model for efficient simultaneous alignment and folding of RNA sequences"],"prefix":"10.1093","volume":"24","author":[{"given":"Chuong B.","family":"Do","sequence":"first","affiliation":[{"name":"Computer Science Department, Stanford University, Stanford, CA 94305, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuan-Sheng","family":"Foo","sequence":"additional","affiliation":[{"name":"Computer Science Department, Stanford University, Stanford, CA 94305, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serafim","family":"Batzoglou","sequence":"additional","affiliation":[{"name":"Computer Science Department, Stanford University, Stanford, CA 94305, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"2023020210403211000_B1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1093\/bioinformatics\/btm223","article-title":"Efficient parameter estimation for RNA secondary structure prediction","volume":"23","author":"Andronescu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020210403211000_B2","article-title":"Convex analysis and optimization","author":"Bertsekas","year":"2003"},{"key":"2023020210403211000_B3","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1146\/annurev.biophys.26.1.113","article-title":"Hierarchy and dynamics of RNA folding","volume":"26","author":"Brion","year":"1997","journal-title":"Annu. Rev. Biophys. Biomol. Struct"},{"key":"2023020210403211000_B4","doi-asserted-by":"crossref","first-page":"1593","DOI":"10.1093\/bioinformatics\/btl142","article-title":"STRAL: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time","volume":"22","author":"Dalli","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020210403211000_B5","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1101\/gr.3.3.S30","article-title":"General concepts for PCR primer design","volume":"3","author":"Dieffenbach","year":"1993","journal-title":"PCR Methods Appl"},{"key":"2023020210403211000_B6","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1101\/gr.2821705","article-title":"PROBCONS: probabilistic consistency-based multiple sequence alignment","volume":"15","author":"Do","year":"2005","journal-title":"Genome Res"},{"key":"2023020210403211000_B7","first-page":"160","article-title":"CONTRAlign: discriminative training for protein sequence alignment","volume-title":"RECOMB","author":"Do","year":"2006"},{"key":"2023020210403211000_B8","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":"2023020210403211000_B9","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":"2023020210403211000_B10","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0092-8674(02)00727-4","article-title":"Computational genomics of noncoding RNA genes","volume":"109","author":"Eddy","year":"2002","journal-title":"Cell"},{"key":"2023020210403211000_B11","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":"2023020210403211000_B12","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":"2023020210403211000_B13","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":"2023020210403211000_B14","doi-asserted-by":"crossref","first-page":"2135","DOI":"10.1093\/nar\/29.10.2135","article-title":"Discovering common stem-loop motifs in unaligned RNA sequences","volume":"29","author":"Gorodkin","year":"2001","journal-title":"Nucleic Acids Res"},{"key":"2023020210403211000_B15","doi-asserted-by":"crossref","first-page":"D121","DOI":"10.1093\/nar\/gki081","article-title":"Rfam: annotating non-coding RNAs in complete genomes","volume":"33","author":"Griffiths-Jones","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023020210403211000_B16","doi-asserted-by":"crossref","DOI":"10.1186\/1471-2105-8-130","article-title":"Efficient pairwise RNA structure prediction using probabilistic alignment constraints in Dynalign","volume":"8","author":"Harmanci","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023020210403211000_B17","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00818163","article-title":"Fast folding and comparison of RNA secondary structures (The Vienna RNA Package)","volume":"125","author":"Hofacker","year":"1994","journal-title":"Monatsh. Chem"},{"key":"2023020210403211000_B18","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":"2023020210403211000_B19","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":"2023020210403211000_B20","doi-asserted-by":"crossref","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":"2023020210403211000_B21","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":"2023020210403211000_B22","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":"2023020210403211000_B23","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":"2023020210403211000_B24","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":"2023020210403211000_B25","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","article-title":"Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure","volume":"288","author":"Mathews","year":"1999","journal-title":"J. Mol. Biol"},{"key":"2023020210403211000_B26","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/0005-2795(75)90109-9","article-title":"Comparison of predicted and observed secondary structure of T4 phage lysozyme","volume":"405","author":"Matthews","year":"1975","journal-title":"Biochim. Biophys. Acta"},{"key":"2023020210403211000_B27","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":"2023020210403211000_B28","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":"2023020210403211000_B29","article-title":"Logarithmic regret algorithms for strongly convex repeated games, 2007","author":"Shalev-Shwartz","year":"2007"},{"key":"2023020210403211000_B30","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1145\/1273496.1273598","article-title":"Pegasos: Primal estimated sub-gradient solver for svm","volume-title":"ICML","author":"Shalev-Shwartz","year":"2007"},{"key":"2023020210403211000_B31","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1038\/193855a0","article-title":"Numerical taxonomy","volume":"193","author":"Sneath","year":"1962","journal-title":"Nature"},{"key":"2023020210403211000_B32","doi-asserted-by":"crossref","first-page":"1723","DOI":"10.1093\/bioinformatics\/btl177","article-title":"SCARNA: fast and accurate structural alignment of RNA sequences by matching fixed-length stem fragments","volume":"22","author":"Tabei","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020210403211000_B33","article-title":"Max-margin markov networks","volume-title":"NIPS 16","author":"Taskar","year":"2003"},{"key":"2023020210403211000_B34","doi-asserted-by":"crossref","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","article-title":"A comprehensive comparison of multiple sequence alignment programs","volume":"27","author":"Thompson","year":"1999","journal-title":"Nucleic Acids Res"},{"key":"2023020210403211000_B35","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1101\/gr.5226606","article-title":"Thousands of corresponding human and mouse genomic regions unalignable in primary sequence contain common RNA structure","volume":"16","author":"Torarinsson","year":"2006","journal-title":"Genome Res"},{"key":"2023020210403211000_B36","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":"2023020210403211000_B37","first-page":"W142","article-title":"CARNAC: folding families of related RNAs","volume-title":"Nucleic Acids Res., 32 (Web Server)","author":"Touzet","year":"2004"},{"key":"2023020210403211000_B38","doi-asserted-by":"crossref","first-page":"1692","DOI":"10.1093\/nar\/gkl091","article-title":"M-Coffee: combining multiple sequence alignment methods with T-Coffee","volume":"34","author":"Wallace","year":"2006","journal-title":"Nucleic Acids Res"},{"key":"2023020210403211000_B39","doi-asserted-by":"crossref","first-page":"856","DOI":"10.1089\/cmb.2007.R020","article-title":"A study of accessible motifs and RNA folding complexity","volume":"14","author":"Wexler","year":"2007","journal-title":"J. Comput. Biol"},{"key":"2023020210403211000_B40","doi-asserted-by":"crossref","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":"2023020210403211000_B41","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\/13\/i68\/49053583\/bioinformatics_24_13_i68.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i68\/49053583\/bioinformatics_24_13_i68.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:25:19Z","timestamp":1675340719000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/i68\/235334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,1]]},"references-count":41,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn177","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,7,1]]},"published":{"date-parts":[[2008,7,1]]}}}