{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T16:25:22Z","timestamp":1790785522702,"version":"4.1.0"},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"24","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,12,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: As more non\u2013coding RNAs are discovered, the importance of methods for RNA analysis increases. Since the structure of ncRNA is intimately tied to the function of the molecule, programs for RNA structure prediction are necessary tools in this growing field of research. Furthermore, it is known that RNA structure is often evolutionarily more conserved than sequence. However, few existing methods are capable of simultaneously considering multiple sequence alignment and structure prediction.<\/jats:p><jats:p>Result: We present a novel solution to the problem of simultaneous structure prediction and multiple alignment of RNA sequences. Using Markov chain Monte Carlo in a simulated annealing framework, the algorithm MASTR (Multiple Alignment of STructural RNAs) iteratively improves both sequence alignment and structure prediction for a set of RNA sequences. This is done by minimizing a combined cost function that considers sequence conservation, covariation and basepairing probabilities. The results show that the method is very competitive to similar programs available today, both in terms of accuracy and computational efficiency.<\/jats:p><jats:p>Availability: Source code available from http:\/\/mastr.binf.ku.dk\/<\/jats:p><jats:p>Contact: \u00a0stinus@binf.ku.dk<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm525","type":"journal-article","created":{"date-parts":[[2007,11,16]],"date-time":"2007-11-16T01:43:16Z","timestamp":1195177396000},"page":"3304-3311","source":"Crossref","is-referenced-by-count":62,"title":["MASTR: multiple alignment and structure prediction of non-coding RNAs using simulated annealing"],"prefix":"10.1093","volume":"23","author":[{"given":"Stinus","family":"Lindgreen","sequence":"first","affiliation":[{"name":"1 Bioinformatics Centre and 2Molecular Evolution Group, Department of Molecular Biology, University of Copenhagen, Ole Maaloes Vej 5, 2200 Copenhagen N, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul P.","family":"Gardner","sequence":"additional","affiliation":[{"name":"1 Bioinformatics Centre and 2Molecular Evolution Group, Department of Molecular Biology, University of Copenhagen, Ole Maaloes Vej 5, 2200 Copenhagen N, Denmark"},{"name":"1 Bioinformatics Centre and 2Molecular Evolution Group, Department of Molecular Biology, University of Copenhagen, Ole Maaloes Vej 5, 2200 Copenhagen N, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anders","family":"Krogh","sequence":"additional","affiliation":[{"name":"1 Bioinformatics Centre and 2Molecular Evolution Group, Department of Molecular Biology, University of Copenhagen, Ole Maaloes Vej 5, 2200 Copenhagen N, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2007,11,15]]},"reference":[{"key":"2023041107274143800_","first-page":"1","article-title":"RNAs everywhere: genome-wide annotation of structured RNAs","volume":"308","author":"Athanasius","year":"2007","journal-title":"J. Exp. Zoolog. Mol. Dev. Evol"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.thbio.2005.01.002","article-title":"Evolutionary patterns of non-coding RNAs","volume":"123","author":"Bompf\u00fcnewerer","year":"2005","journal-title":"Theory Biosci"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1126\/science.1108625","article-title":"Transcriptional maps of 10 human chromosomes at 5-nucleotide resolution","volume":"308","author":"Cheng","year":"2005","journal-title":"Science"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"14664","DOI":"10.1073\/pnas.0703836104","article-title":"Automated de novo prediction of native-like RNA tertiary structures","volume":"104","author":"Das","year":"2007","journal-title":"Proc. Natl Acad. Sci"},{"key":"2023041107274143800_","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 Acids Res"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis. Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin","year":"1998"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1093\/nar\/gki541","article-title":"A benchmark of multiple sequence alignment programs upon structural RNAs","volume":"33","author":"Gardner","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"4843","DOI":"10.1093\/nar\/gkh779","article-title":"Abstract shapes of RNA","volume":"32","author":"Giegerich","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"3724","DOI":"10.1093\/nar\/25.18.3724","article-title":"Finding the most significant common sequence and structure motifs in a set of RNA sequences","volume":"25","author":"Gorodkin","year":"1997","journal-title":"Nucleic Acids Res"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"D121","DOI":"10.1093\/nar\/gki081","article-title":"Rfam: annotating non-coding RNAs in complete genomes","volume":"33","author":"Griffiths-Jones","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511613586","volume-title":"Finite Markov Chains and Algorithmic Applications","author":"H\u00e4ggstr\u00f6m","year":"2002"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","article-title":"Monte carlo sampling methods using Markov chains and their applications","volume":"57","author":"Hastings","year":"1970","journal-title":"Biometrika"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"1815","DOI":"10.1093\/bioinformatics\/bti279","article-title":"Pairwise local structure alignment of RNA sequences with sequence similarity less than 40%","volume":"21","author":"Havgaard","year":"2005","journal-title":"Bioinformatics"},{"key":"2023041107274143800_","first-page":"649","article-title":"A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences when the phylogeny is given","volume":"6","author":"Hein","year":"1989","journal-title":"Mol. Biol. Evol"},{"key":"2023041107274143800_","first-page":"159","article-title":"Local similarity of RNA secondary structures","author":"H\u00f6chsmann","year":"2003"},{"key":"2023041107274143800_","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":"2023041107274143800_","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":"2023041107274143800_","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":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/j.mib.2007.05.010","article-title":"RNA structure: bioinformatic analysis","volume":"10","author":"Jossinet","year":"2007","journal-title":"Curr. Opin. Microbiol"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1093\/bioinformatics\/15.6.446","article-title":"RNA secondary structure prediction using stochastic context-free grammars and evolutionary history","volume":"15","author":"Knudsen","year":"1999","journal-title":"Bioinformatics"},{"key":"2023041107274143800_","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":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"2988","DOI":"10.1093\/bioinformatics\/btl514","article-title":"Measuring covariation in RNA alignments: physical realism improves information measures","volume":"22","author":"Lindgreen","year":"2006","journal-title":"Bioinformatics"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"2511","DOI":"10.1093\/nar\/20.10.2511","article-title":"Multiple alignment using simulated annealing: branch point definition in human mRNA splicing","volume":"20","author":"Lukashin","year":"1992","journal-title":"Nucleic Acids Res"},{"key":"2023041107274143800_","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":"2023041107274143800_","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":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"e149","DOI":"10.1371\/journal.pcbi.0030149","article-title":"SimulFold: simultaneously inferring RNA structures including pseudoknots, alignments and trees using a Bayesian MCMC framework","volume":"3","author":"Meyer","year":"2007","journal-title":"PLoS Comput. Biol"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","DOI":"10.1093\/bib\/bbm011","article-title":"A practical guide to the art of RNA gene prediction","author":"Meyer","year":"2007","journal-title":"Brief. Bioinformatics"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0135006","article-title":"Algorithms for loop matchings","volume":"35","author":"Nussinov","year":"1978","journal-title":"SIAM J. Appl. Math"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/j.sbi.2004.04.001","article-title":"RNA folding and unfolding","volume":"14","author":"Onoa","year":"2004","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"e33","DOI":"10.1371\/journal.pcbi.0020033","article-title":"Identification and classification of conserved RNA secondary structures in the human genome","volume":"2","author":"Pedersen","year":"2006","journal-title":"PLoS Comput. Biol"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"3516","DOI":"10.1093\/bioinformatics\/bti577","article-title":"Consensus shapes: An alternative to the Sankoff algorithm for RNA consensus structure prediction","volume":"21","author":"Reeder","year":"2005","journal-title":"Bioinformatics"},{"key":"2023041107274143800_","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":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.sbi.2007.03.001","article-title":"Bridging the gap in RNA structure prediction","volume":"17","author":"Shapiro","year":"2007","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"3352","DOI":"10.1093\/bioinformatics\/bti550","article-title":"MARNA: multiple alignment and consensus structure prediction of RNAs based on sequence structure comparisons","volume":"21","author":"Siebert","year":"2005","journal-title":"Bioinformatics"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/322139.322143","article-title":"The tree-to-tree correction problem","volume":"26","author":"Tai","year":"1979","journal-title":"J. ACM"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","article-title":"A comprehensive comparison of multiple sequence alignment programs","volume":"27","author":"Thompson","year":"1999","journal-title":"Nucleic Acids Res"},{"key":"2023041107274143800_","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":"2023041107274143800_","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":"2023041107274143800_","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":"2023041107274143800_","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"},{"key":"2023041107274143800_","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1137\/0218082","article-title":"Simple fast algorithms for the editing distance between trees and related problems","volume":"18","author":"Zhang","year":"1989","journal-title":"SIAM J. Comput"},{"key":"2023041107274143800_","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/24\/3304\/49823971\/bioinformatics_23_24_3304.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/24\/3304\/49823971\/bioinformatics_23_24_3304.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T19:17:35Z","timestamp":1684091855000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/24\/3304\/264286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,15]]},"references-count":44,"journal-issue":{"issue":"24","published-print":{"date-parts":[[2007,12,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm525","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,12,15]]},"published":{"date-parts":[[2007,11,15]]}}}