{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T17:40:30Z","timestamp":1736444430763,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540354550"},{"type":"electronic","value":"9783540354611"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11780441_20","type":"book-chapter","created":{"date-parts":[[2006,6,30]],"date-time":"2006-06-30T15:02:51Z","timestamp":1151679771000},"page":"211-222","source":"Crossref","is-referenced-by-count":4,"title":["Approximation of RNA Multiple Structural Alignment"],"prefix":"10.1007","author":[{"given":"Marcin","family":"Kubica","sequence":"first","affiliation":[]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44888-8_1","volume-title":"Combinatorial Pattern Matching","author":"M.I. Abouelhoda","year":"2003","unstructured":"Abouelhoda, M.I., Ohlebusch, E.: Multiple Genome Alignment: Chaining Algorithms Revisited. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 1\u201316. Springer, Heidelberg (2003)"},{"key":"20_CR2","first-page":"1","volume-title":"Computing similarity between RNA strings","author":"V. Bafna","year":"1995","unstructured":"Bafna, V., Muthukrishnan, S., Ravi, R.: Computing similarity between RNA strings, vol.\u00a0937, pp. 1\u201316. Springer, Berlin (1995)"},{"key":"20_CR3","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/11415770_13","volume-title":"Research in Computational Molecular Biology","author":"V. Bafna","year":"2005","unstructured":"Bafna, V., Tang, H., Zhang, S.: Consensus Folding of Unaligned RNA Sequences Revisited. In: Miyano, S., Mesirov, J., Kasif, S., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2005. LNCS (LNBI), vol.\u00a03500, pp. 172\u2013187. Springer, Heidelberg (2005)"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/11533719_6","volume-title":"Computing and Combinatorics","author":"S. Bereg","year":"2005","unstructured":"Bereg, S., Zhu, B.: RNA multiple structural alignment with longest common subsequences. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 32\u201341. Springer, Heidelberg (2005)"},{"issue":"5","key":"20_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00008","volume":"2","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D., M\u00fcller, H.: Treewidth and minimum fill-in on d-trapezoid graphs. Journal of Graph Algorithms and Applications\u00a02(5), 1\u201323 (1998)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(88)90032-7","volume":"21","author":"I. Dagan","year":"1988","unstructured":"Dagan, I., Golumbic, M.C., Pinter, R.Y.: Trapezoid graphs and their coloring. Discrete Applied Mathematics\u00a021, 35\u201346 (1988)","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/978-3-540-27801-6_19","volume-title":"Combinatorial Pattern Matching","author":"E. Davydov","year":"2004","unstructured":"Davydov, E., Batzoglou, S.: A Computational Model for RNA Multiple Structural Alignment. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 254\u2013269. Springer, Heidelberg (2004)"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(96)00013-3","volume":"74","author":"S. Felsner","year":"1997","unstructured":"Felsner, S., M\u00fcller, R., Wernisch, L.: Trapezoid graphs and generalizations: Geometry and algorithms. Discrete Applied Math.\u00a074, 13\u201332 (1997)","journal-title":"Discrete Applied Math."},{"issue":"2","key":"20_CR9","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(95)00062-V","volume":"63","author":"C. Flotow","year":"1995","unstructured":"Flotow, C.: On powers of m-trapezoid graphs. Discrete Applied Mathematics\u00a063(2), 187\u2013192 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR10","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/3-540-36206-1_17","volume-title":"FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science","author":"J. Gramm","year":"2002","unstructured":"Gramm, J., Guo, J., Niedermeier, R.: Pattern Matching for arc-annotated sequences. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol.\u00a02556, pp. 182\u2013193. Springer, Heidelberg (2002)"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Holmes, I., Rubin, G.M.: Pairwise RNA structure comparison with stochastic context-free grammars. In: Pacific Symposium on Biocomputing, pp. 163\u2013174 (2002)","DOI":"10.1142\/9789812799623_0016"},{"issue":"3","key":"20_CR13","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1016\/S0022-0000(02)00004-1","volume":"65","author":"G. Lin","year":"2002","unstructured":"Lin, G., Chen, Z.-Z., Jiang, T., Wen, J.: The longest common subsequence problem for sequences with nested arc annotations. Journal of Computer and System Sciences\u00a065(3), 465\u2013480 (2002) (Special issue on computational biology)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR14","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":"20_CR15","unstructured":"Lozano, A., Valiente, G.: On the maximum common embedded subtree problem for ordered trees. In: Iliopoulos, C., Lecroq, T. (eds.) String Algorithmics, ch. 7. King\u2019s College London Publications (2004)"},{"issue":"1","key":"20_CR16","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0135006","volume":"35","author":"R. Nussinov","year":"1978","unstructured":"Nussinov, R., Pieczenik, G., Griggs, J.R., Kleitman, D.J.: Algorithms for loop matching. SIAM Journal of Applied Mathematics\u00a035(1), 68\u201382 (1978)","journal-title":"SIAM Journal of Applied Mathematics"},{"issue":"2-3","key":"20_CR17","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.tcs.2003.08.010","volume":"312","author":"S. Vialette","year":"2004","unstructured":"Vialette, S.: On the computational complexity of 2-interval pattern matching. Theoretical Computer Science\u00a0312(2-3), 223\u2013249 (2004)","journal-title":"Theoretical Computer Science"},{"key":"20_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to computational biology - Maps, sequences and genomes","author":"M.S. Waterman","year":"1995","unstructured":"Waterman, M.S.: Introduction to computational biology - Maps, sequences and genomes. Chapman and Hall, London (1995)"},{"issue":"6","key":"20_CR19","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K. Zhang","year":"1989","unstructured":"Zhang, K., Shacha, D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal of Computing\u00a018(6), 1245\u20131262 (1989)","journal-title":"SIAM Journal of Computing"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11780441_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T17:08:49Z","timestamp":1736442529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11780441_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540354550","9783540354611"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11780441_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}