Pattern matching with address errors: rearrangement distances

DOI10.1016/j.jcss.2009.03.001zbMath1175.68567OpenAlexW2006249627MaRDI QIDQ923879

Ely Porat, Gary Benson, Yonatan Aumann, Uzi Vishne, Ohad Lipsky, Amihood Amir, Avivit Levy, Steven S. Skiena

Publication date: 24 July 2009

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2009.03.001

zbMATH Keywords

swapsapproximate pattern matchingaddress metricsrearrangement errors

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

Exploiting pseudo-locality of interchange distance, On the hardness of the consensus string problem, An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applications, Sorting by Transpositions Is Difficult, Pattern matching in pseudo real-time, Approximate string matching with stuck address bits, Average parameterization and partial kernelization for computing medians

Uses Software

• Mathematica

Cites Work

• Sorting permutations by block-interchanges
• Efficient string matching with k mismatches
• Mixing and covering in the symmetric groups
• Fast algorithms for approximately counting mismatches
• Overlap matching.
• String matching under a general matching relation
• Products of conjugacy classes in groups
• Approximate String Matching with Address Bit Errors
• Dictionary matching and indexing with errors and don't cares
• Generalized String Matching
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• An Extension of the String-to-String Correction Problem
• Sorting by Transpositions
• Faster algorithms for string matching with k mismatches
• A theory of parameterized pattern matching
• On the Cost of Interchange Rearrangement in Strings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item