{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T09:57:00Z","timestamp":1781949420387,"version":"3.54.5"},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Base pairing probability matrices have been frequently used for the analyses of structural RNA sequences. Recently, there has been a growing need for computing these probabilities for long DNA sequences by constraining the maximal span of base pairs to a limited value. However, none of the existing programs can exactly compute the base pairing probabilities associated with the energy model of secondary structures under such a constraint.<\/jats:p>\n               <jats:p>Results: We present an algorithm that exactly computes the base pairing probabilities associated with the energy model under the constraint on the maximal span W of base pairs. The complexity of our algorithm is given by in time and in memory, where N is the sequence length. We show that our algorithm has a higher sensitivity to the true base pairs as compared to that of RNAplfold. We also present an algorithm that predicts a mutually consistent set of local secondary structures by maximizing the expected accuracy function. The comparison of the local secondary structure predictions with those of RNALfold indicates that our algorithm is more accurate. Our algorithms are implemented in the software named \u2018Rfold.\u2019<\/jats:p>\n               <jats:p>Availability: The C++ source code of the Rfold software and the test dataset used in this study are available at http:\/\/www.ncrna.org\/software\/Rfold\/<\/jats:p>\n               <jats:p>Contact: \u00a0kiryu-h@aist.go.jp<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm591","type":"journal-article","created":{"date-parts":[[2007,12,5]],"date-time":"2007-12-05T02:49:49Z","timestamp":1196822989000},"page":"367-373","source":"Crossref","is-referenced-by-count":52,"title":["Rfold: an exact algorithm for computing local base pairing probabilities"],"prefix":"10.1093","volume":"24","author":[{"given":"Hisanori","family":"Kiryu","sequence":"first","affiliation":[{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064 and 2Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Taishin","family":"Kin","sequence":"additional","affiliation":[{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064 and 2Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kiyoshi","family":"Asai","sequence":"additional","affiliation":[{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064 and 2Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"},{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064 and 2Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2007,12,4]]},"reference":[{"key":"2023061011435793200_B1","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1093\/bioinformatics\/btk014","article-title":"Local RNA base pairing probabilities in large sequences","volume":"22","author":"Bernhart","year":"2006","journal-title":"Bioinformatics"},{"key":"2023061011435793200_B2","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":"2023061011435793200_B3","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":"2023061011435793200_B4","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":"2023061011435793200_B5","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":"2023061011435793200_B6","doi-asserted-by":"crossref","first-page":"2480","DOI":"10.1093\/bioinformatics\/btl431","article-title":"Mining frequent stem patterns from unaligned RNA sequences","volume":"22","author":"Hamada","year":"2006","journal-title":"Bioinformatics"},{"key":"2023061011435793200_B7","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":"2023061011435793200_B8","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":"2023061011435793200_B9","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":"2023061011435793200_B10","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1089\/cmb.1998.5.493","article-title":"Dynamic programming alignment accuracy","volume":"5","author":"Holmes","year":"1998","journal-title":"J. Comput. Biol"},{"key":"2023061011435793200_B11","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1093\/nar\/gkl837","article-title":"fRNAdb: a platform for mining\/annotating functional RNA candidates from non-coding RNA sequences","volume":"35","author":"Kin","year":"2007","journal-title":"Nucleic Acids Res"},{"key":"2023061011435793200_B12","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1093\/bioinformatics\/btl636","article-title":"Robust prediction of consensus secondary structures using averaged base pairing probability matrices","volume":"23","author":"Kiryu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023061011435793200_B13","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":"2023061011435793200_B14","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":"2023061011435793200_B15","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":"2023061011435793200_B16","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":"2023061011435793200_B17","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":"2023061011435793200_B18","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1038\/nature01266","article-title":"Analysis of the mouse transcriptome based on functional annotation of 60,770 full-length cDNAs","volume":"420","author":"Okazaki","year":"2002","journal-title":"Nature"},{"key":"2023061011435793200_B19","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":"2023061011435793200_B20","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":"2023061011435793200_B21","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/3\/367\/50568154\/bioinformatics_24_3_367.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/3\/367\/50568154\/bioinformatics_24_3_367.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,10]],"date-time":"2023-06-10T11:45:05Z","timestamp":1686397505000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/3\/367\/252919"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,4]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm591","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,2,1]]},"published":{"date-parts":[[2007,12,4]]}}}