{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T06:46:12Z","timestamp":1790491572769,"version":"4.1.0"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Recent transcriptomic studies have revealed the existence of a considerable number of non-protein-coding RNA transcripts in higher eukaryotic cells. To investigate the functional roles of these transcripts, it is of great interest to find conserved secondary structures from multiple alignments on a genomic scale. Since multiple alignments are often created using alignment programs that neglect the special conservation patterns of RNA secondary structures for computational efficiency, alignment failures can cause potential risks of overlooking conserved stem structures.<\/jats:p><jats:p>Results: We investigated the dependence of the accuracy of secondary structure prediction on the quality of alignments. We compared three algorithms that maximize the expected accuracy of secondary structures as well as other frequently used algorithms. We found that one of our algorithms, called McCaskill-MEA, was more robust against alignment failures than others. The McCaskill-MEA method first computes the base pairing probability matrices for all the sequences in the alignment and then obtains the base pairing probability matrix of the alignment by averaging over these matrices. The consensus secondary structure is predicted from this matrix such that the expected accuracy of the prediction is maximized. We show that the McCaskill-MEA method performs better than other methods, particularly when the alignment quality is low and when the alignment consists of many sequences. Our model has a parameter that controls the sensitivity and specificity of predictions. We discussed the uses of that parameter for multi-step screening procedures to search for conserved secondary structures and for assigning confidence values to the predicted base pairs.<\/jats:p><jats:p>Availability: The C++ source code that implements the McCaskill-MEA algorithm and the test dataset used in this paper are available at<\/jats:p><jats:p>Contact: \u00a0kiryu-h@aist.go.jp<\/jats:p><jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl636","type":"journal-article","created":{"date-parts":[[2006,12,21]],"date-time":"2006-12-21T01:34:06Z","timestamp":1166664846000},"page":"434-441","source":"Crossref","is-referenced-by-count":48,"title":["Robust prediction of consensus secondary structures using averaged base pairing probability matrices"],"prefix":"10.1093","volume":"23","author":[{"given":"Hisanori","family":"Kiryu","sequence":"first","affiliation":[{"name":"Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST) 1 \u00a0 1 \u00a0 \u00a0 2-42 Aomi, Koto-ku, Tokyo, 135-0064, Japan"},{"name":"Graduate School of Information Sciences, Nara Institute of Science and Technology 2 \u00a0 2 \u00a0 \u00a0 8916-5 Takayama-cho, Ikoma, Nara 630-0192, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Taishin","family":"Kin","sequence":"additional","affiliation":[{"name":"Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST) 1 \u00a0 1 \u00a0 \u00a0 2-42 Aomi, Koto-ku, Tokyo, 135-0064, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kiyoshi","family":"Asai","sequence":"additional","affiliation":[{"name":"Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST) 1 \u00a0 1 \u00a0 \u00a0 2-42 Aomi, Koto-ku, Tokyo, 135-0064, Japan"},{"name":"Department of Computational Biology, Faculty of Frontier Science 3 \u00a0 3 \u00a0 \u00a0 The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2006,12,20]]},"reference":[{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0148063","article-title":"The multiple sequence alignment problem in biology","volume":"48","author":"Carillo","year":"1988","journal-title":"SIAM J. Appl. Math."},{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"1559","DOI":"10.1126\/science.1112014","article-title":"The transcriptional landscape of the mammalian genome","volume":"309","author":"Carninci","year":"2005","journal-title":"Science"},{"key":"2023041109270707000_","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":"2023041109270707000_","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":"2023041109270707000_","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":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1038\/nature02379","article-title":"The DNA sequence and analysis of human chromosome 13","volume":"428","author":"Dunham","year":"2004","journal-title":"Nature"},{"key":"2023041109270707000_","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":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1093\/nar\/gkg006","article-title":"Rfam: an RNA family database","volume":"31","author":"Griffiths-Jones","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"3429","DOI":"10.1093\/nar\/gkg599","article-title":"Vienna RNA secondary structure server","volume":"31","author":"Hofacker","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1016\/S0097-8485(99)00013-3","article-title":"Automatic detection of conserved base pairing patterns in RNA virus genomes","volume":"23","author":"Hofacker","year":"1999","journal-title":"Comput. Chem."},{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"3825","DOI":"10.1093\/nar\/26.16.3825","article-title":"Automatic detection of conserved RNA structure elements in complete RNA virus genomes","volume":"26","author":"Hofacker","year":"1998","journal-title":"Nucleic Acids Res."},{"key":"2023041109270707000_","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":"2023041109270707000_","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":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1093\/bioinformatics\/btg388","article-title":"Prediction of locally stable RNA secondary structures for genome-wide surveys","volume":"20","author":"Hofacker","year":"2004","journal-title":"Bioinformatics"},{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"1323","DOI":"10.1261\/rna.5168504","article-title":"BayesFold: rational 2 degrees folds that combine thermodynamic, covariation, and chemical data for aligned RNA sequences","volume":"10","author":"Knight","year":"2004","journal-title":"RNA"},{"key":"2023041109270707000_","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":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1006\/jmbi.1996.0289","article-title":"Thermodynamic prediction of conserved secondary structure: application to the RRE element of HIV, the tRNA-like element of CMV and the mRNA of prion protein","volume":"258","author":"Luck","year":"1996","journal-title":"J. Mol. Biol."},{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"4208","DOI":"10.1093\/nar\/27.21.4208","article-title":"ConStruct: a tool for thermodynamic controlled prediction of conserved secondary structure","volume":"27","author":"Luck","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023041109270707000_","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":"2023041109270707000_","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":"2023041109270707000_","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":"2023041109270707000_","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":"2023041109270707000_","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":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0135006","article-title":"Algorithms for loop matchings","volume":"35","author":"Nussnov","year":"1978","journal-title":"SIAM J. Appl. Math."},{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1038\/nature01266","article-title":"Analysis of the mouse transcriptome based on functional annotation of 60\u2009770 full-length cDNAs","volume":"420","author":"Okazaki","year":"2002","journal-title":"Nature"},{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"e33","DOI":"10.1371\/journal.pcbi.0020033","article-title":"Identification and classification of conserved RNA secondary structures in the human genome","volume":"2","author":"Pedersen","year":"2006","journal-title":"PLoS Comput. Biol."},{"key":"2023041109270707000_","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":"2023041109270707000_","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":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.jmb.2004.07.018","article-title":"Consensus folding of aligned sequences as a new measure for the detection of functional RNAs by comparative genomics","volume":"342","author":"Washietl","year":"2004","journal-title":"J. Mol. Biol."},{"key":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"1383","DOI":"10.1038\/nbt1144","article-title":"Mapping of conserved RNA secondary structures predicts thousands of functional noncoding RNAs in the human genome","volume":"23","author":"Washietl","year":"2005","journal-title":"Nat. Biotechnol."},{"key":"2023041109270707000_","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":"2023041109270707000_","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/0076-6879(89)80106-5","article-title":"Computer prediction of RNA structure","volume":"180","author":"Zuker","year":"1989","journal-title":"Methods Enzymol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/4\/434\/49830277\/bioinformatics_23_4_434.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/4\/434\/49830277\/bioinformatics_23_4_434.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T05:54:37Z","timestamp":1683698077000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/4\/434\/182043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12,20]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl636","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,2,15]]},"published":{"date-parts":[[2006,12,20]]}}}