{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T22:18:29Z","timestamp":1761862709936},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>In recent years, RNA molecules that are not translated into proteins (ncRNAs) have drawn a great deal of attention, as they were shown to be involved in many cellular functions. One of the most important computational problems regarding ncRNA is to predict the secondary structure of a molecule from its sequence. In particular, we attempted to predict the secondary structure for a set of unaligned ncRNA molecules that are taken from the same family, and thus presumably have a similar structure.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We developed the RNAspa program, which comparatively predicts the secondary structure for a set of ncRNA molecules in linear time in the number of molecules. We observed that in a list of several hundred suboptimal minimal free energy (MFE) predictions, as provided by the RNAsubopt program of the Vienna package, it is likely that at least one suggested structure would be similar to the true, correct one. The suboptimal solutions of each molecule are represented as a layer of vertices in a graph. The shortest path in this graph is the basis for structural predictions for the molecule. We also show that RNA secondary structures can be compared very rapidly by a simple string Edit-Distance algorithm with a minimal loss of accuracy. We show that this approach allows us to more deeply explore the suboptimal structure space.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>The algorithm was tested on three datasets which include several ncRNA families taken from the Rfam database. These datasets allowed for comparison of the algorithm with other methods. In these tests, RNAspa performed better than four other programs.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-8-366","type":"journal-article","created":{"date-parts":[[2007,10,2]],"date-time":"2007-10-02T06:14:12Z","timestamp":1191305652000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["RNAspa: a shortest path approach for comparative prediction of the secondary structure of ncRNA molecules"],"prefix":"10.1186","volume":"8","author":[{"given":"Yair","family":"Horesh","sequence":"first","affiliation":[]},{"given":"Tirza","family":"Doniger","sequence":"additional","affiliation":[]},{"given":"Shulamit","family":"Michaeli","sequence":"additional","affiliation":[]},{"given":"Ron","family":"Unger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,1]]},"reference":[{"key":"1738_CR1","doi-asserted-by":"publisher","first-page":"1303","DOI":"10.1261\/rna.2380905","volume":"11","author":"ZP Huang","year":"2005","unstructured":"Huang ZP, Zhou H, He HL, Chen CL, Liang D, Qu LH: Genome-wide analyses of two families of snoRNA genes from Drosophila melanogaster, demonstrating the extensive utilization of introns for coding of snoRNAs. RNA 2005, 11: 1303\u20131316. 10.1261\/rna.2380905","journal-title":"RNA"},{"key":"1738_CR2","doi-asserted-by":"crossref","first-page":"3928","DOI":"10.1093\/nar\/29.19.3928","volume":"29","author":"RJ Carter","year":"2001","unstructured":"Carter RJ, Dubchak I, Holbrook SR: A computational approach to identify genes for functional RNAs in genomic sequences. Nucleic Acids Res 2001, 29: 3928\u20133938.","journal-title":"Nucleic Acids Res"},{"key":"1738_CR3","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0303-2647(02)00013-8","volume":"65","author":"S Chen","year":"2002","unstructured":"Chen S, Lesnik EA, Hall TA, Sampath R, Griffey RH, Ecker DJ, Blyn LB: A bioinformatics based approach to discover small RNA genes in the Escherichia coli genome. Biosystems 2002, 65: 157\u2013177. 10.1016\/S0303-2647(02)00013-8","journal-title":"Biosystems"},{"key":"1738_CR4","doi-asserted-by":"publisher","first-page":"3732","DOI":"10.1093\/nar\/gkf505","volume":"30","author":"B Tjaden","year":"2002","unstructured":"Tjaden B, Saxena RM, Stolyar S, Haynor DR, Kolker E, Rosenow C: Transcriptome analysis of Escherichia coli using high-density oligonucleotide probe arrays. Nucleic Acids Res 2002, 30: 3732\u20133738. 10.1093\/nar\/gkf505","journal-title":"Nucleic Acids Res"},{"key":"1738_CR5","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1007\/PL00000913","volume":"58","author":"VA Erdmann","year":"2001","unstructured":"Erdmann VA, Barciszewska MZ, Hochberg A, de Groot N, Barciszewski J: Regulatory RNAs. Cell Mol Life Sci 2001, 58: 960\u2013977. 10.1007\/PL00000913","journal-title":"Cell Mol Life Sci"},{"key":"1738_CR6","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0092-8674(02)00718-3","volume":"109","author":"T Kiss","year":"2002","unstructured":"Kiss T: Small nucleolar RNAs: an abundant group of noncoding RNAs with diverse cellular functions. Cell 2002, 109: 145\u2013148. 10.1016\/S0092-8674(02)00718-3","journal-title":"Cell"},{"key":"1738_CR7","doi-asserted-by":"publisher","first-page":"930","DOI":"10.1002\/bies.10332","volume":"25","author":"JS Mattick","year":"2003","unstructured":"Mattick JS: Challenging the dogma: the hidden layer of non-protein-coding RNAs in complex organisms. Bioessays 2003, 25: 930\u2013939. 10.1002\/bies.10332","journal-title":"Bioessays"},{"key":"1738_CR8","doi-asserted-by":"publisher","first-page":"R17","DOI":"10.1093\/hmg\/ddl046","volume":"15 Spec No 1","author":"JS Mattick","year":"2006","unstructured":"Mattick JS, Makunin IV: Non-coding RNA. Hum Mol Genet 2006, 15 Spec No 1: R17-R29. 10.1093\/hmg\/ddl046","journal-title":"Hum Mol Genet"},{"key":"1738_CR9","doi-asserted-by":"publisher","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","volume":"20","author":"IL Hofacker","year":"2004","unstructured":"Hofacker IL, Bernhart SH, Stadler PF: Alignment of RNA base pairing probability matrices. Bioinformatics 2004, 20: 2222\u20132227. 10.1093\/bioinformatics\/bth229","journal-title":"Bioinformatics"},{"key":"1738_CR10","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1093\/bioinformatics\/16.7.583","volume":"16","author":"E Rivas","year":"2000","unstructured":"Rivas E, Eddy SR: Secondary structure alone is generally not statistically significant for the detection of noncoding RNAs. Bioinformatics 2000, 16: 583\u2013605. 10.1093\/bioinformatics\/16.7.583","journal-title":"Bioinformatics"},{"key":"1738_CR11","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1261\/rna.7174805","volume":"11","author":"XH Liang","year":"2005","unstructured":"Liang XH, Uliel S, Hury A, Barth S, Doniger T, Unger R, Michaeli S: A genome-wide analysis of C\/D and H\/ACA-like small nucleolar RNAs in Trypanosoma brucei reveals a trypanosome-specific pattern of rRNA modification. RNA 2005, 11: 619\u2013645. 10.1261\/rna.7174805","journal-title":"RNA"},{"key":"1738_CR12","doi-asserted-by":"publisher","first-page":"2454","DOI":"10.1073\/pnas.0409169102","volume":"102","author":"S Washietl","year":"2005","unstructured":"Washietl S, Hofacker IL, Stadler PF: Fast and reliable prediction of noncoding RNAs. Proc Natl Acad Sci U S A 2005, 102: 2454\u20132459. 10.1073\/pnas.0409169102","journal-title":"Proc Natl Acad Sci U S A"},{"key":"1738_CR13","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. J Mol Biol 1999, 288: 911\u2013940. 10.1006\/jmbi.1999.2700","journal-title":"J Mol Biol"},{"key":"1738_CR14","doi-asserted-by":"publisher","first-page":"3406","DOI":"10.1093\/nar\/gkg595","volume":"31","author":"M Zuker","year":"2003","unstructured":"Zuker M: Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res 2003, 31: 3406\u20133415. 10.1093\/nar\/gkg595","journal-title":"Nucleic Acids Res"},{"key":"1738_CR15","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 Res 2003, 31: 3429\u20133431. 10.1093\/nar\/gkg599","journal-title":"Nucleic Acids Res"},{"key":"1738_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00818163","volume":"125","author":"IL Hofacker","year":"1994","unstructured":"Hofacker IL, Fontana W, Stadler PF, Bonhoeffer S, Tacker M, Schuster P: Fast folding and comparison of RNA secondary structures. Monatshefte f Chemie 1994, 125: 167\u2013188. 10.1007\/BF00818163","journal-title":"Monatshefte f Chemie"},{"key":"1738_CR17","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zuker","year":"1981","unstructured":"Zuker M, Stiegler P: Optimal Computer Folding of Large Rna Sequences Using Thermodynamics and Auxiliary Information. Nucleic Acids Research 1981, 9: 133\u2013148. 10.1093\/nar\/9.1.133","journal-title":"Nucleic Acids Research"},{"key":"1738_CR18","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0135006","volume":"35","author":"R Nussinov","year":"1978","unstructured":"Nussinov R, Pieczenik G, Griggs JR, Kleitman DJ: Algorithms for Loop Matchings. Siam Journal on Applied Mathematics 1978, 35: 68\u201382. 10.1137\/0135006","journal-title":"Siam Journal on Applied Mathematics"},{"key":"1738_CR19","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/0076-6879(95)59047-1","volume":"259","author":"MJ Serra","year":"1995","unstructured":"Serra MJ, Turner DH: Predicting thermodynamic properties of RNA. Methods Enzymol 1995, 259: 242\u2013261.","journal-title":"Methods Enzymol"},{"key":"1738_CR20","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.jbiotec.2006.01.034","volume":"124","author":"J Reeder","year":"2006","unstructured":"Reeder J, Hochsmann M, Rehmsmeier M, Voss B, Giegerich R: Beyond Mfold: recent advances in RNA bioinformatics. J Biotechnol 2006, 124: 41\u201355. 10.1016\/j.jbiotec.2006.01.034","journal-title":"J Biotechnol"},{"key":"1738_CR21","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","volume":"49","author":"S Wuchty","year":"1999","unstructured":"Wuchty S, Fontana W, Hofacker IL, Schuster P: Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers 1999, 49: 145\u2013165. 10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","journal-title":"Biopolymers"},{"key":"1738_CR22","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. J Mol Biol 2002, 319: 1059\u20131066. 10.1016\/S0022-2836(02)00308-X","journal-title":"J Mol Biol"},{"key":"1738_CR23","doi-asserted-by":"publisher","first-page":"1323","DOI":"10.1261\/rna.5168504","volume":"10","author":"R Knight","year":"2004","unstructured":"Knight R, Birmingham A, Yarus M: BayesFold: rational 2 degrees folds that combine thermodynamic, covariation, and chemical data for aligned RNA sequences. RNA 2004, 10: 1323\u20131336. 10.1261\/rna.5168504","journal-title":"RNA"},{"key":"1738_CR24","doi-asserted-by":"publisher","first-page":"4208","DOI":"10.1093\/nar\/27.21.4208","volume":"27","author":"R Luck","year":"1999","unstructured":"Luck R, Graf S, Steger G: ConStruct: a tool for thermodynamic controlled prediction of conserved secondary structure. Nucleic Acids Res 1999, 27: 4208\u20134217. 10.1093\/nar\/27.21.4208","journal-title":"Nucleic Acids Res"},{"key":"1738_CR25","doi-asserted-by":"publisher","first-page":"5471","DOI":"10.1093\/nar\/gkl692","volume":"34","author":"B Voss","year":"2006","unstructured":"Voss B: Structural analysis of aligned RNAs. Nucleic Acids Res 2006, 34: 5471\u20135481. 10.1093\/nar\/gkl692","journal-title":"Nucleic Acids Res"},{"key":"1738_CR26","doi-asserted-by":"publisher","first-page":"3352","DOI":"10.1093\/bioinformatics\/bti550","volume":"21","author":"S Siebert","year":"2005","unstructured":"Siebert S, Backofen R: MARNA: multiple alignment and consensus structure prediction of RNAs based on sequence structure comparisons. Bioinformatics 2005, 21: 3352\u20133359. 10.1093\/bioinformatics\/bti550","journal-title":"Bioinformatics"},{"key":"1738_CR27","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/TCBB.2004.11","volume":"1","author":"M Hochsmann","year":"2004","unstructured":"Hochsmann M, Voss B, Giegerich R: Pure multiple RNA secondary structure alignments: a progressive profile approach. IEEE\/ACM Trans Comput Biol Bioinform 2004, 1: 53\u201362. 10.1109\/TCBB.2004.11","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"1738_CR28","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: Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. J Mol Biol 2002, 317: 191\u2013203. 10.1006\/jmbi.2001.5351","journal-title":"J Mol Biol"},{"key":"1738_CR29","doi-asserted-by":"publisher","first-page":"1723","DOI":"10.1093\/bioinformatics\/btl177","volume":"22","author":"Y Tabei","year":"2006","unstructured":"Tabei Y, Tsuda K, Kin T, Asai K: SCARNA: fast and accurate structural alignment of RNA sequences by matching fixed-length stem fragments. Bioinformatics 2006, 22: 1723\u20131729. 10.1093\/bioinformatics\/btl177","journal-title":"Bioinformatics"},{"key":"1738_CR30","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 Res 2000, 28: 991\u2013999. 10.1093\/nar\/28.4.991","journal-title":"Nucleic Acids Res"},{"key":"1738_CR31","doi-asserted-by":"publisher","first-page":"2480","DOI":"10.1093\/bioinformatics\/btl431","volume":"22","author":"M Hamada","year":"2006","unstructured":"Hamada M, Tsuda K, Kudo T, Kin T, Asai K: Mining frequent stem patterns from unaligned RNA sequences. Bioinformatics 2006, 22: 2480\u20132487. 10.1093\/bioinformatics\/btl431","journal-title":"Bioinformatics"},{"key":"1738_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":"1738_CR33","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 Journal on Applied Mathematics 1985, 45: 810\u2013825. 10.1137\/0145048","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"1738_CR34","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1186\/1471-2105-5-140","volume":"5","author":"PP Gardner","year":"2004","unstructured":"Gardner PP, Giegerich R: A comprehensive comparison of comparative RNA structure prediction approaches. BMC Bioinformatics 2004, 5: 140. 10.1186\/1471-2105-5-140","journal-title":"BMC Bioinformatics"},{"key":"1738_CR35","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1186\/1471-2105-6-73","volume":"6","author":"I Holmes","year":"2005","unstructured":"Holmes I: Accelerated probabilistic inference of RNA structure evolution. BMC Bioinformatics 2005, 6: 73. 10.1186\/1471-2105-6-73","journal-title":"BMC Bioinformatics"},{"key":"1738_CR36","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1002\/bip.360290621","volume":"29","author":"JS McCaskill","year":"1990","unstructured":"McCaskill JS: The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers 1990, 29: 1105\u20131119. 10.1002\/bip.360290621","journal-title":"Biopolymers"},{"key":"1738_CR37","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1093\/bioinformatics\/btm049","volume":"23","author":"E Torarinsson","year":"2007","unstructured":"Torarinsson E, Havgaard JH, Gorodkin J: Multiple structural alignment and clustering of RNA sequences. Bioinformatics 2007, 23: 926\u2013932. 10.1093\/bioinformatics\/btm049","journal-title":"Bioinformatics"},{"key":"1738_CR38","doi-asserted-by":"publisher","first-page":"3516","DOI":"10.1093\/bioinformatics\/bti577","volume":"21","author":"J Reeder","year":"2005","unstructured":"Reeder J, Giegerich R: Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction. Bioinformatics 2005, 21: 3516\u20133523. 10.1093\/bioinformatics\/bti577","journal-title":"Bioinformatics"},{"key":"1738_CR39","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1093\/bioinformatics\/btk010","volume":"22","author":"P Steffen","year":"2006","unstructured":"Steffen P, Voss B, Rehmsmeier M, Reeder J, Giegerich R: RNAshapes: an integrated RNA analysis package based on abstract shapes. Bioinformatics 2006, 22: 500\u2013503. 10.1093\/bioinformatics\/btk010","journal-title":"Bioinformatics"},{"key":"1738_CR40","doi-asserted-by":"publisher","first-page":"2433","DOI":"10.1093\/nar\/gki541","volume":"33","author":"PP Gardner","year":"2005","unstructured":"Gardner PP, Wilm A, Washietl S: A benchmark of multiple sequence alignment programs upon structural RNAs. Nucleic Acids Res 2005, 33: 2433\u20132439. 10.1093\/nar\/gki541","journal-title":"Nucleic Acids Res"},{"key":"1738_CR41","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1186\/1748-7188-1-19","volume":"1","author":"A Wilm","year":"2006","unstructured":"Wilm A, Mainz I, Steger G: An enhanced RNA alignment benchmark for sequence alignment programs. Algorithms Mol Biol 2006, 1: 19. 10.1186\/1748-7188-1-19","journal-title":"Algorithms Mol Biol"},{"key":"1738_CR42","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1261\/rna.2164906","volume":"12","author":"E Bindewald","year":"2006","unstructured":"Bindewald E, Shapiro BA: RNA secondary structure prediction from sequence alignments using a network of k-nearest neighbor classifiers. RNA 2006, 12: 342\u2013352. 10.1261\/rna.2164906","journal-title":"RNA"},{"key":"1738_CR43","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 1970, 48: 443\u2013453. 10.1016\/0022-2836(70)90057-4","journal-title":"J Mol Biol"},{"key":"1738_CR44","doi-asserted-by":"publisher","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","volume":"3","author":"S Will","year":"2007","unstructured":"Will S, Reiche K, Hofacker IL, Stadler PF, Backofen R: Inferring Noncoding RNA Families and Classes by Means of Genome-Scale Structure-Based Clustering. PLoS Comput Biol 2007, 3: e65. 10.1371\/journal.pcbi.0030065","journal-title":"PLoS Comput Biol"},{"key":"1738_CR45","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":"1738_CR46","unstructured":"RNA families database of alignments and CMs2007. [http:\/\/www.sanger.ac.uk\/Software\/Rfam\/]"},{"key":"1738_CR47","unstructured":"Gutell Lab CRW Site2007. [http:\/\/www.rna.ccbb.utexas.edu\/]"},{"key":"1738_CR48","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological SequenceAnalysis: Probabilistic Models of Proteins and Nucleic Acids","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy S, Krogh A, Mitchison G: Biological SequenceAnalysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge, UK., University Press; 1998."},{"key":"1738_CR49","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 Res 1994, 22: 2079\u20132088. 10.1093\/nar\/22.11.2079","journal-title":"Nucleic Acids Res"},{"key":"1738_CR50","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/1471-2105-3-18","volume":"3","author":"SR Eddy","year":"2002","unstructured":"Eddy SR: A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure. BMC Bioinformatics 2002, 3: 18. 10.1186\/1471-2105-3-18","journal-title":"BMC Bioinformatics"},{"key":"1738_CR51","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 Res 2001, 29: 2135\u20132144. 10.1093\/nar\/29.10.2135","journal-title":"Nucleic Acids Res"},{"key":"1738_CR52","doi-asserted-by":"publisher","first-page":"3886","DOI":"10.1093\/nar\/gkf485","volume":"30","author":"YJ Hu","year":"2002","unstructured":"Hu YJ: Prediction of consensus structural motifs in a family of coregulated RNA sequences. Nucleic Acids Res 2002, 30: 3886\u20133893. 10.1093\/nar\/gkf485","journal-title":"Nucleic Acids Res"},{"key":"1738_CR53","volume-title":"The Tree Alignment Model: Algorithms, Implementations and Applications for the Analysis of RNA Secondary Structures","author":"H M","year":"2005","unstructured":"M H: The Tree Alignment Model: Algorithms, Implementations and Applications for the Analysis of RNA Secondary Structures. International NRW Graduate School in Bioinformatics and Genome Research -- Center for Biotechnology (CeBiTec); 2005."},{"key":"1738_CR54","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. 10.1126\/science.2468181","journal-title":"Science"},{"key":"1738_CR55","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/322139.322143","volume":"26","author":"KC Tai","year":"1979","unstructured":"Tai KC: Tree-To-Tree Correction Problem. Journal of the Acm 1979, 26: 422\u2013433. 10.1145\/322139.322143","journal-title":"Journal of the Acm"},{"key":"1738_CR56","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"KZ Zhang","year":"1989","unstructured":"Zhang KZ, Shasha D: Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems. Siam Journal on Computing 1989, 18: 1245\u20131262. 10.1137\/0218082","journal-title":"Siam Journal on Computing"},{"key":"1738_CR57","volume-title":"Arxiv preprint cs DS\/0604037","author":"ED Demaine","year":"2006","unstructured":"Demaine ED, Mozes S, Rossman B, Weimann B: An O(n3)-time algorithm for tree edit distance. Arxiv preprint cs DS\/0604037 2006."},{"key":"1738_CR58","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/S0377-2217(99)00262-3","volume":"123","author":"EM Macambira","year":"2000","unstructured":"Macambira EM, de Souza CC: The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations. European Journal of Operational Research 2000, 123: 346\u2013371. 10.1016\/S0377-2217(99)00262-3","journal-title":"European Journal of Operational Research"},{"key":"1738_CR59","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.cell.2006.06.024","volume":"126","author":"E Nudler","year":"2006","unstructured":"Nudler E: Flipping riboswitches. Cell 2006, 126: 19\u201322. 10.1016\/j.cell.2006.06.024","journal-title":"Cell"},{"key":"1738_CR60","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/S0959-440X(96)80054-6","volume":"6","author":"M Vingron","year":"1996","unstructured":"Vingron M: Near-optimal sequence alignment. Curr Opin Struct Biol 1996, 6: 346\u2013352. 10.1016\/S0959-440X(96)80054-6","journal-title":"Curr Opin Struct Biol"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-8-366.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T01:52:37Z","timestamp":1630461157000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-8-366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,1]]},"references-count":60,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["1738"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-8-366","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,1]]},"assertion":[{"value":"7 June 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"366"}}