{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T18:59:15Z","timestamp":1762541955571},"reference-count":55,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: With recent advances in sequencing, structural and functional studies of RNA lag behind the discovery of sequences. Computational analysis of RNA is increasingly important to reveal structure\u2013function relationships with low cost and speed. The purpose of this study is to use multiple homologous sequences to infer a conserved RNA structure.<\/jats:p>\n               <jats:p>Results: A new algorithm, called Multilign, is presented to find the lowest free energy RNA secondary structure common to multiple sequences. Multilign is based on Dynalign, which is a program that simultaneously aligns and folds two sequences to find the lowest free energy conserved structure. For Multilign, Dynalign is used to progressively construct a conserved structure from multiple pairwise calculations, with one sequence used in all pairwise calculations. A base pair is predicted only if it is contained in the set of low free energy structures predicted by all Dynalign calculations. In this way, Multilign improves prediction accuracy by keeping the genuine base pairs and excluding competing false base pairs. Multilign has computational complexity that scales linearly in the number of sequences. Multilign was tested on extensive datasets of sequences with known structure and its prediction accuracy is among the best of available algorithms. Multilign can run on long sequences (&amp;gt; 1500 nt) and an arbitrarily large number of sequences.<\/jats:p>\n               <jats:p>Availability: The algorithm is implemented in ANSI C++ and can be downloaded as part of the RNAstructure package at: http:\/\/rna.urmc.rochester.edu<\/jats:p>\n               <jats:p>Contact: \u00a0david_mathews@urmc.rochester.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq726","type":"journal-article","created":{"date-parts":[[2010,12,31]],"date-time":"2010-12-31T01:59:43Z","timestamp":1293760783000},"page":"626-632","source":"Crossref","is-referenced-by-count":53,"title":["Multilign: an algorithm to predict secondary structures conserved in multiple RNA sequences"],"prefix":"10.1093","volume":"27","author":[{"given":"Zhenjiang","family":"Xu","sequence":"first","affiliation":[{"name":"1 Department of Biochemistry and Biophysics and Center for RNA Biology and 2Department of Biostatistics and Computational Biology, University of Rochester Medical Center, Rochester, NY, USA"}]},{"given":"David H.","family":"Mathews","sequence":"additional","affiliation":[{"name":"1 Department of Biochemistry and Biophysics and Center for RNA Biology and 2Department of Biostatistics and Computational Biology, University of Rochester Medical Center, Rochester, NY, USA"},{"name":"1 Department of Biochemistry and Biophysics and Center for RNA Biology and 2Department of Biostatistics and Computational Biology, University of Rochester Medical Center, Rochester, NY, USA"}]}],"member":"286","published-online":{"date-parts":[[2010,12,30]]},"reference":[{"key":"2023012511564007000_B1","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1186\/1471-2105-8-34","article-title":"Computational RNA secondary structure design: empirical complexity and improved methods","volume":"8","author":"Aguirre-Hernandez","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012511564007000_B2","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.sbi.2006.05.001","article-title":"Structures of regulatory elements in mRNAs","volume":"16","author":"Batey","year":"2006","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012511564007000_B3","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1186\/1471-2105-8-190","article-title":"Can Clustal-style progressive pairwise alignment of multiple sequences be used in RNA secondary structure prediction?","volume":"8","author":"Bellamy-Royds","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012511564007000_B4","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":"2023012511564007000_B5","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1093\/bfgp\/elp043","article-title":"From consensus structure prediction to RNA gene finding","volume":"8","author":"Bernhart","year":"2009","journal-title":"Brief. Funct. Genomics Proteomics"},{"key":"2023012511564007000_B6","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1093\/nar\/27.1.314","article-title":"The ribonuclease P database","volume":"27","author":"Brown","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023012511564007000_B7","doi-asserted-by":"crossref","first-page":"6971","DOI":"10.1021\/bi0029548","article-title":"Thermodynamics of three-way multibranch loops in RNA","volume":"40","author":"Diamond","year":"2001","journal-title":"Biochemistry"},{"key":"2023012511564007000_B8","doi-asserted-by":"crossref","first-page":"1392","DOI":"10.1093\/nar\/gkh291","article-title":"Paradigms for computational nucleic acid design","volume":"32","author":"Dirks","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012511564007000_B9","doi-asserted-by":"crossref","first-page":"i68","DOI":"10.1093\/bioinformatics\/btn177","article-title":"A max-margin model for efficient simultaneous alignment and folding of RNA sequences","volume":"24","author":"Do","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012511564007000_B10","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":"2023012511564007000_B11","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nrm1647","article-title":"The catalytic diversity of RNAs","volume":"6","author":"Fedor","year":"2005","journal-title":"Nat. Rev. Mol. Cell Biol."},{"key":"2023012511564007000_B12","doi-asserted-by":"crossref","first-page":"3051","DOI":"10.1093\/nar\/21.13.3051","article-title":"Collection of small subunit (16S- and 16S-like) ribosomal RNA structures","volume":"21","author":"Gutell","year":"1993","journal-title":"Nucleic Acids Res."},{"key":"2023012511564007000_B13","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0959-440X(02)00339-1","article-title":"The accuracy of ribosomal RNA comparative structure models","volume":"12","author":"Gutell","year":"2002","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012511564007000_B14","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1186\/1471-2105-8-130","article-title":"Efficient pairwise RNA structure prediction using probabilistic alignment constraints in Dynalign","volume":"8","author":"Harmanci","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012511564007000_B15","doi-asserted-by":"crossref","first-page":"2406","DOI":"10.1093\/nar\/gkn043","article-title":"PARTS: Probabilistic Alignment for RNA joinT Secondary structure prediction","volume":"36","author":"Harmanci","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012511564007000_B16","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1186\/1471-2105-6-73","article-title":"Accelerated probabilistic inference of RNA structure evolution","volume":"6","author":"Holmes","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023012511564007000_B17","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":"2023012511564007000_B18","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1016\/S0092-8674(00)81308-2","article-title":"Site-specific ribose methylation of preribosomal RNA: a novel function for small nucleolar RNAs","volume":"85","author":"Kiss-Laszlo","year":"1996","journal-title":"Cell"},{"key":"2023012511564007000_B19","doi-asserted-by":"crossref","first-page":"2947","DOI":"10.1093\/bioinformatics\/btm404","article-title":"Clustal W and Clustal X version 2.0","volume":"23","author":"Larkin","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012511564007000_B20","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1093\/nar\/26.1.177","article-title":"The signal recognition particle Database (SRPDB)","volume":"26","author":"Larsen","year":"1998","journal-title":"Nucleic Acids Res."},{"key":"2023012511564007000_B21","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1016\/0092-8674(93)90529-Y","article-title":"The C. elegans heterochronic gene lin-4 encodes small RNAs with antisense complementarity to lin-14","volume":"75","author":"Lee","year":"1993","journal-title":"Cell"},{"key":"2023012511564007000_B22","doi-asserted-by":"crossref","first-page":"7039","DOI":"10.1073\/pnas.0702137104","article-title":"Real-time control of the energy landscape by force directs the folding of RNA molecules","volume":"104","author":"Li","year":"2007","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012511564007000_B23","doi-asserted-by":"crossref","first-page":"3304","DOI":"10.1093\/bioinformatics\/btm525","article-title":"MASTR: multiple alignment and structure prediction of non-coding RNAs using simulated annealing","volume":"23","author":"Lindgreen","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012511564007000_B24","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1038\/nsmb1226","article-title":"Potent effect of target structure on microRNA function","volume":"14","author":"Long","year":"2007","journal-title":"Nat. Struct. Mol. Biol."},{"key":"2023012511564007000_B25","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1093\/nar\/gkm920","article-title":"Efficient siRNA selection using hybridization thermodynamics","volume":"36","author":"Lu","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012511564007000_B26","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1504\/IJBRA.2005.007581","article-title":"Simultaneous alignment and structure prediction of three RNA sequences","volume":"1","author":"Masoumi","year":"2005","journal-title":"Int. J. Bioinform. Res. Appl."},{"key":"2023012511564007000_B27","doi-asserted-by":"crossref","first-page":"1178","DOI":"10.1261\/rna.7650904","article-title":"Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization","volume":"10","author":"Mathews","year":"2004","journal-title":"RNA"},{"key":"2023012511564007000_B28","doi-asserted-by":"crossref","first-page":"2246","DOI":"10.1093\/bioinformatics\/bti349","article-title":"Predicting a set of minimal free energy RNA secondary structures common to two sequences","volume":"21","author":"Mathews","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012511564007000_B29","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/s00214-005-0027-7","article-title":"Predicting RNA secondary structure by free energy minimization","volume":"116","author":"Mathews","year":"2006","journal-title":"Theor. Chem. Acc."},{"key":"2023012511564007000_B30","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":"2023012511564007000_B31","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.sbi.2006.05.010","article-title":"Prediction of RNA secondary structure by free energy minimization","volume":"16","author":"Mathews","year":"2006","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012511564007000_B32","first-page":"1","article-title":"Secondary structure model of the RNA recognized by the reverse transcriptase from the R2 retrotransposable element","volume":"3","author":"Mathews","year":"1997","journal-title":"RNA"},{"key":"2023012511564007000_B33","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":"2023012511564007000_B34","doi-asserted-by":"crossref","first-page":"7287","DOI":"10.1073\/pnas.0401799101","article-title":"Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure","volume":"101","author":"Mathews","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012511564007000_B35","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1126\/science.289.5481.920","article-title":"The structural basis of ribosome activity in peptide bond synthesis","volume":"289","author":"Nissen","year":"2000","journal-title":"Science"},{"key":"2023012511564007000_B36","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1101\/gr.4200206","article-title":"Experimental validation of the regulated expression of large numbers of non-coding RNAs from the mouse genome","volume":"16","author":"Ravasi","year":"2006","journal-title":"Genome Res."},{"key":"2023012511564007000_B37","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1186\/1471-2105-11-129","article-title":"RNAstructure: software for RNA secondary structure prediction and analysis","volume":"11","author":"Reuter","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012511564007000_B38","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":"2023012511564007000_B39","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1038\/nature08756","article-title":"The primary transcriptome of the major human pathogen Helicobacter pylori","volume":"464","author":"Sharma","year":"2010","journal-title":"Nature"},{"key":"2023012511564007000_B40","doi-asserted-by":"crossref","first-page":"D139","DOI":"10.1093\/nar\/gki012","article-title":"Compilation of tRNA sequences and sequences of tRNA genes","volume":"33","author":"Sprinzl","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012511564007000_B41","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1093\/bioinformatics\/btk010","article-title":"RNAshapes: an integrated RNA analysis package based on abstract shapes","volume":"22","author":"Steffen","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012511564007000_B42","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1093\/nar\/27.1.158","article-title":"5S ribosomal RNA data bank","volume":"27","author":"Szymanski","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023012511564007000_B43","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1038\/nbt1404","article-title":"The impact of target site accessibility on the design of effective siRNAs","volume":"26","author":"Tafer","year":"2008","journal-title":"Nat. Biotechnol."},{"key":"2023012511564007000_B44","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1038\/nature05874","article-title":"Identification and analysis of functional elements in 1% of the human genome by the ENCODE pilot project","volume":"447","author":"The Encode Project Consortium","year":"2007","journal-title":"Nature"},{"key":"2023012511564007000_B45","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":"The Fantom Consortium the Riken Genome Exploration Research Group Phase I & II Team","year":"2002","journal-title":"Nature"},{"key":"2023012511564007000_B46","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1101\/gr.5226606","article-title":"Thousands of corresponding human and mouse genomic regions unalignable in primary sequence contain common RNA structure","volume":"16","author":"Torarinsson","year":"2006","journal-title":"Genome Res."},{"key":"2023012511564007000_B47","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1093\/bioinformatics\/btm049","article-title":"Multiple structural alignment and clustering of RNA sequences","volume":"23","author":"Torarinsson","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012511564007000_B48","doi-asserted-by":"crossref","first-page":"D280","DOI":"10.1093\/nar\/gkp892","article-title":"NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure","volume":"38","author":"Turner","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023012511564007000_B49","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1186\/1471-2105-7-173","article-title":"Detection of non-coding RNAs on the basis of predicted secondary structure formation free energy change","volume":"7","author":"Uzilov","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012511564007000_B50","doi-asserted-by":"crossref","first-page":"6117","DOI":"10.1021\/bi702356j","article-title":"Anticodon domain modifications contribute order to tRNA for ribosome-mediated codon binding","volume":"47","author":"Vendeix","year":"2008","journal-title":"Biochemistry"},{"key":"2023012511564007000_B51","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":"2023012511564007000_B52","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":"2023012511564007000_B53","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."},{"key":"2023012511564007000_B54","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-Crick base pairs","volume":"37","author":"Xia","year":"1998","journal-title":"Biochemistry"},{"key":"2023012511564007000_B55","doi-asserted-by":"crossref","first-page":"1883","DOI":"10.1093\/bioinformatics\/btm272","article-title":"RNA Sampler: a new sampling based algorithm for common RNA secondary structure prediction and structural alignment","volume":"23","author":"Xu","year":"2007","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/5\/626\/48863537\/bioinformatics_27_5_626.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/5\/626\/48863537\/bioinformatics_27_5_626.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T12:32:42Z","timestamp":1674649962000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/5\/626\/1745961"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,30]]},"references-count":55,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq726","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,3,1]]},"published":{"date-parts":[[2010,12,30]]}}}