{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:13:18Z","timestamp":1725516798125},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540697329"},{"type":"electronic","value":"9783540697336"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69733-6_32","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T12:07:43Z","timestamp":1218542863000},"page":"319-330","source":"Crossref","is-referenced-by-count":4,"title":["Sequence Alignment Algorithms for Run-Length-Encoded Strings"],"prefix":"10.1007","author":[{"given":"Guan Shieng","family":"Huang","sequence":"first","affiliation":[]},{"given":"Jia Jie","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Yue Li","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"32_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M.M., Moran, S., Shor, P., Wilher, R.: Geometric Applications of a Matrix-Searching Algorithm. Algorithmica\u00a02(1), 195\u2013208 (1987)","journal-title":"Algorithmica"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Park, J.: Notes on Searching in Multidimensional Monotone Arrays. In: Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (FOCS 1988), pp. 497\u2013512 (1988)","DOI":"10.1109\/SFCS.1988.21966"},{"issue":"5","key":"32_CR3","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1137\/0219066","volume":"19","author":"A. Apostolico","year":"1990","unstructured":"Apostolico, A., Atallah, M.J., Larmore, L.L., Mcfaddin, S.: Efficient Parallel Algorithms for String Editing and Related Problems. SIAM Journal on Computing\u00a019(5), 968\u2013988 (1990)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"32_CR4","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1006\/jcom.1998.0493","volume":"15","author":"A. Apostolico","year":"1999","unstructured":"Apostolico, A., Landau, G.M., Skiena, S.: Matching for Run-Length Encoded Strings. Journal of Complexity\u00a015(1), 4\u201316 (1999)","journal-title":"Journal of Complexity"},{"issue":"6","key":"32_CR5","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/S0020-0190(02)00215-6","volume":"83","author":"O. Arbell","year":"2002","unstructured":"Arbell, O., Landau, G.M., Mitchell, J.S.B.: Edit Distance of Run-Length Encoded Strings. Information Processing Letters\u00a083(6), 307\u2013314 (2002)","journal-title":"Information Processing Letters"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"Bein, W.W., Golin, M.J., Larmore, L.L., Zhang, Y.: The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity. In: Proceedings of the 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 31\u201340 (2006)","DOI":"10.1145\/1109557.1109562"},{"issue":"1\u20132","key":"32_CR7","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/0304-3975(95)92848-R","volume":"145","author":"G. Benson","year":"1995","unstructured":"Benson, G.: A Space Efficient Algorithm for Finding the Best Nonoverlapping Alignment Score. Theoretical Computer Science\u00a0145(1\u20132), 357\u2013369 (1995)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"32_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0020-0190(95)00005-W","volume":"54","author":"H. Bunke","year":"1995","unstructured":"Bunke, H., Csirik, J.: An Improved Algorithm for Computing the Edit Distance of Run-Length Coded Strings. Information Processing Letters\u00a054(2), 93\u201396 (1995)","journal-title":"Information Processing Letters"},{"issue":"2","key":"32_CR9","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"R.E. Burkard","year":"1996","unstructured":"Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge Properties in Optimization. Discrete Applied Mathematics\u00a070(2), 95\u2013161 (1996)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"32_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2005.04.050","volume":"176","author":"R.E. Burkard","year":"2007","unstructured":"Burkard, R.E.: Monge Properties, Discrete Convexity and Applications. European Journal of Operational Research\u00a0176(1), 1\u201314 (2007)","journal-title":"European Journal of Operational Research"},{"issue":"6","key":"32_CR11","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\u20131673 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"32_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Cambridge University Press, Cambridge (1997)"},{"issue":"6","key":"32_CR13","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D.S. Hirschberg","year":"1975","unstructured":"Hirschberg, D.S.: A Linear Space Algorithm for Computing Maximal Common Subsequences. Communications of the ACM\u00a018(6), 341\u2013343 (1975)","journal-title":"Communications of the ACM"},{"issue":"3","key":"32_CR14","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539794262677","volume":"25","author":"S.K. Kannan","year":"1996","unstructured":"Kannan, S.K., Myers, E.W.: An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score. SIAM Journal on Computing\u00a025(3), 648\u2013662 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"32_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/11575832_35","volume-title":"String Processing and Information Retrieval","author":"J.W. Kim","year":"2005","unstructured":"Kim, J.W., Amir, A., Landau, G.M., Park, K.: Computing Similarity of Run-Length Encoded Strings with Affine Gap Penalty. In: Consens, M.P., Navarro, G. (eds.) SPIRE 2005. LNCS, vol.\u00a03772, pp. 315\u2013326. Springer, Heidelberg (2005)"},{"issue":"2","key":"32_CR16","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1006\/jagm.2001.1191","volume":"41","author":"G.M. Landau","year":"2001","unstructured":"Landau, G.M., Ziv-Ukelson, M.: On the Common Substring Alignment Problem. Journal of Algorithms\u00a041(2), 338\u2013359 (2001)","journal-title":"Journal of Algorithms"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"Ledergerber, C., Dessimoz, C.: Alignments with Non-overlapping Moves, Inversions and Tandem Duplications in o(n 4) Time. Journal of Combinatorial Optimization (to appear, 2007)","DOI":"10.1007\/s10878-007-9132-y"},{"key":"32_CR18","first-page":"707","volume":"10","author":"V.I. Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary Codes Capable of Correcting, Deletions, Insertions and Reversals. Soviet Physics Doklady\u00a010, 707\u2013710 (1966)","journal-title":"Soviet Physics Doklady"},{"issue":"1","key":"32_CR19","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.ipl.2007.07.006","volume":"105","author":"J.J. Liu","year":"2007","unstructured":"Liu, J.J., Huang, G.S., Wang, Y.L., Lee, R.C.T.: Edit Distance for a Run-Length-Encoded String and an Uncompressed String. Information Processing Letters\u00a0105(1), 12\u201316 (2007)","journal-title":"Information Processing Letters"},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Liu, J.J., Wang, Y.L., Lee, R.C.T.: Finding a Longest Common Subsequence Between a Run-Length-Encoded String and an Uncompressed String. Journal of Complexity (to appear, 2008)","DOI":"10.1016\/j.jco.2007.06.003"},{"issue":"4","key":"32_CR21","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s00453-002-1005-2","volume":"35","author":"V. M\u00e4kinen","year":"2003","unstructured":"M\u00e4kinen, V., Navarro, G., Ukkonen, E.: Approximate Matching of Run-Length Compressed Strings. Algorithmica\u00a035(4), 347\u2013369 (2003)","journal-title":"Algorithmica"},{"key":"32_CR22","unstructured":"Mitchell, J.: A Geometric Shortest Path Problem, with Application to Computing a Longest Common Subsequence in Run-Length Encoded Strings. Technical report, SUNY Stony Brook (1997)"},{"issue":"4","key":"32_CR23","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 Journal on Computing\u00a027(4), 972\u2013992 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"32_CR24","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R.A. Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The String-to-String Correction Problem. Journal of the ACM\u00a021(1), 168\u2013173 (1974)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69733-6_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:02:15Z","timestamp":1605744135000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69733-6_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540697329","9783540697336"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69733-6_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}