Optimal spaced seeds for faster approximate string matching

DOI10.1016/j.jcss.2007.03.007zbMath1123.68119OpenAlexW2037307735MaRDI QIDQ2643727

Yanyan Li

Publication date: 27 August 2007

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.03.007

zbMATH Keywords

Hamming distancepattern matchingseeds design

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (5)

Design and analysis of periodic multiple seeds ⋮ Better spaced seeds using quadratic residues ⋮ Hardness of optimal spaced seed design ⋮ Combinatorics on partial word correlations ⋮ Seed optimization for i.i.d. similarities is no easier than optimal Golomb ruler design

Uses Software

• PatternHunter

Cites Work

• Unnamed Item
• Vector seeds: An extension to spaced seeds
• On spaced seeds for similarity search
• Approximate String Matching: A Simpler Faster Algorithm
• Fast parallel and serial approximate string matching
• Faster algorithms for string matching with k mismatches
• Combinatorial Pattern Matching

This page was built for publication: Optimal spaced seeds for faster approximate string matching