Hardness of optimal spaced seed design

DOI10.1016/j.jcss.2007.10.001zbMath1160.68030OpenAlexW1987857466MaRDI QIDQ931726

Eric Rivals, François Nicolas

Publication date: 26 June 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.10.001

zbMATH Keywords

filtrationalignmenttilingstring matchingmaximum independent setsequence comparisonspaced seedapproximabilityGolomb rulermaximum coveragegapped seed

Mathematics Subject Classification ID

Combinatorics on words (68R15) Pattern recognition, speech recognition (68T10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

Design and analysis of periodic multiple seeds ⋮ Better spaced seeds using quadratic residues ⋮ On the complexity of finding gapped motifs ⋮ Combinatorics on partial word correlations

Uses Software

• PatternHunter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate string-matching with \(q\)-grams and maximal matches
• Sublinear approximate string matching and biological applications
• Tiling figures of the plane with two bars
• Sensitivity analysis and efficient method for identifying optimal spaced seeds
• On the complexity of the spaced seeds
• Optimal spaced seeds for faster approximate string matching
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A threshold of ln n for approximating set cover
• Superiority and complexity of the spaced seeds
• Efficient randomized pattern-matching algorithms
• Paths, Trees, and Flowers
• Combinatorial Pattern Matching

This page was built for publication: Hardness of optimal spaced seed design