Efficient string-matching allowing for non-overlapping inversions

DOI10.1016/J.TCS.2012.06.009MaRDI QIDQ390885zbMATHOpenAlexFDO

Authors Domenico Cantone, Salvatore Cristofaro, Simone Faro

Publication date 9 January 2014

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

Full work available at URL https://doi.org/10.1016/j.tcs.2012.06.009

zbMATH Keywords

information retrievalapproximate string matchingaverage complexity analysistext processing

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10) Algorithms on strings (68W32)

Recommendations

• Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time
• Speeding up transposition-invariant string matching
• Efficient parameterized string matching
• Practical algorithms for transposition-invariant string-matching
• Efficient comparison based string matching
• Efficient string matching with k mismatches
• String matching with involutions
• scientific article; zbMATH DE number 1962813
• String matching with inversions and translocations in linear average time (most of the time)

Cites work

• A local algorithm for DNA sequence alignment with inversions
• A space-efficient algorithm for sequence alignment with inversions and reversals
• Introduction to algorithms
• New and faster filters for multiple approximate string matching
• Simple and efficient string matching with k mismatches
• String matching with inversions and translocations in linear average time (most of the time)

Cited in

(19)

• Block reversal on finite words
• Sequence searching allowing for non-overlapping adjacent unbalanced translocations
• Text searching allowing for inversions and translocations of factors
• Pseudo-inversion: closure properties and decidability
• On pattern matching with \(k\) mismatches and few don't cares
• Duplications and pseudo-duplications
• Two-way string-matching
• Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time
• An efficient algorithm for computing non-overlapping inversion and transposition distance
• String matching with inversions and translocations in linear average time (most of the time)
• String matching with involutions
• Alignment with non-overlapping inversions on two strings
• State complexity of inversion operations
• Efficient matching of biological sequences allowing for non-overlapping inversions
• Rich words in the block reversal of a word
• Alignment with non-overlapping inversions and translocations on two strings
• Non-overlapping inversion on strings and languages
• An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applications
• Pattern matching with non overlapping reversals -- approximation and on-line algorithms

This page was built for publication: Efficient string-matching allowing for non-overlapping inversions

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