Edit distance with block deletions

DOI10.3390/a4010040zbMath1461.68087OpenAlexW1988010239MaRDI QIDQ1736478

James A. Storer, Dana Shapira

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingNP-completenessapproximation algorithmsedit distancetext processingblock operations

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for the block edit problems
• The greedy algorithm for edit distance with moves
• A faster algorithm computing string edit distances
• Block edit models for approximate string matching
• Edit distance with move operations
• The string edit distance matching problem with moves
• Approximate nearest neighbors and sequence comparison with block operations
• Algorithms for approximate string matching
• Algorithms on Strings, Trees and Sequences
• Sorting by Transpositions
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Polynomial-time algorithm for computing translocation distance between genomes

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