{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T03:27:44Z","timestamp":1725593264251},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642214578"},{"type":"electronic","value":"9783642214585"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21458-5_37","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T21:11:27Z","timestamp":1309209087000},"page":"441-454","source":"Crossref","is-referenced-by-count":2,"title":["Edit Distance with Duplications and Contractions Revisited"],"prefix":"10.1007","author":[{"given":"Tamar","family":"Pinhas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dekel","family":"Tsur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Zakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Ziv-Ukelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"37_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1142\/S0219720009004060","volume":"7","author":"M.I. Abouelhoda","year":"2009","unstructured":"Abouelhoda, M.I., Giegerich, R., Behzadi, B., Steyaert, J.-M.: Alignment of minisatellite maps based on run-length encoding scheme. J. of Bioinformatics and Computational Biology\u00a07(2), 287\u2013308 (2009)","journal-title":"J. of Bioinformatics and Computational Biology"},{"issue":"2","key":"37_CR2","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1023\/A:1009898029639","volume":"3","author":"T. Akutsu","year":"1999","unstructured":"Akutsu, T.: Approximation and exact algorithms for RNA secondary structure prediction and recognition of stochastic context-free languages. J. of Combinatorial Optimization\u00a03(2), 321\u2013336 (1999)","journal-title":"J. of Combinatorial Optimization"},{"key":"37_CR3","first-page":"1209","volume":"11","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of an oriented graph. Soviet Math. Dokl.\u00a011, 1209\u20131210 (1970)","journal-title":"Soviet Math. Dokl."},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"Behzadi, B., Steyaert, J.M.: The minisatellite transformation problem revisited: A run length encoded approach. Algorithms in Bioinformatics, 290\u2013301 (2004)","DOI":"10.1007\/978-3-540-30219-3_25"},{"issue":"2-4","key":"37_CR5","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/j.jda.2004.08.014","volume":"3","author":"B. Behzadi","year":"2005","unstructured":"Behzadi, B., Steyaert, J.M.: An improved algorithm for generalized comparison of minisatellites. J. of Discrete Algorithms\u00a03(2-4), 375\u2013389 (2005)","journal-title":"J. of Discrete Algorithms"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"Bened\u00ed, J.M., S\u00e1nchez, J.A.: Fast stochastic context-free parsing: A stochastic version of the Valiant algorithm. Pattern Recognition and Image Analysis, 80\u201388 (2007)","DOI":"10.1007\/978-3-540-72847-4_12"},{"key":"37_CR7","first-page":"303","volume":"2","author":"S. B\u00e9rard","year":"2006","unstructured":"B\u00e9rard, S., Nicolas, F., Buard, J., Gascuel, O., Rivals, E.: A fast and specific alignment method for minisatellite maps. Evolutionary bioinformatics online\u00a02, 303 (2006)","journal-title":"Evolutionary bioinformatics online"},{"issue":"3-4","key":"37_CR8","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1089\/10665270360688066","volume":"10","author":"S. B\u00e9rard","year":"2003","unstructured":"B\u00e9rard, S., Rivals, E.: Comparison of minisatellites. J. of Computational biology\u00a010(3-4), 357\u2013372 (2003)","journal-title":"J. of Computational biology"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. In: Proc. 39th ACM Symposium on Theory of Computing (STOC), pp. 590\u2013598 (2007)","DOI":"10.1145\/1250790.1250877"},{"key":"37_CR10","unstructured":"Chappelier, J.C., Rajman, M.: A generalized CYK algorithm for parsing stochastic CFG. In: Tabulation en analyse syntaxique et d\u00e9duction. Journ\u00e9es, pp. 133\u2013137 (1998)"},{"issue":"11","key":"37_CR11","doi-asserted-by":"publisher","first-page":"2117","DOI":"10.1093\/hmg\/8.11.2117","volume":"8","author":"M.A. Jobling","year":"1999","unstructured":"Jobling, M.A., Heyer, E., Dieltjes, P., de Knijff, P.: Y-chromosome-specific microsatellite mutation rates re-examined using a minisatellite, MSY1. Human Molecular Genetics\u00a08(11), 2117\u20132120 (1999)","journal-title":"Human Molecular Genetics"},{"key":"37_CR12","unstructured":"Kasami, T.: An efficient recognition and syntax-analysis algorithm for context-free languages. Defense Technical Information Center (1965)"},{"issue":"2","key":"37_CR13","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"Valiant, L.G.: General context-free recognition in less than cubic time. J. of Computer and System Sciences\u00a010(2), 308\u2013314 (1975)","journal-title":"J. of Computer and System Sciences"},{"key":"37_CR14","unstructured":"Williams, R.: Matrix-vector multiplication in sub-quadratic time(some preprocessing required). In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 995\u20131001 (2007)"},{"key":"37_CR15","doi-asserted-by":"crossref","unstructured":"Zakov, S., Tsur, D., Ziv-Ukelson, M.: Reducing the worst case running times of a family of RNA and CFG problems, using Valiant\u2019s approach. In: Algorithms in Bioinformatics, pp. 65\u201377 (2010)","DOI":"10.1007\/978-3-642-15294-8_6"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21458-5_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T12:04:34Z","timestamp":1560341074000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}