Optimal spaced seeds for faster approximate string matching

DOI10.1016/J.JCSS.2007.03.007MaRDI QIDQ2643727zbMATH OpenOpenAlexFDO

Authors 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) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Recommendations

• Automata, Languages and Programming
• Fast and practical approximate string matching
• Faster approximate string matching
• A randomized algorithm for approximate string matching
• scientific article; zbMATH DE number 3845091
• scientific article; zbMATH DE number 975393
• Average-optimal single and multiple approximate string matching
• Average-optimal multiple approximate string matching
• scientific article; zbMATH DE number 2087055

Cites work

• Approximate String Matching: A Simpler Faster Algorithm
• Combinatorial Pattern Matching
• Fast parallel and serial approximate string matching
• Faster algorithms for string matching with k mismatches
• scientific article; zbMATH DE number 1998337 (Why is no real title available?)
• On spaced seeds for similarity search
• Vector seeds: An extension to spaced seeds

Cited in

(13)

• Lossless filter for multiple repetitions with Hamming distance
• On spaced seeds for similarity search
• Design and analysis of periodic multiple seeds
• Better spaced seeds using quadratic residues
• Fast spaced seed hashing
• Efficient Algorithms for Shortest Partial Seeds in Words
• Faster filters for approximate string matching
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Automata, Languages and Programming
• 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

Describes a project that uses

Uses Software

• PatternHunter

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

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