Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time

DOI10.1007/978-3-319-08016-1_13MaRDI QIDQ3188843zbMATH OpenOpenAlexFDO

Authors Hwee Kim, Yo-Sub Han

Publication date 2 September 2014

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-08016-1_13

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32) Analysis of algorithms (68W40) Protein sequences, DNA sequences (92D20)

Recommendations

• String matching with inversions and translocations in linear average time (most of the time)
• Constant-space string-matching in sublinear average time
• Efficient string-matching allowing for non-overlapping inversions
• Fast and practical approximate string matching
• Efficient algorithms for approximate string matching with swaps
• Speeding up transposition-invariant string matching
• Average-optimal single and multiple approximate string matching
• scientific article; zbMATH DE number 975393
• scientific article; zbMATH DE number 3845091

Cited in

(7)

• Reversal distance for strings with duplicates: linear time approximation using hitting set
• String matching with inversions and translocations in linear average time (most of the time)
• Efficient matching of biological sequences allowing for non-overlapping inversions
• Efficient string-matching allowing for non-overlapping inversions
• String matching with involutions
• Text searching allowing for inversions and translocations of factors
• On the Simon's congruence neighborhood of languages

This page was built for publication: Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188843)