{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T10:20:50Z","timestamp":1790936450086,"version":"4.1.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"S11","license":[{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T00:00:00Z","timestamp":1559779200000},"content-version":"vor","delay-in-days":5,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1186\/s12859-019-2819-0","type":"journal-article","created":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T21:02:40Z","timestamp":1559768560000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":59,"title":["String correction using the Damerau-Levenshtein distance"],"prefix":"10.1186","volume":"20","author":[{"given":"Chunchun","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sartaj","family":"Sahni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,6,6]]},"reference":[{"issue":"8","key":"2819_CR1","first-page":"707","volume":"10","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein VI. Binary codes capable of correcting deletions, insertions, and reversals. Sov Phys Dokl. 1966; 10(8):707\u201310.","journal-title":"Sov Phys Dokl"},{"issue":"3","key":"2819_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1145\/363958.363994","volume":"7","author":"FJ Damerau","year":"1964","unstructured":"Damerau FJ. A technique for computer detection and correction of spelling errors. Commun ACM. 1964; 7(3):171\u20136.","journal-title":"Commun ACM"},{"issue":"2","key":"2819_CR3","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier D. The complexity of some problems on subsequences and supersequences. J ACM. 1978; 25(2):322\u201336.","journal-title":"J ACM"},{"key":"2819_CR4","doi-asserted-by":"publisher","DOI":"10.1515\/9783110198164","volume-title":"An Introduction to Abstract Algebra","author":"DJS Robinson","year":"2003","unstructured":"Robinson DJS. An Introduction to Abstract Algebra. Berlin: Walter de Gruyter; 2003, pp. 255\u20137."},{"issue":"406","key":"2819_CR5","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1080\/01621459.1989.10478785","volume":"84","author":"MA Jaro","year":"1989","unstructured":"Jaro MA. Advances in record-linkage methodology as applied to matching the 1985 census of Tampa, Florida. J Am Stat Assoc. 1989; 84(406):414\u201320.","journal-title":"J Am Stat Assoc"},{"issue":"3","key":"2819_CR6","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970; 48(3):443\u201353.","journal-title":"J Mol Biol"},{"key":"2819_CR7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS. Identification of common molecular subsequences. J Mol Biol. 1981; 147:195\u20137.","journal-title":"J Mol Biol"},{"issue":"2","key":"2819_CR8","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/321879.321880","volume":"22","author":"R Lowrance","year":"1975","unstructured":"Lowrance R, Wagner RA. An extension of the string-to-string correction problem. J ACM. 1975; 22(2):177\u201383.","journal-title":"J ACM"},{"key":"2819_CR9","volume-title":"Proceedings of the 38th Annual Meeting on Association for Computational Linguistics","author":"E Brill","year":"2000","unstructured":"Brill E, Moore RC. An improved error model for noisy channel spelling correction. In: Proceedings of the 38th Annual Meeting on Association for Computational Linguistics. Stroudsburg: Association for Computational Linguistics: 2000. p. 286\u201393."},{"key":"2819_CR10","volume-title":"Proceedings of the Fifth Australasian Symposium on ACSW Frontiers - Volume 68. ACSW \u201907","author":"GV Bard","year":"2007","unstructured":"Bard GV. Spelling-error tolerant, order-independent pass-phrases via the Damerau-Levenshtein string-edit distance metric. In: Proceedings of the Fifth Australasian Symposium on ACSW Frontiers - Volume 68. ACSW \u201907. Darlinghurst: Australian Computer Society, Inc.: 2007. p. 117\u201324."},{"key":"2819_CR11","volume-title":"Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics. ACL-44","author":"M Li","year":"2006","unstructured":"Li M, Zhang Y, Zhu M, Zhou M. Exploring distributional similarity based models for query spelling correction. In: Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics. ACL-44. Stroudsburg: Association for Computational Linguistics: 2006. p. 1025\u201332."},{"issue":"1","key":"2819_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10618-006-0057-3","volume":"15","author":"C Faloutsos","year":"2007","unstructured":"Faloutsos C, Megalooikonomou V. On data mining, compression, and kolmogorov complexity. Data Min Knowl Disc. 2007; 15(1):3\u201320.","journal-title":"Data Min Knowl Disc"},{"key":"2819_CR13","volume-title":"Proceedings of the 2012 ACM Conference on Computer and Communications Security","author":"X Cai","year":"2012","unstructured":"Cai X, Zhang XC, Joshi B, Johnson R. Touching from a distance: Website fingerprinting attacks and defenses. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York: ACM: 2012. p. 605\u201316."},{"key":"2819_CR14","volume-title":"Nucleic Acids Research, vol. 2","author":"KA Majorek","year":"2014","unstructured":"Majorek KA, Dunin-Horkawicz S, Steczkiewicz K, Muszewska A, Nowotny M, Ginalski K, Bujnicki JM. The RNase H-like superfamily: new members, comparative structural analysis and evolutionary classification. In: Nucleic Acids Research, vol. 2. Oxford: Oxford University Press: 2014. p. 4160\u201379."},{"key":"2819_CR15","unstructured":"Protein Data Bank. \n                    http:\/\/www.rcsb.org\/pdb\/home\/home.do\n                    \n                  . Accessed 15 Aug 2017."},{"issue":"1","key":"2819_CR16","first-page":"29","volume":"10","author":"H Hyyr\u00f6","year":"2003","unstructured":"Hyyr\u00f6 H. A bit-vector algorithm for computing levenshtein and damerau edit distances. Nord J Comput. 2003; 10(1):29\u201339.","journal-title":"Nord J Comput"},{"key":"2819_CR17","volume-title":"1995 IEEE International Conference on Systems, Man and Cybernetics. Intelligent Systems for the 21st Century, vol. 2","author":"BJ Oommen","year":"1995","unstructured":"Oommen BJ, Loke R. Pattern recognition of strings containing traditional and generalized transposition errors. In: 1995 IEEE International Conference on Systems, Man and Cybernetics. Intelligent Systems for the 21st Century, vol. 2. Washington: IEEE: 1995. p. 1154\u20139."},{"key":"2819_CR18","unstructured":"Damerau\u2013Levenshtein Distance. \n                    https:\/\/en.wikipedia.org\/wiki\/Damerau-Levenshtein_distance\n                    \n                  . Accessed 15 Aug 2017."},{"key":"2819_CR19","volume-title":"5th IEEE International Conference on Computational Advances in Bio and Medical Sciences","author":"C Zhao","year":"2015","unstructured":"Zhao C, Sahni S. Cache and energy efficient alignment of very long sequences. In: 5th IEEE International Conference on Computational Advances in Bio and Medical Sciences. Washington: IEEE: 2015. p. 1\u20136."},{"issue":"1","key":"2819_CR20","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner RA, Fischer MJ. The string-to-string correction problem. J ACM. 1974; 21(1):168\u201373.","journal-title":"J ACM"},{"issue":"6","key":"2819_CR21","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS. A linear space algorithm for computing longest common subsequences. Commun ACM. 1975; 18(6):341\u20133.","journal-title":"Commun ACM"},{"issue":"1","key":"2819_CR22","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1093\/bioinformatics\/4.1.11","volume":"4","author":"EW Myers","year":"1988","unstructured":"Myers EW, Miller W. Optimal alignments in linear space. Bioinformatics. 1988; 4(1):11\u20137.","journal-title":"Bioinformatics"},{"key":"2819_CR23","unstructured":"Source Code Download Link. \n                    http:\/\/www.cise.ufl.edu\/%7esahni\/papers\/DLDistanceAlgs.tar.gz\n                    \n                  . Accessed 15 Aug 2017."},{"key":"2819_CR24","unstructured":"Perf Tool. \n                    https:\/\/perf.wiki.kernel.org\/index.php\/Main_Page\n                    \n                  . Accessed 15 Aug 2017."},{"key":"2819_CR25","unstructured":"NCBI Database. \n                    http:\/\/www.ncbi.nlm.nih.gov\/gquery\n                    \n                  . Accessed 15 Aug 2017."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-2819-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-019-2819-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-2819-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T19:05:44Z","timestamp":1591297544000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-019-2819-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":25,"journal-issue":{"issue":"S11","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["2819"],"URL":"https:\/\/doi.org\/10.1186\/s12859-019-2819-0","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6]]},"assertion":[{"value":"6 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Publisher\u2019s Note"}}],"article-number":"277"}}