{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,31]],"date-time":"2025-08-31T23:32:16Z","timestamp":1756683136908},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540200765"},{"type":"electronic","value":"9783540397632"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39763-2_1","type":"book-chapter","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T16:49:30Z","timestamp":1277484570000},"page":"1-16","source":"Crossref","is-referenced-by-count":11,"title":["A Local Chaining Algorithm and Its Applications in Comparative Genomics"],"prefix":"10.1007","author":[{"given":"Mohamed Ibrahim","family":"Abouelhoda","sequence":"first","affiliation":[]},{"given":"Enno","family":"Ohlebusch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_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":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/3-540-45784-4_35","volume-title":"Algorithms in Bioinformatics","author":"M.I. Abouelhoda","year":"2002","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: The enhanced suffix array and its applications to genome analysis. In: Guig\u00f3, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol.\u00a02452, pp. 449\u2013463. Springer, Heidelberg (2002)"},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S.F. Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: A basic local alignment search tool. J. Mol. Biol.\u00a0215, 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1101\/gr.10.7.950","volume":"10","author":"S. Batzoglou","year":"2001","unstructured":"Batzoglou, S., Pachter, L., Mesirov, J.P., Berger, B., Lander, E.S.: Human and mouse gene structure: Comparative analysis and application to exon prediction. Genome Research\u00a010, 950\u2013958 (2001)","journal-title":"Genome Research"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/98524.98564","volume-title":"6th Annual ACM Symposium on Computational Geometry","author":"J.L. Bently","year":"1990","unstructured":"Bently, J.L.: K-d trees for semidynamic point sets. In: 6th Annual ACM Symposium on Computational Geometry, pp. 187\u2013197. ACM, New York (1990)"},{"issue":"5331","key":"1_CR6","doi-asserted-by":"publisher","first-page":"1453","DOI":"10.1126\/science.277.5331.1453","volume":"277","author":"F.R. Blattner","year":"1997","unstructured":"Blattner, F.R., et al.: The complete genome sequence of Escherichia coli K-12. Science\u00a0277(5331), 1453\u20131474 (1997)","journal-title":"Science"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1101\/gr.789803","volume":"13","author":"N. Bray","year":"2003","unstructured":"Bray, N., Dubchak, I., Pachter, L.: AVID: A global alignment program. Genome Research\u00a013, 97\u2013102 (2003)","journal-title":"Genome Research"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1109\/CSB.2002.1039337","volume-title":"Proceedings of the IEEE Computer Society Bioinformatics Conference","author":"M. Brudno","year":"2002","unstructured":"Brudno, M., Morgenstern, B.: Fast and sensitive alignment of large genomic sequences. In: Proceedings of the IEEE Computer Society Bioinformatics Conference, pp. 138\u2013150. IEEE, Los Alamitos (2002)"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Chain, P., Kurtz, S., Ohlebusch, E., Slezak, T.: An applications-focused review of comparative genomics tools: Capabilities, limitations and future challenges. Briefings in Bioinformatics\u00a04(2) (2003)","DOI":"10.1093\/bib\/4.2.105"},{"issue":"3","key":"1_CR10","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing\u00a017(3), 427\u2013462 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","volume":"27","author":"A.L. Delcher","year":"1999","unstructured":"Delcher, A.L., Kasif, S., Fleischmann, R.D., Peterson, J., White, O., Salzberg, S.L.: Alignment of whole genomes. Nucleic Acids Res.\u00a027, 2369\u20132376 (1999)","journal-title":"Nucleic Acids Res."},{"issue":"11","key":"1_CR12","doi-asserted-by":"publisher","first-page":"2478","DOI":"10.1093\/nar\/30.11.2478","volume":"30","author":"A.L. Delcher","year":"2002","unstructured":"Delcher, A.L., Phillippy, A., Carlton, J., Salzberg, S.L.: Fast algorithms for large-scale genome alignment and comparison. Nucleic Acids Res.\u00a030(11), 2478\u20132483 (2002)","journal-title":"Nucleic Acids Res."},{"issue":"6","key":"1_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/gb-2000-1-6-research0011","volume":"1","author":"J.A. Eisen","year":"2000","unstructured":"Eisen, J.A., Heidelberg, J.F., White, O., Salzberg, S.L.: Evidence for symmetric chromosomal inversions around the replication origin in bacteria. Genome Biology\u00a01(6), 1\u20139 (2000)","journal-title":"Genome Biology"},{"key":"1_CR14","unstructured":"Eppstein, D.: http:\/\/www.ics.uci.edu\/eppstein\/pubs\/p-sparsedp.html"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1145\/146637.146650","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Giancarlo, R., Galil, Z., Italiano, G.F.: Sparse dynamic programming. I:Linear cost functions; II:Convex and concave cost functions. Journal of the ACM\u00a039, 519\u2013567 (1992)","journal-title":"Journal of the ACM"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1038\/35020000","volume":"406","author":"J.F. Heidelberg","year":"2000","unstructured":"Heidelberg, J.F., et al.: DNA sequence of both chromosomes of the cholera pathogen Vibrio cholerae. Nature\u00a0406, 477\u2013483 (2000)","journal-title":"Nature"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1093\/nar\/25.4.701","volume":"25","author":"R. Himmelreich","year":"1997","unstructured":"Himmelreich, R., Plagens, H., Hilbert, H., Reiner, B., Herrmann, R.: Comparative analysis of the genomes of the bacteria Mycoplasma pneumoniae and Mycoplasma genitalium. Nucleic Acids Res.\u00a025, 701\u2013712 (1997)","journal-title":"Nucleic Acids Res."},{"key":"1_CR18","unstructured":"Hughes, D.: Evaluating genome dynamics: The constraints on rearrangements within bacterial genomes. Genome Biology 1(6), reviews 0006.1\u20130006.8 (2000)"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01786986","volume":"15","author":"D.B. Johnson","year":"1982","unstructured":"Johnson, D.B.: A priority queue in which initialization and queue operations take O(log logD) time. Math. Sys. Theory\u00a015, 295\u2013309 (1982)","journal-title":"Math. Sys. Theory"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1101\/gr.10.8.1115","volume":"10","author":"W.J. Kent","year":"2000","unstructured":"Kent, W.J., Zahler, A.M.: Conservation, regulation, synteny, and introns in a large-scale C.briggsae-C.elegans genomic alignment. Genome Research\u00a010, 1115\u20131125 (2000)","journal-title":"Genome Research"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF00263763","volume":"9","author":"D.T. Lee","year":"1977","unstructured":"Lee, D.T., Wong, C.K.: Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica\u00a09, 23\u201329 (1977)","journal-title":"Acta Informatica"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"H\u00f6hl, M., Kurtz, S., Ohlebusch, E.: Efficient multiple genome alignment. In: Proceedings of the 10th International Conference on Intelligent Systems for Molecular Biology. Bioinformatics, vol.\u00a018(Suppl. 1), pp. 312\u2013320 (2002)","DOI":"10.1093\/bioinformatics\/18.suppl_1.S312"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1093\/bioinformatics\/16.10.948","volume":"16","author":"B. Morgenstern","year":"2000","unstructured":"Morgenstern, B.: A space-efficient algorithm for aligning large genomic sequences. Bioinformatics\u00a016, 948\u2013949 (2000)","journal-title":"Bioinformatics"},{"key":"1_CR24","unstructured":"Myers, E.W., Miller, W.: Chaining multiple-alignment fragments in subquadratic time. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 38\u201347 (1995)"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","volume":"85","author":"W.R. Pearson","year":"1988","unstructured":"Pearson, W.R., Lipman, D.J.: Improved tools for biological sequence comparison. Proc. Natl. Acad. Sci. USA\u00a085, 2444\u20132448 (1988)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"1_CR26","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":"Preparata, F.P., Shamos, M.I.: Computational geometry: An introduction. Springer, New York (1985)"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"1673","DOI":"10.1093\/bioinformatics\/18.12.1673","volume":"18","author":"M.A. Roytberg","year":"2002","unstructured":"Roytberg, M.A., Ogurtsov, A.Y., Shabalina, S.A., Kondrashov, A.S.: A hierarchical approach to aligning collinear regions of genomes. Bioinformatics\u00a018, 1673\u20131680 (2002)","journal-title":"Bioinformatics"},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1101\/gr.809403","volume":"13","author":"S. Schwartz","year":"2003","unstructured":"Schwartz, S., Kent, J.K., Smit, A., Zhang, Z., Baertsch, R., Hardison, R., Haussler, D., Miller, W.: Human-mouse alignments with BLASTZ. Genome Research\u00a013, 103\u2013107 (2003)","journal-title":"Genome Research"},{"issue":"4","key":"1_CR29","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1101\/gr.10.4.577","volume":"10","author":"S. Schwartz","year":"2000","unstructured":"Schwartz, S., Zhang, Z., Frazer, K.A., Smit, A., Riemer, C., Bouck, J., Gibbs, R., Hardison, R., Miller, W.: PipMaker\u2014A web server for aligning two genomic DNA sequences. Genome Research\u00a010(4), 577\u2013586 (2000)","journal-title":"Genome Research"},{"issue":"3","key":"1_CR30","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":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters\u00a06(3), 80\u201382 (1977)","journal-title":"Information Processing Letters"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1093\/bioinformatics\/14.8.715","volume":"14","author":"P. Vincens","year":"1998","unstructured":"Vincens, P., Buffat, L., Andre, C., Chevrolat, J.P., Boisvieux, J.F., Hazout, S.: A strategy for finding regions of similarity in complete genome sequences. Bioinformatics\u00a014, 715\u2013725 (1998)","journal-title":"Bioinformatics"},{"key":"1_CR32","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1089\/cmb.1994.1.51","volume":"1","author":"Z. Zhang","year":"1994","unstructured":"Zhang, Z., Raghavachari, B., Hardison, R.C., Miller, W.: Chaining multiplealignment blocks. J. Computational Biology\u00a01, 51\u201364 (1994)","journal-title":"J. Computational Biology"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39763-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T08:52:30Z","timestamp":1559206350000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39763-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540200765","9783540397632"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39763-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}