{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T02:31:47Z","timestamp":1791081107401,"version":"4.1.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,4,7]],"date-time":"2005-04-07T00:00:00Z","timestamp":1112832000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2005,4,7]],"date-time":"2005-04-07T00:00:00Z","timestamp":1112832000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                        <jats:title>Background<\/jats:title>\n                        <jats:p>Alignment of RNA secondary structures is important in studying functional RNA motifs. In recent years, much progress has been made in RNA motif finding and structure alignment. However, existing tools either require a large number of prealigned structures or suffer from high time complexities. This makes it difficult for the tools to process RNAs whose prealigned structures are unavailable or process very large RNA structure databases.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>We present here an efficient tool called RSmatch for aligning RNA secondary structures and for motif detection. Motivated by widely used algorithms for RNA folding, we decompose an RNA secondary structure into a set of atomic structure components that are further organized by a tree model to capture the structural particularities. RSmatch can find the optimal global or local alignment between two RNA secondary structures using two scoring matrices, one for single-stranded regions and the other for double-stranded regions. The time complexity of RSmatch is <jats:italic>O(mn)<\/jats:italic> where <jats:italic>m<\/jats:italic> is the size of the query structure and <jats:italic>n<\/jats:italic> that of the subject structure. When applied to searching a structure database, RSmatch can find similar RNA substructures, and is capable of conducting multiple structure alignment and iterative database search. Therefore it can be used to identify functional RNA motifs. The accuracy of RSmatch is tested by experiments using a number of known RNA structures, including simple stem-loops and complex structures containing junctions.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusion<\/jats:title>\n                        <jats:p>With respect to computing efficiency and accuracy, RSmatch compares favorably with other tools for RNA structure alignment and motif detection. This tool shall be useful to researchers interested in comparing RNA structures obtained from wet lab experiments or RNA folding programs, particularly when the size of the structure dataset is large.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-6-89","type":"journal-article","created":{"date-parts":[[2005,4,8]],"date-time":"2005-04-08T06:57:49Z","timestamp":1112943469000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":35,"title":["A method for aligning RNA secondary structures and its application to RNA motif detection"],"prefix":"10.1186","volume":"6","author":[{"given":"Jianghui","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jason TL","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Hu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Tian","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,4,7]]},"reference":[{"key":"414_CR1","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1093\/nar\/gkg006","volume":"31","author":"S Griffiths-Jones","year":"2003","unstructured":"Griffiths-Jones S, Bateman A, Marshall M, Khanna A, Eddy SR: Rfam: an RNA family database. Nucleic Acids Res 2003, 31: 439\u2013441. 10.1093\/nar\/gkg006","journal-title":"Nucleic Acids Res"},{"key":"414_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1261\/rna.2183803","volume":"9","author":"V Ambros","year":"2003","unstructured":"Ambros V, Bartel B, Bartel DP, Berge CB, Carrington JC, Chen X, Dreyfuss G, Eddy SR, Griffiths-Jones S, Marshall M, Matzke M, Ruvkun G, Tuschl T: A uniform system for microRNA annotation. RNA 2003, 9: 277\u2013279. 10.1261\/rna.2183803","journal-title":"RNA"},{"key":"414_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1093\/nar\/30.1.335","volume":"30","author":"G Pesole","year":"2002","unstructured":"Pesole G, Liuni S, Grillo G, Licciulli F, Mignone F, Gissi C, Saccone C: UTRdb and UTRsite: specialized databases of sequences and functional elements of 5' and 3' untranslated regions of eukaryotic mRNAs. Nucleic Acids Research 2002, 30: 335\u2013340. 10.1093\/nar\/30.1.335","journal-title":"Nucleic Acids Research"},{"key":"414_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0968-0004(03)00002-1","volume":"28","author":"B Mazumder","year":"2003","unstructured":"Mazumder B, Seshadri V, Fox PL: Translational control by the 3'UTR: the ends specify the means. Trends Biochem Sci 2003, 28: 91\u201398. 10.1016\/S0968-0004(03)00002-1","journal-title":"Trends Biochem Sci"},{"key":"414_CR5","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1038\/nrg1125","volume":"4","author":"S Kuersten","year":"2003","unstructured":"Kuersten S, Goodwin EB: The power of 3'UTR: translational control and development. Nat Rev Genet 2003, 4: 626\u2013637. 10.1038\/nrg1125","journal-title":"Nat Rev Genet"},{"key":"414_CR6","doi-asserted-by":"publisher","first-page":"1495","DOI":"10.1093\/bioinformatics\/bth108","volume":"20","author":"IL Hofacker","year":"2004","unstructured":"Hofacker IL, Stadler PF, Stocsits RR: Conserved RNA secondary structures in viral genomes: a survey. Bioinformatics 2004, 20: 1495\u20131599. 10.1093\/bioinformatics\/bth108","journal-title":"Bioinformatics"},{"key":"414_CR7","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/0076-6879(89)80106-5","volume":"180","author":"M Zuker","year":"1989","unstructured":"Zuker M: Computer prediction of RNA structure. Methods Enzymol 1989, 180: 262\u2013288.","journal-title":"Methods Enzymol"},{"key":"414_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1098\/rspb.1994.0040","volume":"255","author":"P Schuster","year":"1994","unstructured":"Schuster P, Fontana W, Stadler PF, Hofacker IL: From sequences to shapes and back: a case study in RNA secondary structures. Proc Biol Sci 1994, 255: 279\u2013284.","journal-title":"Proc Biol Sci"},{"key":"414_CR9","doi-asserted-by":"publisher","first-page":"3429","DOI":"10.1093\/nar\/gkg599","volume":"31","author":"IL Hofacker","year":"2003","unstructured":"Hofacker IL: Vienna RNA secondary structure server. Nucleic Acids Research 2003, 31: 3429\u20133431. 10.1093\/nar\/gkg599","journal-title":"Nucleic Acids Research"},{"key":"414_CR10","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","volume":"285","author":"E Rivas","year":"1999","unstructured":"Rivas E, Eddy SR: A dynamic programming algorithm for RNA structure prediction including pseudoknots. J Mol Biol 1999, 285: 2053\u20132068. 10.1006\/jmbi.1998.2436","journal-title":"J Mol Biol"},{"key":"414_CR11","first-page":"350","volume-title":"Pac Symp Biocomput","author":"B Gulko","year":"1996","unstructured":"Gulko B, Haussler D: Using multiple alignments and phylogenetic trees to detect RNA secondary structure. Pac Symp Biocomput 1996, 350\u2013367."},{"key":"414_CR12","first-page":"10","volume-title":"Proc Int Conf Intell Syst Mol Biol","author":"VR Akmaev","year":"1999","unstructured":"Akmaev VR, Kelley ST, Stormo GD: A phylogenetic approach to RNA structure prediction. Proc Int Conf Intell Syst Mol Biol 1999, 10\u201317."},{"key":"414_CR13","doi-asserted-by":"publisher","first-page":"3423","DOI":"10.1093\/nar\/gkg614","volume":"31","author":"B Knudsen","year":"2003","unstructured":"Knudsen B, Hein J: Pfold: RNA secondary structure predection using stochastic context-free grammars. Nucleic Acids Research 2003, 31: 3423\u20133428. 10.1093\/nar\/gkg614","journal-title":"Nucleic Acids Research"},{"key":"414_CR14","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1016\/S0022-2836(02)00308-X","volume":"319","author":"IL Hofacker","year":"2002","unstructured":"Hofacker IL, Fekete M, Stadler PF: Secondary structure prediction for aligned RNA sequences. Journal of Molecular Biology 2002, 319: 1059\u20131066. 10.1016\/S0022-2836(02)00308-X","journal-title":"Journal of Molecular Biology"},{"key":"414_CR15","doi-asserted-by":"publisher","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","volume":"85","author":"WR Pearson","year":"1988","unstructured":"Pearson WR, Lipman DJ: Improved tools for biological sequence comparison. Proc Natl Acad Sci USA 1988, 85: 2444\u20132448.","journal-title":"Proc Natl Acad Sci USA"},{"key":"414_CR16","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ: Basic local alignment search tool. Journal of Molecular Biology 1990, 215: 403\u2013410. 10.1006\/jmbi.1990.9999","journal-title":"Journal of Molecular Biology"},{"key":"414_CR17","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D Sankoff","year":"1985","unstructured":"Sankoff D: Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J Appl Math 1985, 45: 810\u2013825. 10.1137\/0145048","journal-title":"SIAM J Appl Math"},{"key":"414_CR18","doi-asserted-by":"publisher","first-page":"2135","DOI":"10.1093\/nar\/29.10.2135","volume":"29","author":"J Gorodkin","year":"2001","unstructured":"Gorodkin J, Stricklin SL, Stormo GD: Discovering common stem-loop motifs in unaligned RNA sequences. Nucleic Acids Research 2001, 29: 2135\u20132144. 10.1093\/nar\/29.10.2135","journal-title":"Nucleic Acids Research"},{"key":"414_CR19","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jmbi.2001.5351","volume":"317","author":"DH Mathews","year":"2002","unstructured":"Mathews DH, Turner DH: Dyalign: an algorithm for finding the secondary structure common to two RNA sequences. Journal of Molecular Biology 2002, 317: 191\u2013203. 10.1006\/jmbi.2001.5351","journal-title":"Journal of Molecular Biology"},{"key":"414_CR20","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1093\/bioinformatics\/19.1.108","volume":"19","author":"O Perriquet","year":"2003","unstructured":"Perriquet O, Touzet H, Dauchet M: Finding the common structure shared by two homologous RNAs. Bioinformatics 2003, 19: 108\u2013118. 10.1093\/bioinformatics\/19.1.108","journal-title":"Bioinformatics"},{"key":"414_CR21","doi-asserted-by":"publisher","first-page":"1591","DOI":"10.1093\/bioinformatics\/bth131","volume":"20","author":"Y Ji","year":"2004","unstructured":"Ji Y, Xu X, Stormo GD: A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics 2004, 20: 1591\u20131602. 10.1093\/bioinformatics\/bth131","journal-title":"Bioinformatics"},{"key":"414_CR22","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1093\/nar\/25.22.4570","volume":"25","author":"C Notredame","year":"1997","unstructured":"Notredame C, O'Brien EA, Higgins DG: RAGA: RNA sequence alignment by genetic algorithm. Nucleic Acids Research 1997, 25: 4570\u20134580. 10.1093\/nar\/25.22.4570","journal-title":"Nucleic Acids Research"},{"key":"414_CR23","first-page":"259","volume":"12","author":"J Kim","year":"1996","unstructured":"Kim J, Cole JR, Pramanik S: Alignment of possible secondary structures in multiple RNA sequences using simulated annealing. Comput Appl Biosci 1996, 12: 259\u2013267.","journal-title":"Comput Appl Biosci"},{"key":"414_CR24","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1093\/nar\/28.4.991","volume":"28","author":"JH Chen","year":"2000","unstructured":"Chen JH, Le SY, Maizel JV: Prediction of common secondary structures of RNAs: a genetic algorithm approach. Nucleic Acids Research 2000, 28: 991\u2013999. 10.1093\/nar\/28.4.991","journal-title":"Nucleic Acids Research"},{"key":"414_CR25","first-page":"309","volume":"6","author":"BA Shapiro","year":"1990","unstructured":"Shapiro BA, Zhang K: Comparing multiple RNA secondary structures using tree comparisons. Comput Appl Biosci 1990, 6: 309\u2013318.","journal-title":"Comput Appl Biosci"},{"key":"414_CR26","first-page":"211","volume-title":"Edit distance between two RNA structures: ; Montreal, Canada.","author":"GH Lin","year":"2001","unstructured":"Lin GH, Ma B, Zhang K: Edit distance between two RNA structures: ; Montreal, Canada. ; 2001:211\u2013220."},{"key":"414_CR27","first-page":"159","volume-title":"Local similarity in RNA secondary structures","author":"M Hochsmann","year":"2003","unstructured":"Hochsmann M, Toller T, Giegerich R, Kurtz S: Local similarity in RNA secondary structures: ; Stanford, California. IEEE; 2003:159\u2013168."},{"key":"414_CR28","doi-asserted-by":"publisher","first-page":"5112","DOI":"10.1093\/nar\/22.23.5112","volume":"22","author":"Y Sakakibara","year":"1994","unstructured":"Sakakibara Y, Brown M, Hughey R, Mian IS, Sjolander K, Underwood RC, Haussler D: Stochastic context-free grammars for tRNA modeling. Nucleic Acids Research 1994, 22: 5112\u20135120.","journal-title":"Nucleic Acids Research"},{"key":"414_CR29","doi-asserted-by":"publisher","first-page":"2079","DOI":"10.1093\/nar\/22.11.2079","volume":"22","author":"SR Eddy","year":"1994","unstructured":"Eddy SR, Durbin R: RNA sequence analysis using covariance models. Nucleic Acids Research 1994, 22: 2079\u20132088.","journal-title":"Nucleic Acids Research"},{"key":"414_CR30","doi-asserted-by":"publisher","first-page":"1168","DOI":"10.1126\/science.283.5405.1168","volume":"283","author":"T Lowe","year":"1999","unstructured":"Lowe T, Eddy SR: A computational screen for methylation guide snoRNAs in yeast. Science 1999, 283: 1168\u20131171. 10.1126\/science.283.5405.1168","journal-title":"Science"},{"key":"414_CR31","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1186\/1471-2105-4-44","volume":"4","author":"RJ Klein","year":"2003","unstructured":"Klein RJ, Eddy SR: RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics 2003, 4: 44. 10.1186\/1471-2105-4-44","journal-title":"BMC Bioinformatics"},{"key":"414_CR32","first-page":"163","volume-title":"Pac Symp Biocomput","author":"I Holmes","year":"2002","unstructured":"Holmes I, Rubin GM: Pairwise RNA structure comparison with stochastic context-free grammars. Pac Symp Biocomput 2002, 163\u2013174."},{"key":"414_CR33","first-page":"211","volume":"10","author":"A Laferriere","year":"1994","unstructured":"Laferriere A, Gautheret D, Cedergren R: An RNA pattern matching program with enhanced performance and portability. Comput Appl Biosci 1994, 10: 211\u2013212.","journal-title":"Comput Appl Biosci"},{"key":"414_CR34","doi-asserted-by":"publisher","first-page":"4724","DOI":"10.1093\/nar\/29.22.4724","volume":"29","author":"TJ Macke","year":"2001","unstructured":"Macke TJ, Ecker DJ, Gutell RR, Gautheret D, Case DA, Sampath R: RNAMotif, an RNA secondary structure definition and search algorithm. Nucleic Acids Research 2001, 29: 4724\u20134735. 10.1093\/nar\/29.22.4724","journal-title":"Nucleic Acids Research"},{"key":"414_CR35","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1093\/bioinformatics\/16.5.439","volume":"16","author":"G Pesole","year":"2000","unstructured":"Pesole G, Liuni S, D'Souza M: PatSearch: a pattern matcher software that finds functional elements in nucleotide and protein sequences and assesses their statistical significance. Bioinformatics 2000, 16: 439\u2013450. 10.1093\/bioinformatics\/16.5.439","journal-title":"Bioinformatics"},{"key":"414_CR36","doi-asserted-by":"publisher","first-page":"7706","DOI":"10.1073\/pnas.86.20.7706","volume":"86","author":"JA Jaeger","year":"1989","unstructured":"Jaeger JA, Turner DH, Zuker M: Improved predictions of secondary structures for RNA. Proc Natl Acad Sci USA 1989, 86: 7706\u20137710.","journal-title":"Proc Natl Acad Sci USA"},{"key":"414_CR37","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1126\/science.2468181","volume":"244","author":"M Zuker","year":"1989","unstructured":"Zuker M: On finding all suboptimal foldings of an RNA molecule. Science 1989, 244: 48\u201352.","journal-title":"Science"},{"key":"414_CR38","unstructured":"PatSearch[http:\/\/www.ba.itb.cnr.it\/BIG\/PatSearch]"},{"key":"414_CR39","unstructured":"Stemloc Tutorial [http:\/\/dart.sourceforge.net\/stemloc]."},{"key":"414_CR40","unstructured":"Eddy lab :: Software[http:\/\/selab.wustl.edu\/research.html]"},{"key":"414_CR41","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1006\/jmbi.2001.5102","volume":"313","author":"D Gautheret","year":"2001","unstructured":"Gautheret D, Lambert A: Direct RNA motif definition and identification from multiple sequence alignments using secondary structure profiles. Journal of Molecular Biology 2001, 313: 1003\u20131011. 10.1006\/jmbi.2001.5102","journal-title":"Journal of Molecular Biology"},{"key":"414_CR42","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1016\/S0955-0674(02)00387-3","volume":"14","author":"WF Marzluff","year":"2002","unstructured":"Marzluff WF, Duronio RJ: Histone mRNA expression: multiple levels of cell cycle regulation and important developmental consequences. Curr Opin Cell Biol 2002, 14: 692\u2013699. 10.1016\/S0955-0674(02)00387-3","journal-title":"Curr Opin Cell Biol"},{"key":"414_CR43","doi-asserted-by":"publisher","first-page":"3608","DOI":"10.1093\/nar\/gkg548","volume":"31","author":"G Grillo","year":"2003","unstructured":"Grillo G, Licciulli F, Liuni S, Sbisa E, Pesole G: PatSearch: a program for the detection of patterns and structural motifs in nucleotide sequences. Nucleic Acids Research 2003, 31: 3608\u20133612. 10.1093\/nar\/gkg548","journal-title":"Nucleic Acids Research"},{"key":"414_CR44","doi-asserted-by":"publisher","first-page":"2707","DOI":"10.1093\/nar\/19.10.2707","volume":"19","author":"M Zuker","year":"1991","unstructured":"Zuker M, Jeager JA, Turner DH: A comparison of optimal and suboptimal RNA secondary structures predicted by free energy minimization with structures determined by phylogenetic comparison. Nucleic Acids Research 1991, 19: 2707\u20132714.","journal-title":"Nucleic Acids Research"},{"key":"414_CR45","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","volume":"288","author":"DH Mathews","year":"1999","unstructured":"Mathews DH, Sabina J, Zuker M, Turner DH: Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. Journal of Molecular Biology 1999, 288: 911\u2013940. 10.1006\/jmbi.1999.2700","journal-title":"Journal of Molecular Biology"},{"key":"414_CR46","doi-asserted-by":"publisher","first-page":"2264","DOI":"10.1073\/pnas.87.6.2264","volume":"87","author":"S Karlin","year":"1990","unstructured":"Karlin S, Altschul SF: Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proc Natl Acad Sci U S A 1990, 87: 2264\u20132268.","journal-title":"Proc Natl Acad Sci U S A"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-89.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-6-89\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-89.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:10:18Z","timestamp":1728303018000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-89"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4,7]]},"references-count":46,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["414"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-89","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,4,7]]},"assertion":[{"value":"4 December 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"89"}}