{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T04:15:40Z","timestamp":1746159340414,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":47,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642544545"},{"type":"electronic","value":"9783642544552"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54455-2_3","type":"book-chapter","created":{"date-parts":[[2014,2,7]],"date-time":"2014-02-07T03:33:45Z","timestamp":1391744025000},"page":"70-82","source":"Crossref","is-referenced-by-count":2,"title":["Optimisation Problems for Pairwise RNA Sequence and Structure Comparison: A Brief Survey"],"prefix":"10.1007","author":[{"given":"Alain","family":"Denise","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philippe","family":"Rinaudo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","first-page":"775","volume":"38","author":"J. Allali","year":"2008","unstructured":"Allali, J., Sagot, M.-F.: A multiple layer model to compare RNA secondary structures. Software: Practice and Experience\u00a038, 775\u2013792 (2008)","journal-title":"Software: Practice and Experience"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Allali, J., Saule, C., Chauve, C., D\u2019Aubenton-Carafa, Y., Denise, A., Drevet, C., Ferraro, P., Gautheret, D., Herrbach, C., Leclerc, F., De Monte, A., Ouangraoua, A., Sagot, M.-F., Termier, M., Thermes, C., Touzet, H.: BRASERO: A resource for benchmarking RNA secondary structure comparison algorithms (2012) (submitted for publication)","DOI":"10.1155\/2012\/893048"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Bauer, M., Klau, G.W., Reinert, K.: Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization. BMC Bioinformatics\u00a08(271) (2007)","DOI":"10.1186\/1471-2105-8-271"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Blin, G., Crochemore, M., Vialette, S.: Algorithmic Aspects of Arc-Annotated Sequences. In: Zomaya Albert, Y., Mourad, E. (eds.) Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications, pp. 113\u2013126. Wiley (February 2011)","DOI":"10.1002\/9780470892107.ch6"},{"issue":"2","key":"3_CR5","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1109\/TCBB.2008.28","volume":"7","author":"G. Blin","year":"2010","unstructured":"Blin, G., Denise, A., Dulucq, S., Herrbach, C., Touzet, H.: Alignments of RNA structures. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a07(2), 309\u2013322 (2010)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-540-74450-4_13","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"G. Blin","year":"2007","unstructured":"Blin, G., Fertin, G., Rusu, I., Sinoquet, C.: Extending the Hardness of RNA Secondary Structure Comparison. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614, pp. 140\u2013151. Springer, Heidelberg (2007)"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/11880561_24","volume-title":"String Processing and Information Retrieval","author":"G. Blin","year":"2006","unstructured":"Blin, G., Touzet, H.: How to Compare Arc-Annotated Sequences: The Alignment Hierarchy. In: Crestani, F., Ferragina, P., Sanderson, M. (eds.) SPIRE 2006. LNCS, vol.\u00a04209, pp. 291\u2013303. Springer, Heidelberg (2006)"},{"issue":"6","key":"3_CR8","doi-asserted-by":"publisher","first-page":"1654","DOI":"10.1137\/S0097539702402007","volume":"32","author":"M. Crochemore","year":"2003","unstructured":"Crochemore, M., Landau, G.M., Ziv-Ukelson, M.: A subquadratic sequence alignment algorithm for unrestricted scoring matrices. SIAM Journal on Computing\u00a032(6), 1654\u20131676 (2003)","journal-title":"SIAM Journal on Computing"},{"issue":"15","key":"3_CR9","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 secondary structure. Bioinformatics\u00a025(15), 1974\u20131975 (2009)","journal-title":"Bioinformatics"},{"issue":"1-3","key":"3_CR10","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1016\/S0304-3975(03)00323-2","volume":"306","author":"S. Dulucq","year":"2003","unstructured":"Dulucq, S., Tichit, L.: RNA secondary structure comparison: exact analysis of the Zhang-Shasha tree edit algorithm. Theoretical Computer Science\u00a0306(1-3), 471\u2013484 (2003)","journal-title":"Theoretical Computer Science"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/3-540-44888-8_7","volume-title":"Combinatorial Pattern Matching","author":"S. Dulucq","year":"2003","unstructured":"Dulucq, S., Touzet, H.: Analysis of tree edit distance algorithms. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 83\u201395. Springer, Heidelberg (2003)"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Eddy, R., Durbin, R.: RNA sequence analysis using covariance models. Nucleic Acid Research\u00a022(11) (1994)","DOI":"10.1093\/nar\/22.11.2079"},{"key":"3_CR13","unstructured":"Evans, P.A.: Algorithms and Complexity for Annotated Sequence Analysis. PhD thesis, University of Victoria (1999)"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-48452-3_20","volume-title":"Combinatorial Pattern Matching","author":"P.A. Evans","year":"1999","unstructured":"Evans, P.A.: Finding common subsequences with arcs and pseudoknots. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol.\u00a01645, p. 270. Springer, Heidelberg (1999)"},{"key":"3_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/11575832_38","volume-title":"String Processing and Information Retrieval","author":"V. Guignon","year":"2005","unstructured":"Guignon, V., Chauve, C., Hamel, S.: An edit distance between RNA stem-loops. In: Consens, M.P., Navarro, G. (eds.) SPIRE 2005. LNCS, vol.\u00a03772, pp. 335\u2013347. Springer, Heidelberg (2005)"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Han, B., Dost, B., Bafna, V., Zhang, S.: Structural alignment of pseudoknotted RNA. Journal of Computational Biology\u00a015(5) (2008)","DOI":"10.1089\/cmb.2007.0214"},{"key":"3_CR17","unstructured":"Herrbach, C.: \u00c9tude algorithmique et statistique de la comparaison de structures secondaires d\u2019ARN. PhD thesis, Universit\u00e9 Bordeaux 1 (2007)"},{"issue":"26-28","key":"3_CR18","doi-asserted-by":"publisher","first-page":"2423","DOI":"10.1016\/j.tcs.2010.01.014","volume":"411","author":"C. Herrbach","year":"2010","unstructured":"Herrbach, C., Denise, A., Dulucq, S.: Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm. Theoretical Computer Science\u00a0411(26-28), 2423\u20132432 (2010)","journal-title":"Theoretical Computer Science"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"H\u00f6chsmann, M., T\u00f6ller, T., Giegerich, R., Kurtz, S.: Local similarity in RNA secondary structures. In: Proc. IEEE Comput. Soc. Bioinform. Conf., pp. 159\u2013168 (2003)","DOI":"10.1109\/CSB.2003.1227315"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00818163","volume":"125","author":"I.L. Hofacker","year":"1994","unstructured":"Hofacker, I.L., Fontana, W., Stadler, P.F., Bonhoeffer, S.L., Tacker, M., Schuster, P.: Fast Folding and Comparison of RNA Secondary Structures. Monatsh. Chem.\u00a0125, 167\u2013188 (1994)","journal-title":"Monatsh. Chem."},{"issue":"2","key":"3_CR21","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1089\/10665270252935511","volume":"9","author":"T. Jiang","year":"2002","unstructured":"Jiang, T., Lin, G.-H., Ma, B., Zhang, K.: A general edit distance between RNA structures. Journal of Computational Biology\u00a09(2), 371\u2013388 (2002)","journal-title":"Journal of Computational Biology"},{"key":"3_CR22","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","volume":"143","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Wang, L., Zhang, K.: Alignment of trees - an alternative to tree edit. Theoretical Computer Science\u00a0143, 137\u2013148 (1995)","journal-title":"Theoretical Computer Science"},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/3-540-68530-8_8","volume-title":"Algorithms - ESA \u201998","author":"P.N. Klein","year":"1998","unstructured":"Klein, P.N.: Computing the edit-distance between unrooted ordered trees. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 91\u2013102. Springer, Heidelberg (1998)"},{"issue":"1","key":"3_CR24","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1186\/1471-2105-4-44","volume":"4","author":"R.J. Klein","year":"2003","unstructured":"Klein, R.J., Eddy, S.R.: RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics\u00a04(1), 44 (2003)","journal-title":"BMC Bioinformatics"},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A. Lempel","year":"1976","unstructured":"Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Trans. Inform. Theory\u00a022, 75\u201381 (1976)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Lenhof, H., Reinert, K., Vingron, M.: A polyhedral approach to RNA sequence structure alignment. In: Proc. 2nd Ann. Int. Conf. Computational Molecular Biology (RECOMB 1998), pp. 153\u2013159 (1998)","DOI":"10.1145\/279069.279109"},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1017\/S1355838201002515","volume":"7","author":"N.B. Leontis","year":"2001","unstructured":"Leontis, N.B., Westhof, E.: Geometric nomenclature and classification of RNA base pairs. RNA\u00a07, 499\u2013512 (2001)","journal-title":"RNA"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1145\/369133.369214","volume-title":"Proceedings of the Fifth Annual International Conference on Computational Biology, RECOMB 2001","author":"G.-H. Lin","year":"2001","unstructured":"Lin, G.-H., Ma, B., Zhang, K.: Edit distance between two rna structures. In: Proceedings of the Fifth Annual International Conference on Computational Biology, RECOMB 2001, pp. 211\u2013220. ACM, New York (2001)"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Liu, J., Wang, J.T., Hu, J., Tian, B.: A method for aligning RNA secondary structures and its application to RNA motif detection. BMC Bioinformatics\u00a06(89) (2005)","DOI":"10.1186\/1471-2105-6-89"},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Mathews, D.H., Moss, W.N., Turner, D.H.: Folding and finding RNA secondary structure. Cold Spring Harbor Perspectives in Biology\u00a02(12) (December 2010)","DOI":"10.1101\/cshperspect.a003665"},{"key":"3_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-540-69068-9_9","volume-title":"Combinatorial Pattern Matching","author":"M. M\u00f6hl","year":"2008","unstructured":"M\u00f6hl, M., Will, S., Backofen, R.: Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 69\u201381. Springer, Heidelberg (2008)"},{"issue":"3","key":"3_CR32","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S.B. Needleman","year":"1970","unstructured":"Needleman, S.B., Wunsch, C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol.\u00a048(3), 443\u2013453 (1970)","journal-title":"J. Mol. Biol."},{"key":"3_CR33","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.jda.2006.03.010","volume":"5","author":"A. Ouangraoua","year":"2007","unstructured":"Ouangraoua, A., Ferraro, P., Tichit, L., Dulucq, S.: Local similarity between quotiented ordered trees. J. Discrete Algorithms\u00a05, 23\u201335 (2007)","journal-title":"J. Discrete Algorithms"},{"issue":"8-10","key":"3_CR34","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1016\/j.tcs.2010.11.020","volume":"412","author":"A. Ouangraoua","year":"2011","unstructured":"Ouangraoua, A., Guignon, V., Hamel, S., Chauve, C.: A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes. Theoretical Computer Science\u00a0412(8-10 ), 753\u2013764 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"5740","key":"3_CR35","doi-asserted-by":"publisher","first-page":"1507","DOI":"10.1126\/science.309.5740.1507","volume":"309","author":"G. Riddihough","year":"2005","unstructured":"Riddihough, G.: In the forests of RNA dark matter. Science\u00a0309(5740), 1507\u20131507 (2005)","journal-title":"Science"},{"key":"3_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-642-33122-0_12","volume-title":"Algorithms in Bioinformatics","author":"P. Rinaudo","year":"2012","unstructured":"Rinaudo, P., Ponty, Y., Barth, D., Denise, A.: Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots (extended abstract). In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, vol.\u00a07534, pp. 149\u2013164. Springer, Heidelberg (2012)"},{"issue":"6","key":"3_CR37","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1089\/cmb.2006.13.1197","volume":"13","author":"E.A.A. R\u00f8dland","year":"2006","unstructured":"R\u00f8dland, E.A.A.: Pseudoknots in RNA secondary structures: representation, enumeration, and prevalence. Journal of Computational Biology\u00a013(6), 1197\u20131213 (2006)","journal-title":"Journal of Computational Biology"},{"issue":"2","key":"3_CR38","doi-asserted-by":"crossref","first-page":"ii237","DOI":"10.1093\/bioinformatics\/bti1139","volume":"21","author":"K. Sato","year":"2005","unstructured":"Sato, K., Sakakibara, Y.: RNA secondary structural alignment with conditional random fields. Bioinformatics\u00a021(suppl. 2), ii237\u2013ii242 (2005)","journal-title":"Bioinformatics"},{"issue":"3","key":"3_CR39","first-page":"387","volume":"4","author":"B.A. Shapiro","year":"1988","unstructured":"Shapiro, B.A.: An algorithm for comparing multiple RNA secondary structures. Computer Applications in the Biosciences\u00a04(3), 387\u2013393 (1988)","journal-title":"Computer Applications in the Biosciences"},{"issue":"suppl. 2","key":"3_CR40","doi-asserted-by":"crossref","first-page":"W373","DOI":"10.1093\/nar\/gkq316","volume":"38","author":"C. Smith","year":"2010","unstructured":"Smith, C., Heyne, S., Richter, A.S., Will, S., Backofen, R.: Freiburg rna tools: a web server integrating intarna, exparna and locarna. Nucleic Acids Research\u00a038(suppl. 2), W373\u2013W377 (2010)","journal-title":"Nucleic Acids Research"},{"key":"3_CR41","doi-asserted-by":"crossref","unstructured":"Song, Y., Liu, C., Huang, X., Malmberg, R.L., Xu, Y., Cai, L.: Efficient parameterized algorithms for biopolymer structure-sequence alignment. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a03(4) (2006)","DOI":"10.1109\/TCBB.2006.52"},{"key":"3_CR42","doi-asserted-by":"crossref","unstructured":"St-Onge, K., Thibault, P., Hamel, S., Major, F.: Modeling RNA tertiary structure motifs by graph-grammars. Nucleic Acids Research\u00a035(5) (2007)","DOI":"10.1093\/nar\/gkm069"},{"key":"3_CR43","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1093\/bioinformatics\/bti743","volume":"22","author":"Z. Weinberg","year":"2006","unstructured":"Weinberg, Z., Ruzzo, W.L.: Sequence-based heuristics for faster annotation of non-coding RNA families. Bioninformatics\u00a022, 35\u201339 (2006)","journal-title":"Bioninformatics"},{"issue":"4","key":"3_CR44","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1089\/cmb.2010.0052","volume":"19","author":"T.K. Wong","year":"2012","unstructured":"Wong, T.K., Yiu, S.M.: Structural alignment of RNA with triple helix structure. Journal of Computational Biology\u00a019(4), 365\u2013378 (2012)","journal-title":"Journal of Computational Biology"},{"key":"3_CR45","doi-asserted-by":"crossref","unstructured":"Wong, T.K.F., Lam, T.W., Sung, W.K., Cheung, B.W.Y., Yiu, S.M.: Structural alignment of RNA with complex pseudoknot structure. Journal of Computational Biology\u00a018(1) (2011)","DOI":"10.1089\/cmb.2009.0275"},{"issue":"6","key":"3_CR46","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K. Zhang","year":"1989","unstructured":"Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput.\u00a018(6), 1245\u20131262 (1989)","journal-title":"SIAM J. Comput."},{"key":"3_CR47","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/BF02459506","volume":"46","author":"M. Zuker","year":"1984","unstructured":"Zuker, M., Sankoff, D.: RNA secondary structures and their prediction. Bull. Math. Biol.\u00a046, 591\u2013621 (1984)","journal-title":"Bull. Math. Biol."}],"container-title":["Lecture Notes in Computer Science","Transactions on Computational Intelligence XIII"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54455-2_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T20:12:52Z","timestamp":1746130372000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54455-2_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642544545","9783642544552"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54455-2_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}