{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T19:44:27Z","timestamp":1744400667992},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540403111"},{"type":"electronic","value":"9783540448884"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44888-8_1","type":"book-chapter","created":{"date-parts":[[2007,3,5]],"date-time":"2007-03-05T11:34:12Z","timestamp":1173094452000},"page":"1-16","source":"Crossref","is-referenced-by-count":6,"title":["Multiple Genome Alignment: Chaining Algorithms Revisited"],"prefix":"10.1007","author":[{"given":"Mohamed Ibrahim","family":"Abouelhoda","sequence":"first","affiliation":[]},{"given":"Enno","family":"Ohlebusch","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,5,27]]},"reference":[{"key":"1_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/3-540-68530-8_7","volume-title":"Proc. 6th European Symposium on Algorithms","author":"B.S. Baker","year":"1998","unstructured":"B.S. Baker and R. Giancarlo. Longest common subsequence from fragments via sparse dynamic programming. In Proc. 6th European Symposium on Algorithms, LNCS 1461, pp. 79\u201390, 1998."},{"issue":"3","key":"1_CR2","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17(3):427\u2013462, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"11","key":"1_CR3","doi-asserted-by":"publisher","first-page":"2478","DOI":"10.1093\/nar\/30.11.2478","volume":"30","author":"A.L. Delcher","year":"2002","unstructured":"A.L. Delcher, A. Phillippy, J. Carlton, and S.L. Salzberg. Fast algorithms for large-scale genome alignment and comparison. Nucleic Acids Res., 30(11):2478\u20132483, 2002.","journal-title":"Nucleic Acids Res"},{"key":"1_CR4","unstructured":"D. Eppstein. \n                  http:\/\/www.ics.uci.edu\/~eppstein\/pubs\/p-sparsedp.html\n                  \n                ."},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1145\/146637.146650","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, R. Giancarlo, Z. Galil, and G.F. Italiano. Sparse dynamic programming. I:Linear cost functions; II:Convex and concave cost functions. Journal of the ACM, 39:519\u2013567, 1992.","journal-title":"Journal of the ACM"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"9061","DOI":"10.1073\/pnas.93.17.9061","volume":"93","author":"M.S. Gelfand","year":"1996","unstructured":"M.S. Gelfand, A.A. Mironov, and P.A. Pevzner. Gene recognition via spliced sequence alignment. Proc. Nat. Acad. Sci., 93:9061\u20139066, 1996.","journal-title":"Proc. Nat. Acad. Sci."},{"issue":"4","key":"1_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(83)90045-5","volume":"17","author":"L.J. Guibas","year":"1983","unstructured":"L.J. Guibas and J. Stolfi. On computing all north-east nearest neighbors in the L\n                        1 metric. Information Processing Letters, 17(4):219\u2013223, 1983.","journal-title":"Information Processing Letters"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01786986","volume":"15","author":"D.B. Johnson","year":"1982","unstructured":"D.B. Johnson. A priority queue in which initialization and queue operations take O(log log D) time. Mathematical Systems Theory, 15:295\u2013309, 1982.","journal-title":"Mathematical Systems Theory"},{"key":"1_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/3-540-55706-7_29","volume-title":"Proc. 3rd Scandinavian Workshop on Algorithm Theory","author":"D. Joseph","year":"1992","unstructured":"D. Joseph, J. Meidanis, and P. Tiwari. Determining DNA sequence similarity using maximum independent set algorithms for interval graphs. Proc. 3rd Scandinavian Workshop on Algorithm Theory, LNCS 621, pp. 326\u2013337, 1992."},{"key":"1_CR10","doi-asserted-by":"crossref","first-page":"S312","DOI":"10.1093\/bioinformatics\/18.suppl_1.S312","volume":"18","author":"M. H\u00f6hl","year":"2002","unstructured":"M. H\u00f6hl, S. Kurtz, and E. Ohlebusch. Efficient multiple genome alignment. Bioinformatics, 18:S312\u2013S320, 2002.","journal-title":"Bioinformatics"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1016\/0022-2836(91)90938-3","volume":"221","author":"M.-Y. Leung","year":"1991","unstructured":"M.-Y. Leung, B.E. Blaisdell, C. Burge, and S. Karlin. An efficient algorithm for identifying matches with errors in multiple long molecular sequences. Journal of Molecular Biology, 221:1367\u20131378, 1991.","journal-title":"Journal of Molecular Biology"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1093\/bioinformatics\/17.5.391","volume":"17","author":"W. Miller","year":"2001","unstructured":"W. Miller. Comparison of genomic DNA sequences: Solved and unsolved problems. Bioinformatics, 17:391\u2013397, 2001.","journal-title":"Bioinformatics"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1093\/bioinformatics\/16.10.948","volume":"16","author":"B. Morgenstern","year":"2000","unstructured":"B. Morgenstern. A space-efficient algorithm for aligning large genomic sequences. Bioinformatics 16:948\u2013949, 2000.","journal-title":"Bioinformatics"},{"issue":"4","key":"1_CR14","first-page":"599","volume":"54","author":"E.W. Myers","year":"1992","unstructured":"E.W. Myers and X. Huang. An O(n\n                        2 log n) restriction map comparison and search algorithm. Bulletin of Mathematical Biology, 54(4):599\u2013618, 1992.","journal-title":"Bulletin of Mathematical Biology"},{"key":"1_CR15","unstructured":"E.W. Myers and W. Miller. Chaining multiple-alignment fragments in sub-quadratic time. Proc. 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 38\u201347, 1995."},{"key":"1_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational geometry: An introduction","author":"F.P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos. Computational geometry: An introduction. Springer-Verlag, New York, 1985."},{"issue":"10","key":"1_CR17","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1101\/gr.10.4.577","volume":"4","author":"S. Schwartz","year":"2000","unstructured":"S. Schwartz, Z. Zhang, K.A. Frazer, A. Smit, C. Riemer, J. Bouck, R. Gibbs, R. Hardison, and W. Miller. PipMaker\u2014A web server for aligning two genomic DNA sequences., Genome Research, 4(10):577\u2013586, 2000.","journal-title":"Genome Research"},{"issue":"3","key":"1_CR18","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80\u201382, 1977.","journal-title":"Information Processing Letters"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1137\/0214019","volume":"14","author":"D.E. Willard","year":"1985","unstructured":"D.E. Willard. New data structures for orthogonal range queries. SIAM Journal of Computing, 14:232\u2013253, 1985.","journal-title":"SIAM Journal of Computing"},{"key":"1_CR20","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1089\/cmb.1994.1.51","volume":"1","author":"Z. Zhang","year":"1994","unstructured":"Z. Zhang, B. Raghavachari, R. Hardison, and W. Miller. Chaining multiple-alignment blocks. Journal of Computational Biology, 1:51\u201364, 1994.","journal-title":"Journal of Computational Biology"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44888-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,15]],"date-time":"2019-02-15T22:31:49Z","timestamp":1550269909000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44888-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540403111","9783540448884"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-44888-8_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}