{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:51:43Z","timestamp":1757314303772},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Evaluating all possible internal loops is one of the key steps in predicting the optimal secondary structure of an RNA molecule. The best algorithm available runs in time O(L3), L is the length of the RNA.<\/jats:p>\n               <jats:p>Results: We propose a new algorithm for evaluating internal loops, its run-time is O(M*log2L), M&amp;lt;L2 is a number of possible nucleotide pairings. We created a software tool Afold which predicts the optimal secondary structure of RNA molecules of lengths up to 28 000 nt, using a computer with 2 Gb RAM. We also propose algorithms constructing sets of conditionally optimal multi-branch loop free (MLF) structures, e.g. the set that for every possible pairing (x, y) contains an optimal MLF structure in which nucleotides x and y form a pair. All the algorithms have run-time O(M*log2L).<\/jats:p>\n               <jats:p>Availability: Executables of Afold software tool, precompiled for Linux and Windows, are available at .<\/jats:p>\n               <jats:p>Contact: \u00a0MRoytberg@impb.psn.ru<\/jats:p>\n               <jats:p>Supplementary information: \u00a0<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl083","type":"journal-article","created":{"date-parts":[[2006,3,17]],"date-time":"2006-03-17T01:14:18Z","timestamp":1142558058000},"page":"1317-1324","source":"Crossref","is-referenced-by-count":36,"title":["Analysis of internal loops within the RNA secondary structure in almost quadratic time"],"prefix":"10.1093","volume":"22","author":[{"given":"Aleksey Y.","family":"Ogurtsov","sequence":"first","affiliation":[{"name":"National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health 1 \u00a0 1 \u00a0 \u00a0 Bethesda, MD 20894, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Svetlana A.","family":"Shabalina","sequence":"additional","affiliation":[{"name":"National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health 1 \u00a0 1 \u00a0 \u00a0 Bethesda, MD 20894, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexey S.","family":"Kondrashov","sequence":"additional","affiliation":[{"name":"National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health 1 \u00a0 1 \u00a0 \u00a0 Bethesda, MD 20894, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail A.","family":"Roytberg","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Problems in Biology, Russian Academy of Science 2 \u00a0 2 \u00a0 \u00a0 Pushchino, Moscow Region, 142290, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2006,3,16]]},"reference":[{"key":"2023012408410149300_b1","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"2023012408410149300_b2","doi-asserted-by":"crossref","first-page":"15991","DOI":"10.1074\/jbc.M300714200","article-title":"The efficacy of small interfering RNAs targeted to the type 1 insulin-like growth factor receptor (IGF1R) is influenced by secondary structure in the IGF1R transcript","volume":"278","author":"Bohula","year":"2003","journal-title":"J. Biol. Chem."},{"key":"2023012408410149300_b3","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1145\/146637.146656","article-title":"Sparse dynamic programming II: convex and concave cost functions","volume":"39","author":"Eppstein","year":"1992","journal-title":"J. ACM"},{"key":"2023012408410149300_b4","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0303-2647(93)90058-K","article-title":"Computation of biopolymers: a general approach to different problems","volume":"30","author":"Finkelstein","year":"1993","journal-title":"Biosystems"},{"key":"2023012408410149300_b5","doi-asserted-by":"crossref","first-page":"7706","DOI":"10.1073\/pnas.86.20.7706","article-title":"Improved predictions of secondary structures for RNA","volume":"20","author":"Jaeger","year":"1989","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408410149300_b6","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. Chemie"},{"key":"2023012408410149300_b7","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.1093\/bioinformatics\/bth108","article-title":"Conserved RNA secondary structures in viral genomes: a survey","volume":"20","author":"Hofacker","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012408410149300_b8","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","article-title":"A linear space algorithm for computing maximal common subsequences","volume":"18","author":"Hirschberg","year":"1975","journal-title":"Commun. ACM"},{"key":"2023012408410149300_b9","doi-asserted-by":"crossref","first-page":"4417","DOI":"10.1093\/nar\/gkg649","article-title":"The activity of siRNA in mammalian cells is related to structural target accessibility: a comparison with antisense oligonucleotides","volume":"31","author":"Kretschmer-Kazemi Far","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012408410149300_b10","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0196-6774(91)90016-R","article-title":"On-line dynamic programming with applications to the prediction of RNA secondary structure","volume":"12","author":"Larmore","year":"1991","journal-title":"J. Algorithms"},{"key":"2023012408410149300_b11","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1038\/nbt0502-500","article-title":"Expression of small interfering RNAs targeted against HIV-1 rev transcripts in human cells","volume":"20","author":"Lee","year":"2002","journal-title":"Nat. Biotechnol."},{"key":"2023012408410149300_b12","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/15.6.440","article-title":"Fast evaluation of internal loops in RNA secondary structure prediction","volume":"15","author":"Lyngs\u00f8","year":"1999","journal-title":"Bioinformatics"},{"key":"2023012408410149300_b13","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.bbrc.2004.04.027","article-title":"The gene-silencing efficiency of siRNA is strongly dependent on the local structure of mRNA at the target region","volume":"318","author":"Luo","year":"2004","journal-title":"Biochem. Biopys. Res. Commun"},{"key":"2023012408410149300_b14","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":"2023012408410149300_b15","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":"2023012408410149300_b16","doi-asserted-by":"crossref","first-page":"6309","DOI":"10.1073\/pnas.77.11.6309","article-title":"Fast algorithm for predicting the secondary structure of single-stranded RNA","volume":"77","author":"Nussinov","year":"1980","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408410149300_b17","doi-asserted-by":"crossref","first-page":"1673","DOI":"10.1093\/bioinformatics\/18.12.1673","article-title":"A hierarchical approach to aligning collinear regions of genomes","volume":"18","author":"Roytberg","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012408410149300_b18","doi-asserted-by":"crossref","first-page":"3362","DOI":"10.1038\/230362a0","article-title":"Estimation of secondary structure in ribonucleic acids","volume":"230","author":"Tinoco","year":"1971","journal-title":"Nature"},{"key":"2023012408410149300_b19","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1038\/newbio246040a0","article-title":"Improved estimation of secondary structure in ribonucleic acids","volume":"246","author":"Tinoco","year":"1973","journal-title":"Nat. New Biol."},{"key":"2023012408410149300_b20","doi-asserted-by":"crossref","first-page":"7108","DOI":"10.1074\/jbc.M210326200","article-title":"Efficient reduction of target RNAs by small interfering RNA and RNase H-dependent antisense agents. A comparative analysis","volume":"278","author":"Vickers","year":"2003","journal-title":"J. Biol. Chem."},{"key":"2023012408410149300_b21","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","article-title":"Complete suboptimal folding of RNA and the stability of secondary structures","volume":"49","author":"Wuchty","year":"1999","journal-title":"Biopolymers"},{"key":"2023012408410149300_b22","doi-asserted-by":"crossref","first-page":"14719","DOI":"10.1021\/bi9809425","article-title":"Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson\u2013Crick base pairs","volume":"37","author":"Xia","year":"1998","journal-title":"Biochemistry"},{"key":"2023012408410149300_b23","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1126\/science.2468181","article-title":"On finding all suboptimal foldings of an RNA molecule","volume":"244","author":"Zuker","year":"1989","journal-title":"Science"},{"key":"2023012408410149300_b24","doi-asserted-by":"crossref","first-page":"3406","DOI":"10.1093\/nar\/gkg595","article-title":"Mfold web server for nucleic acid folding and hybridization prediction","volume":"31","author":"Zuker","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012408410149300_b25","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-94-011-4485-8_2","article-title":"Algorithms and thermodynamics for RNA secondary structure prediction: a practical guide","volume-title":"RNA Biochemistry and Biotechnology, NATO ASI Series","author":"Zuker","year":"1999"},{"key":"2023012408410149300_b26","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1093\/nar\/9.1.133","article-title":"Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information","volume":"9","author":"Zuker","year":"1981","journal-title":"Nucleic Acids. Res."},{"key":"2023012408410149300_b27","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1016\/S0092-8240(84)80062-2","article-title":"RNA secondary structures and their prediction","volume":"46","author":"Zuker","year":"1984","journal-title":"Bull. Math. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/11\/1317\/48838864\/bioinformatics_22_11_1317.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/11\/1317\/48838864\/bioinformatics_22_11_1317.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T08:56:19Z","timestamp":1674550579000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/22\/11\/1317\/237926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3,16]]},"references-count":27,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2006,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl083","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2006,6,1]]},"published":{"date-parts":[[2006,3,16]]}}}