{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:15:38Z","timestamp":1762917338926,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2011,3,7]],"date-time":"2011-03-07T00:00:00Z","timestamp":1299456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Several variants of the edit distance problem with block deletions are considered. Polynomial time optimal algorithms are presented for the edit distance with block deletions allowing character insertions and character moves, but without block moves. We show that the edit distance with block moves and block deletions is NP-complete (Nondeterministic Polynomial time problems in which any given solution to such problem can be verified in polynomial time, and any NP problem can be converted into it in polynomial time), and that it can be reduced to the problem of non-recursive block moves and block deletions within a constant factor.<\/jats:p>","DOI":"10.3390\/a4010040","type":"journal-article","created":{"date-parts":[[2011,3,8]],"date-time":"2011-03-08T09:11:15Z","timestamp":1299575475000},"page":"40-60","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Edit Distance with Block Deletions"],"prefix":"10.3390","volume":"4","author":[{"given":"Dana","family":"Shapira","sequence":"first","affiliation":[{"name":"Ashkelon Academic College, 12 Ben-Tzvi Street, Ashkelon 78211, Israel"}]},{"given":"James A.","family":"Storer","sequence":"additional","affiliation":[{"name":"Brandeis University, 415 South Street, Waltham, MA 02453, USA"}]}],"member":"1968","published-online":{"date-parts":[[2011,3,7]]},"reference":[{"key":"ref_1","unstructured":"Gusfield, D. (2007). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Press Syndicate of the University of Cambridge."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","article-title":"A Faster Algorithm for Computing String Edit Distances","volume":"20","author":"Masek","year":"1980","journal-title":"J. Comput. Syst. Sci. Int."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1137\/S0097539702402007","article-title":"A sub-quadratic sequence alignment algorithm for unrestricted cost matrices","volume":"32","author":"Crochemore","year":"2003","journal-title":"SIAM J.Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/j.jda.2005.01.010","article-title":"Edit Distance with Move Operations","volume":"5","author":"Shapira","year":"2007","journal-title":"J. Discrete Algorithms"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","article-title":"Algorithms for approximate string matching","volume":"64","author":"Ukkonen","year":"1985","journal-title":"Inf. Control"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/j.ic.2009.12.001","article-title":"Efficient algorithms for the block-edit problems","volume":"208","author":"Ann","year":"2010","journal-title":"Inf. Comput."},{"key":"ref_7","unstructured":"Muthukrishnan, S., and Sahinalp, S.C. Approximate Nearest Neighbors and Sequence Comparison with Block Operations."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/3-540-45452-7_22","article-title":"Simple and Practical Sequence Nearest Neighbors with Block Operations","volume":"2373","author":"Muthukrishnan","year":"2002","journal-title":"Springer Lect. Notes Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Cormode, G., and Muthukrishnan, S. (2007). The String Edit Distance Matching Problem with Moves. ACM Trans. Algorithms, 3.","DOI":"10.1145\/1219944.1219947"},{"key":"ref_10","unstructured":"Cormode, G., Paterson, M., Sahinalp, S.C., and Vishkin, U. Communication Complexity of Document Exchange. Symp."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-540-24597-1_16","article-title":"Comparing Sequences with Segment Rearrangements","volume":"2914","author":"Ergun","year":"2003","journal-title":"Lect. Notes in Comput. Sci."},{"key":"ref_12","first-page":"84","article-title":"The Greedy Algorithm for the Minimum Common String Partition Problem","volume":"1","author":"Chrobak","year":"2004","journal-title":"ACM Trans. Algorithms"},{"key":"ref_13","first-page":"23","article-title":"The Greedy Algorithm for Edit Distance with Moves","volume":"1","author":"Shafrir","year":"2006","journal-title":"Inf. Process. Lett."},{"key":"ref_14","first-page":"124","article-title":"Sorting by Transpositions","volume":"11","author":"Bafna","year":"199","journal-title":"SIAM J. Discrete Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0304-3975(96)00268-X","article-title":"Block Edit Models for Approximate String Matching","volume":"181","author":"Lopresti","year":"1997","journal-title":"Theor. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/357401.357404","article-title":"The String to String Correction Problem with Block Moves","volume":"2","author":"Tichy","year":"1984","journal-title":"ACM Trans. Comput. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0166-218X(96)00061-3","article-title":"Polynomial-Time Algorithm for Computing Translocation Distance between Genomes","volume":"71","author":"Hannenhalli","year":"1996","journal-title":"Discrete Appl. Math."},{"key":"ref_18","unstructured":"Durand, D., Farach, M., Ravi, R., and Singh, M. (1997). A Short Course in Computational Molecular Biology, Center for Discrete Mathematics & Theoretical Computer Science. DIMACS Technical Report 97-63."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of Common Molecular Sequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"ref_20","unstructured":"Hermelin, D., Landau, G.M., Landau, S., and Weimann, O. (2009). A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression. Symp. Theor. Aspects Comput. Sci. 2009, 529\u2013540."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/4\/1\/40\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:55:28Z","timestamp":1760219728000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/4\/1\/40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,7]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2011,3]]}},"alternative-id":["a4010040"],"URL":"https:\/\/doi.org\/10.3390\/a4010040","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2011,3,7]]}}}