Edit distance with move operations

DOI10.1016/j.jda.2005.01.010zbMath1127.68118MaRDI 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-complete; bin packing problem; longest common substring; Edit-distance

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R15: Combinatorics on words

92C40: Biochemistry, molecular biology

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Related Items

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

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