{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T21:50:06Z","timestamp":1757541006399},"reference-count":51,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Many computerized methods for RNA\u2013RNA interaction structure prediction have been developed. Recently, O(N6) time and O(N4) space dynamic programming algorithms have become available that compute the partition function of RNA\u2013RNA interaction complexes. However, few of these methods incorporate the knowledge concerning related sequences, thus relevant evolutionary information is often neglected from the structure determination. Therefore, it is of considerable practical interest to introduce a method taking into consideration both: thermodynamic stability as well as sequence\/structure covariation.<\/jats:p>\n               <jats:p>Results: We present the a priori folding algorithm ripalign, whose input consists of two (given) multiple sequence alignments (MSA). ripalign outputs (i) the partition function, (ii) base pairing probabilities, (iii) hybrid probabilities and (iv) a set of Boltzmann-sampled suboptimal structures consisting of canonical joint structures that are compatible to the alignments. Compared to the single sequence-pair folding algorithm rip, ripalign requires negligible additional memory resource but offers much better sensitivity and specificity, once alignments of suitable quality are given. ripalign additionally allows to incorporate structure constraints as input parameters.<\/jats:p>\n               <jats:p>Availability: The algorithm described here is implemented in C as part of the rip package. The supplemental material, source code and input\/output files can freely be downloaded from http:\/\/www.combinatorics.cn\/cbpc\/ripalign.html.<\/jats:p>\n               <jats:p>Contact: \u00a0duck@santafe.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq659","type":"journal-article","created":{"date-parts":[[2010,12,7]],"date-time":"2010-12-07T04:48:21Z","timestamp":1291697301000},"page":"456-463","source":"Crossref","is-referenced-by-count":38,"title":["RNA\u2013RNA interaction prediction based on multiple sequence alignments"],"prefix":"10.1093","volume":"27","author":[{"given":"Andrew X.","family":"Li","sequence":"first","affiliation":[{"name":"1 Center for Combinatorics, the Key Laboratory of Pure Mathematics and Combinarorics, Tianjin Key Laboratory of Combinatorics (LPMC-TJKLC), Nankai University Tianjin 300071, PR China, 2RNA Bioinformatics Group, Philipps-University Marburg, Marbacher Weg 6, 34037 Marburg, 3Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, 4Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany and 5College of Life Science, Nankai University Tianjin 300071, PR China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manja","family":"Marz","sequence":"additional","affiliation":[{"name":"1 Center for Combinatorics, the Key Laboratory of Pure Mathematics and Combinarorics, Tianjin Key Laboratory of Combinatorics (LPMC-TJKLC), Nankai University Tianjin 300071, PR China, 2RNA Bioinformatics Group, Philipps-University Marburg, Marbacher Weg 6, 34037 Marburg, 3Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, 4Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany and 5College of Life Science, Nankai University Tianjin 300071, PR China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jing","family":"Qin","sequence":"additional","affiliation":[{"name":"1 Center for Combinatorics, the Key Laboratory of Pure Mathematics and Combinarorics, Tianjin Key Laboratory of Combinatorics (LPMC-TJKLC), Nankai University Tianjin 300071, PR China, 2RNA Bioinformatics Group, Philipps-University Marburg, Marbacher Weg 6, 34037 Marburg, 3Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, 4Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany and 5College of Life Science, Nankai University Tianjin 300071, PR China"},{"name":"1 Center for Combinatorics, the Key Laboratory of Pure Mathematics and Combinarorics, Tianjin Key Laboratory of Combinatorics (LPMC-TJKLC), Nankai University Tianjin 300071, PR China, 2RNA Bioinformatics Group, Philipps-University Marburg, Marbacher Weg 6, 34037 Marburg, 3Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, 4Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany and 5College of Life Science, Nankai University Tianjin 300071, PR China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian M.","family":"Reidys","sequence":"additional","affiliation":[{"name":"1 Center for Combinatorics, the Key Laboratory of Pure Mathematics and Combinarorics, Tianjin Key Laboratory of Combinatorics (LPMC-TJKLC), Nankai University Tianjin 300071, PR China, 2RNA Bioinformatics Group, Philipps-University Marburg, Marbacher Weg 6, 34037 Marburg, 3Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, 4Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany and 5College of Life Science, Nankai University Tianjin 300071, PR China"},{"name":"1 Center for Combinatorics, the Key Laboratory of Pure Mathematics and Combinarorics, Tianjin Key Laboratory of Combinatorics (LPMC-TJKLC), Nankai University Tianjin 300071, PR China, 2RNA Bioinformatics Group, Philipps-University Marburg, Marbacher Weg 6, 34037 Marburg, 3Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, 4Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany and 5College of Life Science, Nankai University Tianjin 300071, PR China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2010,12,5]]},"reference":[{"key":"2023012511572180700_B1","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0166-218X(00)00186-4","article-title":"Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots","volume":"104","author":"Akutsu","year":"2000","journal-title":"Disc. Appl. Math."},{"key":"2023012511572180700_B2","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1089\/cmb.2006.13.267","article-title":"RNA-RNA interaction prediction and antisense RNA target search","volume":"13","author":"Alkan","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023012511572180700_B3","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1038\/nature02871","article-title":"The functions of animal microRNAs","volume":"431","author":"Ambros","year":"2004","journal-title":"Nature"},{"key":"2023012511572180700_B4","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1016\/j.jmb.2004.10.082","article-title":"Secondary structure prediction of interacting RNA molecules","volume":"345","author":"Andronescu","year":"2005","journal-title":"J. Mol. Biol."},{"key":"2023012511572180700_B5","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1006\/jmbi.2000.3942","article-title":"fhlA repression by OxyS RNA: kissing complex formation at two sites results in a stable antisense-target RNA complex","volume":"300","author":"Argaman","year":"2000","journal-title":"J. Mol. Biol."},{"key":"2023012511572180700_B6","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1016\/S0300-9084(02)01402-5","article-title":"The expanding snoRNA world","volume":"84","author":"Bachellerie","year":"2002","journal-title":"Biochimie"},{"key":"2023012511572180700_B7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/1748-7188-1-3","article-title":"Partition function and base pairing probabilities of RNA heterodimers","volume":"1","author":"Bernhart","year":"2006","journal-title":"Algorithms Mol. Biol."},{"key":"2023012511572180700_B8","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1186\/1471-2105-9-474","article-title":"RNAalifold: improved consensus structure prediction for RNA alignments","volume":"9","author":"Bernhart","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012511572180700_B9","first-page":"122","article-title":"An element in human U6 RNA destabilizes the U4\/U6 spliceosomal RNA complex","volume":"1","author":"Brow","year":"1995","journal-title":"RNA"},{"key":"2023012511572180700_B10","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1016\/S0300-9084(02)01401-3","article-title":"RNA loop-loop interactions as dynamic functional motifs","volume":"84","author":"Brunel","year":"2003","journal-title":"Biochimie"},{"key":"2023012511572180700_B11","doi-asserted-by":"crossref","first-page":"2849","DOI":"10.1093\/bioinformatics\/btn544","article-title":"IntaRNA: efficient prediction of bacterial sRNA targets incorporating target site accessibility and seed regions","volume":"24","author":"Busch","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012511572180700_B12","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-3-642-04241-6_3","article-title":"biRNA: Fast RNA-RNA binding sites prediction","volume-title":"Proceedings of the 9th Workshop on Algorithms in Bioinformatics (WABI)","author":"Chitsaz","year":"2009"},{"key":"2023012511572180700_B13","doi-asserted-by":"crossref","first-page":"i365","DOI":"10.1093\/bioinformatics\/btp212","article-title":"A partition function algorithm for interacting nucleic acid strands","volume":"25","author":"Chitsaz","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012511572180700_B14","doi-asserted-by":"crossref","first-page":"7280","DOI":"10.1093\/nar\/gkg938","article-title":"A statistical sampling algorithm for RNA secondary structure prediction","volume":"31","author":"Ding","year":"2003","journal-title":"Nucleic Acid Res."},{"key":"2023012511572180700_B15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1137\/060651100","article-title":"Thermodynamic analysis of interacting nucleic acid strands","volume":"49","author":"Dirks","year":"2007","journal-title":"SIAM Rev."},{"key":"2023012511572180700_B16","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0300-9084(96)84750-X","article-title":"Structural features of U6 snRNA and dynamic interactions with other spliceosomal components leading to pre-mRNA splicing","volume":"78","author":"Forne","year":"1996","journal-title":"Biochimie"},{"key":"2023012511572180700_B17","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1006\/jmbi.1995.0608","article-title":"An interactive framework for RNA secondary structure prediction with a dynamical treatment of constraints","volume":"254","author":"Gaspin","year":"1995","journal-title":"J. Mol. Biol"},{"key":"2023012511572180700_B18","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1038\/sj.emboj.7600058","article-title":"Hfq, a new chaperoning role: binding to messenger RNA determines access for small RNA regulator","volume":"23","author":"Geissmann","year":"2004","journal-title":"EMBO J."},{"key":"2023012511572180700_B19","doi-asserted-by":"crossref","first-page":"1813","DOI":"10.1093\/nar\/gkg297","article-title":"A survey of small RNA-encoding genes in Escherichia coli","volume":"31","author":"Hershberg","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012511572180700_B20","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":"2023012511572180700_B21","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":"2023012511572180700_B22","doi-asserted-by":"crossref","first-page":"2646","DOI":"10.1093\/bioinformatics\/btp481","article-title":"Partition function and base pairing probabilities for RNA-RNA interaction prediction","volume":"25","author":"Huang","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012511572180700_B23","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1093\/bioinformatics\/btp635","article-title":"Target prediction and a statistical sampling algorithm for RNA-RNA interaction","volume":"26","author":"Huang","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012511572180700_B24","article-title":"Hfold:RNA pseudoknotted secondary structure prediction using hierarchial folding","volume-title":"Algorithms in Bioinformatics, 7th International Workshop, WABI 2007.","author":"Jabbari","year":"2007"},{"key":"2023012511572180700_B25","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/S0300-9084(97)86148-2","article-title":"Chlamydomonas U2, U4 and U6 snRNAs. An evolutionary conserved putative third interaction between U4 and U6 snrnas which has a counterpart in the U4atac-U6atac snRNA duplex","volume":"79","author":"Jakab","year":"1997","journal-title":"Biochimie"},{"key":"2023012511572180700_B26","doi-asserted-by":"crossref","first-page":"i460","DOI":"10.1093\/bioinformatics\/btq372","article-title":"RactIP: fast and accurate prediction of RNA-RNA interaction using integer programming","volume":"26","author":"Kato","year":"2010","journal-title":"Bioinfomatics"},{"key":"2023012511572180700_B27","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1017\/S135583820099215X","article-title":"An unusual structure formed by antisense-target RNA binding involves an extended kissing complex with a four-way junction and a side-by-side helical alignment","volume":"6","author":"Kolb","year":"2000","journal-title":"RNA"},{"key":"2023012511572180700_B28","doi-asserted-by":"crossref","first-page":"3001","DOI":"10.1093\/nar\/gkn142","article-title":"Computational screen for spliceosomal RNA genes aids in defining the phylogenetic distribution of major and minor spliceosomal components","volume":"36","author":"L\u00f3pez","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012511572180700_B29","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1261\/rna.426707","article-title":"A novel family of C. elegans snRNPs contains proteins associated with Trans-splicing","volume":"13","author":"MacMorris","year":"2007","journal-title":"RNA"},{"key":"2023012511572180700_B30","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1007\/s00239-008-9149-6","article-title":"Evolution of spliceosomal snRNA genes in metazoan animals","volume":"67","author":"Marz","year":"2008","journal-title":"J. Mol. Evol."},{"key":"2023012511572180700_B31","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":"2023012511572180700_B32","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":"2023012511572180700_B33","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1109\/TCBB.2007.70258","article-title":"On the approximation of optimal structures for RNA-RNA interaction","volume":"6","author":"Mneimneh","year":"2009","journal-title":"IEEE\/ACM Trans. Comp. Biol. Bioinf."},{"key":"2023012511572180700_B34","doi-asserted-by":"crossref","first-page":"1177","DOI":"10.1093\/bioinformatics\/btl024","article-title":"Thermodynamics of RNA-RNA binding","volume":"22","author":"M\u00fcckstein","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012511572180700_B35","first-page":"114","article-title":"Translational control by RNA-RNA interaction: improved computation of RNA-RNA binding thermodynamics","volume-title":"BioInformatics Research and Development \u2014 BIRD 2008","author":"M\u00fcckstein","year":"2008"},{"key":"2023012511572180700_B36","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/j.ceb.2004.04.003","article-title":"miRNAs on the move: miRNA biogenesis and the RNAi machinery","volume":"16","author":"Murchison","year":"2004","journal-title":"Curr. Opin. Cell. Biol."},{"key":"2023012511572180700_B37","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/S1097-2765(02)00441-0","article-title":"The divergent U12-type splicesome is sequired for pre-mRNA splicing and is essential for development in Drosophila","volume":"9","author":"Otake","year":"2002","journal-title":"Mol. Cell"},{"key":"2023012511572180700_B38","first-page":"92","article-title":"IRIS: Intermolecular RNA interaction search","volume":"15","author":"Pervouchine","year":"2004","journal-title":"Proc. Genome Informatics"},{"key":"2023012511572180700_B39","first-page":"1507","article-title":"Fast and effective prediction of microRNA\/target duplexes","volume":"10","author":"Rehmsmeier","year":"2004","journal-title":"Gene"},{"key":"2023012511572180700_B40","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1046\/j.1365-2958.2003.03454.x","article-title":"Small non-coding RNAs, co-ordinators of adaptation processes in Escherichia coli: The RpoS paradigm","volume":"48","author":"Repoila","year":"2003","journal-title":"Mol. Microbiol."},{"key":"2023012511572180700_B41","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","article-title":"A dynamic programming algorithms for RNA structure prediction including pseudoknots","volume":"285","author":"Rivas","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023012511572180700_B42","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/978-3-642-04241-6_22","article-title":"Fast prediction of RNA-RNA interaction","volume-title":"Proceedings of the 9th Workshop on Algorithms in Bioinformatics (WABI)","author":"Salari","year":"2009"},{"key":"2023012511572180700_B43","doi-asserted-by":"crossref","first-page":"6355","DOI":"10.1093\/nar\/gkn544","article-title":"Unifying evolutionary and thermodynamic information for RNA folding of multiple alignments","volume":"36","author":"Seemann","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012511572180700_B44","article-title":"PETcofold: Predicting conserved interactions and structures of two multiple alignments of RNA sequences","author":"Seemann","year":"2010","journal-title":"Bioinformatics."},{"key":"2023012511572180700_B45","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1186\/1748-7188-5-22","article-title":"Hierarchical folding of multiple sequence alignments for the prediction of structures and RNA-RNA interactions","volume":"5","author":"Seemann","year":"2010","journal-title":"Algorithms Mol. Biology"},{"key":"2023012511572180700_B46","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/0166-6851(94)00040-9","article-title":"The spliceosomal U small nuclear RNAs of Ascaris lumbricoides","volume":"64","author":"Shambaugh","year":"1994","journal-title":"Mol. Biochem. Parasitol."},{"key":"2023012511572180700_B47","doi-asserted-by":"crossref","first-page":"4650","DOI":"10.1093\/nar\/gkf609","article-title":"Domains of human U4atac snRNA required for U12-dependent splicing in vivo","volume":"30","author":"Shukla","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023012511572180700_B48","doi-asserted-by":"crossref","first-page":"2633","DOI":"10.1093\/nar\/18.9.2633","article-title":"The spliceosomal snRNAs of Caenorhabditis elegans","volume":"18","author":"Thomas","year":"1990","journal-title":"Nucleic Acids Res."},{"key":"2023012511572180700_B49","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1016\/S1097-2765(00)00131-3","article-title":"Crystal structure of the spliceosomal 15.5kD protein bound to a U4 snRNA fragment","volume":"6","author":"Vidovic","year":"2000","journal-title":"Mol. Cell"},{"key":"2023012511572180700_B50","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0168-9525(02)02658-6","article-title":"Antisense RNAs everywhere?","volume":"18","author":"Wagner","year":"2002","journal-title":"Trends Genet."},{"key":"2023012511572180700_B51","article-title":"Nupack: analysis and design of nucleic acid systems","author":"Zadeh","year":"2010","journal-title":"J. Comput. Chem."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/4\/456\/48867015\/bioinformatics_27_4_456.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/4\/456\/48867015\/bioinformatics_27_4_456.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T12:41:44Z","timestamp":1674650504000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/4\/456\/197158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,5]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq659","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,2,15]]},"published":{"date-parts":[[2010,12,5]]}}}