{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:11Z","timestamp":1759638551176},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540580942"},{"type":"electronic","value":"9783540484509"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58094-8_23","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:12:01Z","timestamp":1330269121000},"page":"259-273","source":"Crossref","is-referenced-by-count":39,"title":["Approximate string matching and local similarity"],"prefix":"10.1007","author":[{"given":"William I.","family":"Chang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas G.","family":"Marr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1016\/0022-2836(91)90193-A","volume":"219","author":"S.F. Altschul","year":"1991","unstructured":"S.F. Altschul, Amino Acid Substitution Matrices from an Information Theoretic Perspective, J. Molecular Biology, 219(1991), pp. 555\u2013565.","journal-title":"J. Molecular Biology"},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S.F. Altschul","year":"1990","unstructured":"S.F. Altschul, W. Gish, W. Miller, E.W. Myers, and D.J. Lipman, A Basic Local Alignment Search Tool, J. Molecular Biology, 215(1990), pp. 403\u2013410.","journal-title":"J. Molecular Biology"},{"key":"23_CR3","unstructured":"P. Argos and M. Vingron, Sensitive Comparison of Protein Amino Acid Sequences, in R.F. Doolittle, ed. Methods in Enzymology Volume 183, Academic Press (1990), pp. 352\u2013365."},{"key":"23_CR4","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1093\/protein\/4.4.375","volume":"4","author":"P. Argos","year":"1991","unstructured":"P. Argos, M. Vingron, and G. Vogt, Protein sequence comparison: methods and significance, Protein Engineering 4(1991), pp. 375\u2013383.","journal-title":"Protein Engineering"},{"key":"23_CR5","unstructured":"W.I. Chang, Approximate Pattern Matching and Biological Applications, Ph.D. thesis, U.C. Berkeley, August 1991. Also available as Computer Science Division Reports UCB\/CSD 91\/653\u2013654."},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science 644","first-page":"172","volume-title":"Proc. Combinatorial Pattern Matching '92","author":"W.I. Chang","year":"1992","unstructured":"W.I. Chang and J. Lampe, Theoretical and Empirical Comparisons of Approximate String Matching Algorithms, Proc. Combinatorial Pattern Matching '92, Tucson, AZ, April 29-May 1, 1992, Lecture Notes in Computer Science 644, Springer-Verlag, pp. 172\u2013181."},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"W.I. Chang and E.L. Lawler, Approximate String Matching in Sublinear Expected Time, Proc. 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis, MO, Oct. 22\u201324, 1990, pp. 116\u2013124.","DOI":"10.1109\/FSCS.1990.89530"},{"key":"23_CR8","unstructured":"W.I. Chang and W.L. Lawler, Sublinear Expected Time Approximate String Matching and Biological Applications, Algorithmica, in press."},{"key":"23_CR9","unstructured":"V. Chv\u00e1tal and D. Sankoff, Longest Common Subsequences of Two Random Sequences, Technical Report STAN-CS-75-477, Stanford University, Computer Science Department, 1975."},{"key":"23_CR10","first-page":"345","volume-title":"Atlas of Protein Sequence and Structure vol. 5","author":"M.O. Dayhoff","year":"1979","unstructured":"M.O. Dayhoff, R.M. Schwartz, and B.C. Orcutt, A Model of Evolutionary Change in Proteins, in M.O. Dayhoff, ed., Atlas of Protein Sequence and Structure vol. 5. suppl. 3., Nat. Biomed. Res. Found., Washington, D.C., pp. 345\u2013352, 1979."},{"key":"23_CR11","unstructured":"R.F. Doolittle, ed. Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences, Methods in Enzymology Volume 183, Academic Press (1990)."},{"key":"23_CR12","unstructured":"D.G. George, W.C. Barker, and L.T. Hunt, Mutation Data Matrix and Its Uses, in R.F. Doolittle, ed. Methods in Enzymology Volume 183, Academic Press (1990), pp. 333\u2013351."},{"key":"23_CR13","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1093\/nar\/10.1.247","volume":"10","author":"W.B. Goad","year":"1982","unstructured":"W.B. Goad and M.I. Kanehisa, Pattern Recognition in Nucleic Acid Sequences I, A General Method for Finding Local Homologies and Symmetries, Nucl. Acids Res. 10(1982), pp. 247\u2013263.","journal-title":"Nucl. Acids Res."},{"key":"23_CR14","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O. Gotoh","year":"1982","unstructured":"O. Gotoh, An improved algorithm for matching biological sequences, J. Mol. Biol. 162(1982), pp. 705\u2013708.","journal-title":"J. Mol. Biol."},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"X. Huang, A Contig Assembly Program Based on Sensitive Detection of Fragment Overlaps, Genomics, 1992.","DOI":"10.1016\/S0888-7543(05)80277-0"},{"key":"23_CR16","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0196-8858(91)90017-D","volume":"12","author":"X. Huang","year":"1991","unstructured":"X. Huang and W. Miller, A time-efficient, linear-space local similarity algorithm. Advances in Applied Mathematics 12(1991), pp. 337\u2013357.","journal-title":"Advances in Applied Mathematics"},{"key":"23_CR17","doi-asserted-by":"crossref","first-page":"2264","DOI":"10.1073\/pnas.87.6.2264","volume":"87","author":"S. Karlin","year":"1990","unstructured":"S. Karlin and S.F. Altschul, Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes, Proc. Nat. Acad. Sci., USA, 87(1990), 2264\u20132268.","journal-title":"Proc. Nat. Acad. Sci., USA"},{"issue":"2","key":"23_CR18","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"D.E. Knuth, J.H. Morris, and V.R. Pratt, Fast Pattern Matching in Strings, SIAM J. Comput. 6:2 (1977), pp. 323\u2013350.","journal-title":"SIAM J. Comput."},{"key":"23_CR19","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0022-0000(88)90045-1","volume":"37","author":"G.M. Landau","year":"1988","unstructured":"G.M. Landau and U. Vishkin, Fast String Matching with k Differences, J. Comp. Sys. Sci. 37(1988), pp. 63\u201378.","journal-title":"J. Comp. Sys. Sci."},{"key":"23_CR20","volume-title":"Technical Report TR90-25","author":"E.W. Myers","year":"1991","unstructured":"E.W. Myers (1991a), A Sublinear Algorithm for Approximate Keyword Matching, Technical Report TR90-25, Computer Science Dept., University of Arizona, Tucson, September 1991."},{"key":"23_CR21","volume-title":"Technical Report TR91-29","author":"E.W. Myers","year":"1991","unstructured":"E.W. Myers (1991b), An Overview of Sequence Comparison Algorithms in Molecular Biology, Technical Report TR91-29, Computer Science Dept., University of Arizona, Tucson, December 1991."},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"E.W. Myers, Algorithmic Advances for Searching Biosequence Databases, to appear in S. Suhai, ed., Computational Methods in Genome Research, Plenum Press (1994).","DOI":"10.1007\/978-1-4615-2451-9_10"},{"key":"23_CR23","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S.B. Needleman","year":"1970","unstructured":"S.B. Needleman and C.E. Wunsch, A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins, J. Mol. Biol. 48(1970), pp. 443\u2013453.","journal-title":"J. Mol. Biol."},{"key":"23_CR24","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1016\/0888-7543(91)90071-L","volume":"11","author":"W.R. Pearson","year":"1991","unstructured":"W.R. Pearson, Searching protein sequence libraries: comparison of the sensitivity and selectivity of the Smith-Waterman and FASTA algorithms, Genomics 11(1991), pp. 635\u2013650.","journal-title":"Genomics"},{"key":"23_CR25","doi-asserted-by":"crossref","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","volume":"85","author":"W.R. Pearson","year":"1988","unstructured":"W.R. Pearson and D.J. Lipman, Improved tools for biological sequence comparison, Proc. Natl. Acad. Sci. USA 85(1988), pp. 2444\u20132448.","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"23_CR26","unstructured":"D. Sankoff and J.B. Kruskal, eds., Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley (1983)."},{"key":"23_CR27","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P.H. Sellers","year":"1980","unstructured":"P.H. Sellers, The Theory and Computation of Evolutionary Distances: Pattern Recognition, J. Algorithms 1(1980), pp. 359\u2013373.","journal-title":"J. Algorithms"},{"key":"23_CR28","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/BF02459499","volume":"46","author":"P.H. Sellers","year":"1984","unstructured":"P.H. Sellers, Pattern Recognition in Genetic Sequences by Mismatch Density, Bull. Math. Biol. 46(1984), pp. 501\u2013514.","journal-title":"Bull. Math. Biol."},{"key":"23_CR29","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T.F. Smith","year":"1981","unstructured":"T.F. Smith and M.S. Waterman, Identification of Common Molecular Subsequences, J. Mol. Biol. 147(1981), pp. 195\u2013197.","journal-title":"J. Mol. Biol."},{"key":"23_CR30","volume-title":"MPsrch version 1.3","author":"S.S. Sturrock","year":"1993","unstructured":"S.S. Sturrock and J.F. Collins (1993), MPsrch version 1.3, Biocomputing Research Unit, University of Edinburgh, UK."},{"key":"23_CR31","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","volume":"6","author":"E. Ukkonen","year":"1985","unstructured":"E. Ukkonen, Finding Approximate Patterns in Strings, J. Algorithms 6(1985), pp. 132\u2013137.","journal-title":"J. Algorithms"},{"key":"23_CR32","unstructured":"M. Vingron and M.S. Waterman, Parametric Sequence Alignments and Penalty Choice: Case Studies, manuscript, 1993."},{"key":"23_CR33","unstructured":"M.S. Waterman, Sequence Alignments, in M.S. Waterman, ed., Mathematical Methods for DNA Sequences, CRC Press (1989), pp. 53\u201392."},{"key":"23_CR34","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1016\/0022-2836(87)90478-5","volume":"197","author":"M.S. Waterman","year":"1987","unstructured":"M.S. Waterman and M. Eggert, A new algorithm for best subsequence alignments with applicaiton to tRNA-rRNA comparison, J. Mol. Biol. 197(1987), pp. 723\u2013728.","journal-title":"J. Mol. Biol."},{"key":"23_CR35","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/135239.135244","volume":"35","author":"S. Wu","year":"1992","unstructured":"S. Wu and U. Manber, Fast Text Searching Allowing Errors, Comm. ACM 35(1992), pp. 83\u201391.","journal-title":"Comm. ACM"},{"key":"23_CR36","volume-title":"Technical Report TR92-36","author":"S. Wu","year":"1992","unstructured":"S. Wu, U. Manber, and E.W. Myers, A Sub-quadratic Algorithm for Approximate Limited Expression Matching, Technical Report TR92-36, Computer Science Dept., University of Arizona, Tucson, December 1992."},{"key":"23_CR37","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1137\/0208029","volume":"8","author":"A.C. Yao","year":"1979","unstructured":"A.C. Yao, The Complexity of Pattern Matching for a Random String, SIAM J. Comput. 8(1979), pp. 368\u2013387.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58094-8_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:10:55Z","timestamp":1619572255000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58094-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580942","9783540484509"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-58094-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}