{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T06:58:36Z","timestamp":1791269916564,"version":"4.1.0"},"reference-count":55,"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":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>The secondary structure of RNA molecules is intimately related to their function and often more conserved than the sequence. Hence, the important task of searching databases for RNAs requires to match sequence-structure patterns. Unfortunately, current tools for this task have, in the best case, a running time that is only linear in the size of sequence databases. Furthermore, established index data structures for fast sequence matching, like suffix trees or arrays, cannot benefit from the complementarity constraints introduced by the secondary structure of RNAs.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We present a novel method and readily applicable software for time efficient matching of RNA sequence-structure patterns in sequence databases. Our approach is based on affix arrays, a recently introduced index data structure, preprocessed from the target database. Affix arrays support bidirectional pattern search, which is required for efficiently handling the structural constraints of the pattern. Structural patterns like stem-loops can be matched inside out, such that the loop region is matched first and then the pairing bases on the boundaries are matched consecutively. This allows to exploit base pairing information for search space reduction and leads to an expected running time that is sublinear in the size of the sequence database. The incorporation of a new chaining approach in the search of RNA sequence-structure patterns enables the description of molecules folding into complex secondary structures with multiple ordered patterns. The chaining approach removes spurious matches from the set of intermediate results, in particular of patterns with little specificity. In benchmark experiments on the Rfam database, our method runs up to two orders of magnitude faster than previous methods.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>The presented method's sublinear expected running time makes it well suited for RNA sequence-structure pattern matching in large sequence databases. RNA molecules containing several stem-loop substructures can be described by multiple sequence-structure patterns and their matches are efficiently handled by a novel chaining method. Beyond our algorithmic contributions, we provide with <jats:italic>Structator<\/jats:italic> a complete and robust open-source software solution for index-based search of RNA sequence-structure patterns. The <jats:italic>Structator<\/jats:italic> software is available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/www.zbh.uni-hamburg.de\/Structator\" ext-link-type=\"uri\">http:\/\/www.zbh.uni-hamburg.de\/Structator<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-12-214","type":"journal-article","created":{"date-parts":[[2011,5,28]],"date-time":"2011-05-28T06:21:15Z","timestamp":1306563675000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Structator: fast index-based search for RNA sequence-structure patterns"],"prefix":"10.1186","volume":"12","author":[{"given":"Fernando","family":"Meyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Kurtz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Beckstette","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2011,5,27]]},"reference":[{"issue":"4","key":"4708_CR1","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1038\/nrg1321","volume":"5","author":"J Mattick","year":"2004","unstructured":"Mattick J: RNA regulation: a new genetics? Nat Rev Genet 2004, 5(4):316\u2013323. 10.1038\/nrg1321","journal-title":"Nat Rev Genet"},{"key":"4708_CR2","volume-title":"Trends Genet","author":"J Mattick","year":"2009","unstructured":"Mattick J, Taft R, Faulkner G: A global view of genomic information - moving beyond the gene and the master regulator. Trends Genet 2009."},{"key":"4708_CR3","volume-title":"Nucl. Acids Res","author":"P Gardner","year":"2010","unstructured":"Gardner P, Daub J, Tate J, Moore B, Osuch I, Griffiths-Jones S, Finn R, Nawrocki E, Kolbe D, Eddy S, Bateman A: Rfam: Wikipedia, clans and the \"decimal\" release. Nucl. Acids Res 2010."},{"key":"4708_CR4","doi-asserted-by":"publisher","first-page":"D136","DOI":"10.1093\/nar\/gkn766","volume":"37","author":"P Gardner","year":"2008","unstructured":"Gardner P, Daub J, Tate J, Nawrocji E, Kolbe D, Lindgreen S, Wilkinson A, Finn R, Griffith-Jones S, Eddy S, Bateman A: Rfam: updates to the RNA families database. Nucl. Acids Res 2008, 37: D136-D140.","journal-title":"Nucl. Acids Res"},{"issue":"8","key":"4708_CR5","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. Nucl. Acids Res 2005, 33(8):2433\u20139. 10.1093\/nar\/gki541","journal-title":"Nucl. Acids Res"},{"key":"4708_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/TCBB.2004.11","volume":"1","author":"M H\u00f6chsmann","year":"2004","unstructured":"H\u00f6chsmann 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"},{"issue":"16","key":"4708_CR7","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(16):3352\u20133359. 10.1093\/bioinformatics\/bti550","journal-title":"Bioinformatics"},{"key":"4708_CR8","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 problem. SIAM Journal on Applied Mathematics 1985, 45: 810\u2013825. 10.1137\/0145048","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"18","key":"4708_CR9","doi-asserted-by":"publisher","first-page":"3724","DOI":"10.1093\/nar\/25.18.3724","volume":"25","author":"J Gorodkin","year":"1997","unstructured":"Gorodkin J, Heyer LJ, Stormo GD: Finding the most significant common sequence and structure motifs in a set of RNA sequences. Nucl. Acids Res 1997, 25(18):3724\u201332. 10.1093\/nar\/25.18.3724","journal-title":"Nucl. Acids Res"},{"key":"4708_CR10","doi-asserted-by":"publisher","first-page":"1815","DOI":"10.1093\/bioinformatics\/bti279","volume":"21","author":"J Havgaard","year":"2005","unstructured":"Havgaard J, Lyngso R, Stormo G, Gorodkin J: Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%. Bioinformatics 2005, 21: 1815\u20131824. 10.1093\/bioinformatics\/bti279","journal-title":"Bioinformatics"},{"issue":"2","key":"4708_CR11","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. Journal of Molecular Biology 2002, 317(2):191\u2013203. 10.1006\/jmbi.2001.5351","journal-title":"Journal of Molecular Biology"},{"issue":"4","key":"4708_CR12","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(4):e65. 10.1371\/journal.pcbi.0030065","journal-title":"PLoS Comput. Biol"},{"issue":"22","key":"4708_CR13","doi-asserted-by":"publisher","first-page":"4724","DOI":"10.1093\/nar\/29.22.4724","volume":"29","author":"T Macke","year":"2001","unstructured":"Macke T, Ecker D, Gutell R, Gautheret D, Case D, Sampath R: RNAMotif - A new RNA secondary structure definition and discovery algorithm. Nucl. Acids Res 2001, 29(22):4724\u20134735. 10.1093\/nar\/29.22.4724","journal-title":"Nucl. Acids Res"},{"issue":"4","key":"4708_CR14","first-page":"325","volume":"6","author":"D Gautheret","year":"1990","unstructured":"Gautheret D, Major F, Cedergren R: Pattern searching\/alignment with RNA primary and secondary structures: an effective descriptor for tRNA. Comput Appl Biosci 1990, 6(4):325\u201331.","journal-title":"Comput Appl Biosci"},{"key":"4708_CR15","unstructured":"RNABOB: a program to search for RNA secondary structure motifs in sequence databases[http:\/\/selab.janelia.org\/software.html]"},{"key":"4708_CR16","doi-asserted-by":"publisher","first-page":"W423","DOI":"10.1093\/nar\/gkl231","volume":"34","author":"T Chang","year":"2006","unstructured":"Chang T, Huang H, Chuang T, Shien D, Horng J: RNAMST: efficient and flexible approach for identifying RNA structural homologs. Nucl. Acids Res 2006, 34: W423-W428. 10.1093\/nar\/gkl231","journal-title":"Nucl. Acids Res"},{"issue":"12","key":"4708_CR17","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/S0168-9525(97)01347-4","volume":"13","author":"M Dsouza","year":"1997","unstructured":"Dsouza M, Larsen N, Overbeek R: Searching for patterns in genomic data. Trends Genet 1997, 13(12):497\u20138.","journal-title":"Trends Genet"},{"issue":"13","key":"4708_CR18","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, Sbis\u00e0 E, Pesole G: PatSearch: A program for the detection of patterns and structural motifs in nucleotide sequences. Nucl. Acids Res 2003, 31(13):3608\u201312. 10.1093\/nar\/gkg548","journal-title":"Nucl. Acids Res"},{"key":"4708_CR19","doi-asserted-by":"crossref","unstructured":"Nawrocki E, Eddy S: Query-dependent banding (QDB) for faster RNA similarity searches. PLoS Comput. Biol 2007., 3(56):","DOI":"10.1371\/journal.pcbi.0030056"},{"key":"4708_CR20","doi-asserted-by":"publisher","first-page":"1335","DOI":"10.1093\/bioinformatics\/btp157","volume":"25","author":"E Nawrocki","year":"2009","unstructured":"Nawrocki E, Kolbe D, Eddy S: Infernal 1.0: inference of RNA alignments. BMC Bioinformatics 2009, 25: 1335\u20131337.","journal-title":"BMC Bioinformatics"},{"key":"4708_CR21","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1186\/1471-2105-4-44","volume":"4","author":"R Klein","year":"2003","unstructured":"Klein R, Eddy S: RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics 2003, 4: 44. 10.1186\/1471-2105-4-44","journal-title":"BMC Bioinformatics"},{"key":"4708_CR22","doi-asserted-by":"publisher","first-page":"i232","DOI":"10.1093\/bioinformatics\/btg1032","volume":"19","author":"Y Sakakibara","year":"2003","unstructured":"Sakakibara Y: Pair hidden markov models on tree structures. BMC Bioinformatics 2003, 19: i232\u201340.","journal-title":"BMC Bioinformatics"},{"key":"4708_CR23","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. J Mol Biol 2001, 313: 1003\u201311. 10.1006\/jmbi.2001.5102","journal-title":"J Mol Biol"},{"key":"4708_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences: computer science and computational biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge Univ. Press; 1997."},{"issue":"5","key":"4708_CR25","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber U, Myers E: Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing 1993, 22(5):935\u2013948. 10.1137\/0222058","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"4708_CR26","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina P, Manzini G: Indexing compressed text. Journal of the ACM 2005, 52(4):552\u2013581. 10.1145\/1082036.1082039","journal-title":"Journal of the ACM"},{"issue":"1-2","key":"4708_CR27","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.tcs.2007.09.029","volume":"389","author":"D Strothmann","year":"2007","unstructured":"Strothmann D: The affix array data structure and its applications to RNA secondary structure analysis. Theor. Comput. Sci 2007, 389(1\u20132):278\u2013294.","journal-title":"Theor. Comput. Sci"},{"key":"4708_CR28","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.tcs.2004.12.015","volume":"335","author":"G Mauri","year":"2005","unstructured":"Mauri G, Pavesi G: Algorithms for pattern matching and discovery in RNA secondary structure. Theor. Comput. Sci 2005, 335: 29\u201351. 10.1016\/j.tcs.2004.12.015","journal-title":"Theor. Comput. Sci"},{"key":"4708_CR29","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00453-003-1029-2","volume":"37","author":"MG Maa\u00df","year":"2003","unstructured":"Maa\u00df MG: Linear bidirectional on-line construction of affix trees. Algorithmica 2003, 37: 43\u201374. 10.1007\/s00453-003-1029-2","journal-title":"Algorithmica"},{"key":"4708_CR30","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-44888-8_21","volume-title":"Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching","author":"G Mauri","year":"2003","unstructured":"Mauri G, Pavesi G: Pattern discovery in RNA secondary structures using affix trees. In Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching. Volume 2676. Springer; 2003:278\u2013294. 10.1007\/3-540-44888-8_21"},{"key":"4708_CR31","volume-title":"Proceedings of the 13th International Conference on Automata, Languges and Programming","author":"J K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen J, Sanders P: Simple linear work suffix array construction. In Proceedings of the 13th International Conference on Automata, Languges and Programming. Springer; 2003."},{"key":"4708_CR32","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1109\/DCC.2005.87","volume-title":"DCC '05: Proceedings of the Data Compression Conference","author":"SJ Puglisi","year":"2005","unstructured":"Puglisi SJ, Smyth W, Turpin A: The performance of linear time suffix sorting algorithms. In DCC '05: Proceedings of the Data Compression Conference. Washington, DC, USA: IEEE Computer Society; 2005:358\u2013367."},{"key":"4708_CR33","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s00453-004-1094-1","volume":"40","author":"G Manzini","year":"2004","unstructured":"Manzini G, Ferragina P: Engineering a lightweight suffix array construction algorithm. Algorithmica 2004, 40: 33\u201350. 10.1007\/s00453-004-1094-1","journal-title":"Algorithmica"},{"key":"4708_CR34","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"M Abouelhoda","year":"2004","unstructured":"Abouelhoda M, Kurtz S, Ohlebusch E: Replacing suffix trees with enhanced suffix arrays. Journal of Discrete Algorithms 2004, 2: 53\u201386. 10.1016\/S1570-8667(03)00065-0","journal-title":"Journal of Discrete Algorithms"},{"issue":"8-9","key":"4708_CR35","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/j.ipl.2010.02.010","volume":"110","author":"J Fischer","year":"2010","unstructured":"Fischer J: Wee LCP. Information Processing Letters 2010, 110(8\u20139):317\u2013320. 10.1016\/j.ipl.2010.02.010","journal-title":"Information Processing Letters"},{"key":"4708_CR36","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching","author":"T Kasai","year":"2001","unstructured":"Kasai T, Lee G, Arimura H, Arikawa S, Park K: Linear-time longest-common-prefix computation in suffix arrays and its applications. Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching 2001, 181\u2013192."},{"key":"4708_CR37","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1186\/1471-2105-7-389","volume":"7","author":"M Beckstette","year":"2006","unstructured":"Beckstette M, Homann R, Giegerich R, Kurtz S: Fast index based algorithms and software for matching position specific scoring matrices. BMC Bioinformatics 2006, 7: 389. 10.1186\/1471-2105-7-389","journal-title":"BMC Bioinformatics"},{"issue":"24","key":"4708_CR38","doi-asserted-by":"publisher","first-page":"3251","DOI":"10.1093\/bioinformatics\/btp593","volume":"25","author":"M Beckstette","year":"2009","unstructured":"Beckstette M, Homann R, Giegerich R, Kurtz S: Significant speedup of database searches with HMMs by search space reduction with PSSM family models. Bioinformatics 2009, 25(24):3251\u20133258. 10.1093\/bioinformatics\/btp593","journal-title":"Bioinformatics"},{"key":"4708_CR39","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/3-540-45735-6_4","volume-title":"Proceedings of the 9th International Symposium on String Processing and Information Retrieval","author":"MI Abouelhoda","year":"2002","unstructured":"Abouelhoda MI, Ohlebusch E, Kurtz S: Optimal exact string matching based on suffix arrays. In Proceedings of the 9th International Symposium on String Processing and Information Retrieval. Volume 2476. Springer; 2002:31\u201343."},{"key":"4708_CR40","first-page":"758","volume":"49","author":"N de Bruijn","year":"1946","unstructured":"de Bruijn N: A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen 1946, 49: 758\u2013764.","journal-title":"Koninklijke Nederlandse Akademie v. Wetenschappen"},{"key":"4708_CR41","doi-asserted-by":"crossref","unstructured":"Gardner P, Giegerich R: A comprehensive comparison of comparative RNA structure prediction approaches. BMC Bioinformatics 2004., 5(140):","DOI":"10.1186\/1471-2105-5-140"},{"issue":"5","key":"4708_CR42","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1016\/S0022-2836(02)00308-X","volume":"319","author":"I Hofacker","year":"2002","unstructured":"Hofacker I, Fekete M, Stadler P: Secondary structure prediction for aligned RNA sequences. Journal of Molecular Biology 2002, 319(5):1059\u201366. 10.1016\/S0022-2836(02)00308-X","journal-title":"Journal of Molecular Biology"},{"issue":"13","key":"4708_CR43","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 prediction using stochastic context-free grammars. Nucl. Acids Res 2003, 31(13):3423\u20138. 10.1093\/nar\/gkg614","journal-title":"Nucl. Acids Res"},{"key":"4708_CR44","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/978-1-59745-514-5_33","volume":"395","author":"I Hofacker","year":"2007","unstructured":"Hofacker I: RNA consensus structure prediction with RNAalifold. Methods Mol Biol 2007, 395: 527\u2013544. 10.1007\/978-1-59745-514-5_33","journal-title":"Methods Mol Biol"},{"key":"4708_CR45","doi-asserted-by":"crossref","unstructured":"Bremges A, Schirmer S, Giegerich R: Fine-tuning structural RNA alignments in the twilight zone. BMC Bioinformatics 2010., 11(222):","DOI":"10.1186\/1471-2105-11-222"},{"key":"4708_CR46","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1093\/bioinformatics\/btm049","volume":"23","author":"E Torarinsson","year":"2007","unstructured":"Torarinsson E, Havgaard J, Gorodkin J: Multiple structural alignment and clustering of RNA sequences. Bioinformatics 2007, 23: 926\u2013932. 10.1093\/bioinformatics\/btm049","journal-title":"Bioinformatics"},{"key":"4708_CR47","doi-asserted-by":"crossref","unstructured":"Harmanci A, Sharma G, Mathews D: Efficient pairwise RNA structure prediction using probabilistic alignment constraints. BMC Bioinformatics 2007., 8(130):","DOI":"10.1186\/1471-2105-8-130"},{"issue":"17","key":"4708_CR48","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(17):3516\u201323. 10.1093\/bioinformatics\/bti577","journal-title":"Bioinformatics"},{"key":"4708_CR49","doi-asserted-by":"crossref","unstructured":"Wilm A, Higgins D, Notredame C: R-Coffee: a method for multiple alignment of non-coding RNA. Nucl. Acids Res 2008., 36(9):","DOI":"10.1093\/nar\/gkn174"},{"issue":"2-4","key":"4708_CR50","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.jda.2004.08.011","volume":"3","author":"M Abouelhoda","year":"2005","unstructured":"Abouelhoda M, Ohlebusch E: Chaining algorithms for multiple genome comparison. J. Discrete Algorithms 2005, 3(2\u20134):321\u2013341. 10.1016\/j.jda.2004.08.011","journal-title":"J. Discrete Algorithms"},{"key":"4708_CR51","volume-title":"Introduction to algorithms","author":"T Cormen","year":"1990","unstructured":"Cormen T, Leiserson C, Rivest R: Introduction to algorithms. Cambridge, MA: MIT Press; 1990."},{"issue":"20","key":"4708_CR52","doi-asserted-by":"publisher","first-page":"6069","DOI":"10.1093\/emboj\/17.20.6069","volume":"15","author":"S Altuvia","year":"1998","unstructured":"Altuvia S, Zhang A, Argaman L, Tiwari A, Storz G: The Escherichia coli OxyS regulatory RNA represses fhlA translation by blocking ribosome binding. EMBO 1998, 15(20):6069\u201375.","journal-title":"EMBO"},{"issue":"7108","key":"4708_CR53","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1038\/nature05113","volume":"443","author":"K Pollard","year":"2006","unstructured":"Pollard K, Salama S, Lambert N, Lambot M, Coppens S, Pedersen J, Katzman S, King B, Onodera C, Siepel A, Kern A, Dehay C, Igel H, Ares M, Vanderhaeghen P, Haussler D: An RNA gene expressed during cortical development evolved rapidly in humans. Nature 2006, 443(7108):167\u2013172. 10.1038\/nature05113","journal-title":"Nature"},{"key":"4708_CR54","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-13509-5_5","volume-title":"Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching","author":"T Schnattinger","year":"2010","unstructured":"Schnattinger T, Ohlebusch E, Gog S: Bidirectional search in a string with wavelet trees. In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching. Volume 6129. Springer; 2010:40\u201350. 10.1007\/978-3-642-13509-5_5"},{"issue":"15","key":"4708_CR55","doi-asserted-by":"publisher","first-page":"1974","DOI":"10.1093\/bioinformatics\/btp250","volume":"25","author":"K Darty","year":"2009","unstructured":"Darty K, Denise A, Ponty Y: VARNA: Interactive drawing and editing of the RNA seondary structure. Bioinformatics 2009, 25(15):1974\u20131975. 10.1093\/bioinformatics\/btp250","journal-title":"Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-12-214.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T15:28:31Z","timestamp":1630510111000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-12-214"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,27]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["4708"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-12-214","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,27]]},"assertion":[{"value":"10 December 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2011","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2011","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"214"}}