Speeding up the detection of tandem repeats over the edit distance

DOI10.1016/j.tcs.2013.04.021zbMath1282.68201OpenAlexW2054084157MaRDI QIDQ2437752

Dina Sokol, Justin Tojeira

Publication date: 13 March 2014

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

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

zbMATH Keywords

tandem repeatsedit distanceLempel-Ziv factorization

Mathematics Subject Classification ID

Combinatorics on words (68R15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Related Items

Period recovery of strings over the Hamming and edit distances

Cites Work

• Lempel-Ziv factorization using less time \& space
• Computing longest previous factor in linear time and applications
• Faster entropy-bounded compressed suffix trees
• Finding approximate repetitions under Hamming distance.
• Detecting leftmost maximal periodicities
• Speeding up the detection of evolutive tandem repeats
• A comparison of index-based lempel-Ziv LZ77 factorization algorithms
• An O(n log n) algorithm for finding all repetitions in a string
• Fast and Practical Algorithms for Computing All the Runs in a String
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Fast parallel and serial approximate string matching
• Algorithms on Strings, Trees and Sequences
• Incremental String Comparison
• New text indexing functionalities of the compressed suffix arrays
• Unnamed Item