Edit distance with block deletions

DOI10.3390/A4010040MaRDI QIDQ1736478zbMATH OpenOpenAlexFDO

Authors Dana Shapira, James A. Storer

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a4010040

zbMATH Keywords

approximation algorithmsblock operationsdynamic programmingedit distanceNP-completenesstext processing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computing methodologies for text processing; mathematical typography (68U15) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Edit distance with block operations
• scientific article; zbMATH DE number 2087046
• Edit distance with move operations
• Large edit distance with multiple block operations.
• Edit distance and its computation
• Block elimination distance
• Block elimination distance
• Edit distance with duplications and contractions revisited

Cites work

• A faster algorithm computing string edit distances
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• A unified algorithm for accelerating edit-distance computation via text-compression
• Algorithms for approximate string matching
• Algorithms on Strings, Trees and Sequences
• Approximate nearest neighbors and sequence comparison with block operations
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Block edit models for approximate string matching
• Edit distance with move operations
• Efficient algorithms for the block edit problems
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 2087059 (Why is no real title available?)
• scientific article; zbMATH DE number 1445304 (Why is no real title available?)
• Polynomial-time algorithm for computing translocation distance between genomes
• Sorting by Transpositions
• The greedy algorithm for edit distance with moves
• The string edit distance matching problem with moves

Cited in

(7)

• Block edit models for approximate string matching
• scientific article; zbMATH DE number 2087046 (Why is no real title available?)
• NP-completeness of special string editing problems
• Edit distance with block operations
• A multi-labeled tree edit distance for comparing ``Clonal trees of tumor progression
• Large edit distance with multiple block operations.
• Subsequence matching and LCS with segment number constraints

This page was built for publication: Edit distance with block deletions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736478)