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

DOI10.1016/j.ipl.2011.02.015zbMath1260.68489arXiv1012.0280MaRDI 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

algorithms; bioinformatics; approximate string matching

Mathematics Subject Classification ID

68W40: Analysis of algorithms

92-08: Computational methods for problems pertaining to biology

68W32: Algorithms on strings

Related Items

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, 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, Efficient Matching of Biological Sequences Allowing for Non-overlapping Inversions

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