Edit distance with block deletions

DOI10.3390/A4010040zbMATH Open1461.68087OpenAlexW1988010239MaRDI QIDQ1736478FDOQ1736478

Authors: Dana Shapira, James A. Storer 

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

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

Recommendations

• scientific article; zbMATH DE number 7378703
• 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

zbMATH Keywords

dynamic programmingapproximation algorithmsNP-completenessedit distancetext processingblock operations

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression.
• Large edit distance with multiple block operations.
• Title not available (Why is that?)
• Title not available (Why is that?)

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)