Speeding up the detection of tandem repeats over the edit distance

DOI10.1016/J.TCS.2013.04.021MaRDI QIDQ2437752zbMATH OpenOpenAlexFDO

Authors 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

edit distanceLempel-Ziv factorizationtandem repeats

Mathematics Subject Classification ID

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

Recommendations

• Linear time algorithms for finding and representing all the tandem repeats in a string
• scientific article; zbMATH DE number 1875416
• Finding the Position of the k-Mismatch and Approximate Tandem Repeats
• scientific article; zbMATH DE number 1929946
• scientific article; zbMATH DE number 7651094

Cites work

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

Cited in

(8)

• Small-space algorithms for the online language distance problem for palindromes and squares
• scientific article; zbMATH DE number 7651094 (Why is no real title available?)
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Period recovery of strings over the Hamming and edit distances
• Speeding up the detection of evolutive tandem repeats
• Finding the Position of the k-Mismatch and Approximate Tandem Repeats
• Double string tandem repeats
• scientific article; zbMATH DE number 1929946 (Why is no real title available?)

This page was built for publication: Speeding up the detection of tandem repeats over the edit distance

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