Lossless filter for multiple repetitions with Hamming distance

DOI10.1016/J.JDA.2007.03.003MaRDI QIDQ1018103zbMATH OpenOpenAlexFDO

Authors Pierre Peterlongo, Nadia Pisanti, Alair Pereira do Lago, Marie-France Sagot, 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

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

Recommendations

• Multiple filtration and approximate pattern matching
• New and faster filters for multiple approximate string matching
• Combinatorial Pattern Matching
• \textsc{Rime}: repeat identification
• Optimal spaced seeds for faster approximate string matching

Cites work

• A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS
• scientific article; zbMATH DE number 1998337 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• Indexing text with approximate \(q\)-grams
• Linear-time construction of suffix arrays (extended abstract)
• Research in Computational Molecular Biology
• Space efficient linear time construction of suffix arrays
• Suffix Arrays: A New Method for On-Line String Searches

Cited in

(6)

• 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
• \textsc{Rime}: repeat identification
• Circular sequence comparison with q-grams
• Elastic-Degenerate String Matching via Fast Matrix Multiplication

Describes a project that uses

Uses Software

• NIMBUS
• PatternHunter

This page was built for publication: Lossless filter for multiple repetitions with Hamming distance

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