Lossless filter for multiple repetitions with Hamming distance

DOI10.1016/j.jda.2007.03.003zbMath1165.94312MaRDI 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\)-factors; approximate repetitions; bi-factor array; bi-factors; multiple local alignment

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R15: Combinatorics on words

68T10: Pattern recognition, speech recognition

94A13: Detection theory in information and communication theory

92D10: Genetics and epigenetics

68P99: Theory of data

Related Items

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

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