{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T20:07:26Z","timestamp":1778789246804,"version":"3.51.4"},"reference-count":105,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"6","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01GM108348"],"award-info":[{"award-number":["R01GM108348"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1109\/tit.2020.2996543","type":"journal-article","created":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T18:04:59Z","timestamp":1590084299000},"page":"3287-3294","source":"Crossref","is-referenced-by-count":127,"title":["Levenshtein Distance, Sequence Comparison and Biological Database Search"],"prefix":"10.1109","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2724-7228","authenticated-orcid":false,"given":"Bonnie","family":"Berger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael S.","family":"Waterman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8275-9576","authenticated-orcid":false,"given":"Yun William","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1137\/0149012"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/27.11.2369"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkh435"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177010382"},{"key":"ref31","first-page":"115","article-title":"Les valeurs extrêmes des distributions statistiques","volume":"5","author":"gumbel","year":"1935","journal-title":"Ann Inst Henri Poincare&#x00B4"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1126\/science.2983426"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1038\/514550a"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1093\/brain\/awh278"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkl164"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2001-2-10-reviews2002"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1089\/106652799318364"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.80.3.726"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.cels.2015.08.004"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1201\/9780203750131"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(87)90478-5"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.89.22.10915"},{"key":"ref101","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2271-7"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1038\/nrg3433"},{"key":"ref100","article-title":"Clustered hierarchical entropy-scaling search of astronomical and biological data","author":"ishaq","year":"2019","journal-title":"arXiv 1908 08551"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1016\/S0092-8240(84)80056-7"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1995.2.291"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1089\/gst.1995.1.9"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892127"},{"key":"ref58","article-title":"A block sorting lossless data compression algorithm","author":"burrows","year":"1994"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.2023"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1101\/gr.089532.108"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1101\/gr.074492.107"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0238"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2012.0021"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1101\/gr.9.12.1163"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/0378-1119(88)90330-7"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(60)90272-2"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb00463.x"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/362919.362934"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/363958.363994"},{"key":"ref8","first-page":"81","article-title":"Speech recognition by dynamic programming","volume":"4","author":"vintsyuk","year":"1968","journal-title":"Cybernetics"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/23.24.4992"},{"key":"ref7","article-title":"Time warps, string edits, and macromolecules","author":"sankoff","year":"1983","journal-title":"The Theory and Practice of Sequence Comparison"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"ref46","article-title":"The complexity of the shortest common matching string problem","author":"turner","year":"1986"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1038\/nrg3367"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/10.15.4731"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0016287"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(75)90213-2"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1101\/gr.229202. Article published online before March 2002"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1126\/science.280.5369.1540"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1101\/gr.7.5.401"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-9-128"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1038\/nbt0509-455"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1016\/j.ygeno.2008.07.001"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1002\/asi.5090040104"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1101\/gr.194201"},{"key":"ref74","first-page":"910","article-title":"Oasis: An online and accurate technique for local-alignment searches on biological sequences","volume":"29","author":"meek","year":"2003","journal-title":"Proc 29th Int Conf Very Large Data Bases"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn032"},{"key":"ref78","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp698"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.1923"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1126\/science.7542800"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1126\/science.287.5461.2196"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1126\/science.274.5287.546"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1126\/science.1058040"},{"key":"ref64","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1038\/35057062","article-title":"Initial sequencing and analysis of the human genome","volume":"409","author":"es","year":"2001","journal-title":"Nature"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1517\/14622416.6.4.373"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1038\/msb4100040"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1016\/j.cell.2015.05.001"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1126\/science.1239119"},{"key":"ref2","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"levenshtein","year":"1966","journal-title":"Sov Phys -Dokl"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1038\/nrg3493"},{"key":"ref1","first-page":"845","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"163","author":"levenshtein","year":"1965","journal-title":"Doklady Akademii Nauk"},{"key":"ref95","first-page":"2013","article-title":"Metric entropy of dynamical system","volume":"20","author":"sinai","year":"2007","journal-title":"Retrieved March"},{"key":"ref94","first-page":"385","article-title":"Certain asymptotic characteristics of completely bounded metric spaces","volume":"108","author":"kolmogorov","year":"1956","journal-title":"Doklady Akademii Nauk"},{"key":"ref93","doi-asserted-by":"publisher","DOI":"10.1016\/0375-9601(88)90193-4"},{"key":"ref92","volume":"173","author":"mandelbrot","year":"1983","journal-title":"The Fractal Geometry of Nature"},{"key":"ref105","doi-asserted-by":"publisher","DOI":"10.1145\/2957324"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.2241"},{"key":"ref104","first-page":"535","article-title":"Metric trees for efficient similarity search in large process model repositories","author":"kunze","year":"2010","journal-title":"Proc Int Conf Bus Process Manage"},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1016\/j.cels.2018.07.005"},{"key":"ref103","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-29151-2"},{"key":"ref102","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt214"},{"key":"ref99","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.3511"},{"key":"ref96","author":"tao","year":"2014","journal-title":"Metric Entropy Analogues of Sum Set Theory"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-7373(70)80008-6"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1978.1163055"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.69.1.4"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(73)90088-X"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1974.1162614"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbq015"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/0126070"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1002\/0471250953.bi1107s32"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(81)90046-4"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1016\/j.gpb.2015.08.002"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1990.9999"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.1376"},{"key":"ref80","article-title":"Faster and more accurate sequence alignment with SNAP","author":"zaharia","year":"2011","journal-title":"arXiv 1111 5572"},{"key":"ref89","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.4366"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-016-1103-0"},{"key":"ref86","doi-asserted-by":"publisher","DOI":"10.1038\/nbt0515-433"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-017-1953-9"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-238"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/9437276\/09097943.pdf?arnumber=9097943","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T11:34:56Z","timestamp":1641987296000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9097943\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6]]},"references-count":105,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.1109\/tit.2020.2996543","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6]]}}}