Lossless filter for multiple repetitions with Hamming distance

DOI10.1016/j.jda.2007.03.003zbMath1165.94312OpenAlexW2112777598MaRDI QIDQ1018103

Pierre Peterlongo, Marie-France Sagot, Alair Pereira do Lago, Nadia Pisanti, Frederic Boyer

Publication date: 13 May 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.03.003

zbMATH Keywords

\(k\)-factorsapproximate repetitionsbi-factor arraybi-factorsmultiple local alignment

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics on words (68R15) Pattern recognition, speech recognition (68T10) Detection theory in information and communication theory (94A13) Genetics and epigenetics (92D10) Theory of data (68P99)

Related Items

Compressed spaced suffix arrays, Circular Sequence Comparison with q-grams, Motif trie: an efficient text index for pattern discovery with don't cares, \textsc{Rime}: repeat identification, Longest property-preserved common factor: a new string-processing framework, Elastic-Degenerate String Matching via Fast Matrix Multiplication

Uses Software

• NIMBUS
• PatternHunter

Cites Work

• Indexing text with approximate \(q\)-grams
• Suffix Arrays: A New Method for On-Line String Searches
• Linear-Time Construction of Suffix Arrays
• Space Efficient Linear Time Construction of Suffix Arrays
• Research in Computational Molecular Biology
• A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS
• Unnamed Item
• Unnamed Item
• Unnamed Item