Finding approximate repetitions under Hamming distance.

DOI10.1016/S0304-3975(02)00448-6zbMath1051.68119OpenAlexW1973272213WikidataQ58064526 ScholiaQ58064526MaRDI QIDQ1401359

Gregory Kucherov, Roman M. Kolpakov

Publication date: 17 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00448-6

zbMATH Keywords

approximate tandem repeat

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items

A matching algorithm in PMWL based on CluTree ⋮ Multidimensional period recovery ⋮ Locating maximal approximate runs in a string ⋮ Can we recover the cover? ⋮ Period recovery of strings over the Hamming and edit distances ⋮ Most pseudo-copy languages are not context-free ⋮ Speeding up the detection of tandem repeats over the edit distance ⋮ AVOIDING APPROXIMATE SQUARES ⋮ On the complexity of finding gapped motifs ⋮ Combinatorics on partial word correlations ⋮ Approximate cover of strings ⋮ Lazy Lempel-Ziv Factorization Algorithms ⋮ Quasi-Periodicity Under Mismatch Errors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal algorithm for computing the repetitions in a word
• A characterization of the squares in a Fibonacci string
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Detecting leftmost maximal periodicities
• Detection of periodicities and string-matching in real time
• Time-space-optimal string matching
• Squares, cubes, and time-space efficient string searching
• An O(n log n) algorithm for finding all repetitions in a string
• Amortized Computational Complexity
• Linear Algorithm for Data Compression via String Matching
• Algorithms on Strings, Trees and Sequences