Edit distance with move operations
From MaRDI portal
Publication:2457310
DOI10.1016/j.jda.2005.01.010zbMath1127.68118MaRDI QIDQ2457310
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
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