{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T20:54:10Z","timestamp":1761512050647},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[1995,2,1]],"date-time":"1995-02-01T00:00:00Z","timestamp":791596800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,2]]},"DOI":"10.1007\/bf01188583","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T21:03:45Z","timestamp":1108674225000},"page":"106-134","source":"Crossref","is-referenced-by-count":23,"title":["Linear-space algorithms that build local alignments from fragments"],"prefix":"10.1007","volume":"13","author":[{"given":"Kun -Mao","family":"Chao","sequence":"first","affiliation":[]},{"given":"W.","family":"Miller","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01188583_CR1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S. Altschul","year":"1990","unstructured":"Altschul, S., W. Gish, W. Miller, E. Myers, and D. Lipman (1990). A basic local alignment search tool.J. Mol Biol,215, 403\u2013410.","journal-title":"J. Mol Biol"},{"key":"BF01188583_CR2","first-page":"247","volume":"4","author":"M. Boguski","year":"1992","unstructured":"Boguski, M., R. C. Hardison, S. Schwartz, and W. Miller (1992). Analysis of conserved domains and sequence motifs in cellular regulatory proteins and locus control regions using new software tools for multiple alignment and visualization.The New Biologist,4, 247\u2013260.","journal-title":"The New Biologist"},{"key":"BF01188583_CR3","first-page":"481","volume":"8","author":"K.-M. Chao","year":"1992","unstructured":"Chao, K.-M., W. R. Pearson, and W. Miller (1992). Aligning two sequences within a specified diagonal band.CABIOS,8, 481\u2013487.","journal-title":"CABIOS"},{"key":"BF01188583_CR4","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/BF02460648","volume":"55","author":"K.-M. Chao","year":"1993","unstructured":"Chao, K.-M., R. C. Hardison, and W. Miller (1993). Constrained sequence alignment.Bull. Math. Biol.,55, 503\u2013524.","journal-title":"Bull. Math. Biol."},{"key":"BF01188583_CR5","series-title":"Methods in Enzymology, Vol. 183","volume-title":"Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences","year":"1990","unstructured":"Doolittle, R. F., ed. (1990).Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences. Methods in Enzymology, Vol. 183. Academic Press, New York."},{"key":"BF01188583_CR6","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1145\/146637.146650","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Z. Galil, R. Giancarlo, and G. F. Italiano (1992a). Sparse dynamic programming. I: Linear cost functions.J. Assoc. Comput. Mach.,39, 519\u2013545.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01188583_CR7","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1145\/146637.146656","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Z. Galil, R. Giancarlo, and G. F. Italiano (1992b). Sparse dynamic programming. II: Convex and concave cost functions.J. Assoc. Comput. Mach.,39, 546\u2013567.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01188583_CR8","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/BF02100085","volume":"21","author":"D. F. Feng","year":"1985","unstructured":"Feng, D. F., M. S. Johnson, and R. F. Doolittle (1985). Aligning amino acid sequences: comparison commonly used methods.J. Mol. Evol.,21, 112\u2013125.","journal-title":"J. Mol. Evol."},{"key":"BF01188583_CR9","doi-asserted-by":"crossref","first-page":"1382","DOI":"10.1073\/pnas.80.5.1382","volume":"80","author":"W. M. Fitch","year":"1983","unstructured":"Fitch, W. M., and T. F. Smith (1983). Optimal sequence alignments,Proc Nat. Acad. Sci. USA,80, 1382\u20131386.","journal-title":"Proc Nat. Acad. Sci. USA"},{"key":"BF01188583_CR10","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0304-3975(89)90101-1","volume":"64","author":"Z. Galil","year":"1989","unstructured":"Galil, Z., and R. Giancarlo (1989). Speeding up dynamic programming with applications to molecular biology.Theor. Comput. Sci.,64, 107\u2013118.","journal-title":"Theor. Comput. Sci."},{"key":"BF01188583_CR11","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(92)90135-3","volume":"92","author":"Z. Galil","year":"1992","unstructured":"Galil, Z., and K. Park (1992). Dynamic programming with convexity, concavity, and sparsity.Theoret. Comput. Sci.,92, 49\u201376.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01188583_CR12","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1093\/nar\/10.1.247","volume":"10","author":"W. B. Goad","year":"1982","unstructured":"Goad, W. B., and M. I. Kanehisa (1982). Pattern recognition in nucleic acid sequences. I: A general method for finding local homologies and symmetries.Nucleic Acids Res.,10, 247\u2013263.","journal-title":"Nucleic Acids Res."},{"key":"BF01188583_CR13","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O. Gotoh","year":"1982","unstructured":"Gotoh, O. (1982). An improved algorithm for matching biological sequences.J. Mol. Biol.,162, 705\u2013708.","journal-title":"J. Mol. Biol."},{"key":"BF01188583_CR14","first-page":"146","volume-title":"Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences. Methods in Enzymology, Vol. 183","author":"M. Gribskov","year":"1990","unstructured":"Gribskov, M., R. Luthy, and D. Eisenberg (1990). Profile analysis. In R. F. Doolittle (ed.),Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences. Methods in Enzymology, Vol. 183. Academic Press, New York, pp. 146\u2013159."},{"key":"BF01188583_CR15","first-page":"73","volume":"10","author":"R. C. Hardison","year":"1993","unstructured":"Hardison, R. C., and W. Miller (1993). Use of long sequence alignments to study the evolution and regulation of mammalian globin gene clusters.Mol. Biol. Evol.,10, 73\u2013102.","journal-title":"Mol. Biol. Evol."},{"key":"BF01188583_CR16","doi-asserted-by":"crossref","first-page":"1265","DOI":"10.1093\/nar\/21.5.1265","volume":"21","author":"R. C. Hardison","year":"1993","unstructured":"Hardison, R. C., J. Xu, J. Jackson, J. Mansberger, O. Selifonova, B. Grotch, H. Petrykowska, J. Biesecker, and W. Miller (1993a). Comparative analysis of the locus control region of the rabbit\u03b2-like globin gene cluster. HS3 increases transient expression of an embryonic \u03b5-globin gene.Nucleic Acids Res.,21, 1265\u20131272.","journal-title":"Nucleic Acids Res."},{"key":"BF01188583_CR17","doi-asserted-by":"crossref","first-page":"163","DOI":"10.3109\/10425179309015629","volume":"4","author":"R. C. Hardison","year":"1993","unstructured":"Hardison, R. C., K.-M. Chao, M. Adamkiewicz, D. Price, J. Jackson, T. Zeigler, N. Stojanovic, and W. Miller (1993b). Positive and negative regulatory elements of the rabbit \u03b5-globin gene revealed by an improved multiple alignment program and functional analysis.DNA Sequence \u2014 J. DNA Sequencing and Mapping,4, 163\u2013176.","journal-title":"DNA Sequence \u2014 J. DNA Sequencing and Mapping"},{"key":"BF01188583_CR18","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","volume":"28","author":"D. S. Hirschberg","year":"1975","unstructured":"Hirschberg, D. S. (1975). A linear space algorithm for computing maximal common subsequences.Comm. ACM,28, 341\u2013343.","journal-title":"Comm. ACM"},{"key":"BF01188583_CR19","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0196-8858(91)90017-D","volume":"12","author":"X. Huang","year":"1991","unstructured":"Huang, X., and W. Miller (1991). A time-efficient, linear-space local similarity algorithm.Adv. in Appl. Math.,12, 337\u2013357.","journal-title":"Adv. in Appl. Math."},{"key":"BF01188583_CR20","first-page":"373","volume":"6","author":"X. Huang","year":"1990","unstructured":"Huang, X., R. C. Hardison, and W. Miller (1990). A space-efficient algorithm for local similarities.CABIOS 6, 373\u2013381.","journal-title":"CABIOS"},{"key":"BF01188583_CR21","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF02459948","volume":"50","author":"W. Miller","year":"1988","unstructured":"Miller, W., and E. Myers (1988). Sequence comparison with concave weighting functions.Bull. Math. Biol.,50, 97\u2013120.","journal-title":"Bull. Math. Biol."},{"key":"BF01188583_CR22","first-page":"599","volume":"54","author":"E. Myers","year":"1992","unstructured":"Myers, E., and X. Huang (1992). An0(N 2 logN) restriction map comparison and search algorithm.Bull. Math. Biol.,54, 599\u2013618.","journal-title":"Bull. Math. Biol."},{"key":"BF01188583_CR23","first-page":"11","volume":"4","author":"E. Myers","year":"1988","unstructured":"Myers, E., and W. Miller (1988). Optimal alignments in linear space.CABIOS,4, 11\u201317.","journal-title":"CABIOS"},{"key":"BF01188583_CR24","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S. B. Needleman","year":"1970","unstructured":"Needleman, S. B., and C. D. Wunsch (1970). A general method applicable to the search for similarities in the amino acid sequences of two proteins.J. Mol. Biol.,48, 443\u2013453.","journal-title":"J. Mol. Biol."},{"key":"BF01188583_CR25","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/0022-2836(92)91008-D","volume":"224","author":"S. Pascarella","year":"1992","unstructured":"Pascarella, S., and P. Argos (1992). Analysis of insertions\/deletions in protein structures.J. Mol. Biol.,224, 461\u2013471.","journal-title":"J. Mol. Biol."},{"key":"BF01188583_CR26","series-title":"Methods in Enzymology, Vol. 183","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0076-6879(90)83007-V","volume-title":"Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences","author":"W. R. Pearson","year":"1990","unstructured":"Pearson, W. R. (1990). Rapid and sensitive synthesis comparison with FASTP and FASTA. In R. F. Doolittle (ed.),Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences. Methods in Enzymology, Vol. 183. Academic Press, New York, pp. 63\u201395."},{"key":"BF01188583_CR27","doi-asserted-by":"crossref","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","volume":"85","author":"W. R. Pearson","year":"1988","unstructured":"Pearson, W. R., and D. Lipman (1988). Improved tool or biological sequence comparison.Proc. Nat. Acad. Sci. USA,85, 2444\u20132448.","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"BF01188583_CR28","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"Pugh, W. (1990). Slip lists: a probabilistic alternative to balanced trees.Comm. ACM,33, 668\u2013676.","journal-title":"Comm. ACM"},{"key":"BF01188583_CR29","volume-title":"Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparisons","year":"1983","unstructured":"Sankoff, D., and J. B. Kruskal (eds.) (1983).Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparisons. Addison-Wesley, Reading, MA."},{"key":"BF01188583_CR30","doi-asserted-by":"crossref","first-page":"4663","DOI":"10.1093\/nar\/19.17.4663","volume":"19","author":"S. Schwartz","year":"1991","unstructured":"Schwartz, S., W. Miller, C.-M. Yang, and R. C. Hardison (1991). Software tools for analyzing pairwise sequence alignments.Nucleic Acids Res.,19, 4663\u20134667.","journal-title":"Nucleic Acids Res."},{"key":"BF01188583_CR31","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/BF02459499","volume":"46","author":"P. H. Sellers","year":"1984","unstructured":"Sellers, P. H. (1984). Pattern recognition in genetic sequences by mismatch density.Bull. Math. Biol.,46, 501\u2013514.","journal-title":"Bull. Math. Biol."},{"key":"BF01188583_CR32","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T. F. Smith","year":"1981","unstructured":"Smith, T. F., and M. S. Waterman (1981). Identification of common molecular sequences.J. Mol. Biol.,147, 195\u2013197.","journal-title":"J. Mol. Biol."},{"key":"BF01188583_CR33","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/BF01733210","volume":"18","author":"T. F. Smith","year":"1981","unstructured":"Smith, T. F., M. S. Waterman, and W. M. Fitch (1981). Comparative biosequence metrics.J. Mol. Evol.,18, 38\u201346.","journal-title":"J. Mol. Evol."},{"key":"BF01188583_CR34","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. A. Wagner","year":"1974","unstructured":"Wagner, R. A., and M. J. Fischer (1974). The string-to-string correction problem.J. Assoc. Comput. Mach. 21, 168\u2013173.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01188583_CR35","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/S0022-5193(84)80037-5","volume":"108","author":"M. S. Waterman","year":"1984","unstructured":"Waterman, M. S. (1984). Efficient sequence alignment algorithms.J. Theoret. Biol.,108, 333\u2013337.","journal-title":"J. Theoret. Biol."},{"key":"BF01188583_CR36","first-page":"53","volume-title":"Mathematical Methods for DNA Sequences","author":"M. S. Waterman","year":"1989","unstructured":"Waterman, M. S. (1989). Sequence alignments. In M. S. Waterman, ed.,Mathematical Methods for DNA Sequences. CRC Press, Boca Raton, FL, pp. 53\u201392."},{"key":"BF01188583_CR37","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1016\/0022-2836(87)90478-5","volume":"197","author":"M. S. Waterman","year":"1987","unstructured":"Waterman, M. S., and M. Eggert (1987). A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons.J. Mol. Biol.,197, 723\u2013728.","journal-title":"J. Mol. Biol."},{"key":"BF01188583_CR38","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1073\/pnas.80.3.726","volume":"80","author":"W. Wilbur","year":"1983","unstructured":"Wilbur, W., and D. Lipman (1983). Rapid similarity searches of nucleic acid and protein data banks.Proc. Nat. Acad. Sci. USA,80, 726\u2013730.","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"BF01188583_CR39","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1137\/0144038","volume":"44","author":"W. Wilbur","year":"1984","unstructured":"Wilbur, W., and D. Lipman (1984). The context dependent comparison of biological sequences.SIAM J. Appl. Math.,44, 557\u2013567.","journal-title":"SIAM J. Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188583.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01188583\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188583","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T16:41:44Z","timestamp":1556728904000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01188583"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,2]]},"references-count":39,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1995,2]]}},"alternative-id":["BF01188583"],"URL":"https:\/\/doi.org\/10.1007\/bf01188583","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,2]]}}}