String matching with inversions and translocations in linear average time (most of the time)

DOI10.1016/j.ipl.2011.02.015zbMath1260.68489arXiv1012.0280OpenAlexW2061752733MaRDI QIDQ1944938

Simone Faro, Szymon Grabowski, Emanuele Giaquinta

Publication date: 28 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.0280

zbMATH Keywords

algorithmsbioinformaticsapproximate string matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational methods for problems pertaining to biology (92-08) Algorithms on strings (68W32)

Related Items (8)

Efficient string-matching allowing for non-overlapping inversions ⋮ A graph-theoretic model to solve the approximate string matching problem allowing for translocations ⋮ Text searching allowing for inversions and translocations of factors ⋮ Non-overlapping inversion on strings and languages ⋮ Efficient Matching of Biological Sequences Allowing for Non-overlapping Inversions ⋮ An efficient algorithm for computing non-overlapping inversion and transposition distance ⋮ Improved online algorithms for jumbled matching ⋮ Alignment with non-overlapping inversions and translocations on two strings

Cites Work

• Simple and efficient string matching with k mismatches
• Algorithms on Strings, Trees and Sequences
• New and faster filters for multiple approximate string matching

This page was built for publication: String matching with inversions and translocations in linear average time (most of the time)