Edit distance with move operations

DOI10.1016/j.jda.2005.01.010zbMath1127.68118OpenAlexW2022715218MaRDI QIDQ2457310

James A. Storer, Dana Shapira

Publication date: 30 October 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2005.01.010

zbMATH Keywords

NP-completebin packing problemlongest common substringEdit-distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics on words (68R15) Biochemistry, molecular biology (92C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (9)

A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ Fast computation of a string duplication history under no-breakpoint-reuse ⋮ Unnamed Item ⋮ Edit distance with block deletions ⋮ siEDM: an efficient string index and search algorithm for edit distance with moves ⋮ Property testing of regular tree languages ⋮ Quick Greedy Computation for Minimum Common String Partitions ⋮ Efficient algorithms for the block edit problems ⋮ Quick greedy computation for minimum common string partition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A faster algorithm computing string edit distances
• Block edit models for approximate string matching
• Approximate nearest neighbors and sequence comparison with block operations
• Algorithms on Strings, Trees and Sequences
• Sorting by Transpositions
• Genome Rearrangements and Sorting by Reversals
• 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 move operations