{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T08:33:27Z","timestamp":1780389207100,"version":"3.54.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"4-5","license":[{"start":{"date-parts":[[1994,11,1]],"date-time":"1994-11-01T00:00:00Z","timestamp":783648000000},"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":[[1994,11]]},"DOI":"10.1007\/bf01185431","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T11:12:30Z","timestamp":1108725150000},"page":"327-344","source":"Crossref","is-referenced-by-count":114,"title":["Sublinear approximate string matching and biological applications"],"prefix":"10.1007","volume":"12","author":[{"given":"W. I.","family":"Chang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"E. L.","family":"Lawler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01185431_CR1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A. V. Aho","year":"1975","unstructured":"A. V. Aho and M. J. Corasick, Efficient String Matching: An Aid to Bibliographic Search,Comm. ACM 18 (1975), 333\u2013340.","journal-title":"Comm. ACM"},{"key":"BF01185431_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), 403\u2013410.","journal-title":"J. Molecular Biology"},{"key":"BF01185431_CR3","series-title":"NATO ASI Series F, Vol. 12","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words","author":"A. Apostolico","year":"1985","unstructured":"A. Apostolico, The Myriad Virtues of Subword Trees, in A. Apostolico and Z. Galil, eds.,Combinatorial Algorithms on Words, NATO ASI Series F, Vol. 12, Springer-Verlag, New York, 1985, pp. 85\u201396."},{"key":"BF01185431_CR4","unstructured":"W. I. Chang, Fast Implementation of the Schieber-Vishkin Lowest Common Ancestor Algorithm, Computer program, 1990."},{"key":"BF01185431_CR5","volume-title":"Ph.D. thesis","author":"W. I. Chang","year":"1991","unstructured":"W. I. Chang, Approximate Pattern Matching and Biological Applications, Ph.D. thesis, University of California, Berkeley, August 1991. Also available as Computer Science Division Reports UCB\/CSD 91\/653-654."},{"key":"BF01185431_CR6","volume-title":"Lecture Notes in Computer Science","author":"W. I. Chang","year":"1994","unstructured":"W. I. Chang, Approximate String Matching and Local Similarity,Proc. Fifth Annual Symposium on Combinatorial Pattern Matching, Asilomar, CA, June 5\u20138, 1994, Lecture Notes in Computer Science, Springer-Verlag, Berlin, in press."},{"key":"BF01185431_CR7","first-page":"175","volume-title":"Lecture Notes in Computer Science, Vol. 644","author":"W. I. Chang","year":"1992","unstructured":"W. I. Chang and J. Lampe, Theoretical and Empirical Comparisons of Approximate String Matching Algorithms,Proc. Third Annual Symposium on Combinatorial Pattern Matching, Tucson, AZ, April 29\u2013May 1, 1992, Lecture Notes in Computer Science, Vol. 644, Springer-Verlag, Berlin, 1992, pp. 175\u2013184."},{"key":"BF01185431_CR8","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":"BF01185431_CR9","unstructured":"W. I. Chang and E. L. Lawler, Approximate String Matching and Biological Sequence Analysis (poster),Human Genome II Official Program and Abstracts, San Diego, CA, Oct. 22\u201324, 1990, p. 24."},{"issue":"1","key":"BF01185431_CR10","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1093\/nar\/14.1.141","volume":"14","author":"B. Clift","year":"1986","unstructured":"B. Clift, D. Haussler, R. McConnell, T. D. Schneider, and G. D. Stormo, Sequence Landscapes,Nucleic Acids Res. 14(1) (1986), 141\u2013158.","journal-title":"Nucleic Acids Res."},{"key":"BF01185431_CR11","first-page":"26","volume-title":"Proc. TAPSOFT '87, Lecture Notes in Computer Science, Vol. 249","author":"M. Crochemore","year":"1988","unstructured":"M. Crochemore, Longest Common Factor of Two Words,Proc. TAPSOFT '87, Lecture Notes in Computer Science, Vol. 249, Springer-Verlag, Berlin, 1988, pp. 26\u201336."},{"key":"BF01185431_CR12","volume-title":"Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences, Methods in Enzymology, Volume 183","year":"1990","unstructured":"R. F. Doolittle, ed.Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences, Methods in Enzymology, Volume 183, Academic Press, New York, 1990."},{"issue":"4","key":"BF01185431_CR13","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/63334.63341","volume":"32","author":"E. R. Fiala","year":"1989","unstructured":"E. R. Fiala and D. H. Greene, Data Compression with Finite Windows,Comm. ACM 32(4) (1989), 490\u2013505.","journal-title":"Comm. ACM"},{"key":"BF01185431_CR14","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0885-064X(88)90008-8","volume":"4","author":"Z. Galil","year":"1988","unstructured":"Z. Galil and R. Giancarlo, Data Structures and Algorithms for Approximate String Matching,J. Complexity 4 (1988), 33\u201372.","journal-title":"J. Complexity"},{"issue":"6","key":"BF01185431_CR15","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1137\/0219067","volume":"19","author":"Z. Galil","year":"1990","unstructured":"Z. Galil and K. Park, An Improved Algorithm for Approximate String Matching,SIAM J. Comput. 19(6) (1990), 989\u2013999.","journal-title":"SIAM J. Comput."},{"key":"BF01185431_CR16","volume-title":"Handbook of Algorithms and Data Structures: in Pascal and C","author":"G. H. Gonnet","year":"1991","unstructured":"G. H. Gonnet and R. Baeza-Yates,Handbook of Algorithms and Data Structures: in Pascal and C, 2nd edn., Addison-Wesely, Reading, MA, 1991.","edition":"2nd edn."},{"key":"BF01185431_CR17","volume-title":"Lecture Notes","author":"D. Gusfield","year":"1989","unstructured":"D. Gusfield,Efficient Algorithms for String Manipulation and Pattern Matching, Lecture Notes, University of California, Davis, 1989."},{"key":"BF01185431_CR18","unstructured":"D. Gusfield, K. Balasubramanian, and D. Naor, Parametric Optimization of Sequence Alignment,Proc. Third Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 1992, pp. 432\u2013439."},{"key":"BF01185431_CR19","unstructured":"D. Gusfield, G. M. Landau, and B. Schieber, An Efficient Algorithm for the All Pairs Suffix-Prefix Problem,Proc. Sequences 91, Italy, July 1991."},{"issue":"1","key":"BF01185431_CR20","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/S0888-7543(05)80277-0","volume":"14","author":"X. Huang","year":"1992","unstructured":"X. Huang, A Contig Assembly Program Based on Sensitive Detection of Fragment Overlaps,Genomics 14(1) (1992), 18\u201325.","journal-title":"Genomics"},{"key":"BF01185431_CR21","first-page":"230","volume-title":"Lecture Notes in Computer Science, Vol. 644","author":"L. C. Hui","year":"1992","unstructured":"L. C. Hui, Color Set Size Problem with Applications to String Matching,Proc. Third Annual Symposium on Combinatorial Pattern Matching, Tucson, AZ, April 29\u2013May 1, 1992, Lecture Notes in Computer Science, Vol. 644, Springer-Verlag, Berlin, pp. 230\u2013243."},{"key":"BF01185431_CR22","unstructured":"P. Jokinen, J. Tarhio, and E. Ukkonen, A Comparison of Approximate String Matching Algorithms, Manuscript, 1990,"},{"key":"BF01185431_CR23","doi-asserted-by":"crossref","unstructured":"S. Kannan and T. Warnow, Inferring Evolutionary History from DNA Sequences,Proc. 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis, MO, October 1990, pp. 362\u2013371.","DOI":"10.1109\/FSCS.1990.89555"},{"key":"BF01185431_CR24","first-page":"133","volume-title":"Mathematical Methods for DNA Sequences","author":"S. Karlin","year":"1989","unstructured":"S. Karlin, F. Ost, and B. E. Blaisdell, Patterns in DNA and Amino Acid Sequences and Their Statistical Significance, in M. S. Waterman, ed.,Mathematical Methods for DNA Sequences, CRC Press, Boca Raton, FL, 1989, pp. 133\u2013157."},{"key":"BF01185431_CR25","volume-title":"Lecture notes","author":"R. M. Karp","year":"1988","unstructured":"R. M. Karp,Probabilistic Analysis of Algorithms, Lecture notes, University of California, Berkeley, Spring 1988; Fall 1989."},{"key":"BF01185431_CR26","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R. M. Karp","year":"1987","unstructured":"R. M. Karp and M. O. Rabin, Efficient Randomized Pattern-Matching Algorithms,IBM J. Res. Develop 31 (1987), 249\u2013260.","journal-title":"IBM J. Res. Develop"},{"key":"BF01185431_CR27","volume-title":"Ph.D. thesis","author":"J. D. Kececioglu","year":"1991","unstructured":"J. D. Kececioglu, Exact and Approximate Algorithms for DNA Sequence Reconstruction, Ph.D. thesis, University of Arizona, Tucson, 1991. Also available as Technical Report TR91-26, Computer Science Department, University of Arizona, Tucson."},{"issue":"2","key":"BF01185431_CR28","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), 323\u2013350.","journal-title":"SIAM J. Comput."},{"key":"BF01185431_CR29","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 withk Differences,J. Comp. System Sci. 37 (1988), 63\u201378.","journal-title":"J. Comp. System Sci."},{"key":"BF01185431_CR30","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G. M. Landau","year":"1989","unstructured":"G. M. Landau and U. Vishkin, Fast Parallel and Serial Approximate String Matching,J. Algorithms 10 (1989), 157\u2013169.","journal-title":"J. Algorithms"},{"key":"BF01185431_CR31","first-page":"126","volume":"6","author":"V. Levenshtein","year":"1966","unstructured":"V. Levenshtein, Binary Codes Capable of Correcting Deletions, Insertions and Reversals,Soviet Phys. Dokl. 6 (1966), 126\u2013136.","journal-title":"Soviet Phys. Dokl."},{"issue":"2","key":"BF01185431_CR32","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E. M. McCreight","year":"1976","unstructured":"E. M. McCreight, A Space-Economical Suffix Tree Construction Algorithm,J. Assoc. Comput. Mach. 23(2) (1976), 262\u2013272.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01185431_CR33","volume-title":"Technical Report TR90-25","author":"E. W. Myers","year":"1991","unstructured":"E. W. Myers, A Sublinear Algorithm for Approximate Keyword Matching, Technical Report TR90-25, Computer Science Department, University of Arizona, Tucson, September 1991."},{"key":"BF01185431_CR34","unstructured":"National Center for Human Genome Research,Understanding Our Genetic Inheritance (The U.S. Human Genome Project: The First Five Years FY 1991\u20131995), NIH Publication No. 90-1580, April 1990."},{"key":"BF01185431_CR35","unstructured":"K. Park, Fast String Matching On the Average, Manuscript, 1990."},{"key":"BF01185431_CR36","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. Nat. Acad. Sci. USA 85 (1988), 2444\u20132448.","journal-title":"Proc. Nat. Acad. Sci. USA"},{"issue":"1","key":"BF01185431_CR37","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1093\/nar\/12.1Part1.307","volume":"12","author":"H. Peltola","year":"1984","unstructured":"H. Peltola, H. S\u00f6derlund, and E. Ukkonen, SEQAID: A DNA Sequence Assembling Program Based on a Mathematical Model,Nucleic Acids Res. 12(1) (1984), 307\u2013321.","journal-title":"Nucleic Acids Res."},{"issue":"1","key":"BF01185431_CR38","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/322234.322237","volume":"28","author":"M. Rodeh","year":"1981","unstructured":"M. Rodeh, V. R. Pratt, and S. Even, Linear Algorithms for Data Compression via String Matching,J. Assoc. Comput. Mach. 28(1) (1981), 16\u201324.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01185431_CR39","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","year":"1983","unstructured":"D. Sankoff and J. B. Kruskal, eds.,Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, MA, 1983."},{"issue":"6","key":"BF01185431_CR40","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin, On Finding Lowest Common Ancestors: Simplification and Parallelization,SIAM J. Comput. 17(6) (1988), 1253\u20131262.","journal-title":"SIAM J. Comput."},{"key":"BF01185431_CR41","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), 359\u2013373.","journal-title":"J. Algorithms"},{"key":"BF01185431_CR42","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), 132\u2013137.","journal-title":"J. Algorithms"},{"key":"BF01185431_CR43","unstructured":"E. Ukkonen, Personal communications."},{"key":"BF01185431_CR44","unstructured":"E. Ukkonen and D. Wood, Approximate String Matching with Suffix Automata, Report A-1990-4, Department of Computer Science, University of Helsinki, April 1990."},{"key":"BF01185431_CR45","first-page":"53","volume-title":"Mathematical Methods for DNA Sequences","author":"M. S. Waterman","year":"1989","unstructured":"M. S. Waterman, Sequence Alignments, in M. S. Waterman, ed.,Mathematical Methods for DNA Sequences, CRC Press, Boca Raton, FL, 1989, pp. 53\u201392."},{"key":"BF01185431_CR46","doi-asserted-by":"crossref","first-page":"6090","DOI":"10.1073\/pnas.89.13.6090","volume":"89","author":"M. S. Waterman","year":"1992","unstructured":"M. S. Waterman, M. Eggert, and E. Lander, Parametric Sequence Comparisons,Proc. Nat. Acad. Sci. USA 89 (1992), 6090\u20136093.","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"BF01185431_CR47","doi-asserted-by":"crossref","unstructured":"P. Weiner, Linear Pattern Matching Algorithms,Proc. IEEE Symposium on Switching and Automata Theory, 1973, pp. 1\u201311.","DOI":"10.1109\/SWAT.1973.13"},{"key":"BF01185431_CR48","volume-title":"Technical Report TR91-20","author":"S. Wu","year":"1991","unstructured":"S. Wu, U. Manber, and E. Myers, Improving the Running Times for Some String Matching Problems, Technical Report TR91-20, Computer Science Department, University of Arizona, Tucson, August 1991."},{"key":"BF01185431_CR49","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), 368\u2013387.","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185431.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01185431\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T12:41:39Z","timestamp":1556714499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01185431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,11]]},"references-count":49,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[1994,11]]}},"alternative-id":["BF01185431"],"URL":"https:\/\/doi.org\/10.1007\/bf01185431","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,11]]}}}