{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:20:24Z","timestamp":1757542824299},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Many regulatory non-coding RNAs (ncRNAs) function through complementary binding with mRNAs or other ncRNAs, <jats:italic>e.g<\/jats:italic>., microRNAs, snoRNAs and bacterial sRNAs. Predicting these RNA interactions is essential for functional studies of putative ncRNAs or for the design of artificial RNAs. Many ncRNAs show clear signs of undergoing compensating base changes over evolutionary time. Here, we postulate that a non-negligible part of the existing RNA-RNA interactions contain preserved but covarying patterns of interactions.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Methods<\/jats:title>\n            <jats:p>We present a novel method that takes compensating base changes across the binding sites into account. The algorithm works in two steps on two pre-generated multiple alignments. In the first step, individual base pairs with high reliability are found using the  algorithm, which includes evolutionary and thermodynamic properties. In step two (where high reliability base pairs from step one are constrained as unpaired), the principle of cofolding is combined with hierarchical folding. The final prediction of <jats:italic>intra<\/jats:italic>- and <jats:italic>inter<\/jats:italic>-molecular base pairs consists of the reliabilities computed from the constrained expected accuracy scoring, which is an extended version of that used for individual multiple alignments.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We derived a rather extensive algorithm. One of the advantages of our approach (in contrast to other RNA-RNA interaction prediction methods) is the application of covariance detection and prediction of pseudoknots between <jats:italic>intra<\/jats:italic>- and <jats:italic>inter<\/jats:italic>-molecular base pairs. As a proof of concept, we show an example and discuss the strengths and weaknesses of the approach.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1748-7188-5-22","type":"journal-article","created":{"date-parts":[[2010,5,21]],"date-time":"2010-05-21T18:26:07Z","timestamp":1274466367000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Hierarchical folding of multiple sequence alignments for the prediction of structures and RNA-RNA interactions"],"prefix":"10.1186","volume":"5","author":[{"given":"Stefan E","family":"Seemann","sequence":"first","affiliation":[]},{"given":"Andreas S","family":"Richter","sequence":"additional","affiliation":[]},{"given":"Jan","family":"Gorodkin","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,5,21]]},"reference":[{"key":"95_CR1","doi-asserted-by":"publisher","first-page":"1383","DOI":"10.1038\/nbt1144","volume":"23","author":"S Washietl","year":"2005","unstructured":"Washietl S, Hofacker IL, Lukasser M, H\u00fcttenhofer A, Stadler PF: Genome-wide mapping of conserved RNA secondary structure structures predicts thousands of functional non-coding RNAs in human. Nature Biotechnology. 2005, 23: 1383-1390. 10.1038\/nbt1144","journal-title":"Nature Biotechnology"},{"key":"95_CR2","doi-asserted-by":"publisher","first-page":"e33","DOI":"10.1371\/journal.pcbi.0020033","volume":"2","author":"JS Pedersen","year":"2006","unstructured":"Pedersen JS, Bejerano G, Siepel A, Rosenbloom K, Lindblad-Toh K, Lander ES, Kent J, Miller W, Haussler D: Identification and classification of conserved RNA secondary structures in the human genome. PLoS Comput Biol. 2006, 2: e33- 10.1371\/journal.pcbi.0020033","journal-title":"PLoS Comput Biol"},{"key":"95_CR3","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1101\/gr.5226606","volume":"16","author":"E Torarinsson","year":"2006","unstructured":"Torarinsson E, Sawera M, Havgaard JH, Fredholm M, Gorodkin J: Thousands of corresponding human and mouse genomic regions unalignable in primary sequence contain common RNA structure. Genome Research. 2006, 16: 885-889. [(Erratum in: Genome Res. 2006 16:1439)]. 10.1101\/gr.5226606","journal-title":"Genome Research"},{"key":"95_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1186\/1471-2105-7-173","volume":"7","author":"AV Uzilov","year":"2006","unstructured":"Uzilov AV, Keegan JM, Mathews DH: Detection of non-coding RNAs on the basis of predicted secondary structure formation free energy change. BMC Bioinformatics. 2006, 7: 173- 10.1186\/1471-2105-7-173","journal-title":"BMC Bioinformatics"},{"key":"95_CR5","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1101\/gr.5650707","volume":"17","author":"S Washietl","year":"2007","unstructured":"Washietl S, Pedersen JS, Korbel JO, Stocsits C, Gruber AR, Hackerm\u00fcller J, Hertel J, Lindemeyer M, Reiche K, Tanzer A, Ucla C, Wyss C, Antonarakis SE, Denoeud F, Lagarde J, Drenkow J, Kapranov P, Gingeras TR, Guig\u00f3 R, Snyder M, Gerstein MB, Reymond A, Hofacker IL, Stadler PF: Structured RNAs in the ENCODE selected regions of the human genome. Genome Research. 2007, 17: 852-864. 10.1101\/gr.5650707","journal-title":"Genome Research"},{"key":"95_CR6","doi-asserted-by":"publisher","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","volume":"3","author":"S Will","year":"2007","unstructured":"Will S, Reiche K, Hofacker IL, Stadler PF, Backofen R: Inferring noncoding RNA families and classes by means of genome-scale structure-based clustering. PLoS Computational Biology. 2007, 3: e65- 10.1371\/journal.pcbi.0030065","journal-title":"PLoS Computational Biology"},{"key":"95_CR7","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1101\/gr.6887408","volume":"18","author":"E Torarinsson","year":"2008","unstructured":"Torarinsson E, Yao Z, Wiklund ED, Bramsen JB, Hansen C, Kjems J, Tommerup N, Ruzzo WL, Gorodkin J: Comparative genomics beyond sequence based alignments: RNA structures in the ENCODE regions. Genome Research. 2008, 18: 242-251. 10.1101\/gr.6887408","journal-title":"Genome Research"},{"key":"95_CR8","volume-title":"RNA Biol","author":"R Backofen","year":"2010","unstructured":"Backofen R, Hess WR: Computational prediction of sRNAs and their targets in bacteria. RNA Biol. 2010, 7:"},{"issue":"10","key":"95_CR9","doi-asserted-by":"publisher","first-page":"1177","DOI":"10.1093\/bioinformatics\/btl024","volume":"22","author":"U M\u00fcckstein","year":"2006","unstructured":"M\u00fcckstein U, Tafer H, Hackerm\u00fcller J, Bernhart SH, Stadler PF, Hofacker IL: Thermodynamics of RNA-RNA binding. Bioinformatics. 2006, 22 (10): 1177-82. 10.1093\/bioinformatics\/btl024","journal-title":"Bioinformatics"},{"issue":"24","key":"95_CR10","doi-asserted-by":"publisher","first-page":"2849","DOI":"10.1093\/bioinformatics\/btn544","volume":"24","author":"A Busch","year":"2008","unstructured":"Busch A, Richter AS, Backofen R: IntaRNA: efficient prediction of bacterial sRNA targets incorporating target site accessibility and seed regions. Bioinformatics. 2008, 24 (24): 2849-56. 10.1093\/bioinformatics\/btn544","journal-title":"Bioinformatics"},{"issue":"5","key":"95_CR11","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1006\/jmbi.2000.3942","volume":"300","author":"L Argaman","year":"2000","unstructured":"Argaman L, Altuvia S: fhlA repression by OxyS RNA: kissing complex formation at two sites results in a stable antisense-target RNA complex. Journal of Molecular Biology. 2000, 300 (5): 1101-12. 10.1006\/jmbi.2000.3942","journal-title":"Journal of Molecular Biology"},{"issue":"5","key":"95_CR12","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1016\/j.jmb.2004.10.082","volume":"345","author":"M Andronescu","year":"2005","unstructured":"Andronescu M, Zhang ZC, Condon A: Secondary structure prediction of interacting RNA molecules. Journal of Molecular Biology. 2005, 345 (5): 987-1001. 10.1016\/j.jmb.2004.10.082","journal-title":"Journal of Molecular Biology"},{"key":"95_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1748-7188-1-3","volume":"1","author":"SH Bernhart","year":"2006","unstructured":"Bernhart SH, Tafer H, M\u00fcckstein U, Flamm C, Stadler PF, Hofacker IL: Partition function and base pairing probabilities of RNA heterodimers. Algorithms Mol Biol. 2006, 1: 3- 10.1186\/1748-7188-1-3","journal-title":"Algorithms Mol Biol"},{"key":"95_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/060651100","volume":"49","author":"RM Dirks","year":"2007","unstructured":"Dirks RM, Bois JS, Schaeffer JM, Winfree E, Pierce NA: Thermodynamic Analysis of Interacting Nucleic Acid Strands. SIAM Review. 2007, 49: 65-88. 10.1137\/060651100","journal-title":"SIAM Review"},{"key":"95_CR15","first-page":"267","volume":"25","author":"M Zuker","year":"1994","unstructured":"Zuker M: Prediction of RNA secondary structure by energy minimization. Methods in Molecular Biology. 1994, 25: 267-94.","journal-title":"Methods in Molecular Biology"},{"key":"95_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00818163","volume":"125","author":"IL Hofacker","year":"1994","unstructured":"Hofacker IL, Fontana W, Stadler PF, Bonhoeffer S, Tacker M, Schuster P: Fast Folding and Comparison of RNA Secondary Structures. Monatshefte Chemie. 1994, 125: 167-188. 10.1007\/BF00818163","journal-title":"Monatshefte Chemie"},{"issue":"2","key":"95_CR17","first-page":"92","volume":"15","author":"DD Pervouchine","year":"2004","unstructured":"Pervouchine DD: IRIS: intermolecular RNA interaction search. Genome Inform. 2004, 15 (2): 92-101.","journal-title":"Genome Inform"},{"issue":"2","key":"95_CR18","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1089\/cmb.2006.13.267","volume":"13","author":"C Alkan","year":"2006","unstructured":"Alkan C, Karakoc E, Nadeau JH, Sahinalp SC, Zhang K: RNA-RNA interaction prediction and antisense RNA target search. Journal of Computational Biology. 2006, 13 (2): 267-82. 10.1089\/cmb.2006.13.267","journal-title":"Journal of Computational Biology"},{"issue":"12","key":"95_CR19","doi-asserted-by":"publisher","first-page":"i365","DOI":"10.1093\/bioinformatics\/btp212","volume":"25","author":"H Chitsaz","year":"2009","unstructured":"Chitsaz H, Salari R, Sahinalp SC, Backofen R: A partition function algorithm for interacting nucleic acid strands. Bioinformatics. 2009, 25 (12): i365-73. 10.1093\/bioinformatics\/btp212","journal-title":"Bioinformatics"},{"issue":"20","key":"95_CR20","doi-asserted-by":"publisher","first-page":"2646","DOI":"10.1093\/bioinformatics\/btp481","volume":"25","author":"FWD Huang","year":"2009","unstructured":"Huang FWD, Qin J, Reidys CM, Stadler PF: Partition function and base pairing probabilities for RNA-RNA interaction prediction. Bioinformatics. 2009, 25 (20): 2646-54. 10.1093\/bioinformatics\/btp481","journal-title":"Bioinformatics"},{"issue":"2","key":"95_CR21","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1093\/bioinformatics\/btp635","volume":"26","author":"FWD Huang","year":"2010","unstructured":"Huang FWD, Qin J, Reidys CM, Stadler PF: Target prediction and a statistical sampling algorithm for RNA-RNA interaction. Bioinformatics. 2010, 26 (2): 175-81. 10.1093\/bioinformatics\/btp635","journal-title":"Bioinformatics"},{"key":"95_CR22","first-page":"25","volume-title":"Proc. of the 9th Workshop on Algorithms in Bioinformatics (WABI), Volume 5724 of Lecture Notes in Computer Science","author":"H Chitsaz","year":"2009","unstructured":"Chitsaz H, Backofen R, Sahinalp SC: biRNA: Fast RNA-RNA Binding Sites Prediction. Proc. of the 9th Workshop on Algorithms in Bioinformatics (WABI), Volume 5724 of Lecture Notes in Computer Science. Edited by: Salzberg S, Warnow T. 2009, 25-36."},{"key":"95_CR23","first-page":"261","volume-title":"Proc. of the 9th Workshop on Algorithms in Bioinformatics (WABI), Volume 5724 of Lecture Notes in Computer Science","author":"R Salari","year":"2009","unstructured":"Salari R, Backofen R, Sahinalp SC: Fast prediction of RNA-RNA Interaction. Proc. of the 9th Workshop on Algorithms in Bioinformatics (WABI), Volume 5724 of Lecture Notes in Computer Science. Edited by: Salzberg S, Warnow T. 2009, 261-272."},{"key":"95_CR24","volume-title":"Proc of RECOMB 2010","author":"R Salari","year":"2010","unstructured":"Salari R, M\u00f6hl M, Will S, Sahinalp SC, Backofen R: Time and space efficient RNA-RNA interaction prediction via sparse folding. Proc of RECOMB 2010. 2010"},{"key":"95_CR25","doi-asserted-by":"publisher","first-page":"6355","DOI":"10.1093\/nar\/gkn544","volume":"36","author":"SE Seemann","year":"2008","unstructured":"Seemann SE, Gorodkin J, Backofen R: Unifying evolutionary and thermodynamic information for RNA folding of multiple alignments. Nucleic Acids Research. 2008, 36: 6355-6362. 10.1093\/nar\/gkn544","journal-title":"Nucleic Acids Research"},{"key":"95_CR26","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1006\/jmbi.1995.0608","volume":"254","author":"C Gaspin","year":"1995","unstructured":"Gaspin C, Westhof E: An interactive framework for RNA secondary structure prediction with a dynamical treatment of constraints. J Mol Biol. 1995, 254: 163-174. 10.1006\/jmbi.1995.0608","journal-title":"J Mol Biol"},{"key":"95_CR27","first-page":"323","volume-title":"In Algorithms in Bioinformatics, 7th International Workshop, WABI Philadelphia, PA, USA, September 8-9, 2007, Proceedings","author":"H Jabbari","year":"2007","unstructured":"Jabbari H, Condon A, Pop A, Pop C, Zhao Y: HFold: RNA Pseudoknotted Secondary Structure Prediction Using Hierarchical Folding. In Algorithms in Bioinformatics, 7th International Workshop, WABI Philadelphia, PA, USA, September 8-9, 2007, Proceedings. Edited by: Giancarlo R, Hannenhalli S. 2007, 323-334."},{"key":"95_CR28","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1093\/bioinformatics\/15.6.446","volume":"15","author":"B Knudsen","year":"1999","unstructured":"Knudsen B, Hein JJ: RNA secondary structure prediction using stochastic context-free grammars and evolutionary history. Bioinformatics. 1999, 15: 446-454. 10.1093\/bioinformatics\/15.6.446","journal-title":"Bioinformatics"},{"issue":"6-7","key":"95_CR29","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1002\/bip.360290621","volume":"29","author":"JS McCaskill","year":"1990","unstructured":"McCaskill JS: The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers. 1990, 29 (6-7): 1105-19. 10.1002\/bip.360290621","journal-title":"Biopolymers"},{"key":"95_CR30","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0135006","volume":"35","author":"R Nussinov","year":"1978","unstructured":"Nussinov R, Pieczenik G, Griggs JR, Kleitman DJ: Algorithms for Loop Matchings. SIAM Journal on Applied Mathematics. 1978, 35: 68-82. 10.1137\/0135006","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"8","key":"95_CR31","doi-asserted-by":"publisher","first-page":"1157","DOI":"10.1261\/rna.2500605","volume":"11","author":"Y Ding","year":"2005","unstructured":"Ding Y, Chan CY, Lawrence CE: RNA secondary structure prediction by centroids in a Boltzmann weighted ensemble. RNA. 2005, 11 (8): 1157-66. 10.1261\/rna.2500605","journal-title":"RNA"},{"issue":"3","key":"95_CR32","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.compbiolchem.2004.04.001","volume":"28","author":"B Knudsen","year":"2004","unstructured":"Knudsen B, Andersen ES, Damgaard C, Kjems J, Gorodkin J: Evolutionary rate variation and RNA secondary structure prediction. Comput Biol Chem. 2004, 28 (3): 219-226. 10.1016\/j.compbiolchem.2004.04.001","journal-title":"Comput Biol Chem"},{"issue":"9","key":"95_CR33","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1093\/bioinformatics\/btp033","volume":"25","author":"AM Waterhouse","year":"2009","unstructured":"Waterhouse AM, Procter JB, Martin DMA, Clamp M, Barton GJ: Jalview Version 2-a multiple sequence alignment editor and analysis workbench. Bioinformatics. 2009, 25 (9): 1189-91. 10.1093\/bioinformatics\/btp033","journal-title":"Bioinformatics"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-5-22.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T11:53:52Z","timestamp":1630497232000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-5-22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,21]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["95"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-5-22","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,21]]},"assertion":[{"value":"10 April 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"22"}}