{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:27:21Z","timestamp":1764937641107,"version":"3.44.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"12","license":[{"start":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T00:00:00Z","timestamp":1700179200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p>To what extent have the techniques for theoretical analysis of edit distance algorithms achieved their goals?<\/jats:p>","DOI":"10.1145\/3582490","type":"journal-article","created":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T10:06:08Z","timestamp":1700215568000},"page":"64-71","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Theoretical Analysis of Edit Distance Algorithms"],"prefix":"10.1145","volume":"66","author":[{"given":"Paul","family":"Medvedev","sequence":"first","affiliation":[{"name":"Pennsylvania State University, University Park, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,11,17]]},"reference":[{"volume-title":"Proceedings of the 2015 IEEE 56th Annual Symp. Foundations of Computer Science, 59--78","author":"Abboud A.","key":"e_1_2_1_1_1","unstructured":"Abboud, A., Backus, A., and Williams, V.V. Tight hardness results for LCS and other sequence similarity measures. In Proceedings of the 2015 IEEE 56th Annual Symp. Foundations of Computer Science, 59--78."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897653"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz234"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344434"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00215-6"},{"key":"e_1_2_1_6_1","volume-title":"On economical construction of the transitive closure of an oriented graph. Doklady Akademii Nauk 194","author":"Arlazarov V.","year":"1970","unstructured":"Arlazarov, V., Dinitz, Y., Kronrod, M., and Faradzhev, I. On economical construction of the transitive closure of an oriented graph. Doklady Akademii Nauk 194. Russian Academy of Sciences, (1970), 487--488."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053128"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.99"},{"key":"e_1_2_1_9_1","unstructured":"Brinda K. Boeva V. and Kucherov G. Ococo: An online consensus caller (2017); arXiv:1712.01146."},{"volume-title":"Proceedings of the 2015 IEEE 56th Annual Symp. Foundations of Computer Science, 79--97","author":"Bringmann K.","key":"e_1_2_1_10_1","unstructured":"Bringmann, K. and K\u00fcnnemann, M. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proceedings of the 2015 IEEE 56th Annual Symp. Foundations of Computer Science, 79--97."},{"volume-title":"Proceedings of the 2018 IEEE 59th Annual Symp. Foundations of Computer Science.","author":"Chakraborty D.","key":"e_1_2_1_11_1","unstructured":"Chakraborty, D., Das, D., Goldenberg, E., Koucky, M., and Saks, M. Approximating edit distance within constant factor in truly sub-quadratic time. In Proceedings of the 2018 IEEE 59th Annual Symp. Foundations of Computer Science."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.1064503"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-016-0930-z"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-9-11"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 20th Intern. Workshop on Algorithms in Bioinformatics 172, Leibniz International Proceedings in Informatics. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik","author":"Ganesh A.","year":"2020","unstructured":"Ganesh, A. and Sy, A. Near-linear time edit distance for indel channels. In Proceedings of the 20th Intern. Workshop on Algorithms in Bioinformatics 172, Leibniz International Proceedings in Informatics. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, (2020), 17:1--17:18."},{"volume-title":"Proceedings of the 2012 Intern. Symp. String Processing and Information Retrieval. Springer, 229--236","author":"Gawrychowski P.","key":"e_1_2_1_17_1","unstructured":"Gawrychowski, P. Faster algorithm for computing the edit distance between SLP-compressed strings. In Proceedings of the 2012 Intern. Symp. String Processing and Information Retrieval. Springer, 229--236."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conf. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik","author":"Goldwasser S.","year":"2017","unstructured":"Goldwasser, S. and Holden, D. The complexity of problems in p given correlated instances. In Proceedings of the 8th Innovations in Theoretical Computer Science Conf. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (2017)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Gusfield D. Algorithms on Strings Trees and Sequences. (1997).","DOI":"10.1017\/CBO9780511574931"},{"key":"e_1_2_1_20_1","unstructured":"Hermelin D. Landau G.M. Landau S. and weimann O.A. A unified algorithm for accelerating edit-distance computation via textcompression (2009); arXiv:0902.2649."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.3102\/0002831219866687"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.04.028"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.71"},{"key":"e_1_2_1_24_1","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"Levenshtein V.I","unstructured":"Levenshtein, V.I. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10, 707--710.","journal-title":"Soviet Physics Doklady"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1999.6.125"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-1005-2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaa777"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature23264"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_2_1_30_1","unstructured":"Medvedev P. The limitations of the theoretical analysis of applied algorithms. (2022); arXiv:2205.01785."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840446"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/316542.316550"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_2_1_36_1","volume-title":"Multi-Threaded implementation of four russians edit distance algorithm. Bachelor's thesis","author":"Rejmon M.","year":"2019","unstructured":"Rejmon, M. Multi-Threaded implementation of four russians edit distance algorithm. Bachelor's thesis. Czech Technical University in Prague, Faculty of Information Technology, (2019)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3232535"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2019.0299"},{"volume-title":"Proceedings of the 2018 ACM Intern. Conf. Bioinformatics, Computational Biology, and Health Informatics, 27--36","author":"Sarkar H.","key":"e_1_2_1_39_1","unstructured":"Sarkar, H., Zakeri, M., Malik, L., and Patro, R. Towards selective-alignment: Bridging the accuracy gap between alignment-based and alignment-free transcript quantification. In Proceedings of the 2018 ACM Intern. Conf. Bioinformatics, Computational Biology, and Health Informatics, 27--36."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btw753"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.214270.116"},{"key":"e_1_2_1_43_1","first-page":"1","volume":"21","author":"Wagner R.A.","year":"1974","unstructured":"Wagner, R.A. and Fischer, M.J. The String-to-String Correction Problem. JACM 21, 1 (1974), 168--173.","journal-title":"The String-to-String Correction Problem. JACM"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty930"},{"key":"e_1_2_1_45_1","unstructured":"Zook J.M. et al. A robust benchmark for germline structural variant detection. BioRxiv. (2019) 664623."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582490","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3582490","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T18:29:06Z","timestamp":1755973746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582490"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,17]]},"references-count":45,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.1145\/3582490"],"URL":"https:\/\/doi.org\/10.1145\/3582490","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2023,11,17]]},"assertion":[{"value":"2023-11-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}