{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T22:20:08Z","timestamp":1761862808126},"reference-count":31,"publisher":"Oxford University Press (OUP)","issue":"16","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2799,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,8,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Specific functions of ribonucleic acid (RNA) molecules are often associated with different motifs in the RNA structure. The key feature that forms such an RNA motif is the combination of sequence and structure properties. In this article, we introduce a new RNA sequence\u2013structure comparison method which maintains exact matching substructures. Existing common substructures are treated as whole unit while variability is allowed between such structural motifs.<\/jats:p>\n               <jats:p>Based on a fast detectable set of overlapping and crossing substructure matches for two nested RNA secondary structures, our method ExpaRNA (exact pattern of alignment of RNA) computes the longest collinear sequence of substructures common to two RNAs in O(H\u00b7nm) time and O(nm) space, where H \u226a n\u00b7m for real RNA structures. Applied to different RNAs, our method correctly identifies sequence\u2013structure similarities between two RNAs.<\/jats:p>\n               <jats:p>Results: We have compared ExpaRNA with two other alignment methods that work with given RNA structures, namely RNAforester and RNA_align. The results are in good agreement, but can be obtained in a fraction of running time, in particular for larger RNAs. We have also used ExpaRNA to speed up state-of-the-art Sankoff-style alignment tools like LocARNA, and observe a tradeoff between quality and speed. However, we get a speedup of 4.25 even in the highest quality setting, where the quality of the produced alignment is comparable to that of LocARNA alone.<\/jats:p>\n               <jats:p>Availability: The presented algorithm is implemented in the program ExpaRNA, which is available from our website (http:\/\/www.bioinf.uni-freiburg.de\/Software).<\/jats:p>\n               <jats:p>Contact: {exparna@informatik.uni-freiburg.de,backofen@informatik.uni-freiburg.de}<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp065","type":"journal-article","created":{"date-parts":[[2009,2,4]],"date-time":"2009-02-04T02:21:04Z","timestamp":1233714064000},"page":"2095-2102","source":"Crossref","is-referenced-by-count":30,"title":["Lightweight comparison of RNAs based on exact sequence\u2013structure matches"],"prefix":"10.1093","volume":"25","author":[{"given":"Steffen","family":"Heyne","sequence":"first","affiliation":[{"name":"Bioinformatics Group, Albert-Ludwigs-University Freiburg, Georges-Koehler-Allee 106, Freiburg, D-79110, Germany"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Albert-Ludwigs-University Freiburg, Georges-Koehler-Allee 106, Freiburg, D-79110, Germany"}]},{"given":"Michael","family":"Beckstette","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Albert-Ludwigs-University Freiburg, Georges-Koehler-Allee 106, Freiburg, D-79110, Germany"}]},{"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Albert-Ludwigs-University Freiburg, Georges-Koehler-Allee 106, Freiburg, D-79110, Germany"}]}],"member":"286","published-online":{"date-parts":[[2009,2,2]]},"reference":[{"key":"2023013112093062700_B1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/TCBB.2005.2","article-title":"A new distance for high level RNA secondary structure comparison","volume":"2","author":"Allali","year":"2005","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinfor."},{"key":"2023013112093062700_B2","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023013112093062700_B3","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/j.jda.2006.03.015","article-title":"Fast detection of common sequence structure patterns in RNAs","volume":"5","author":"Backofen","year":"2007","journal-title":"J. Discrete Algorithm"},{"key":"2023013112093062700_B4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-60044-2_30","article-title":"Computing similarity between RNA strings","volume-title":"Proceedings of the 6th Symposium Combinatorial Pattern Matching.","author":"Bafna","year":"1995"},{"key":"2023013112093062700_B5","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1093\/nar\/29.1.323","article-title":"BAliBASE (Benchmark Alignment dataBASE): enhancements for repeats, transmembrane sequences and circular permutations","volume":"29","author":"Bahr","year":"2001","journal-title":"Nucleic Acids Res."},{"key":"2023013112093062700_B6","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1186\/1471-2105-8-271","article-title":"Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization","volume":"8","author":"Bauer","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023013112093062700_B7","article-title":"RNA sequences and theedit(nested,nested)problem","volume-title":"Technical Report RR-IRIN-03.07","author":"Blin","year":"2003"},{"key":"2023013112093062700_B8","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1186\/1471-2105-3-15","article-title":"The Comparative RNA Web (CRW) Site: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs: Correction","volume":"3","author":"Cannone","year":"2002","journal-title":"BMC Bioinformatics"},{"key":"2023013112093062700_B9","article-title":"Algorithms and Complexity for Annotated Sequence Analysis","volume-title":"Ph.D. thesis","author":"Evans","year":"1999"},{"key":"2023013112093062700_B10","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":"2023013112093062700_B11","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":"2023013112093062700_B12","doi-asserted-by":"crossref","first-page":"1896","DOI":"10.1371\/journal.pcbi.0030193","article-title":"Fast pairwise structural RNA alignments by pruning of the dynamical programming matrix","volume":"3","author":"Havgaard","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023013112093062700_B13","doi-asserted-by":"crossref","first-page":"8175","DOI":"10.1073\/pnas.93.16.8175","article-title":"Molecular control of vertebrate iron metabolism: mRNA-based regulatory circuits operated by iron, nitric oxide, and oxidative stress","volume":"93","author":"Hentze","year":"1996","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023013112093062700_B14","first-page":"159","article-title":"Local similarity in RNA secondary structures","volume-title":"Proceedings of Computational Systems Bioinformatics (CSB 2003)","author":"H\u00f6chsmann","year":"2003"},{"key":"2023013112093062700_B15","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":"2023013112093062700_B16","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":"2023013112093062700_B17","first-page":"354","article-title":"Solution structure of mRNA hairpins promoting selenocysteine incorporation in Escherichia coli and their base-specific interaction with special elongation factor SELB","volume":"2","author":"Huttenhofer","year":"1996","journal-title":"RNA"},{"key":"2023013112093062700_B18","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","article-title":"Alignment of trees - an alternative to tree edit","volume":"143","author":"Jiang","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"2023013112093062700_B19","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1089\/10665270252935511","article-title":"A general edit distance between RNA structures","volume":"9","author":"Jiang","year":"2002","journal-title":"J. Comput. Biol."},{"key":"2023013112093062700_B20","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/S0022-0000(02)00004-1","article-title":"The longest common subsequence problem for sequences with nested arc annotations","volume":"65","author":"Lin","year":"2002","journal-title":"J. Comput. Syst. Sci."},{"key":"2023013112093062700_B21","doi-asserted-by":"crossref","first-page":"7622","DOI":"10.1128\/MCB.24.17.7622-7635.2004","article-title":"Internal ribosome entry site structural motifs conserved among mammalian fibroblast growth factor 1 alternatively spliced mRNAs","volume":"24","author":"Martineau","year":"2004","journal-title":"Mol. Cell Biol."},{"key":"2023013112093062700_B22","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":"2023013112093062700_B23","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":"2023013112093062700_B24","first-page":"178","article-title":"Structure local multiple alignment of RNA","volume-title":"Proceedings of German Conference on Bioinformatics (GCB'2008)","author":"Otto","year":"2008"},{"key":"2023013112093062700_B25","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":"2023013112093062700_B26","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1038\/nrg2172","article-title":"Ribozymes, riboswitches and beyond: regulation of gene expression without proteins","volume":"8","author":"Serganov","year":"2007","journal-title":"Nat. Rev. Genet."},{"key":"2023013112093062700_B27","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":"2023013112093062700_B28","doi-asserted-by":"crossref","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","article-title":"Inferring non-coding RNA families and classes by means of genome-scale structure-based clustering","volume":"3","author":"Will","year":"2007","journal-title":"PLOS Comput. Biol."},{"key":"2023013112093062700_B29","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1186\/1748-7188-1-19","article-title":"An enhanced RNA alignment benchmark for sequence alignment programs","volume":"1","author":"Wilm","year":"2006","journal-title":"Algorithms Mol. Biol."},{"key":"2023013112093062700_B30","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1006\/jmbi.1996.0812","article-title":"Selenoprotein synthesis in archaea: identification of an mRNA element of Methanococcus jannaschii probably directing selenocysteine insertion","volume":"266","author":"Wilting","year":"1997","journal-title":"J. Mol. Biol."},{"key":"2023013112093062700_B31","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."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/16\/2095\/48993113\/bioinformatics_25_16_2095.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/16\/2095\/48993113\/bioinformatics_25_16_2095.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T21:30:40Z","timestamp":1675200640000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/16\/2095\/203852"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,2]]},"references-count":31,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2009,8,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp065","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,8,15]]},"published":{"date-parts":[[2009,2,2]]}}}