Block edit models for approximate string matching

DOI10.1016/S0304-3975(96)00268-XzbMath0901.68039MaRDI QIDQ1391305

Andrew Tomkins, Daniel Lopresti

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

string block edit distance

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items

An efficient algorithm for sequence comparison with block reversals ⋮ Fast computation of a string duplication history under no-breakpoint-reuse ⋮ Unnamed Item ⋮ Edit distance with move operations ⋮ Edit distance with block deletions ⋮ An extension of the Burrows-Wheeler transform ⋮ Quick Greedy Computation for Minimum Common String Partitions ⋮ An artificial neural network based approach for online string matching/filtering of large databases ⋮ An algorithm with linear expected running time for string editing with substitutions and substring reversals ⋮ Efficient algorithms for the block edit problems ⋮ Quick greedy computation for minimum common string partition ⋮ Distance measures for biological sequences: some recent approaches ⋮ Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time ⋮ An integer linear programming approach for approximate string comparison ⋮ The greedy algorithm for edit distance with moves

Cites Work

• Data structures and algorithms for approximate string matching
• A time-efficient, linar-space local similarity algorithm
• Sublinear approximate string matching and biological applications
• An Improved Algorithm For Approximate String Matching
• Algorithms for approximate string matching
• Fast parallel and serial approximate string matching
• The String-to-String Correction Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item