{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T10:32:42Z","timestamp":1761561162071},"reference-count":42,"publisher":"Oxford University Press (OUP)","issue":"15","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Non-coding RNA genes and RNA structural regulatory motifs play important roles in gene regulation and other cellular functions. They are often characterized by specific secondary structures that are critical to their functions and are often conserved in phylogenetically or functionally related sequences. Predicting common RNA secondary structures in multiple unaligned sequences remains a challenge in bioinformatics research.<\/jats:p><jats:p>Methods and Results: We present a new sampling based algorithm to predict common RNA secondary structures in multiple unaligned sequences. Our algorithm finds the common structure between two sequences by probabilistically sampling aligned stems based on stem conservation calculated from intrasequence base pairing probabilities and intersequence base alignment probabilities. It iteratively updates these probabilities based on sampled structures and subsequently recalculates stem conservation using the updated probabilities. The iterative process terminates upon convergence of the sampled structures. We extend the algorithm to multiple sequences by a consistency-based method, which iteratively incorporates and reinforces consistent structure information from pairwise comparisons into consensus structures. The algorithm has no limitation on predicting pseudoknots. In extensive testing on real sequence data, our algorithm outperformed other leading RNA structure prediction methods in both sensitivity and specificity with a reasonably fast speed. It also generated better structural alignments than other programs in sequences of a wide range of identities, which more accurately represent the RNA secondary structure conservations.<\/jats:p><jats:p>Availability: The algorithm is implemented in a C program, RNA Sampler, which is available at http:\/\/ural.wustl.edu\/software.html<\/jats:p><jats:p>Contact: \u00a0xingxu@ural.wustl.edu and stormo@genetics.wustl.edu.<\/jats:p><jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm272","type":"journal-article","created":{"date-parts":[[2007,5,31]],"date-time":"2007-05-31T00:18:18Z","timestamp":1180570698000},"page":"1883-1891","source":"Crossref","is-referenced-by-count":53,"title":["RNA Sampler: a new sampling based algorithm for common RNA secondary structure prediction and structural alignment"],"prefix":"10.1093","volume":"23","author":[{"given":"Xing","family":"Xu","sequence":"first","affiliation":[{"name":"Department of Genetics, Washington University, School of Medicine, St. Louis, MO 63110, USA"}]},{"given":"Yongmei","family":"Ji","sequence":"additional","affiliation":[{"name":"Department of Genetics, Washington University, School of Medicine, St. Louis, MO 63110, USA"}]},{"given":"Gary D.","family":"Stormo","sequence":"additional","affiliation":[{"name":"Department of Genetics, Washington University, School of Medicine, St. Louis, MO 63110, USA"}]}],"member":"286","published-online":{"date-parts":[[2007,5,30]]},"reference":[{"key":"2023041105313729500_","volume-title":"RNA secondary structure prediction via energy density minimization. Research in Computational Molecular Biology (RECOMB)","author":"Alkan","year":"2006"},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1089\/cmb.2006.13.283","article-title":"Consensus folding of unaligned RNA sequences revisited","volume":"13","author":"Bafna","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0092-8674(04)00045-5","article-title":"MicroRNAs: genomics, biogenesis, mechanism, and function","volume":"116","author":"Bartel","year":"2004","journal-title":"Cell"},{"key":"2023041105313729500_","first-page":"75","article-title":"Graph-theoretic approach to RNA modeling using comparative data","volume":"3","author":"Cary","year":"1995","journal-title":"Proc. Int. Conf. Intell. Syst. Mol. Biol."},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"1295","DOI":"10.1002\/jcc.20057","article-title":"An algorithm for computing nucleic acid base-pairing probabilities including pseudoknots","volume":"25","author":"Dirks","year":"2004","journal-title":"J. Comput. Chem."},{"key":"2023041105313729500_","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":"2023041105313729500_","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":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1038\/35103511","article-title":"Non-coding RNA genes and the modern RNA world","volume":"2","author":"Eddy","year":"2001","journal-title":"Nat. Rev. Genet."},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"2079","DOI":"10.1093\/nar\/22.11.2079","article-title":"RNA sequence analysis using covariance models","volume":"22","author":"Eddy","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023041105313729500_","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":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"4843","DOI":"10.1093\/nar\/gkh779","article-title":"Abstract shapes of RNA","volume":"32","author":"Giegerich","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023041105313729500_","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":"2023041105313729500_","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":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"5785","DOI":"10.1093\/nar\/20.21.5785","article-title":"Identifying constraints on the higher-order structure of RNA: continued development and application of comparative sequence analysis methods","volume":"20","author":"Gutell","year":"1992","journal-title":"Nucleic Acids Res."},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00818163","article-title":"Fast folding and comparison of RNA secondary structures","volume":"125","author":"Hofacker","year":"1994","journal-title":"Monatsh Chem."},{"key":"2023041105313729500_","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":"2023041105313729500_","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":"2023041105313729500_","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":"2023041105313729500_","first-page":"163","article-title":"Pairwise RNA structure comparison with stochastic context-free grammars","author":"Holmes","year":"2002","journal-title":"Pac. Symp. Biocomput."},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"1591","DOI":"10.1093\/bioinformatics\/bth131","article-title":"A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences","volume":"20","author":"Ji","year":"2004","journal-title":"Bioinformatics"},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1093\/bioinformatics\/15.6.446","article-title":"RNA secondary structure prediction using stochastic context-free grammars and evolutionary history","volume":"15","author":"Knudsen","year":"1999","journal-title":"Bioinformatics"},{"key":"2023041105313729500_","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":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/0005-2795(75)90109-9","article-title":"Comparison of the predicted and observed secondary structure of T4 phage lysozyme","volume":"405","author":"Matthews","year":"1975","journal-title":"Biochim. Biophys. Acta"},{"key":"2023041105313729500_","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":"2023041105313729500_","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":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1093\/protein\/8.10.999","article-title":"A reliable sequence alignment method based on probabilities of residue correspondences","volume":"8","author":"Miyazawa","year":"1995","journal-title":"Protein Eng."},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"S153","DOI":"10.1093\/bioinformatics\/18.suppl_2.S153","article-title":"Stochastic pairwise alignments","volume":"18","author":"Muckstein","year":"2002","journal-title":"Bioinformatics"},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","article-title":"A dynamic programming algorithm for RNA structure prediction including pseudoknots","volume":"285","author":"Rivas","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"5112","DOI":"10.1093\/nar\/22.23.5112","article-title":"Stochastic context-free grammars for tRNA modeling","volume":"22","author":"Sakakibara","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023041105313729500_","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":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"3352","DOI":"10.1093\/bioinformatics\/bti550","article-title":"MARNA: multiple alignment and consensus structure prediction of RNAs based on sequence structure comparisons","volume":"21","author":"Siebert","year":"2005","journal-title":"Bioinformatics"},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1093\/nar\/26.1.148","article-title":"Compilation of tRNA sequences and sequences of tRNA genes","volume":"26","author":"Sprinzl","year":"1998","journal-title":"Nucleic Acids Res."},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1093\/bioinformatics\/btk010","article-title":"RNAshapes: an integrated RNA analysis package based on abstract shapes","volume":"22","author":"Steffen","year":"2006","journal-title":"Bioinformatics"},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"9465","DOI":"10.1073\/pnas.181334498","article-title":"Do mRNAs act as direct sensors of small molecules to control their expression?","volume":"98","author":"Stormo","year":"2001","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1093\/bioinformatics\/14.8.691","article-title":"An RNA folding method capable of identifying pseudoknots and base triples","volume":"14","author":"Tabaska","year":"1998","journal-title":"Bioinformatics"},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023041105313729500_","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":"2023041105313729500_","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":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"W142","DOI":"10.1093\/nar\/gkh415","article-title":"CARNAC: folding families of related RNAs","volume":"32","author":"Touzet","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"2454","DOI":"10.1073\/pnas.0409169102","article-title":"Fast and reliable prediction of noncoding RNAs","volume":"102","author":"Washietl","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023041105313729500_","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1016\/j.cbpa.2005.09.016","article-title":"Riboswitches and the role of noncoding RNAs in bacterial metabolic control","volume":"9","author":"Winkler","year":"2005","journal-title":"Curr. Opin. Chem. Biol."},{"key":"2023041105313729500_","first-page":"267","article-title":"Prediction of RNA secondary structure by energy minimization","volume":"25","author":"Zuker","year":"1994","journal-title":"Methods Mol. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/15\/1883\/49815049\/bioinformatics_23_15_1883.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/15\/1883\/49815049\/bioinformatics_23_15_1883.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T17:16:59Z","timestamp":1707931019000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/15\/1883\/203678"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5,30]]},"references-count":42,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2007,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm272","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,8]]},"published":{"date-parts":[[2007,5,30]]}}}