{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T11:40:05Z","timestamp":1744026005883,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642331213"},{"type":"electronic","value":"9783642331220"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33122-0_11","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T10:43:09Z","timestamp":1346150589000},"page":"135-148","source":"Crossref","is-referenced-by-count":0,"title":["RNA Tree Comparisons via Unrooted Unordered Alignments"],"prefix":"10.1007","author":[{"given":"Nimrod","family":"Milo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Zakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erez","family":"Katzenelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eitan","family":"Bachmat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yefim","family":"Dinitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Ziv-Ukelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1186\/1471-2105-9-340","volume":"9","author":"M. Andronescu","year":"2008","unstructured":"Andronescu, M., Bereg, V., Hoos, H., Condon, A.: Rna strand: the rna secondary structure and statistical analysis database. BMC Bioinformatics\u00a09, 340 (2008)","journal-title":"BMC Bioinformatics"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"2543","DOI":"10.1046\/j.1432-1033.2003.03634.x","volume":"270","author":"I. Agmon","year":"2003","unstructured":"Agmon, I., Auerbach, T., Baram, D., Bartels, H., Bashan, A., Berisio, R., Fucini, P., Hansen, H., Harms, J., Kessler, M., et al.: On peptide bond formation, translocation, nascent protein progression and the regulatory properties of ribosomes. European Journal of Biochemistry\u00a0270, 2543\u20132556 (2003)","journal-title":"European Journal of Biochemistry"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00818163","volume":"125","author":"I. Hofacker","year":"1994","unstructured":"Hofacker, I., Fontana, W., Stadler, P., Bonhoeffer, L., Tacker, M., Schuster, P.: Fast folding and comparison of RNA secondary structures. Monatshefte fur Chemie\/Chemical Monthly\u00a0125, 167\u2013188 (1994)","journal-title":"Monatshefte fur Chemie\/Chemical Monthly"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Steffen, P., Voss, B., Rehmsmeier, M., Reeder, J., Giegerich, R.: RNAshapes: an integrated RNA analysis package based on abstract shapes (2006)","DOI":"10.1093\/bioinformatics\/btk010"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Hochsmann, M., Toller, T., Giegerich, R., Kurtz, S.: Local similarity in RNA secondary structures. In: Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003, pp. 159\u2013168. IEEE (2003)","DOI":"10.1109\/CSB.2003.1227315"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1089\/10665270252935511","volume":"9","author":"T. Jiang","year":"2002","unstructured":"Jiang, T., Lin, G., Ma, B., Zhang, K.: A general edit distance between RNA structures. Journal of Computational Biology\u00a09, 371\u2013388 (2002)","journal-title":"Journal of Computational Biology"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/3-540-48452-3_21","volume-title":"Combinatorial Pattern Matching","author":"K. Zhang","year":"1999","unstructured":"Zhang, K., Wang, L., Ma, B.: Computing Similarity between RNA Structures. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol.\u00a01645, pp. 281\u2013293. Springer, Heidelberg (1999)"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P. Bille","year":"2005","unstructured":"Bille, P.: A survey on tree edit distance and related problems. Theoretical Computer Science\u00a0337, 217\u2013239 (2005)","journal-title":"Theoretical Computer Science"},{"key":"11_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-642-21458-5_11","volume-title":"Combinatorial Pattern Matching","author":"S. Schirmer","year":"2011","unstructured":"Schirmer, S., Giegerich, R.: Forest Alignment with Affine Gaps and Anchors. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 104\u2013117. Springer, Heidelberg (2011)"},{"key":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/11575832_39","volume-title":"String Processing and Information Retrieval","author":"J. Allali","year":"2005","unstructured":"Allali, J., Sagot, M.-F.: A Multiple Graph Layers Model with Application to RNA Secondary Structures Comparison. In: Consens, M.P., Navarro, G. (eds.) SPIRE 2005. LNCS, vol.\u00a03772, pp. 348\u2013359. Springer, Heidelberg (2005)"},{"key":"11_CR11","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, 309\u2013322 (2010)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.virusres.2005.10.011","volume":"119","author":"E. Jan","year":"2006","unstructured":"Jan, E.: Divergent ires elements in invertebrates. Virus Research\u00a0119, 16\u201328 (2006)","journal-title":"Virus Research"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"1002031","DOI":"10.1371\/journal.pcbi.1002031","volume":"7","author":"J. Perreault","year":"2011","unstructured":"Perreault, J., Weinberg, Z., Roth, A., Popescu, O., Chartrand, P., Ferbeyre, G., Breaker, R.: Identification of hammerhead ribozymes in all domains of life reveals novel structural variations. PLoS Computational Biology\u00a07, e1002031 (2011)","journal-title":"PLoS Computational Biology"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1432-1033.1997.t01-3-00001.x","volume":"245","author":"K. Birikh","year":"1997","unstructured":"Birikh, K., Heaton, P., Eckstein, F.: The structure, function and application of the hammerhead ribozyme. European Journal of Biochemistry\u00a0245, 1\u201316 (1997)","journal-title":"European Journal of Biochemistry"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"4093","DOI":"10.1093\/nar\/26.18.4093","volume":"26","author":"E. Haas","year":"1998","unstructured":"Haas, E., Brown, J.: Evolutionary variation in bacterial RNase P RNAs. Nucleic Acids Research\u00a026, 4093\u20134099 (1998)","journal-title":"Nucleic Acids Research"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(94)90062-0","volume":"49","author":"K. Zhang","year":"1994","unstructured":"Zhang, K., Jiang, T.: Some MAX SNP-hard results concerning unordered labeled trees. Information Processing Letters\u00a049, 249\u2013254 (1994)","journal-title":"Information Processing Letters"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1999.1044","volume":"33","author":"R. Shamir","year":"1999","unstructured":"Shamir, R., Tsur, D.: Faster subtree isomorphism. J. of Algorithms\u00a033, 267\u2013280 (1999)","journal-title":"J. of Algorithms"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0196-6774(87)90030-7","volume":"8","author":"M. Chung","year":"1987","unstructured":"Chung, M.: O (n2. 5) time algorithms for the subgraph homeomorphism problem on trees. Journal of Algorithms\u00a08, 106\u2013112 (1987)","journal-title":"Journal of Algorithms"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1016\/j.jda.2007.07.001","volume":"6","author":"R.Y. Pinter","year":"2008","unstructured":"Pinter, R.Y., Rokhlenko, O., Tsur, D., Ziv-Ukelson, M.: Approximate labelled subtree homeomorphism. Journal of Discrete Algorithms\u00a06, 480\u2013496 (2008)","journal-title":"Journal of Discrete Algorithms"},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF01975866","volume":"15","author":"K. Zhang","year":"1996","unstructured":"Zhang, K.: A constrained edit distance between unordered labeled trees. Algorithmica\u00a015, 205\u2013222 (1996)","journal-title":"Algorithmica"},{"key":"11_CR21","unstructured":"Kao, M., Lam, T., Sung, W., Ting, H.: Cavity matchings, label compressions, and unrooted evolutionary trees. Arxiv preprint cs\/0101031 (2001)"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM)\u00a019, 248\u2013264 (1972)","journal-title":"Journal of the ACM (JACM)"},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. Fredman","year":"1987","unstructured":"Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM)\u00a034, 596\u2013615 (1987)","journal-title":"Journal of the ACM (JACM)"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H. Gabow","year":"1989","unstructured":"Gabow, H., Tarjan, R.: Faster scaling algorithms for network problems. SIAM Journal on Computing\u00a018, 1013 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01586040","volume":"54","author":"J. Orlin","year":"1992","unstructured":"Orlin, J., Ahuja, R.: New scaling algorithms for the assignment and minimum mean cycle problems. Mathematical Programming\u00a054, 41\u201356 (1992)","journal-title":"Mathematical Programming"},{"key":"11_CR26","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/0031-3203(94)00109-Y","volume":"28","author":"K. Zhang","year":"1995","unstructured":"Zhang, K.: Algorithms for the constrained editing distance between ordered labeled trees and related problems. Pattern Recognition\u00a028, 463\u2013474 (1995)","journal-title":"Pattern Recognition"},{"key":"11_CR27","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0020-0190(90)90109-B","volume":"35","author":"M. Maes","year":"1990","unstructured":"Maes, M.: On a cyclic string-to-string correction problem. Information Processing Letters\u00a035, 73\u201378 (1990)","journal-title":"Information Processing Letters"},{"key":"11_CR28","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/S0097539795288489","volume":"27","author":"J.P. Schmidt","year":"1998","unstructured":"Schmidt, J.P.: All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM J. of Computing\u00a027, 972\u2013992 (1998)","journal-title":"SIAM J. of Computing"},{"key":"11_CR29","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/s11786-007-0033-3","volume":"1","author":"A. Tiskin","year":"2008","unstructured":"Tiskin, A.: Semi-local string comparison: Algorithmic techniques and applications. Mathematics in Computer Science\u00a01, 571\u2013603 (2008)","journal-title":"Mathematics in Computer Science"},{"key":"11_CR30","doi-asserted-by":"publisher","first-page":"3429","DOI":"10.1093\/nar\/gkg599","volume":"31","author":"I. Hofacker","year":"2003","unstructured":"Hofacker, I.: Vienna RNA secondary structure server. Nucleic Acids Research\u00a031, 3429 (2003)","journal-title":"Nucleic Acids Research"},{"key":"11_CR31","doi-asserted-by":"crossref","first-page":"1919","DOI":"10.1128\/jb.177.8.1919-1928.1995","volume":"177","author":"N.R. Pace","year":"1995","unstructured":"Pace, N.R., Brown, J.W.: Evolutionary perspective on the structure and function of ribonuclease P, a ribozyme. J. Bacteriol.\u00a0177, 1919\u20131928 (1995)","journal-title":"J. Bacteriol."},{"key":"11_CR32","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1093\/nar\/27.1.314","volume":"27","author":"J. Brown","year":"1999","unstructured":"Brown, J.: The ribonuclease p database. Nucleic acids research\u00a027, 314 (1999)","journal-title":"Nucleic acids research"},{"key":"11_CR33","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1186\/1471-2105-9-340","volume":"9","author":"M. Andronescu","year":"2008","unstructured":"Andronescu, M., Bereg, V., Hoos, H.H., Condon, A.: RNA STRAND: the RNA secondary structure and statistical analysis database. BMC Bioinformatics\u00a09, 340 (2008)","journal-title":"BMC Bioinformatics"},{"key":"11_CR34","unstructured":"H\u00f6chsmann, M.: The tree alignment model: algorithms, implementations and applications for the analysis of RNA secondary structures. PhD thesis, Universit\u00e4tsbibliothek Bielefeld (2005)"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33122-0_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T11:01:23Z","timestamp":1744023683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33122-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642331213","9783642331220"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33122-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}